A meta-heuristic method for maximum capacity path interdiction problem with multiple attackers
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 a...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | fas |
| Published: |
Semnan University
2022-09-01
|
| Series: | مجله مدل سازی در مهندسی |
| Subjects: | |
| Online Access: | https://modelling.semnan.ac.ir/article_6604_b4f196df5be930e948d32a31e89e3582.pdf |
| _version_ | 1797296480489308160 |
|---|---|
| author | Hamid Bigdeli Seyed Mohammad Sadegh Mirdamadi Javad Tayyebi |
| author_facet | Hamid Bigdeli Seyed Mohammad Sadegh Mirdamadi Javad Tayyebi |
| author_sort | Hamid Bigdeli |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-07T22:05:23Z |
| format | Article |
| id | doaj.art-8ca9dd08fd6b4faeadb0bfe02213f914 |
| institution | Directory Open Access Journal |
| issn | 2008-4854 2783-2538 |
| language | fas |
| last_indexed | 2024-03-07T22:05:23Z |
| publishDate | 2022-09-01 |
| publisher | Semnan University |
| record_format | Article |
| series | مجله مدل سازی در مهندسی |
| spelling | doaj.art-8ca9dd08fd6b4faeadb0bfe02213f9142024-02-23T19:09:41ZfasSemnan Universityمجله مدل سازی در مهندسی2008-48542783-25382022-09-01207013314610.22075/jme.2022.26026.22136604A meta-heuristic method for maximum capacity path interdiction problem with multiple attackersHamid Bigdeli0Seyed Mohammad Sadegh Mirdamadi1Javad Tayyebi2Institute for the Study of War, Command and Staff UniversityResearcher, Institute for the Study of War, AJA Command and Staff UniversityDepartment of Industrial Engineering, Birjand University of Technology, Birjand, IranNetwork 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.https://modelling.semnan.ac.ir/article_6604_b4f196df5be930e948d32a31e89e3582.pdfzero-sum gamenetwork interdictionmaximum capacity path problemrevised dijkstra's algorithmsimulated annealing algorithm |
| spellingShingle | Hamid Bigdeli Seyed Mohammad Sadegh Mirdamadi Javad Tayyebi A meta-heuristic method for maximum capacity path interdiction problem with multiple attackers مجله مدل سازی در مهندسی zero-sum game network interdiction maximum capacity path problem revised dijkstra' s algorithm simulated annealing algorithm |
| title | A meta-heuristic method for maximum capacity path interdiction problem with multiple attackers |
| title_full | A meta-heuristic method for maximum capacity path interdiction problem with multiple attackers |
| title_fullStr | A meta-heuristic method for maximum capacity path interdiction problem with multiple attackers |
| title_full_unstemmed | A meta-heuristic method for maximum capacity path interdiction problem with multiple attackers |
| title_short | A meta-heuristic method for maximum capacity path interdiction problem with multiple attackers |
| title_sort | meta heuristic method for maximum capacity path interdiction problem with multiple attackers |
| topic | zero-sum game network interdiction maximum capacity path problem revised dijkstra' s algorithm simulated annealing algorithm |
| url | https://modelling.semnan.ac.ir/article_6604_b4f196df5be930e948d32a31e89e3582.pdf |
| work_keys_str_mv | AT hamidbigdeli ametaheuristicmethodformaximumcapacitypathinterdictionproblemwithmultipleattackers AT seyedmohammadsadeghmirdamadi ametaheuristicmethodformaximumcapacitypathinterdictionproblemwithmultipleattackers AT javadtayyebi ametaheuristicmethodformaximumcapacitypathinterdictionproblemwithmultipleattackers AT hamidbigdeli metaheuristicmethodformaximumcapacitypathinterdictionproblemwithmultipleattackers AT seyedmohammadsadeghmirdamadi metaheuristicmethodformaximumcapacitypathinterdictionproblemwithmultipleattackers AT javadtayyebi metaheuristicmethodformaximumcapacitypathinterdictionproblemwithmultipleattackers |