A Tabu-search algorithm for location-interdiction-protection problem under asymmetric information

Document Type : Research Paper

Authors

1 Department of Industrial Engineering, Golpaigan University, Iran

2 Industrial Engineering Dept., Golpayegan University of Technology, Golpaygan, Isfahan, Iran

Abstract

Most of the terrorist activities that have taken place over the past two decades have been based on accurate information, which has led to disturbances in the security and some extensive damages and it is a major threat to public and government infrastructures. The dramatic expansion of such activities has shown the necessity and importance of the correct location and protection of these infrastructures in order to reduce the damage caused by the attack to increase the reliability of facilities for providing services. In such cases, a Stachelberg game is formed between the system designer and the attacker. Due to the high value and the lack of accurate information in the context of confliction, in this research, we are going to model the location-interdiction-protection problem under asymmetric information as a bi-level programming model and explore the advantages and risks of neglecting the information asymmetry in decision-making. In order to solve the suggested bi-level model, two solution methods are proposed. At first, Karush-Kuhn-Tucker conditions are used to convert the model to a single level model.Then for large size problems, we develop a matheuristic which searches the solution space of the upper level problem according to tabu search principles, where a hash function calculates and records the hash values of all visited solutions for the purpose of avoiding cycling, and resorts to a CPLEX based exact solution technique to tackle the lower level problem. Test results show efficiency and effectiveness of the proposed heuristic algorithm.

Keywords

References

[1] Smith, J. C. (2010). Basic interdiction models. Wiley Encyclopedia of Operations Research and Management Science.
[2] 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, 94(3): 491-502.
[3] Murray, A. T., Matisziw, T. C., Grubesic, T. H. (2007). “Critical network infrastructure analysis: interdiction and system flow”, Journal of Geographical Systems, 9(2): 103-117.
[4] Scaparra, M. P., & Church, R. (2012). “Protecting supply systems to mitigate potential disaster: a model to fortify capacitated facilities”, International Regional Science Review, 35(2): 188-210.
[5] Snyder, L. V., Scaparra, M. P., Daskin, M. S., Church, R. L. (2006). “Planning for disruptions in supply chain networks”, In Models, methods, and applications for innovative decision making (pp. 234-257). INFORMS.
[6] O’Hanley, J. R., Church, R. L. (2011). “Designing robust coverage networks to hedge against worst-case facility losses”, European Journal of Operational Research, 209(1): 23-36.
[7] Church, R. L., Scaparra, M. P. (2007). “Protecting critical assets: the r‐interdiction median problem with fortification”, Geographical Analysis, 39(2): 129-146.
[8] Scaparra, M. P., & Church, R. L. (2008). “A bilevel mixed-integer program for critical infrastructure protection planning”, Computers & Operations Research, 35(6): 1905-1923.
[9] Smith, J. C., Lim, C., Sudargho, F. (2007). “Survivable network design under optimal and heuristic interdiction scenarios”, Journal of global optimization, 38(2): 181-199.
[10] Aksen, D., Piyade, N., Aras, N. (2010). “The budget constrained r-interdiction median problem with capacity expansion”, Central European Journal of Operations Research, 18(3): 269-291.
[11] 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, 217(3): 519-530.
[12] 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, 38(1): 357-366.
[13] Cappanera, P., Scaparra, M. P. (2011). “Optimal allocation of protective resources in shortest-path networks”, Transportation Science, 45(1): 64-80.
[14] Roboredo, M. C., Pessoa, A. A., Aizemberg, L. (2019). “An exact approach for the r-interdiction median problem with fortification”, RAIRO: Recherche Opérationnelle, 53(2): 505-516
[15] Mahmoodjanloo, M., Parvasi, S. P., Ramezanian, R. (2016). “A tri-level covering fortification model for facility protection against disturbance in r-interdiction median problem”, Computers & Industrial Engineering, 102: 219-232.
[16] Lim, C., Smith, J. C. (2007). “Algorithms for discrete and continuous multicommodity flow network interdiction problems”, IIE Transactions, 39(1): 15-26.
[17] Berman, O., Gavious, A. (2007). “Location of terror response facilities: A game between state and terrorist”, European Journal of Operational Research, 177(2): 1113-1133.
[18] Berman, O., Gavious, A., & Huang, R. (2010). “Location of response facilities: a simultaneous game between state and terrorist”, International Journal of Operational Research, 10(1): 102-120.
[19] Church, R., ReVelle, C. (1974). “The maximal covering location problem”, Papers in regional science, 32(1): 101-118.
[20] Berman, O., Drezner, T., Drezner, Z., Wesolowsky, G. O. (2009). “A defensive maximal covering problem on a network”, International Transactions in Operational Research, 16(1): 69-86.
[21] Aksen, D., & Aras, N. (2012). “A bilevel fixed charge location model for facilities under imminent attack”, Computers & Operations Research, 39(7): 1364-1381.
[22] Keçici, S., Aras, N., & Verter, V. (2012). “Incorporating the threat of terrorist attacks in the design of public service facility networks”, Optimization Letters, 6(6): 1101-1121.
[23] Akbari-Jafarabadi, M., Tavakkoli-Moghaddam, R., Mahmoodjanloo, M., & Rahimi, Y. (2017). “A tri-level r-interdiction median model for a facility location problem under imminent attack”. Computers & Industrial Engineering, 114: 151-165.
[24] Zhang, X. Y., Zheng, Z., Cai, K. Y. (2017). “A fortification model for decentralized supply systems and its solution algorithms”, IEEE Transactions on Reliability, 67(1): 381-400.
[25] Fard, A. M. F., Hajiaghaei-Keshteli, M. (2018). “A bi-objective partial interdiction problem considering different defensive systems with capacity expansion of facilities under imminent attacks”, Applied Soft Computing, 68: 343-359.
[26] Aliakbarian, N., Dehghanian, F., Salari, M. (2015). “A bi-level programming model for protection of hierarchical facilities under imminent attacks”, Computers & operations research, 64, 210-224.
[27] Forghani, A. & Dehghanian, F. & Salari, M. & Ghiami, Y. (2020). “A bi-level model and solution methods for partial interdiction problem on capacitated hierarchical facilities”. Computers & Operations Research 114. 104831.10/1016/j.cor2019/10483.
[28] Bricha, N., & Nourelfath, M. (2013). “Critical supply network protection against intentional attacks: A game-theoretical model”, Reliability Engineering & System Safety, 119: 1-10.
[29] Bricha, N., Nourelfath, M. (2014). “Extra-capacity versus protection for supply networks under attack”, Reliability Engineering & System Safety, 131: 185-196.
[30] Bricha, N., Nourelfath, M. (2015). “Protection of warehouses and plants under capacity constraint”, Reliability Engineering & System Safety, 138: 93-104.
[31] Berman, O., Krass, D., & Drezner, Z. (2003). “The gradual covering decay location problem on a network”, European Journal of Operational Research, 151(3): 474-480.
[32] Sinha, A., Malo, P., Deb, K. (2017). “A review on bilevel optimization: From classical to evolutionary approaches and applications”, IEEE Transactions on Evolutionary Computation, 22(2): 276-295.
[33] Sun, M. (2006). “Solving the uncapacitated facility location problem using tabu search”, Computers & Operations Research, 33(9): 2563-2589.
[34] Aras, N., & Aksen, D. (2008). “Locating collection centers for distance-and incentive-dependent returns”, International Journal of Production Economics, 111(2): 316-333.
[35] Aras, N., Aksen, D., Tanuğur, A. G. (2008). “Locating collection centers for incentive-dependent returns under a pick-up policy with capacitated vehicles”. European Journal of Operational Research, 191(3): 1223-1240.
[36] Aksen, D., Aras, N. (2013). “A matheuristic for leader-follower games involving facility location-protection-interdiction decisions”. In Metaheuristics for Bi-level Optimization (pp. 115-151). Springer, Berlin, Heidelberg
Journal of Industrial Engineering Research in Production Systems
Volume 7, Issue 15
March 2020
Pages 255-271

Files

Share

How to cite

Statistics