The Traveling Salesman Problem with Differential Neighborhoods

We introduce a novel differential 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 com-pared to the distance between the nodes, the optimal so-lution 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, de-fined 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.