PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Baraglia R., Hidalgo J. I., Perego R. A Hybrid Heuristic for the Traveling Salesman Problem. 2001.
 
 
Abstract
(English)
The combination of genetic and local search heuristics has been shown to be an effective approach to solving the traveling salesman problem (TSP). This paper describes a new hybrid algorithm that exploits a compact genetic algorithm in order to generate high-quality tours, which are then refined by means of the Lin–Kernighan (LK) local search. Local optima found by the LK local search are in turn exploited by the evolutionary part of the algorithm in order to improve the quality of its simulated population. The results of several experiments conducted on different TSP instances with up to 13 509 cities show the efficacy of the symbiosis between the two heuristics
Subject Compact genetic algorithms
hybrid GA
Lin–Kernighan algorithm, TSP


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