Iterative improvement methods for a multiperiod network design problem

Iterative improvement methods for a multiperiod network design problem

0.00 Avg rating0 Votes
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: , ,
Keywords: heuristics
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.