ارائه الگوریتم جستجوی ممنوعه جهت حل مسئله مکانیابی-حمله- حفاظت تسهیلات بحرانی در شرایط عدم‌تقارن اطلاعات

نوع مقاله : مقاله پژوهشی

نویسندگان

1 دانشگاه گلپایگان

2 عضو هیئت علمی

چکیده

اکثر فعالیت‏های تروریستی که طی دو دهه گذشته به وقوع پیوسته است مبتنی بر اطلاعات دقیق انجام گرفته‏اند که منجر به ایجاد اختلال در فعالیت‏های اساسی کشور شده و خسارات گسترده‏ای را به‌همراه داشته است و ازاین‌رو این موضوع تهدیدی برای زیرساخت‏های عمومی می‏باشد. گسترش چشمگیر چنین فعالیت‏هایی، لزوم برای مکانیابی صحیح و حفاظت از این زیرساخت‏ها به‌منظور افزایش پایایی تسهیلات برای ارائه خدمات را نشان می‏دهد. در چنین شرایطی، بازی استکلبرگی بین طراح سیستم و مهاجم شکل می‏گیرد که طی آن بازیکنان بر اساس اطلاعاتی که از رقیب خود در اختیار دارند، در تلاشند تا با پیش‌بینی و پاسخگویی به استراتژی‏ انتخابی رقیب، ریسک تصمیم‏گیری‏ خود را کاهش دهند. به‌دلیل ارزش بالای اطلاعات و در اختیار نداشتن اطلاعات دقیق و صحیح در شرایط تضاد منافع، در این تحقیق برآنیم تا با مدل‌سازی مسئله مکانیابی-حمله-حفاظت در شرایط عدم‌تقارن اطلاعات و با فرض امکان حملات جزئی، به‌صورت یک مدل برنامه‏ریزی دوسطحی به بررسی مزایا و ریسک‏های ناشی از نادیده گرفتن عدم‌تقارن اطلاعات توسط طراح سیستم بپردازیم. با توجه به منطقی نبودن زمان حل روش کروش-کان-تاکر در مسائل بزرگ، در این تحقیق الگوریتم جستجوی ممنوعه‏ای مبتنی بر هش ارائه می‌نماییم و با محاسبه معیارهایی همچون منطقی بودن موزون و مستقیم، کارایی و اثربخشی الگوریتم پیشنهادی را با اجرای الگوریتم بر روی تعدادی مسئله نمونه تولیدشده به‌صورت تصادفی نشان می‌دهیم.

کلیدواژه‌ها

عنوان مقاله [English]

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

نویسندگان [English]

  • M. Mesibidgoli 1
  • Javid Jouzdani 2
1 Department of Industrial Engineering, Golpaigan University, Iran
2 Industrial Engineering Dept., Golpayegan University of Technology, Golpaygan, Isfahan, Iran
چکیده [English]

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.

کلیدواژه‌ها [English]

  • Network Interdiction
  • Covering Facility Location
  • Protection
  • Tabu search algorithm
  • Information asymmetry

مراجع

[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
نشریه پژوهش های مهندسی صنایع در سیستم های تولید
دوره 7، شماره 15
اسفند 1398
صفحه 255-271

فایل ها

هم رسانی

ارجاع به این مقاله

آمار