Shortest Path Network Interdiction with Incomplete Information : A Robust Optimization Approach

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 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, there are 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. In addition, we develop an alternative algorithm based on the decomposition approach. Computational results show that the proposed algorithm obtains the global optimal solution and outperforms the duality-based method. Last, a real case study is presented to show the applicability of the studied problem