Global strategies for augmenting the efficiency of TSP heuristics

Bruno Codenotti, Giovanni Manzini, Luciano Margara, Giovanni Resta

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

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.

Original languageEnglish
Title of host publicationAlgorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings
EditorsFrank Dehne, Jorg-Rudiger Sack, Nicola Santoro, Sue Whitesides
PublisherSpringer Verlag
Pages253-264
Number of pages12
ISBN (Print)9783540571551
DOIs
Publication statusPublished - 1993
Externally publishedYes
Event3rd Workshop on Algorithms and Data Structures, WADS 1993 - Montreal, Canada
Duration: 11 Aug 199313 Aug 1993

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume709 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference3rd Workshop on Algorithms and Data Structures, WADS 1993
Country/TerritoryCanada
CityMontreal
Period11/08/9313/08/93

Fingerprint

Dive into the research topics of 'Global strategies for augmenting the efficiency of TSP heuristics'. Together they form a unique fingerprint.

Cite this