Article ID: | iaor20012051 |
Country: | Netherlands |
Volume: | 126 |
Issue: | 1 |
Start Page Number: | 106 |
End Page Number: | 130 |
Publication Date: | Oct 2000 |
Journal: | European Journal of Operational Research |
Authors: | Helsgaun Keld |
Keywords: | heuristics |
This paper describes an implementation of the Lin–Kernighan heuristic, one of the most successful methods for generating optimal or near-optimal solutions for the symmetric traveling salesman problem. Computational tests show that the implementation is highly effective. It has found optimal solutions for all solved problem instances we have been able to obtain, including a 13,509-city problem (the largest non-trivial problem instance solved to optimality today).