Dynamic Shortest-Path Interdiction

We study a dynamic network game between an attacker and a user. The user wishes to find a shortest path between a pair of nodes in a directed network, and the attacker seeks to interdict a subset of arcs to maximize the user's shortest-path cost. In contrast to most previous studies, the attacker can interdict arcs any time the user reaches a node in the network, and the user can respond by dynamically altering its chosen path. We assume that the attacker can interdict a limited number of arcs, and that an interdicted arc can still be traversed by the user at an increased cost. The challenge is therefore to find an optimal path (possibly repeating arcs in the network), coupled with the attacker's optimal interdiction strategy (i.e., which arcs to interdict and when to interdict them). We propose an exact exponential-state dynamic-programming algorithm for this problem, which can be reduced to a polynomial-time algorithm in the case of acyclic networks. We also develop lower and upper bounds on the optimal objective function value based on classical interdiction and robust optimization models, or based on an exact solution to variations of this problem. We examine the efficiency of our algorithms and the quality of our bounds on a set of randomly generated instances. (C) 2016 Wiley Periodicals, Inc.