DocumentCode
1557917
Title
A hybrid heuristic for the traveling salesman problem
Author
Baraglia, R. ; Hidalgo, J.I. ; Perego, R.
Author_Institution
Ist. CNUCE, CNR, Pisa, Italy
Volume
5
Issue
6
fYear
2001
fDate
12/1/2001 12:00:00 AM
Firstpage
613
Lastpage
622
Abstract
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. The 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
Keywords
genetic algorithms; search problems; travelling salesman problems; Lin-Kernighan algorithm; compact genetic algorithms; heuristics; local search; traveling salesman problem; Cities and towns; Genetic algorithms; Helium; Heuristic algorithms; Hybrid power systems; Optimization methods; Symbiosis; Taxonomy; Testing; Traveling salesman problems;
fLanguage
English
Journal_Title
Evolutionary Computation, IEEE Transactions on
Publisher
ieee
ISSN
1089-778X
Type
jour
DOI
10.1109/4235.974843
Filename
974843
Link To Document