A meta-heuristic method for maximum capacity path interdiction problem with multiple attackers

Document Type : Industry Article

Authors

1 Institute for the Study of War, Command and Staff University

2 Researcher, Institute for the Study of War, AJA Command and Staff University

3 Department of Industrial Engineering, Birjand University of Technology, Birjand, Iran

Abstract

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.

Keywords

Main Subjects

References

[1] C.Turnitsa, C.Blais, A.Tolk, "Simulation and Wargaming", 1th ed, Wiley, 2022.
[2] A.R.Washburn, "Two-person zero-sum games", 4th ed, Springer, 2014.
[3] H.Bigdeli, H.Hassanpour, "A satisfactory strategy of multiobjective two person matrix games with fuzzy payoffs", Iranian Journal of Fuzzy Systems, 2016; 13(4): 17-33. doi: 10.22111/ijfs.2016.2593.
[4] H.Bigdeli, H.Hassanpour, "Solving Defender-Attacker Game with Multiple Decision Makers Using Expected-Value Model", Caspian Journal of Mathematical Sciences (CJMS), 2020; 11(2): 368-380. doi: 10.22080/cjms.2020.18275.1466.
[5] H.Bigdeli, H.Hassanpour, J.Tayyebi, "Constrained Bimatrix Games with Fuzzy Goals and its Application in Nuclear Negotiations", Iranian Journal of Numerical Analysis and Optimization, 2018; 8(1): 81-110. doi: 10.22067/ijnao.v8i1.55385.
[6] H.Bigdeli, H.Hassanpour, J.Tayyebi, "Multiobjective security game with fuzzy payoffs", Iranian Journal of Fuzzy Systems, 2019; 16(1): 89-101. doi: 10.22111/ijfs.2019.4486.
[7] Smith, J.C., and Song, Y., "A survey of network interdiction models and algorithms", European Journal of Operational Research, 2020,Vol. 283, ,  pp. 797-811.
[8] Fulkerson, D.R., and Harding, G.C., "Maximizing the minimum source-sink path subject to a budget constraint", Mathematical Programming, Vol. 13, 1977,  pp. 116-118.
[9] Altner, D.S., Ergun, Ö., and Uhan, N.A., "The maximum flow network interdiction problem: valid inequalities, integrality gaps, and approximability", Operations Research Letters, Vol. 38, 2010,  pp. 33-38.
[10] Church, R.L., Scaparra, M.P., and Middleton, R.S., "Identifying critical infrastructure: the median and covering facility interdiction problems", Annals of the Association of American Geographers, Vol. 94, 2004, pp. 491-502.
[11] von Stackelberg, H., "The Theory of the Market Economy (translated from German) ", William Hodge & Co., London, UK ,1952.
 [12] عباس کاری مجید آباد، مرضیه مظفری و علی نعیمی صدیق، "تعادل استکلبرگ-نش در بازی مکان‌یابی رقابتی تسهیلات میان یک امتیازدهنده و دو سرمایه‌گذار"، نشریه مدل‌سازی در مهندسی، دوره 12، شماره 57، تابستان 1398، صفحه 111- 125.
[13] Wollmer, R., "Removing arcs from a network", Operations Research, Vol. 12, 1964,  pp. 934-940.
[14] Morton, D.P., Pan, F., and Saeger, K.J., "Models for nuclear smuggling interdiction", IIE Transactions, Vol. 39, 2007, pp. 3-14.
[15] Delgadillo, A., Arroyo, J.M., and Alguacil, N., "Analysis of electric grid interdiction with line switching", IEEE Transactions on Power Systems, Vol. 25, 2009, pp. 633-641.
[16] Whiteman, P.S.B., "Improving single strike effectiveness for network interdiction", Military Operations Research, 1999, pp. 15-30.
[17] Israeli, E., and Wood, R.K., "Shortest‐path network interdiction", Networks: An International Journal, Vol. 40, 2002, pp. 97-111.
[18] Zhang, J., Zhuang, J., and Behlendorf, B., "Stochastic shortest path network interdiction with a case study of arizona–mexico border", Reliability Engineering & System Safety, Vol. 179, 2018,pp. 62-73.
[19] Sadeghi, S., Seifi, A., and Azizi, E., "Trilevel shortest path network interdiction with partial fortification", Computers & Industrial Engineering, Vol. 106, 2017, pp. 400-411.
[20] Pollack, M., "Letter to the editor-the maximum capacity through a network", Operations Research, Vol. 8, 1960, pp. 733-736.
[21] Shacham, N., “Multicast routing of hierarchical data,” Discovering a New World of Communications, IEEE, 1992, pp. 1217-1221.
[22] Wang, Z., and Crowcroft, J., “Bandwidth-delay based routing algorithms,” GLOBECOM'95, IEEE, 1995, pp. 2129-2133.
[23] Ullah, E., Lee, K., and Hassoun, S., “An algorithm for identifying dominant-edge metabolic pathways,” Proceeding of. IEEE/ACM International Conference on Computer-Aided Design-Digest of Technical Papers, IEEE, 2009, pp. 144-150.
[24] Mohammadi, A., and Tayyebi, J., "Maximum capacity path interdiction problem with fixed costs", Asia-Pacific Journal of Operational Research, Vol. 36, 2019, pp. 1950018-1-1950018-21.
[25] Dijkstra, E.W., "A note on two problems in connexion with graphs", Numerische mathematik, Vol. 1, 1959, pp. 269-271.
[26] عرفان بابایی تیر کلایی، ایرج مهدوی و میر مهدی سید اصفهانی، "حل مسأله مسیریابی وسایل نقلیه با در نظر گرفتن سفرهای چندگانه و پنجره‌های زمانی در مدیریت پسماند شهری با استفاده از الگوریتم بهینه‌سازی گرگ خاکستری"، نشریه مدل‌سازی در مهندسی، دوره 17، شماره 57، تابستان 1398، صفحه 93- 110.
[27] سید مهدی حسینی مطلق، محمد رضا قطره سامانی و عباس جوکار، "ارائه یک مدل ریاضی و روش حل ابتکاری برای مسئله مکان‌یابی-مسیریابی دوسطحی با در نظر گرفتن شرایط گذاشت و برداشت در حالت عدم قطعیت"، نشریه مدل‌سازی در مهندسی، دوره 16، شماره 53، تابستان 1397، صفحه 339- 361.
[28] Sinha, A., Malo, P., and Deb, K., "A review on bilevel optimization: from classical to evolutionary approaches and applications", IEEE Transactions on Evolutionary Computation, Vol. 22, 2017, pp. 276-295.
[29] Hansen, P., Jaumard, B., and Savard, G., "New branch-and-bound rules for linear bilevel programming", SIAM Journal on scientific and Statistical Computing, Vol. 13, 1992, pp. 1194-1217.
[30] Vicente, L., Savard, G., and Júdice, J., "Descent approaches for quadratic bilevel programming", Journal of optimization theory and applications, Vol. 81, 1994,  pp. 379-399.
[31] Wei, K., Gao, Y., Zhang, W., and Lin, S., “A modified Dijkstra’s algorithm for solving the problem of finding the maximum load path”, Proceeding of 2019 IEEE 2nd International Conference on Information and Computer Technologies (ICICT), IEEE, 2019, pp. 10-13.
[32] Siddique, N., and Adeli, H., "Simulated annealing, its variants and engineering applications", International Journal on Artificial Intelligence Tools, Vol. 25, No. 06, 2016, 1630001.
[33] Yang, J., Borrero, J.S., Prokopyev, O.A., and Sauré, D., "Sequential shortest path interdiction with incomplete information and limited feedback", Decision Analysis, Vol. 18, 2021, pp. 218-244.
[34] Abdolahzadeh, A., Aman, M., and Tayyebi, J., "Minimum st-cut interdiction problem", Computers & Industrial Engineering, Vol. 148, 2020, 106708.
[35] Sinha, A., Malo, P., Frantsev, A., and Deb, K., "Finding optimal strategies in a multi-period multi-leader–follower Stackelberg game using an evolutionary algorithm", Computers & operations research, Vol. 41, 2014, pp. 374-385.
Journal of Modeling in Engineering
Volume 20, Issue 70
September 2022
Pages 133-146

Files

History

  • Receive Date: 23 January 2022
  • Revise Date: 18 April 2022
  • Accept Date: 08 May 2022

Share

How to cite

Statistics