Reoptimizing the traveling salesman problem

Reoptimizing the traveling salesman problem

0.00 Avg rating0 Votes
Article ID: iaor20041854
Country: United States
Volume: 42
Issue: 3
Start Page Number: 154
End Page Number: 159
Publication Date: Oct 2003
Journal: Networks
Authors: , ,
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.