Shortest path network interdiction with incomplete information: a robust optimization approach

Elnaz Azizi () and Abbas Seifi ()
Additional contact information
Elnaz Azizi: Amirkabir University of Technology (Tehran Polytechnic)
Abbas Seifi: Amirkabir University of Technology (Tehran Polytechnic)

Annals of Operations Research, 2024, vol. 335, issue 2, No 5, 727-759

Abstract: Abstract In this paper, we consider a shortest path network interdiction problem with incomplete information and multiple levels of interdiction intensity. The evader knows the attacker’s decision on the network arcs that have been interdicted. However, the extent of damage on each arc depends on the interdiction intensity and the amount of budget spent for interdiction. We consider two cases in which the evader has incomplete information about both the intensity of attack on the interdicted arcs and the additional cost imposed for traversing those arcs. In the first case, the evader’s perception of this cost falls in an interval of uncertainty. In the second case, it is assumed that the evader estimates a relative frequency for each level of interdiction intensity. This gives rise to multiple uncertainty sets for the evader’s estimates of the additional cost. To handle the uncertainty that arises in both cases, a robust optimization approach is employed to derive the mathematical formulation of underlying bilevel optimization problem. For each case, we first take the well-known duality-based approach to reformulate the problem as a single-level model. We show that this method does not always end up with an integer solution or fails in achieving a solution within the time limit. Therefore, we develop an alternative algorithm based on the decomposition approach. Computational results show that the proposed algorithm outperforms the duality-based method to obtain the optimal solution. Last, a real case study is presented to show the applicability of the studied problem.

Keywords: Shortest path; Network interdiction; Incomplete information; Robust optimization; Illicit drug 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-023-05350-1 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:335:y:2024:i:2:d:10.1007_s10479-023-05350-1

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

DOI: 10.1007/s10479-023-05350-1

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 ().