We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Shortest path network interdiction with incomplete information: a robust optimization approach.
- Authors
Azizi, Elnaz; Seifi, Abbas
- 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.
- Subjects
ROBUST optimization; BILEVEL programming; COST estimates; DRUGS of abuse; DRUG traffic
- Publication
Annals of Operations Research, 2024, Vol 335, Issue 2, p727
- ISSN
0254-5330
- Publication type
Article
- DOI
10.1007/s10479-023-05350-1