zbMATH — the first resource for mathematics

A Lagrangean heuristic for the maximal covering location problem. (English) Zbl 0913.90200
Summary: 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.

90B80 Discrete location and assignment
PDF BibTeX Cite
Full Text: DOI
[1] Christofides, N.; Eilon, S., Algorithms for large scale travelling salesman problems, Operational research quarterly, 23, 511-518, (1972) · Zbl 0248.90039
[2] Church, R.L.; ReVelle, C.S., The maximal covering location problem, Papers of the regional science association, 32, 101-118, (1974)
[3] Church, R.L.; Current, J.; Storbeck, J., A bicriterion maximal covering location formulation which considers the satisfaction of uncovered demand, Decision sciences, 22, 38-52, (1991)
[4] Eilon, S.; Galvão, R.D., Single and double vertex substitution in heuristic procedures for the p-Median problem, Management science, 24, 1763-1766, (1978) · Zbl 0491.90036
[5] Garfinkel, R.S.; Neebe, A.W.; Rao, M.R., An algorithm for the m-Median plant location problem, Transportation science, 8, 217-236, (1974)
[6] Kerningan, B.W.; Lin, S., An efficient heuristic procedure for partitioning graphs, Bell system technical journal, 49, 291-307, (1970) · Zbl 0333.05001
[7] Lin, S., Computer solutions of the travelling salesman problem, Bell system technical journal, 44, 2245-2269, (1965) · Zbl 0136.14705
[8] Pastor, J.T.; Alminana, M., Una panorámica de las conexiones y aplicaciones del problema de localización con cubrimiento maximal, Investigación operativa, 3, 25-39, (1993)
[9] Pirkul, H.; Schilling, D., The capacitated maximal covering location problem with backup service, Annals of operations research, 18, 141-154, (1989) · Zbl 0707.90066
[10] Swain, R., A decomposition algorithm for a class of facility location algorithms, ()
[11] Teitz, M.B.; Bart, P., Heuristic methods for estimating the generalized vertex Median of a weighted graph, Operations research, 16, 955-961, (1968) · Zbl 0165.22804
[12] Weaver, J.R.; Church, R.L., A comparison of direct and indirect primal heuristic/dual bounding solution procedures for the maximal covering location problem, (1984), Unpublished paper
[13] Whitaker, R.A., A fast algorithm for the greedy interchange for large-scale clustering and Median location problems, Infor, 21, 95-108, (1983) · Zbl 0527.90017
[14] White, J.; Case, K., On covering problems and the central facility location problem, Geographical analysis, 6, 281-293, (1974)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.