A Polynomial-time Algorithm for Solving the Most Reliable Routing Interdiction Problem

Document Type : Original Article

Authors

1 Associate Professor, Birjand University of Technology, Birjand, Iran

2 Assistant Professor, Bozorgmehr Qaen University, Qaen, Iran

3 Assistant Professor, Imam Ali University, Tahzan, Iran

Abstract

This paper analyzes a specific type of optimization problem in the defense field, titled "The Most Reliable Path Interdiction Problem". This problem arises when an enemy can influence the routing strategies of friendly forces by creating natural or artificial obstacles. It is assumed that the enemy can reduce the reliability of key paths by altering the reliability of routes within budget constraints. In this paper, the costs of reducing the reliability of arcs are defined as a multiplicative function. This paper presents an efficient algorithm for solving the problem in polynomial time, providing military forces with the necessary tools to identify safer routes for the movement of troops and information in the face of sudden threats. To evaluate the performance of the algorithm, tests are conducted on randomly generated samples, and the results are reported. Additionally, a simulation example from the Iraq-Kuwait war is provided to illustrate the algorithm's implementation details. The results of this paper indicate that reliability optimization approaches can enhance the effectiveness and efficiency of military operations in critical and high-stress situations

Keywords

Main Subjects

References


[1]     Juan, W.; Huapu, L.; Xu, S.; Xianfeng, L.; Huijun, Y. “The Best Path Analysis in Military Highway Transport Based on DEA and Multiobjective Fuzzy Decision‐Making”; Math. Prob. Eng. 2014, 206024. DOI:10.1155/2014/206024
[2]     Roosta, M. “Routing Through a Network With Maximum Reliability”; J. Math. Anal. Appl. 1982, 88, 341-347. DOI: 10.1016/0022-247X(82)90144-1
[3]     Tragoudas, S. “The Most Reliable Data-Path Transmission”; IEEE Trans. Reliab. 2001, 50, 281-285. DOI: 10.1109/ 24.932722
[4]     Sanso, B.; Soumis, F.; Gendreau, M. “On the Evaluation of Telecommunications Network Reliability Using Routing Models”; IEEE Trans. Commun. 1991, 39, 1494-1501. DOI: 10.1109/26.103044
[5]     Embrechts, P.; Schied, A.; Wang, R. "Robustness in the optimization of risk measures"; Oper. Res., 2022, 70, 95-110.‏ DOI: 10.1287/opre.2021.2147
[6]     Bazmi, A. A.; Zahedi, G. “Sustainable Energy Systems: Role of Optimization Modeling Techniques in Power Generation and Supply—A Review”; Renew. Sust. Energy Rev. 2011, 15, 3480-3500. DOI:10.1016/j.rser.2011.05.003
[7]     Nikoo, N.; Babaei, M.; Mohaymany, A. S. “Emergency Transportation Network Design Problem: Identification and Evaluation of Disaster Response Routes”; Int. J. Disaster Risk Reduct. 2018, 27, 7-20. DOI:10.1016/j.ijdrr. 2017.07.003
[8]     Zolfpour-Arokhlo, M.; Selamat, A.; Hashim, S. Z. M. “Route Planning Model of Multi-Agent System for Supply Chain Management”; Expert Syst. Appl. 2013, 40, 5, 1505-1518. DOI:10.1016/j.eswa.2012.08.040
[9]     Julien, L. A. “Stackelberg Games”; Handbook of Game Theory and Industrial Organization, Volume I, Edward Elgar Publishing, 2018, 261-311. DOI: 10.4337/9781785363283. 00017
[10] Smith, J. C.; Song, Y. “A Survey of Network Interdiction Models and Algorithms”; Eur. J. Oper. Res. 2020, 283, 797-811. DOI:10.1016/j.ejor.2019.06.024
[11] Boggio Tomasaz, A. “Optimisation and Interdiction Problems for Network Safety”; Springer, 2025. DOI: 10.1007/s10288-025-00587-x
[12] Xiang, Y. “Minimizing the Maximal Reliable Path With a Nodal Interdiction Model Considering Resource Sharing”; Reliab. Eng. Syst. Saf. 2023, 239, 109495. DOI:10.1016/ j.ress.2023.109495
[13] Ahuja, R. K.; Magnanti, T. L.; Orlin, J. B. Network Flows: Theory, Algorithms, and Applications; Prentice Hall: Englewood Cliffs, NJ, 1993.
[14] Tayyebi, J.; Sepasian, A. R. “Partial Inverse Min–Max Spanning Tree Problem”; J. Comb. Optim. 2020, 40, 1075-1091. DOI: 10.1007/s10878-020-00656-3
[15] Tayyebi, J. “On the Inverse Maximum Perfect Matching Problem Under the Bottleneck-Type Hamming Distance”; Commun. Combin. Optim. 2019, 4, 35-46. DOI: 10.22049/cco.2018.26231.1087
[16] Tayyebi, J.; Deaconu, A. “Inverse Generalized Maximum Flow Problems”; Mathematics 2019, 7, 899. DOI: 10.3390/math7100899
[17] Tayyebi, J.; Mohammadi, A.; Kazemi, S. M. R. “Reverse Maximum Flow Problem Under the Weighted Chebyshev Distance”; RAIRO Oper. Res. 2018, 52, 1107-1121. DOI: 10.1051/ro/2018045
[18] Tayyebi, J.; Nguyen, K. T. “Robust Reverse 1-Center Problems on Trees With Interval Costs”; Optim. Methods Softw. 2024, 39, 1383-1406. DOI: 10.1080/10556788.2024. 912345
[19] Tayyebi, J.; Sepasian, A. R. “Reverse 1-Centre Problem on Trees Under Convex Piecewise-Linear Cost Function”; Optimization 2023, 72, 843-860. DOI: 10.1080/02331934. 2021.1995730
[20] Tayyebi, J.; Aman, M. “Efficient Algorithms for the Reverse Shortest Path Problem on Trees Under the Hamming Distance”; YUJOR 2017, 27, 1, 46-60. DOI: 10.2298/YJOR150624009T
[21] Abdolahzadeh, A.; Aman, M.; Tayyebi, J. “Minimum st-cut interdiction problem”; Comput. Ind. Eng. 2020, 148, 106708, DOI: 10.1016/j.cie.2020.106708
[22] Abdolahzadeh, A.; Aman, M.; Tayyebi, J. “Communication Line Protection Against Sabotages Using Dynamic Minimum Cut Interdiction”; J. Adv. Defense Sci. Technol. 2021, 12, 2, 205-215. DOR: 20.1001.1.26762935.1400.12.2.7.5 (in Persian)
[23] Tayyebi, J.; Mitra, A.; Sefair, J. A. “The Continuous Maximum Capacity Path Interdiction Problem”; Eur. J. Oper. Res. 2023, 305,1,38-52. DOI: 10.1016/j.ejor.2022.05.028
[24] Tayyebi, J.; Deaconu, A.; Bigdeli, H.; Niksirat, M. “Shortest Path Interdiction Problem With Convex Piecewise-Linear Costs”; Comput. Appl. Math. 2023, 42, 7, 309. DOI: 10.1007/s40314-023-02445-0
[25] Lozano, L.; Smith, J. C. “A Brief Overview of Interdiction and Robust Optimization”; Optimization in Large Scale Problems: Industry 4.0 and Society 5.0 Applications, 2019, 33-39. DOI: 10.1007/978-3-030-28565-4_7
[26] Gabrel, V.; Murat, C.; Thiele, A. “Recent Advances in Robust Optimization: An Overview”; Eur. J. Oper. Res. 2014, 235, 3,471-483. DOI: 10.1016/j.ejor.2013.09.036
[27] Mohammadi, A.; Tayyebi, J. “Maximum Capacity Path Interdiction Problem With Fixed Costs”; Asia-Pac. J. Oper. Res. 2019, 36, 04, 1950018. DOI: 10.1142/S0217595919500180
[28] Towle, E.; Luedtke, J. “New Solution Approaches for the Maximum-Reliability Stochastic Network Interdiction Problem”; Comput. Manag. Sci. 2018, 15, 455-477. DOI: 10.1007/s10287-018-0321-1
[29] Bigdeli, H.; Hassanpour, H.; Tayyebi, J. “Optimistic and Pessimistic Solutions of Single and Multi-Objective Matrix Games with Fuzzy Payoffs and Analysis of Some Military Cases”; J. Adv. Defense Sci. Technol. 2017, 8, 133-145. DOR: 20.1001.1.26762935.1396.8.2.5.5 (in Persian)
[30] Orlin, J. B. “Max Flows in O(nm) Time, or Better”; Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, 2013, 765-774. DOI: 10.1145/ 2488608.2488705
[31] Washburn, A.; Wood, K. “Two-Person Zero-Sum Games for Network Interdiction”; Oper. Res. 1995, 43, 243-251. DOI: 10.1287/opre.43.2.243
[32] Dehghan, H.; Bigdeli, H. “A Three-level Game Theory Model for Modeling the Defender and Attackers Considering the Deception Strategy Between Them”; J. Adv. Defense Sci. Technol. 2023, 14, 89-99. (in Persian). DOR: 20.1001.1.26762935. 1402.14.2.3.5
 
 
Journal of Advanced Defense Science & Technology
Volume 16, Issue 1 - Serial Number 59
Spring
June 2025
Pages 25-37

Files

History

  • Receive Date: 28 March 2025
  • Revise Date: 17 May 2025
  • Accept Date: 08 June 2025
  • Publish Date: 18 June 2025

Share

How to cite

Statistics