A new approximative algorithm for the expansion problem of 3G networks

In this paper, we propose a tabu search heuristic in order to solve the expansion problem (also known as update problem) of universal mobile telecommunications system (UMTS) networks. The expansion problem is currently being faced by several service providers. In fact, all network planners usually have to decide how to update the current infrastructure in order to meet new demand. This kind of problem is a generalization of the regular planning problem. This means that both the planning and the expansion problems can be solved with the proposed heuristic. Since the expansion problem has been shown to be NP-hard, we concentrate our effort on the development of an approximative approach based on tabu search. The computational results show that our heuristic is providing good results with respect to the optimal solution