An effective implementation of the Lin-Kernighan traveling salesman heuristic

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 (TSP). 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). (C) 2000 Elsevier Science B.V. All rights reserved.