Codenotti, Bruno; Manzini, Giovanni; Margara, Luciano; Resta, Giovanni Perturbation: An efficient technique for the solution of very large instances of the Euclidean TSP. (English) Zbl 0866.90130 INFORMS J. Comput. 8, No. 2, 125-133 (1996). Summary: We introduce a technique for developing efficient iterated local search procedures and we apply it to solve very large instances of the Euclidean traveling salesman problem (TSP). This technique, which we call perturbation, uses global information on TSP instances to speed-up the computation and to improve the quality of the tours found by heuristic methods. The main idea is to escape from local optima by introducing perturbations in the problem instance rather than in the solution. The performance of our algorithms has been tested and compared with known methods. To this end, we have executed a number of experiments both on available benchmarks, for which the optimal tour length is known, and on randomly generated instances, for which the comparison is done with the Held-Karp lower bound. The experimental results, performed on up to 100,000 cities, show that our algorithms outperform the known methods for iterating local search for very large instances. Cited in 12 Documents MSC: 90C35 Programming involving graphs or networks 90C06 Large-scale problems in mathematical programming Keywords:Euclidean traveling salesman problem; perturbation PDFBibTeX XMLCite \textit{B. Codenotti} et al., INFORMS J. Comput. 8, No. 2, 125--133 (1996; Zbl 0866.90130) Full Text: DOI Link