1 Cell Planning with Capacity Expansion in Mobile Communications: A Tabu Search Approach

Cell planning problem with capacity expansion is examined in wireless communications. The problem decides the location and capacity of each new base station to cover expanded and increased traffic demand. The objective is to minimize the cost of new base stations. The coverage by the new and existing base stations is constrained to satisfy a proper portion of traffic demands. The received signal power at the base station also has to meet the receiver sensitivity. The cell planning is formulated as an integer linear programming problem and solved by a Tabu Search algorithm. In the tabu search intensification by add and drop move is implemented by short-term memory embodied by two tabu lists. Diversification is designed to investigate proper capacities of new base stations and to restart the tabu search from new base station locations. Computational results show that the proposed tabu search is highly effective. 10% cost reduction is obtained by the diversification strategies. The gap from the optimal solutions is approximately 1∼5 % in problems that can be handled in appropriate time limits. The proposed tabu search also outperforms the parallel genetic algorithm. The cost reduction by the tabu search approaches 10~20 % in problems with 2,500 traffic demand areas in CDMA.