×

zbMATH — the first resource for mathematics

A maximal covering location model in the presence of partial coverage. (English) Zbl 1107.90028
Summary: The maximal covering location problem (MCLP) addresses the issue of locating a predefined number of facilities in order to maximize the number of demand points that can be covered. In a classical sense, a demand point is assumed to be covered completely if located within the critical distance of the facility and not covered at all outside of the critical distance. Since the optimal solution to a MCLP is likely sensitive to the choice of the critical distance, determining a critical distance value when the coverage does not change in a crisp way from “fully covered” to “not covered” at a specific distance may lead to erroneous results. We allow the coverage to change from “covered” to “not-covered” within a distance range instead of a single critical distance and call this intermediate coverage level partial coverage. In this paper, we formulate the MCLP in the presence of partial coverage, develop a solution procedure based on Lagrangean relaxation and show the effect of the approach on the optimal solution by comparing it with the classical approach.

MSC:
90B80 Discrete location and assignment
90C27 Combinatorial optimization
PDF BibTeX Cite
Full Text: DOI
References:
[1] Brandeau, M.L.; Chui, S.S., An overview of representative problems in location research, Management science, 35, 6, 645-674, (1989) · Zbl 0669.90040
[2] Ghosh A, Rushton G, editors. Spatial analysis and location-allocation models. New York: Van Nostrand Reinhold Company, 1987.
[3] Daskin MS. Network and discrete location: models, algorithms, and applications. New York: Wiley, 1995. p. 6, 125.
[4] Church, R.; ReVelle, C., The maximal covering location problem, Papers of the regional science association, 32, 101-118, (1974)
[5] Megiddo, N.; Zemel, E.; Hakimi, S.L., The maximum coverage location problem, SIAM journal on algebraic discrete methods, 4, 2, 253-261, (1983) · Zbl 0514.90019
[6] Daskin, M.S.; Hogan, K.; ReVelle, C., Integration of multiple, excess, backup, and expected covering models, Environment and planning B: planning and design, 15, 15-35, (1988)
[7] Schilling, D.; Jayaraman, V.; Barkhi, R., A review of covering problems in facility location, Location science, 1, 25-55, (1993) · Zbl 0923.90108
[8] Boffey B, Narula SC. Multiobjective covering and routing problems. In: Karwan MH, Spronk J, Wallenius J. editors. Essays in decision making: a volume in honour of Stanley Zionts. Berlin: Springer, 1997.
[9] Sherali, H.D.; Kim, S.; Parrish, E.L., Probabilistic partial set covering problem, Naval research logistics, 38, 41-51, (1991) · Zbl 0725.90034
[10] Chung, C., Recent applications of the maximal covering location planning (M.C.L.P.) model, Journal of operational research society, 37, 8, 735-746, (1986) · Zbl 0601.90043
[11] Church, R.L.; Roberts, K.L., Generalized coverage models and public facility location, Papers of the regional science association, 53, 117-135, (1983)
[12] Pirkul, H.; Schilling, D.A., The maximal covering location problem with capacities on total workload, Management science, 37, 2, 233-248, (1991) · Zbl 0732.90045
[13] Nguyen, B.U.; Ng, K.Y.K., Modeling Canadian search and rescue operations, Military operations research, 5, 1, 5-16, (2000)
[14] Fisher, M.L., The Lagrangean relaxation method for solving integer programming problems, Management science, 27, 1, 1-18, (1981) · Zbl 0466.90054
[15] Agar, M.C.; Salhi, S., Lagrangean heuristics applied to a variety of large capacitated plant location problems, Journal of operational research society, 49, 1072-1084, (1998) · Zbl 1140.90419
[16] Sridharan, R.A., Lagrangean heuristic for the capacitated plant location problem with side constraints, Journal of operational research society, 42, 7, 579-585, (1991) · Zbl 0736.90050
[17] Cornuejols, G.; Fisher, M.L.; Nemhauser, G.L., Location of bank accounts to optimize floatan analytical study of exact and approximate algorithms, Management science, 23, 8, 789-810, (1977) · Zbl 0361.90034
[18] Galvao, R.D.; ReVelle, C., A Lagrangean heuristic for the maximal covering location problem, European journal of operational research, 88, 114-123, (1996) · Zbl 0913.90200
[19] Galvao, R.D.; Espejo, L.G.A.; Boffey, B., A comparison of Lagrangean and surrogate relaxations for the maximal covering location problem, European journal of operational research, 124, 377-389, (2000) · Zbl 0967.90068
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.