Istituto di Scienza e Tecnologie dell'Informazione     
Codenotti B., Manzini G., Margara L., Resta G. Global strategies for augmenting the efficiency of TSP heuristics. In: WADS'93 - 3rd Workshop on Algorithms and Data Structures (Montreal, Canada, August 1993). Proceedings, pp. 253 - 264. F. Dehne, J.R. Sack, N. Santoro, S. Whitesides (eds.). (Lecture Notes in Computer S cience, vol. 709). Springer, 1993.
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.

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional