An O(n log n) Heuristic for the Euclidean Traveling Salesman Problem

In this paper we present a fast approach for solving large scale Traveling Salesman Problems (TSPs). The heuristic is based on Delaunay Triangulation and its runtime is therefore bounded by O(n log n). The algorithm starts by construction the convex hull and successively replaces one edge with two new edges of the triangulation, thus inserting a new city. The decision which edge to remove is based on edge ranks. Finally the tour is subject to a node insertion improvement heuristic.
By extensive case studies it will be shown that only highly optimized 2/3-Opt heuristics are superior to this approach in both running time and tour lengths for very large TSP instances.