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

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

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

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.