An effective implementation of the Lin–Kernighan traveling salesman heuristic

An effective implementation of the Lin–Kernighan traveling salesman heuristic

0.00 Avg rating0 Votes
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:
Keywords: heuristics
Abstract:

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).

Reviews

Required fields are marked *. Your email address will not be published.