Heuristic search techniques for cell to switch assignment in location area planning for cellular networks

The issue of grouping cells into location areas (LAs), where each LA is serviced by a switch, plays an important role in the planning of cellular networks. It is a combinatorial optimization problem that is known to be NP-hard. This paper proposes a total cost of operation (TCO) minimizing state space search formulation of the problem and a heuristic for assigning cell to switches. The TCO includes both recurring hand-off cost and amortized fixed cost. The proposed heuristic is used with block depth first search (BDFS), and also with iterative deepening A (IDA) to solve the problem. Detailed experiments show that the BDFS has a better performance than IDA with respect to execution time while finding an optimal solution. BDFS also outperforms other existing techniques that are based on meta-heuristics, namely, simulated annealing (SA), genetic algorithm (GA), tabu search (TS), and H-I, in terms of solution quality when they are constrained to run for a user specified time.