Modified Greedy Delaunay Graph-Based Method for TSP Initialization

Finding an initial solution for a traveling salesman efficiently and with reasonable quality is needed both by the stateof-the-art local search and branch-and-bound optimal algorithms. Classical heuristics require O(n<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>), and their quality may be insufficient to keep the efficiency of local search algorithms high. In this paper, we present a modified greedy algorithm. It utilizes a Delaunay neighborhood graph to build initial fragments until no more connections are possible. Then it merges small fragments with other fragments. It then connects the fragments by a two-step process. First, the algorithm re-generates the graph and iterates the process until the number of fragments falls below threshold 1,000. After that, it performs a full search to connect the rest of the fragments in a greedy manner. The method achieves gaps of 2% and 17% for Dots and selected TSPLIB datasets, and gaps of 27.4% and 16.6% for Santa and World TSP when comparison is made to highly optimized solutions.