L. Häme, E. Hyytiä and H. Hakula, The Traveling Salesman Problem with Differential Neighborhoods, in European Workshop on Computational Geometry (EuroCG), 2011, Morschach, Switzerland.
Abstract: 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 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.
Links:
BibTeX entry:
@inproceedings{hame-eurocg-2011,
title = {The Traveling Salesman Problem with Differential Neighborhoods},
author = {Lauri H{\"a}me and Esa Hyyti{\"a} and Harri Hakula},
booktitle = {European Workshop on Computational Geometry ({EuroCG})},
month = {Mar.},
year = {2011},
address = {Morschach, Switzerland},
}