TY - GEN
T1 - Global strategies for augmenting the efficiency of TSP heuristics
AU - Codenotti, Bruno
AU - Manzini, Giovanni
AU - Margara, Luciano
AU - Resta, Giovanni
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1993.
PY - 1993
Y1 - 1993
N2 - In this paper we introduce two different techniques, clustering and perturbation, which use global information on TSP instances to speed-up and improve the quality of the tours found by heuristic methods. This global information is related to two correspondent features of any instance, namely distribution and sensitivity. The performance of our techniques has been tested and compared with known methods. To this end, we performed a number of experiments both on test instances, for which the optimal tour length is known, and on uniformly distributed instances, for which the comparison is done with the Held-Karp lower bound. The experimental results show that our techniques are competitive with the most efficient known methods. It turns out that the viewpoint used in this paper is very satisfactory and deserves further examination.
AB - In this paper we introduce two different techniques, clustering and perturbation, which use global information on TSP instances to speed-up and improve the quality of the tours found by heuristic methods. This global information is related to two correspondent features of any instance, namely distribution and sensitivity. The performance of our techniques has been tested and compared with known methods. To this end, we performed a number of experiments both on test instances, for which the optimal tour length is known, and on uniformly distributed instances, for which the comparison is done with the Held-Karp lower bound. The experimental results show that our techniques are competitive with the most efficient known methods. It turns out that the viewpoint used in this paper is very satisfactory and deserves further examination.
UR - http://www.scopus.com/inward/record.url?scp=21144475957&partnerID=8YFLogxK
U2 - 10.1007/3-540-57155-8_253
DO - 10.1007/3-540-57155-8_253
M3 - Conference contribution
AN - SCOPUS:21144475957
SN - 9783540571551
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 253
EP - 264
BT - Algorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings
A2 - Dehne, Frank
A2 - Sack, Jorg-Rudiger
A2 - Santoro, Nicola
A2 - Whitesides, Sue
PB - Springer Verlag
T2 - 3rd Workshop on Algorithms and Data Structures, WADS 1993
Y2 - 11 August 1993 through 13 August 1993
ER -