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

Research output: Book/ReportReportResearch

Abstract

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
Volume109
Number of pages99
Publication statusPublished - 2006
SeriesRoskilde Universitet. Computer Science. Computer Science Research Report
ISSN0109-9779

Cite this

Helsgaun, K. (2006). An Effective Implementation of K-opt Moves for the Lin-Kernighan TSP Heuristic. Roskilde: Roskilde Universitet. Roskilde Universitet. Computer Science. Computer Science Research Report