Efficient Clustering Techniques for the Geometric Traveling Salesman Problem

TitleEfficient Clustering Techniques for the Geometric Traveling Salesman Problem
Publication TypeTechnical Report
Year of Publication1992
AuthorsCodenotti, B., & Margara L.
Other Numbers741

This paper presents some direct and iterative heuristic methods for the geometric Traveling 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 us to obtain better tours than those found by using LK itself. More precisely, the tour length we get 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^3) worst case running time and finds tours whose length is 9.2% off the optimal one.

Bibliographic Notes

ICSI Technical Report TR-92-036

Abbreviated Authors

B. Codenotti and L. Margara

ICSI Publication Type

Technical Report