Shortest path interdiction problem with arc improvement recourse: A multiobjective approach

Tim Holzmann, J. Cole Smith

Research output: Contribution to journalArticle

1 Scopus citations

Abstract

We consider the shortest path interdiction problem involving two agents, a leader and a follower, playing a Stackelberg game. The leader seeks to maximize the follower's minimum costs by interdicting certain arcs, thus increasing the travel time of those arcs. The follower may improve the network after the interdiction by lowering the costs of some arcs, subject to a cardinality budget restriction on arc improvements. The leader and the follower are both aware of all problem data, with the exception that the leader is unaware of the follower's improvement budget. The effectiveness of an interdiction action is given by the length of a shortest path after arc costs are adjusted by both the interdiction and improvement. We propose a multiobjective optimization model for this problem, with each objective corresponding to a different possible improvement budget value. We provide mathematical optimization techniques to generate a complete set of strategies that are Pareto-optimal. Additionally, for the special case of series-parallel graphs, we provide a dynamic-programming algorithm for generating all Pareto-optimal solutions.

Original languageEnglish (US)
Pages (from-to)230-252
Number of pages23
JournalNaval Research Logistics
Volume66
Issue number3
DOIs
StatePublished - Apr 2019
Externally publishedYes

Keywords

  • dynamic programming
  • interdiction
  • mixed-integer programming
  • multiobjective optimization

ASJC Scopus subject areas

  • Modeling and Simulation
  • Ocean Engineering
  • Management Science and Operations Research

Fingerprint Dive into the research topics of 'Shortest path interdiction problem with arc improvement recourse: A multiobjective approach'. Together they form a unique fingerprint.

Cite this