Network Interdiction: Emerging Research Topics and Progress

doi:10.12005/orms.2022.0019

Abstract

Abstract: Network interdiction, improving the traditional network optimization theory by further considering game problems in network optimization, has gradually become an academic research frontier. This paper reviews the literature on network interdiction from four aspects:model construction, solution algorithms, application and innovations. Furthermore, it also points out current research limitations, suggests more research efforts on potential hot topics, and emphasizes the necessity and importance of certain research areas.

Key words: network optimization, network interdiction, literature review

摘要： 网络阻断(Network Interdiction)研究弥补了传统网络优化理论的不足,进阶地考虑了网络优化中的各类博弈问题,也因其广泛的应用价值而发展成为学术研究的国际前沿领域。针对网络阻断相关研究文献进行综述,从模型构建、求解算法、应用情境和创新点视角方面全面分析了该领域研究的现状和发展脉络,指出当今的研究空白,提出潜在的研究热点问题,并分析了相关领域研究的必要性和迫切性。

关键词: 网络优化, 网络阻断, 文献综述

CLC Number:

O225
F224.32

XIANG Yin. Network Interdiction: Emerging Research Topics and Progress[J]. Operations Research and Management Science, 2022, 31(1): 128-134.

项寅. 网络阻断问题研究热点及发展方向[J]. 运筹与管理, 2022, 31(1): 128-134.

References

[1] 谢凡荣,贾仁安.网络流优化高效智能算法及其应用[M].北京:科学出版社,2015.1-3.
[2] Wood R K. Deterministic network interdiction[J]. Mathematical & Computer Modelling, 1993, 17(17): 1-18
[3] Israeli E, Wood R K. Shortest-path network interdiction[J]. Networks, 2002, 40(40): 97-111
[4] Scaparra M P, Church R L. A bilevel mixed-integer program for critical infrastructure protection planning[J]. Computers & Operations Research, 2008, 35(6): 1905-1923.
[5] Kheirkhah A, Navidi H R, Bidgoli M M. A bi-level network interdiction model for solving the hazmat routing problem[J]. International Journal of Production Research , 2015, 54(2): 1-13.
[6] Bailey M D, Shechter S M, Schaefer A J. SPAR stochastic programming with adversarial recourse[J]. Operation research letters, 2006, 34(3): 307-315.
[7] Assimakopoulos N. A network interdiction model for hospital infection control[J]. Computers in Biology & Medicine, 1987, 17(6): 413.
[8] Zhang J, Zhuang J, Behlendorf B. Stochastic shortest path network interdiction with a case study of arizona-mexico border[J]. Reliability Engineering & System Safety, 2018, on-line.
[9] Wein L M, Liu Y. Analyzing a bioterror attack on the food supply the case of botulinum toxin in milk[J]. Proceedings of the National Academy of Science, 2005, 102(28): 9984-9.
[10] Brown G, Carlyle M, Salmerón J, Wood K. Defending critical infrastructure[J]. Interfaces, 2006, 36(6): 530-544.
[11] Ghaffarinasab N, Atayi R. An implicit enumeration algorithm for the hub interdiction median problem with fortification[J]. European Journal of Operational Research, 2018, on-line
[12] Cormican K J, Morton D P, Wood R K. Stochastic network interdiction[J]. Operations Research, 1998, 46(2): 184-197.
[13] Jeong D. Allocating security resources to a water supply network[J]. IIE Transactions, 2007, 39(1): 95-109.
[14] Royset J O, Wood R K. Solving the bi-objective maximum-flow network-interdiction problem[J]. Informs Journal on Computing, 2007, 19(2): 175-184.
[15] Janjarassuk U, Linderoth J. Reformulation and sampling to solve a stochastic network interdiction problem[J]. Networks, 2008, 52(3): 120-132.
[16] Lunday B J, Sherali H D. A dynamic network interdiction problem[J]. Informatica, 2010, 21(4): 553-574.
[17] Akgüna I, Tansel B C, Wood R K. The multi-terminal maximum-flow network-interdiction problem[J]. European Journal of Operational Research, 2011, 211(2): 241-251.
[18] Afshari M R, Kakhki H T. Maximum dynamic network flow interdiction problem New formulationand solution procedures[J]. Computers & Industrial Engineering, 2013, 65(4): 531-536.
[19] Sullivan K M, Smith J C. Exact algorithms for solving a euclidean maximum flow network interdiction problem[J]. Networks, 2015, 64(2): 109-124.
[20] Bertsimas D, Nasrabadi E, Orlin J B. On the power of randomization in network interdiction[J]. Operations Research Letters, 2016, 44(1): 114-120.
[21] Rad M A, Kakhki H T. Two extended formulations for cardinality maximum flow network interdiction problem[J]. Networks, 2017, 69(4): 367-377.
[22] Lei X, Shen S, Song Y. Stochastic maximum flow interdiction problems under heterogeneous risk preferences[J]. Computers & Operations Research, 2018, 90: 97-109.
[23] Jiang J, Liu X. Multi-objective stackelberg game model for water supply networks against interdictions with incomplete information[J]. European Journal of Operational Research, 2018, 266(3): 920-933.
[24] 李引珍,郭耀煌.交通运输网络最短路径关键边问题研究[J].中国管理科学,2004,12(4):69-73.
[25] 闫化海,徐寅峰,刘明.不确定情形下通信网络最短路径关键点问题[J].系统工程,2006,24(9):1-5.
[26] 闫化海,徐寅峰.不完全信息下交通网络最短路径关键边问题[J].系统工程,2006,24(2):37-40.
[27] Bayrak H, Matthew D B M D. Shortest path network interdiction with asymmetric information[J]. Networks, 2008, 52(3): 133-140.
[28] Brown G G, Carlyle W M, Harney R C, et.al. Interdicting a nuclear-weapons project[J]. Operations Research, 2009, 57(4): 866-877.
[29] Claudio M R S. Marquez J E. a bi-objective approach for shortest-path network interdiction[J]. Computers & Industrial Engineering, 2010, 59(2): 232-240.
[30] Cappanera P, Scaparra M P. Optimal allocation of protective resources in shortest-path networks[J]. Transportation Science, 2011, 45(1): 64-80.
[31] Ertem M. A Stochastic network interdiction model for cyber security[D]. University Of Wisconsin, 2014.
[32] Gutin E, Kuhn D, Wiesemann W. Interdiction games on markovian PERT networks[J]. Management Science, 2015, 61(5): 999-1017.
[33] Sefair J A, Smith J C. Dynamic shortest-path interdiction[J]. Networks, 2016, 68(4): 315-330.
[34] Song Y, Shen S. Risk-averse shortest path interdiction[J]. Informs Journal on Computing, 2016, 28(3): 527-539.
[35] Borrero J S, Prokopyev O A, SauréD. Sequential shortest path interdiction with incomplete information[J]. Decision Analysis , 2016, 13(1): 68-98.
[36] Sadeghi S, Seifi A, Azizi E. Tri-level shortest path network interdiction with partial fortification[J]. Computers & Industrial Engineering, 2017, 106: 400-411.
[37] Church R L, Scaparra M P, Middleton R S. Identifying critical infrastructure: the median and covering facility interdiction problems[J]. Annals of the Association of American Geograph, 2004, 94(3): 491-502.
[38] 杨珺,张敏,王世伟.基于P-中位模型的网络关键设施识别问题的算法设计与实现[J].管理科学,2008,21(4):46-53.
[39] Losada C, Scaparra M P, Church R L. Interdiction of p-median systems with facility recovery time and frequent disruptions: a resiliency analysis[J]. Ann AAG 2010.
[40] Hanleyab J R, Church R L. Designing robust coverage networks to hedge against worst-case facility losses[J]. European Journal of Operational Research, 2011, 209, (1): 23-36.
[41] 杨珺,刘舒佶,王玲.考虑最坏中断损失下的P-中位设施选址问题的模型与算法研究[J].中国管理科学,2011,19(4):120-129.
[42] Keçici S, Aras N, Verter V. Incorporating the threat of terrorist attacks in the design of public service facility networks[J]. Optimization Letters , 2012, 6(6): 1101-1121.
[43] Liberatore F, Scaparra MP, Daskin MS. Hedging against disruptions with ripple effects in location analysis[J]. Omega , 2012, 40(1): 21-30.
[44] 万晓榆,陈煜舟,付德强.中断情景下应急设施保护选址模型研究[J].中国安全科学学报,2013,23(7):98.
[45] 朱悦妮,郑征,张逍怡,等.关键基础设施防护主从对策模型及其求解算法[J].系统工程理论与实践,2014,34(6):1557-1565.
[46] Alguacil N, Delgadillo A, Arroyo J. A trilevel programming approach for electric grid defense planning[J]. Computers & Operations Research, 2014, 41(41): 282-290.
[47] Aliakbarian N, Dehghanian F, Salari M. A bi-level programming model for protection of hierarchical facilities under imminent attacks[J]. Computers & Operations Research, 2015 , 64(C): 210-224.
[48] Medal H R, Pohl E A, Rossetti M D. Allocating protection resources to facilities when the effect of protection is uncertain[J]. IEE Transactions, 2016, 48(3): 220-234.
[49] Mahmoodjanloo M, Parvasi S P, Ramezanian R. A tri-level covering fortification model for facility protectionagainstdisturbance in r-interdiction median problem[J]. Computers & Industrial Engineering, 2016, 102: 219-232.
[50] Akbari J M, Tavakkoli M R, Mahmoodjanloo M. A tri-level r-interdiction median model for a facility location problem under imminent attack[J]. Computers & Industrial Engineering, 2017, 114: 151-165.
[51] Ouyang M. A mathematical framework to optimize resilience of interdependent critical infrastructure systems under spatially localized attacks[J]. European Journal of Operational Research , 2017, 262(3): 1072-1084.
[52] Kheirkhah A S, Navidi H R, Bidgoli M M. An improved benders decomposition algorithm for an arc interdiction vehicle routing problem[J]. IEEE Transactions on Engineering Management, 2016, 63(2): 259-273.
[53] Lozano L, Smith J C, Kurz M E. Solving the traveling salesman problem with interdiction and fortification[J]. Operations Research Letters, 2017, 45(3).
[54] Bidgoli M M, Kheirkhah A S. An arc interdiction vehicle routing problem with information asymmetry[J]. Computers & Industrial Engineering, 2018, on-line.
[55] 欧阳红兵,刘晓东.中国金融机构的系统重要性及系统性风险传染机制分析——基于复杂网络的视角[J].中国管理科学,2015,23(10): 30-37.
[56] Baldacci R, Mingozzi A, Roberti R. Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints[J]. European Journal of Operational Research, 2012, 218(1): 1-6.