Article ID: | iaor19982094 |
Country: | Netherlands |
Volume: | 88 |
Issue: | 1 |
Start Page Number: | 114 |
End Page Number: | 123 |
Publication Date: | Jan 1996 |
Journal: | European Journal of Operational Research |
Authors: | ReVelle Charles, Galvo Roberto Diguez |
Keywords: | programming: integer |
We develop a Lagrangean heuristic for the maximal covering location problem. Upper bounds are given by a vertex addition and substitution heuristic and lower bounds are produced through a subgradient optimization algorithm. The procedure was tested in networks of up to 150 vertices. A duality gap was generally present at the end of the heuristic for the larger problems. The test problems were run in an IBM 3090-600J ‘super-computer’; the maximum computing time was kept below three minutes of CPU.