Robust location of hidden interdictions on a shortest path network

We study a version of the shortest path network interdiction problem in which the follower seeks a path of minimum length on a network and the leader seeks to maximize the follower’s path length by interdicting arcs. We consider placement of interdictions that are not visible to the follower; however, we seek to locate interdictions in a manner that is robust against the possibility that some information about the interdictions becomes known to the follower. We formulate the problem as a bilevel program and derive some properties of the inner problem, which enables solving the problem optimally via a Benders decomposition approach. We derive supervalid inequalities to improve the performance of the algorithm and test the performance of the algorithm on randomly generated, varying-sized grid networks and acyclic networks. We apply our approach to investigate the tradeoffs between conservative (i.e., the follower discovers all interdiction locations) and risky (i.e., the follower discovers no interdiction locations) assumptions regarding the leader’s information advantage.