The Traveling Salesman Problem with Differential Neighborhoods
Lauri Häme, Esa Hyytiä, Harri Hakula · European Workshop on Computational Geometry · 2011
We introduce a novel dierential approach to the Traveling Salesman Problem with Disk Neighborhoods (TSPDN), in which each node may be relocated within radius r from the original location in order to decrease the length of the shortest tour visiting all nodes. When r is small compared to the distance between the nodes, the optimal solution to the TSPDN is achieved by shortening the cycle corresponding to the optimal TSP tour without reordering the nodes. Looking at the shortening rate of a cycle, defined as the ratio of the decrease in tour length to r when r tends to zero, gives us an insight on how the movement of nodes can be converted into savings in tour length. We study the optimal direction for shortening and show how the shortening rate relates to the tightness of turns, number of U-turns and the distance from the origin in Euclidean, Manhattan and hyperbolic metrics, respectively.