Back to Search Results
Solving the traveling salesman problem with interdiction and fortificationAuthor(s): Leonardo Lozano, J Smith, Mary Kurz
Publication Name: Operations Research Letters
Volume: 45, Issue: 3, Page Number(s): 210–216
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.