×

A bilevel fixed charge location model for facilities under imminent attack. (English) Zbl 1251.90232

Summary: We investigate a bilevel fixed charge facility location problem for a system planner (the defender) who has to provide public service to customers. The defender cannot dictate customer-facility assignments since the customers pick their facility of choice according to its proximity. Thus, each facility must have sufficient capacity installed to accommodate all customers for whom it is the closest one. Facilities can be opened either in the protected or unprotected mode. Protection immunizes against an attacker who is capable of destroying at most r unprotected facilities in the worst-case scenario. Partial protection or interdiction is not possible. The defender selects facility sites from m candidate locations which have different costs. The attacker is assumed to know the unprotected facilities with certainty. He makes his interdiction plan so as to maximize the total post-attack cost incurred by the defender. If a facility has been interdicted, its customers are reallocated to the closest available facilities making capacity expansion necessary. The problem is formulated as a static Stackelberg game between the defender (leader) and the attacker (follower). Two solution methods are proposed. The first is a tabu search heuristic where a hash function calculates and records the hash values of all visited solutions for the purpose of avoiding cycling. The second is a sequential method in which the location and protection decisions are separated. Both methods are tested on 60 randomly generated instances in which \(m\) ranges from \(10\) to \(30\), and \(r\) varies between \(1\) and \(3\). The solutions are further validated by means of an exhaustive search algorithm. Test results show that the defender’s facility opening plan is sensitive to the protection and distance costs.

MSC:

90B80 Discrete location and assignment
90C59 Approximation methods and heuristics in mathematical programming

Software:

Tabu search
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Snyder, L. V.; Daskin, M. S., Reliability models for facility location: the expected failure cost case, Transportation Science, 39, 3, 400-416 (2005)
[2] Church, R. L.; Scaparra, M. P.; Middleton, R. S., Identifying critical infrastructure: the median and covering facility interdiction problems, Annals of the Association of American Geographers, 94, 3, 491-502 (2004)
[3] Church, R. L.; Scaparra, M. P., Protecting critical assets: the \(r\)-interdiction median problem with fortification, Geographical Analysis, 39, 2, 129-146 (2007)
[4] Scaparra, M. P.; Church, R. L., A bilevel mixed integer program for critical infrastructure protection planning, Computers & Operations Research, 35, 6, 1905-1923 (2008) · Zbl 1139.90439
[5] Scaparra, M. P.; Church, R. L., An exact solution approach for the interdiction median problem with fortification, European Journal of Operational Research, 189, 1, 76-92 (2008) · Zbl 1175.90050
[6] Scaparra MP, Church RL. Protecting supply systems to mitigate potential disaster: a model to fortify capacitated facilities. Kent Business School Working Paper No. 209, 2010; University of Kent, UK.; Scaparra MP, Church RL. Protecting supply systems to mitigate potential disaster: a model to fortify capacitated facilities. Kent Business School Working Paper No. 209, 2010; University of Kent, UK.
[7] Losada C, Scaparra MP, Church RL, Daskin MS. Modeling approaches for the multi-source interdiction median problem. Kent Business School Working Paper No. 187, 2010; University of Kent, UK.; Losada C, Scaparra MP, Church RL, Daskin MS. Modeling approaches for the multi-source interdiction median problem. Kent Business School Working Paper No. 187, 2010; University of Kent, UK.
[8] Motto, A. L.; Arroyo, J. M.; Galiana, F. D., MILP for the analysis of electric grid security under disruptive threat, IEEE Transactions on Power Systems, 20, 3, 1357-1365 (2005)
[9] O’Hanley, J. R.; Church, R. L.; Gilless, K., Locating and protecting critical reserve sites to minimize expected and worst-case losses, Biological Conservation, 134, 1, 130-141 (2007)
[10] Liberatore, F.; Scaparra, M. P.; Daskin, M. S., Analysis of facility protection strategies against an uncertain number of attacks: the stochastic \(r\)-interdiction median problem with fortification, Computers & Operations Research, 38, 1, 357-366 (2011) · Zbl 1231.90268
[11] Aksen, D.; Piyade, N.; Aras, N., The budget constrained \(r\)-interdiction median problem with capacity expansion, Central European Journal of Operations Research, 18, 3, 269-291 (2010) · Zbl 1204.90058
[12] Teixeira, J. C.; Antunes, A. P., A hierarchical location model for public facility planning, European Journal of Operational Research, 185, 1, 92-104 (2008) · Zbl 1146.90461
[13] Church RL Cohon JL. Multiobjective location analysis of regional energy facility sitting problems. Report prepared for the US Energy Research and Development Administration (BNL 50567); 1976.; Church RL Cohon JL. Multiobjective location analysis of regional energy facility sitting problems. Report prepared for the US Energy Research and Development Administration (BNL 50567); 1976.
[14] Moore, J. T.; Bard, J. F., The mixed-integer linear bilevel programming problem, Operations Research, 38, 5, 911-921 (1990) · Zbl 0723.90090
[15] Gümüş, Z. H.; Floudas, C. A., Global optimization of mixed-integer bilevel programming problems, Computational Management Science, 2, 3, 181-212 (2005) · Zbl 1112.90061
[16] Sherali, H. D.; Adams, W. P., A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems, SIAM Journal on Discrete Mathematics, 3, 3, 411-430 (1990) · Zbl 0712.90050
[17] Sherali, H. D.; Adams, W. P.; Driscoll, P. J., Exploiting special structures in constructing a hierarchy of relaxations for 0-1 mixed integer problems, Operations Research, 46, 3, 396-405 (1998) · Zbl 0979.90090
[18] Floudas, C. A., Deterministic global optimization: theory, methods and applications (nonconvex optimization and its applications, vol. 37) (2000), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht, The Netherlands
[19] Hecheng, L.; Yuping, W., Exponential distribution-based genetic algorithm for solving mixed-integer bilevel programming problems, Journal of Systems Engineering and Electronics, 19, 6, 1157-1164 (2008) · Zbl 1228.90059
[20] Glover, F.; Laguna, M.; Martí, R., Principles of tabu search, (Gonzalez, T., Handbook on approximation algorithms and metaheuristics (2007), Chapman & Hall/CRC: Chapman & Hall/CRC Boca Raton)
[21] Gendreau, M., An introduction to tabu search, (Glover, F.; Kochenberger, G. A., Handbook of metaheuristics. (2003), Kluwer Academic Publishers: Kluwer Academic Publishers Boston, Dordrecht, London), 37-54 · Zbl 1102.90380
[22] Rolland, E.; Schilling, D.; Current, J. R., An efficient tabu search procedure for the \(p\)-median problem, European Journal of Operational Research, 96, 2, 329-342 (1996) · Zbl 0924.90102
[23] Aras, N.; Aksen, D., Locating collection centers for distance- and incentive-dependent returns, International Journal of Production Economics, 111, 2, 316-333 (2008)
[24] Aras, N.; Aksen, D.; Tanuğur, A. G., Locating collection centers for incentive-dependent returns under a pick-up policy with capacitated vehicles, European Journal of Operational Research, 191, 3, 1223-1240 (2008) · Zbl 1162.90004
[25] Woodruff, D. L.; Zemel, E., Hashing vectors for tabu search, Annals of Operations Research, 41, 2, 123-137 (1993) · Zbl 0775.90294
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.