Comparison of different meta-heuristics to solve the global planning problem of UMTS networks

In this paper, we investigate and compare, through extensive simulation, the use of three meta-heuristic algorithms in order to find “good” feasible solutions for the global topology planning problem of universal mobile telecommunications system (UMTS) networks. The latter has been shown to be NP-hard as it is composed of three different subproblems (each one being NP-hard): the cell planning subproblem, the access network planning subproblem and the core network planning subproblem. As a result, we concentrate our effort on the development of approximate algorithms based on tabu search, genetic algorithm and simulated annealing. Numerical results show that these three algorithms perform relatively well. The tabu search algorithm returns the best solutions (on average, within 1.04% of the optimal solution) while the genetic algorithm seems to be slightly faster than the other two. Finally, simulated annealing finds the worst solutions (on average, within 4.91% of the optimal solution) and takes much more time than the other two algorithms.