Deploying sensor nodes randomly most of the time generates initial communication hole even in highly dense networks. These communication holes cannot be totally eliminated even when the deployment is done in a structured manner. In either case, the resulting inter-node distances may degrade the performance of the network. This paper proposes an enhanced deployment algorithm based on Artificial Bees Colony (ABC). The ABC-based deployment is guaranteed to extend the lifetime by optimizing the network parameters and constraining the total number of deployed relays. Simulations validate the effectiveness of the proposed strategy under different cases of problem complexity. Results show that the proposed approach improves the network lifetime considerably when compared to solutions reported in the literature such as Shortest Path 3-D grid Deployment (SP3D) algorithm. Keywords: Artificial Bee Colony, Wiener index, optimization, relay nodes, Laplacian matrix, connected graph, vertex, edge, average distance, Laplacian matrix, Shortest Path 3-D grid Deployment, ABC, SP3D, RNs/CHs, ILDCC, SPRN, O3DwLC, algorithm, approach, single objective, multi objective, eigenvalue, First Phase Relay Nodes, NP-Hard, Deployment, proposed, second phase relay nodes, Ideal Media Access Control, cluster head, Minimum Spanning Tree, non-deterministic polynomial-time hard, two-layer hierarchical structure, Optimized 3-D deployment with Lifetime Constraints, flux, Wireless Sensor Network, size, Lifetime, Network load, number of nodes using packets, Connectivity, two layered, protocols, collision and interference.