An Effective Implementation of K-opt Moves for the Lin-Kernighan TSP Heuristic

Research output: Book/ReportReportResearch


Local search with k-change neighborhoods, k-opt, is the most widely
used heuristic method for the traveling salesman problem (TSP). This
report presents an effective implementation of k-opt for the Lin-
Kernighan TSP heuristic. The effectiveness of the implementation is
demonstrated with extensive experiments on instances ranging from
10,000 to 10,000,000 cities.
Original languageEnglish
Place of PublicationRoskilde
PublisherRoskilde Universitet
Number of pages99
Publication statusPublished - 2006
SeriesRoskilde Universitet. Computer Science. Computer Science Research Report

Cite this