Solving the traveling salesman problem with interdiction and fortification

Leonardo Lozano, J. Cole Smith, Mary E. Kurz

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

We solve a defender-attacker-defender problem over a traveling salesman problem (TSP), in which the defender first acts to defend a subset of arcs, the attacker then interdicts a subset of undefended arcs (thus increasing their costs), and the defender solves a TSP over the remaining network. Our approach employs an exact approach augmented with a TSP restriction phase to accelerate the convergence of the algorithm. Our computational results show success for the first time in optimally solving defender-attacker-defender TSP problems.

Original languageEnglish (US)
Pages (from-to)210-216
Number of pages7
JournalOperations Research Letters
Volume45
Issue number3
DOIs
StatePublished - May 1 2017
Externally publishedYes

Keywords

  • Integer programming
  • Interdiction
  • Traveling salesman problem

ASJC Scopus subject areas

  • Software
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Solving the traveling salesman problem with interdiction and fortification'. Together they form a unique fingerprint.

Cite this