A modified scenario bundling method for shortest path network interdiction under endogenous uncertainty

Somayeh Sadeghi () and Abbas Seifi ()
Additional contact information
Somayeh Sadeghi: Amirkabir University of Technology
Abbas Seifi: Amirkabir University of Technology

Annals of Operations Research, 2024, vol. 343, issue 1, No 16, 429-457

Abstract: Abstract We consider a shortest-path network interdiction problem under endogenous uncertainty on successful detection. Endogenous uncertainty arises from the fact that the interdictor may decide to enforce surveillance on some critical arcs, which would affect the prior probability of success on those arcs. The evader decision is formulated as a two-stage stochastic programming problem. In a “here and now situation”, he has to choose the shortest path in the network before realizing detection scenarios. Then, in the second stage, the evader tries to minimize the expected cost of being detected over all possible scenarios. We consider binary scenarios to represent whether or not the evader is detected on each path and apply a linearization method to deal with the non-linearity in the decision-dependent probability measure. A decomposition method is used to solve the proposed model for a case study of a worldwide drug trafficking network. The case study is concerned with finding the most critical arcs for interdicting drug trafficking. Numerical results show that a tiny increase in the probability of opium seizures leads to a significant change in the expected cost when the critical arcs are interdicted. Due to the exponential number of scenarios, the model could not be solved in a reasonable time. Common scenario reduction methods are designed for exogenous uncertainty. We apply an improved bundling method to reduce the number of scenarios in case of endogenous uncertainty. Computational results show that our method reduces the model size and solution time tremendously without significantly affecting the objective value.

Keywords: Network interdiction; Shortest path; Endogenous uncertainty; Bender’s decomposition; Scenario bundling; Illicit trafficking (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-024-06157-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:343:y:2024:i:1:d:10.1007_s10479-024-06157-4

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-024-06157-4

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().