Two-stage nodal network interdiction under decision-dependent uncertainty

被引:0
作者
Digehsara, Amin Ahmadi [1 ]
Ardestani-Jaafari, Amir [1 ]
Mazahir, Shumail [2 ]
Fathi, Michel [3 ]
机构
[1] Univ British Columbia, Fac Management, 1137 Alumni Ave, Kelowna, BC V1V 1V7, Canada
[2] Univ Cote Azur, SKEMA Business Sch, Ave Willy Brandt, F-59777 Euralille, France
[3] Univ North Texas, G Brint Ryan Coll Business, 1155 Union Circle 311160, Denton, TX 76203 USA
关键词
Network interdiction; Decision-dependent uncertainty; Robust optimization; ROBUST OPTIMIZATION; VULNERABILITY; RESILIENCE; PROTECTION; SUBJECT; DEFENSE; ATTACK; ARCS;
D O I
10.1007/s10479-023-05630-w
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
Infrastructures such as power stations, water systems, railways, highways, subway stations, and roads play an important role in ensuring that the network operates safely and effectively. In this study, we aim to develop a fortification plan to protect the nodes and links from destructive attacks. However, there is often a degree of uncertainty concerning the exact location or degree of the attack. To address this problem, we suggest a trilevel robust shortesth path problem based on the defender-attacker-defender model. In this model, the primary defender provides protection plan against attacks, while the attacker identifies weaknesses and attacks non-fortified components. Lastly, the inner defender determines the shortest path between the source and sink of the interdicted network. To solve the problem efficiently, we resort to a column-and-constraint generation algorithm. Several benchmark examples from the literature are used to demonstrate the effectiveness of our model. Despite the inherent complexity of the problem, we demonstrate that using careful analysis of worst-case attack scenarios, we can develop a successful fortification plan within a reasonable computational time.
引用
收藏
页码:665 / 687
页数:23
相关论文
共 56 条
  • [1] The Maximum Flow Network Interdiction Problem: Valid inequalities, integrality gaps, and approximability
    Altner, Douglas S.
    Ergun, Oezlem
    Uhan, Nelson A.
    [J]. OPERATIONS RESEARCH LETTERS, 2010, 38 (01) : 33 - 38
  • [2] Robust Minimum-Cost Flow Problems Under Multiple Ripple Effect Disruptions
    Ansari, Mehdi
    Borrero, Juan S.
    Lozano, Leonardo
    [J]. INFORMS JOURNAL ON COMPUTING, 2023, 35 (01) : 83 - 103
  • [3] Azaiez MN, 2009, INT SER OPER RES MAN, V128, P99
  • [4] Shortest path network interdiction with asymmetric information
    Bayrak, Halil
    Bailey, Matthew D.
    [J]. NETWORKS, 2008, 52 (03) : 133 - 140
  • [5] A survey on bilevel optimization under uncertainty
    Beck, Yasmine
    Ljubi, Ivana
    Schmidt, Martin
    [J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2023, 311 (02) : 401 - 426
  • [6] On a Computationally Ill-Behaved Bilevel Problem with a Continuous and Nonconvex Lower Level
    Beck, Yasmine
    Bienstock, Daniel
    Schmidt, Martin
    Thuerauf, Johannes
    [J]. JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 2023, 198 (01) : 428 - 447
  • [7] The price of robustness
    Bertsimas, D
    Sim, M
    [J]. OPERATIONS RESEARCH, 2004, 52 (01) : 35 - 53
  • [8] Risk analysis beyond vulnerability and resilience - characterizing the defensibility of critical systems
    Bier, Vicki
    Gutfraind, Alexander
    [J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2019, 276 (02) : 626 - 636
  • [9] Defending and attacking a network of two arcs subject to traffic congestion
    Bier, Vicki M.
    Hausken, Kjell
    [J]. RELIABILITY ENGINEERING & SYSTEM SAFETY, 2013, 112 : 214 - 224
  • [10] Sequential Interdiction with Incomplete Information and Learning
    Borrero, Juan S.
    Prokopyev, Oleg A.
    Saure, Denis
    [J]. OPERATIONS RESEARCH, 2019, 67 (01) : 72 - 89