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

Publikation: Bog/antologi/afhandling/rapportRapportForskning

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.
OriginalsprogEngelsk
Udgivelses stedRoskilde
ForlagRoskilde Universitet
Vol/bind109
Antal sider99
StatusUdgivet - 2006
NavnRoskilde Universitet. Computer Science. Computer Science Research Report
ISSN0109-9779

Citer dette

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