Publication Details
Title: Perturbation: An Efficient Technique for the Solution of Very Large Instances of the Euclidean TSP
Author: B. Codenotti, G. Manzini, L. Margara, and G. Resta
Group: ICSI Technical Reports
Date: July 1993
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-035.pdf
Overview:
In this paper we introduce a technique for building efficient iterated local search procedures. This technique, that we call perturbation, uses global information on TSP instances to speed-up and improve the quality of the tours found by heuristic methods. The experimental results done on up to 100,000 cities, show that our techniques outperform the known methods for iterating local search for very large instances. Keywords: TSP, sensitivity, perturbation, heuristics, experimental evaluation
Bibliographic Information:
ICSI Technical Report TR-93-035
Bibliographic Reference:
B. Codenotti, G. Manzini, L. Margara, and G. Resta. Perturbation: An Efficient Technique for the Solution of Very Large Instances of the Euclidean TSP. ICSI Technical Report TR-93-035, July 1993
Author: B. Codenotti, G. Manzini, L. Margara, and G. Resta
Group: ICSI Technical Reports
Date: July 1993
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-035.pdf
Overview:
In this paper we introduce a technique for building efficient iterated local search procedures. This technique, that we call perturbation, uses global information on TSP instances to speed-up and improve the quality of the tours found by heuristic methods. The experimental results done on up to 100,000 cities, show that our techniques outperform the known methods for iterating local search for very large instances. Keywords: TSP, sensitivity, perturbation, heuristics, experimental evaluation
Bibliographic Information:
ICSI Technical Report TR-93-035
Bibliographic Reference:
B. Codenotti, G. Manzini, L. Margara, and G. Resta. Perturbation: An Efficient Technique for the Solution of Very Large Instances of the Euclidean TSP. ICSI Technical Report TR-93-035, July 1993