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. Link to the article
ARCHETTI, C., BERTAZZI, L. and SPERANZA, M.G. (2003). Reoptimizing the traveling salesman problem. Networks, 42(3), pp. 154-159.
Keywords : #reoptimization-problems