Three algorithms for the Travelling Salesman Problem based on a clustering technique

This paper presents some direct and iterative heuristic methods for the geometric Travelling Salesman Problem (TSP). All these methods are based on a particular notion of mass density, which can be used to construct a tour for the geometric TSP in an incremental fashion. In the iterative method, this technique is combined with the Lin-Kernighan method (LK), and this allows better tours to be obtained than those found by using LK itself. More precisely, the tour length obtained is only 1.1% off the optimum. The direct method finds a solution passing through a sequence of subsolutions over progressively larger sets of points. These points are the relative maxima of the mass density obtained by using different parameter settings. The method has O(n³) worst case running time and finds tours whose length is 9.2% off the optimal one.