Dynamic shortest-path interdiction

Jorge A. Sefair, J. Cole Smith

Research output: Contribution to journalArticle

14 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)315-330
Number of pages16
JournalNetworks
Volume68
Issue number4
DOIs
StatePublished - Dec 1 2016
Externally publishedYes

Keywords

  • bounds
  • dynamic programming
  • network interdiction
  • NP-hardness
  • relaxations
  • robust optimization
  • shortest path

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Dynamic shortest-path interdiction'. Together they form a unique fingerprint.

  • Cite this