Premium
Reoptimizing the traveling salesman problem
Author(s) -
Archetti Claudia,
Bertazzi Luca,
Speranza M. Grazia
Publication year - 2003
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.10091
Subject(s) - travelling salesman problem , node (physics) , heuristic , mathematical optimization , constant (computer programming) , computer science , mathematics , combinatorics , engineering , structural engineering , programming language
In this paper, we study the reoptimization problems which arise when a new node is added to an optimal solution of a traveling salesman problem (TSP) instance or when a node is removed. We show that both reoptimization problems are NP‐hard. Moreover, we show that, while the cheapest insertion heuristic has a tight worst‐case ratio equal to 2 when applied to a TSP instance, it guarantees, in linear time, a tight worst‐case ratio equal to 3/2 when used to add the new node and that also the simplest heuristic to remove a node from the optimal tour guarantees a tight ratio equal to 3/2 in constant time. © 2003 Wiley Periodicals, Inc.