Publication Details
Title: Efficient Clustering Techniques for the Geometric Traveling Salesman Problem
Author: B. Codenotti and L. Margara
Group: ICSI Technical Reports
Date: June 1992
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-92-036.pdf
Overview:
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 Information:
ICSI Technical Report TR-92-036
Bibliographic Reference:
B. Codenotti and L. Margara. Efficient Clustering Techniques for the Geometric Traveling Salesman Problem. ICSI Technical Report TR-92-036, June 1992
Author: B. Codenotti and L. Margara
Group: ICSI Technical Reports
Date: June 1992
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-92-036.pdf
Overview:
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 Information:
ICSI Technical Report TR-92-036
Bibliographic Reference:
B. Codenotti and L. Margara. Efficient Clustering Techniques for the Geometric Traveling Salesman Problem. ICSI Technical Report TR-92-036, June 1992