×

A defensive maximal covering problem on a network. (English) Zbl 1153.90332

Summary: Consider a situation where p facilities need to be located by a leader, on the nodes of a network, to provide maximum coverage of demand generated at nodes of the network. At some point in the future it is expected that one of the links of the network will become unusable either due to a terrorist attack or a natural disaster (by the follower). The follower’s objective is which link to remove. The leader’s objective is to cover the most demand following such a damage to a link. The problem is formulated and analyzed from the leader’s perspective. An efficient approach to solving the follower’s problem is constructed. The leader’s problem is solved heuristically by an ascent algorithm, simulated annealing, and tabu search, using the efficient algorithm for the solution of the follower’s problem. Computational experiments on 40 test problems ranging between 100 and 900 nodes and 5–200 facilities provided good results.

MSC:

90B10 Deterministic network models in operations research
90C35 Programming involving graphs or networks
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Batta, The maximal expected covering location problem, Transportation Science 23 pp 277– (1989) · Zbl 0692.90040
[2] Beasley, OR-library - distributing test problems by electronic mail, Journal of the Operational Research Society 41 pp 1069– (1990)
[3] Berman, The generalized maximal covering location problem, Computers and Operations Research 29 pp 563– (2002) · Zbl 0995.90056
[4] Berman, Locating service facilities whose reliability is distance dependent, Computers and Operations Research 30 pp 1683– (2003) · Zbl 1039.90022
[5] Berman, The gradual covering decay location problem on a network, European Journal of Operational Research 151 pp 474– (2003) · Zbl 1053.90076
[6] Berman, The facility and transfer points location problem, International Transactions in Operational Research 12 pp 387– (2005) · Zbl 1114.90051
[7] Berman, The variable radius covering problem, European Journal of Operational Research (2008)
[8] Carrizosa, Polynomial algorithms for parametric min-quantile and maxcovering planar location problems with locational constraints, TOP 6 pp 179– (1998) · Zbl 0916.90188
[9] Church, Spatial Analysis and Location-Allocation Models pp 163– (1987)
[10] Church, The maximal covering location problem, Papers of the Regional Science Association 32 pp 101– (1974)
[11] Church, Protecting critical assets, Geographical Analysis 39 pp 129– (2007)
[12] Church, A bilevel mixed-integer program for critical infrastructure protection planning, Computers and Operations Research 35 pp 1905– (2008) · Zbl 1139.90439
[13] Current, Facility Location: Applications and Theory pp 81– (2002) · doi:10.1007/978-3-642-56082-8_3
[14] Daskin, A maximum expected covering location model, Transportation Science 17 pp 48– (1983)
[15] Daskin, Network and Discrete Location: Models, Algorithms, and Applications (1995) · Zbl 0870.90076 · doi:10.1002/9781118032343
[16] Daskin, A hierarchical objective set covering model for emergency medical service vehicle deployment, Transportation Science 15 pp 137– (1981)
[17] Drezner, Heuristic solution methods for two location problems with unreliable facilities, Journal of the Operational Research Society 38 pp 509– (1987) · Zbl 0617.90021
[18] Drezner, The gradual covering problem, Naval Research Logistics 51 pp 841– (2004) · Zbl 1075.90047
[19] Glover, Future paths for integer programming and links to artificial intelligence, Computers and Operations Research 13 pp 533– (1986) · Zbl 0615.90083
[20] Glover, Tabu Search (1997) · doi:10.1007/978-1-4615-6089-0
[21] Hakimi, Discrete Location Theory pp 439– (1990)
[22] Kirkpatrick, Optimization by simulated annealing, Science 220 pp 671– (1983) · Zbl 1225.90162
[23] Kolen, Discrete Location Theory pp 263– (1990)
[24] Lee, On solving unreliable planar location problems, Computers and Operations Research 28 pp 329– (2001) · Zbl 0976.90060
[25] Nash, J. , 1950. Non-Cooperative Games, Ph.D. Dissertation, Princeton University. · Zbl 0045.08202
[26] O’Hanley, J.R. , Church, R.L. , 2007. Desingning Robust Coverage Networks to Hedge Against Worst-Case Facility Losses. Working paper, Kent Business School, University of Kent, Canterbury, Kent, UK.
[27] O’Hanley, Locating and protecting critical reserve sites to minimize expected and worst-case losses, Biological Conservation 134 pp 130– (2007)
[28] Plastria, Facility Location: Applications and Theory (2002)
[29] Plastria, Undesirable facility location in the plane with minimal covering objectives, European Journal of Operational Research 119 pp 158– (1999) · Zbl 0934.90051
[30] ReVelle, Applications of the location set covering problem, Geographical Analysis 8 pp 65– (1976) · doi:10.1111/j.1538-4632.1976.tb00529.x
[31] Schilling, A review of covering problems in facility location, Location Science 1 pp 25– (1993) · Zbl 0923.90108
[32] Snyder, Reliability models for facility location, Transportation Science 39 pp 400– (2005)
[33] Snyder, Reliability and Vulnerability in Critical Infrastructure: A Quantitative Geographic Perspective. Advances in Spatial Science Series (2006)
[34] Snyder, Planning for disruptions in supply chain networks, Tutorials in Operations Research, INFORMS pp 234– (2006)
[35] Stackelberg, Marktform und Gleichgewicht (1934)
[36] Teitz, Heuristic methods for estimating the generalized vertex median of a weighted graph, Operations Research 16 pp 955– (1968) · Zbl 0165.22804
[37] Wollmer, Removing arcs from a network, Operations Research 12 pp 934– (1964) · Zbl 0204.20102
[38] Wood, Deterministic network interdiction, Mathematical and Computer Modeling 17 pp 1– (1993) · Zbl 0800.90772
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.