This paper considers an extension of the shortest path network interdiction problem that incorporates robustness to account for parameter uncertainty. The shortest path interdiction problem is a game of two players with conflicting agendas and capabilities: an evader, who traverses the arcs of a network from a source node to a sink node using the path of shortest length, and an interdictor, who maximizes the length of the evader's shortest path by interdicting arcs on the network. It is usually assumed that the parameters defining the network are known exactly by both players. We consider the situation where the evader assumes the nominal parameter values while the interdictor uses robust optimization techniques to account for parameter uncertainty or sensor degradation. We formulate this problem as a nonlinear mixed integer trilevel program and show that it can be converted into a mixed integer linear program with a second order cone constraint. We use random geometric networks and transportation networks to perform computational studies and demonstrate the unique decision strategies that our variant produces. Solving the shortest path interdiction problem with asymmetric uncertainty protects the interdictor from investing in the obvious strategy if that strategy hinges on key interdictions performing as promised. It also provides an alternate strategy that mitigates the risk of these worst-case possibilities.
Citation
Department of Mathematical Sciences, Rensselaer Polytechnic Institute, Troy, NY, USA March 2022
Article
View Shortest Path Network Interdiction with Asymmetric Uncertainty