دانشگاه سمنان مدل سازی در مهندسی 2008-4854 20 70 2022 09 23 A meta-heuristic method for maximum capacity path interdiction problem with multiple attackers یک روش حل فرا ابتکاری برای مسئله ممانعت از بیشینه ظرفیت با چندین مهاجم 133 146 6604 10.22075/jme.2022.26026.2213 FA حمید بیگدلی پژوهشکده عالی جنگ، دانشگاه فرماندهی و ستاد آجا سید محمد صادق میردامادی پژوهش‌گر پژوهشکده عالی جنگ، دانشگاه فرماندهی و ستاد آجا جواد طیبی Department of Industrial Engineering, Birjand University of Technology, Birjand, Iran Journal Article 2022 01 23 Network interdiction problems are a group of problems in which two actors face each other with conflicting goals. In these matters, the benefit of one actor damages the other actor. In the case of maximum capacity path interdiction, a defender in the role of leader applies his interdicting actions according to the available budget. At the next level several attackers, as followers observing the defender's interdiction action, optimize the maximum capacity path problem from the origin to the destination. Interdiction is attacking the network arcs to destroy them and reduce the capacity of the arc. In this research, first, a two-level binary mathematical programming model for the problem is described. Then, due to the complexity of solving two-level problems, a hybrid algorithm including a revised Dijkstra algorithm and a simulated annealing algorithm is proposed to solve the problem. The revised Dijkstra algorithm always finds an optimal solution to the maximum capacity problem. Therefore, the hybrid algorithm can find good solutions in the search space. Then, the efficiency of the proposed algorithm was evaluated up to the size of 100 nodes and 150 arcs, which shows the ability of the algorithm to solve problems in different sizes. Based on the conclusions, increasing the defender budget results in the objective function being improved to a certain extent. The coefficient of attackers in the objective function is inversely related to the quality of the attackers' path and increases or decreases the maximum capacity of the attackers' path. مسائل ممانعت در شبکه، دسته‌ای از مسائل هستند که دو بازیگر با اهداف متضاد به تقابل با یکدیگر می‌پردازند و به صورت کلی منفعت یک بازیگر موجب متضرر شدن بازیگر دیگر می‌شود. در مسئله ممانعت از بیشینه ظرفیت، یک مدافع در نقش رهبر اقدامات ممانعتی خود را با توجه به بودجه موجود بر روی یال‌های یک شبکه اعمال می‌کند. در سطح بعدی، تعدادی مهاجم به عنوان پیرو و با مشاهده اقدامات ممانعتی مدافع، مسئله بیشینه‌سازی ظرفیت مسیر را از مبدأ به مقصد بهینه‌سازی می‌نمایند. ممانعت در واقع حمله به کمان‌های شبکه و تخریب آن‌ها، با هدف کاهش ظرفیت عبوری کمان می‌باشد. در این پژوهش در ابتدا یک مدل برنامه‌ریزی ریاضی دو سطحی صفر و یک برای مسئله مورد نظر بیان شده است. سپس با توجه به پیچیدگی حل مسائل دو سطحی، یک الگوریتم ترکیبی شامل الگوریتم دایکسترا اصلاح شده و الگوریتم شبیه‌سازی تبرید برای حل مسئله پیشنهاد شده است. الگوریتم دایکسترا اصلاح شده همواره جواب بهینه مسئله بیشینه ظرفیت را ارائه می‌دهد که سبب تولید جواب‌های مطلوب در الگوریتم ترکیبی می‌گردد. سپس کارایی الگوریتم‌ پیشنهادی تا ابعاد 100 گره و 150 کمان مورد بررسی قرار گرفت که نشان دهنده توانایی الگوریتم برای حل مسائل در ابعاد مختلف می‌باشد. بر اساس نتایج حاصل شده، افزایش بودجه مدافع تا میزان مشخصی بر بهبود تابع هدف مسئله تأثیرگذار می‌باشد. همچنین مقدار ضریب اهمیت مهاجمان در مسئله، ارتباط معکوس با کیفیت مسیر مهاجمان دارد و موجب افزایش یا کاهش بیشینه ظرفیت مسیر مهاجمان می‌گردد. https://modelling.semnan.ac.ir/article_6604_b4f196df5be930e948d32a31e89e3582.pdf