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.
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.
Originalsprog | Engelsk |
---|
Udgivelsessted | Roskilde |
---|---|
Forlag | Roskilde Universitet |
Vol/bind | 109 |
Antal sider | 99 |
Status | Udgivet - 2006 |
Navn | Roskilde Universitet. Computer Science. Computer Science Research Report |
---|---|
ISSN | 0109-9779 |