Finding an initial solution for traveling salesman fast and with reasonable quality is needed both by the state-of-the-art local search and branch-and-bound optimal algorithms. Classical heuristics require O(n2) and their quality may be insufficient to keep the efficiency of the local search high. In this paper, we present two fast variants that utilize a Delaunay neighborhood graph. The best methods achieve 2.66% gap for Dots datasets, and 15.04% gap for the selected TSPLIB datasets. However, these results were obtained with slower algorithms. The best of the fast methods achieved 5.76% gap for Dots datasets, and 19.07% gap for the selected TSPLIB datasets in 307 milliseconds, on average.
|