Article ID: | iaor19993143 |
Country: | Netherlands |
Volume: | 110 |
Issue: | 1 |
Start Page Number: | 150 |
End Page Number: | 165 |
Publication Date: | Oct 1998 |
Journal: | European Journal of Operational Research |
Authors: | Mahey Philippe, Garcia Bruno-Laurent, LeBlanc Larry J. |
Keywords: | heuristics |
We address an important problem in telecommunications planning: the multiperiod network expansion problem. Our aim is to show that it can be efficiently solved using a new local search approach. To achieve our goal, we first show how to adapt the problem's formulation to meet our local search program's requirements. We then describe GLIT (Generic Local Improvement Template), a new, generic auto-calibrating local search algorithm; the different neighbouring strategies that we designed specifically for this problem; as well as a Genetic algorithm for this problem. We compare and discuss the performance of these algorithms using extensive computational tests on a large range of instances with up to 7500 arcs. These experiments show that GLIT clearly outperforms competitive approaches, especially when it is coupled with Genetic algorithms. We also show that the hybrid algorithms Genetic/Tabu, Genetic/Simulated Annealing, and finally Genetic/GLIT all outperform both pure Genetic and pure local search algorithms.