Presentation of a Tri-level Covering Fortification Model in Order to Protect Facility Against Disturbance in r-interdiction Median Problem with the Approach of Stackelberg Game

Document Type : Research Paper

Authors

Department of Industrial Engineering, Khajeh Nasir Toosi University of Technology, Tehran, Iran

Abstract

In this paper, a tri-level defense facility location model for full coverage in r-interdiction median problem is delivered. The purpose of this model is to design a proper service system in a way that after a worst case scenario of disturbance, they can utilize their full capacity of providing services. Hence, we have considered the defense facilities to provide extra protection for service facilities, and the goal is to optimally locate these facilities. The tri-level model is proposed based on leader-follower games as defender-attacker-defender framework. After the disturbance caused by the attacker, with the purpose of ensuring the operation of service facilities, the defender tries to establish a number of defense facilities in potential locations. Locating these facilities is carried with respect to the establishment of fixed cost of facilities and system’s current cost. It should be noted that each service facility must be at least within the coverage range of at least one defense facility (first level).So, system’s current costs can be defined based on the worst-case scenario of disturbance caused by the attacker. The problem is modeled as a static Stackelberg game between the attacker (level 2) and defender (level 3). In order to solve the model, two approaches have been used. In the first approach, explicit enumeration method is used for the first and second levels and an exact approach is used for the third level. In the second approach, hybrid methods consisting of genetic algorithm, explicit exact enumeration and exact approach have been used to solve the problem in a reasonable time. Comparing the proposed meta-heuristic to the exact approach in some samples, the numerical results show a quite satisfactory of this algorithm.

Keywords

Main Subjects

References

1. Aksen, D., Aras, N. & Piyade, N. (2013). “A bilevel p-median model for the planning and protection of critical facilities”, Journal of Heuristics, Vol. 19, No. 2, PP. 373- 398.
2. Aksen, D., Akca, S. Ş. & Aras, N. (2014). “A bilevel partial interdiction problem with capacitated facilities and demand outsourcing”, Computers & Operations Research, Vol. 41, PP. 346- 358.
3. Wollmer, R. D. (1964). “Removing arcs from a network”, Journal of Operations Research Society of America, Vol. 12, No. 6, PP. 934– 940.
4. Aksen, D. & Aras, N. (2012). “A bilevel fixed charge location model for facilities under imminent attack”, Computers & Operations Research, Vol. 39, No. 7, PP. 1364- 1381.
5. Church, R. L., Scaparra, M. P. & Middleton, R. S. (2004). “Identifying critical infrastructure: The median and covering facility interdiction problems”, Annals of the Association of American Geographers, Vol. 94, No. 3, PP. 491- 502.
6. Scaparra, M. P. & Church, R. L. (2008). “An exact solution approach for the interdiction median problem with fortification”, European Journal of Operational Research, Vol. 189, No. 1, PP. 76- 92.
7. Liberatore, F., Scaparra, M. P. & Daskin, M. S. (2011). “Analysis of facility protection strategies against an uncertain number of attacks: The stochastic R-interdiction median problem with fortification”, Computers & Operations Research, Vol. 38, No. 1, PP. 357- 366.
8. Church, R. L. & Scaparra, M. P. (2007). “Protecting critical assets: The r-interdiction median problem with fortification”, Geographical Analysis, Vol. 39, No. 2, PP. 129- 146.
9. Scaparra, M. P. & Church, R. L. (2008). “A bilevel mixed-integer program for critical infrastructure protection planning”, Computers & Operations Research, Vol. 35, No. 6, PP. 1905- 1923.
10. Scaparra, M. P. & Church, R. (2012). “Protecting supply systems to mitigate potential disaster a model to fortify capacitated facilities”, International Regional Science Review, Vol. 35, No. 2, PP. 188- 210.
11. Aksen, D., Piyade, N. & Aras, N. (2010). “The budget constrained r-interdiction median problem with capacity expansion”, Central European Journal of Operations Research, Vol. 18, No. 3, PP. 269- 291.
12. Liberatore, F., Scaparra, M. P. & Daskin, M. S. (2012). “Hedging against disruptions with ripple effects in location analysis”, Omega, Vol. 40, No. 1, PP. 21- 30.
13. Losada, C., Scaparra, M. P. & O’Hanley, J. R. (2012). “Optimizing system resilience: A facility protection model with recovery time”, European Journal of Operational Research, Vol. 217, No. 3, PP. 519- 530.
14. Zhu, Y., Zheng, Z., Zhang, X. & Cai, K. (2013). “The r-interdiction median problem with probabilistic protection and its solution algorithm”, Computers & Operations Research, Vol. 40, No. 1, PP. 451- 462.
15. Medal, H. R., Rainwater, C. E., Pohl, E. A. & Rossetti, M. D. (2014). “A bi-objective analysis of the r-all-neighbor p-center problem”, Computers & Industrial Engineering, Vol. 72, PP. 114- 128.
16. Alguacil, N., Delgadillo, A. & Arroyo, J. M. (2014). “A tri-level programming approach for electric grid defense planning”, Computers & Operations Research, Vol. 41, PP. 282- 290.
17. Bard, J. F. (1991). “Some properties of the bilevel programming problem”, Journal of Optimization Theory and Applications, Vol. 68, No. 2, PP. 371- 378.
18. Jeroslow, R. G. (1985). “The polynomial hierarchy and a simple model for competitive analysis”, Mathematical Programming, Vol. 32, No. 2, PP. 146- 164.
19. Talbi, El-Ghazali. (2013). “Metaheuristics for Bi-level Optimization”, Springer Heidelberg, Vol. 482.
20. Sakawa, M. & Nishizaki, I. (2009). “Cooperative and noncooperative multi-level programming”, Springer Science & Business Media, Vol. 48.
21. Hejazi, S. R., Memariani, A., Jahanshahloo, G. & Sepehri, M. M. (2002). “Linear bilevel programming solution by genetic algorithm”, Computers & Operations Research, Vol. 29, No. 13, PP. 1913- 1925.
22. Li, H., Jiao, Y. & Zhang, L. (2010). “Orthogonal genetic algorithm for solving quadratic bi-level programming problems”, Journal of Systems Engineering and Electronics, Vol. 21, No. 5, PP. 763- 770.
23. Konak, A., Kulturel-Konak, S. & Snyder, L. V. (2015). “A game-theoretic genetic algorithm for the reliable server assignment problem under attacks”, Computers & Industrial Engineering, Vol. 85, PP. 73– 85.
24. Aliakbarian, N., Dehghanian, F. & Salari, M. (2015). “A bi-level programming model for protection of hierarchical facilities under imminent attacks”, Computers & Operations Research, Vol. 64, PP. 210- 224.
25. Holland, J. H. (1975). Adaptation in natural and artificial systems: An introductory analysis with applications to biology, control, and artificial intelligence, The University of MIT press.
26. Zandieh, M., Amiri, M., Vahdani, B. & Soltani, R. (2009). “A robust parameter design for multi-response problems”, Journal of computational and applied mathematics, Vol. 230, No. 2, PP. 463-476.
Advances in Industrial Engineering
Volume 51, Issue 1
April 2017
Pages 45-58

Files

Share

How to cite

Statistics