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.
| Original language | English |
|---|
| Place of Publication | Roskilde |
|---|---|
| Publisher | Roskilde Universitet |
| Volume | 109 |
| Number of pages | 99 |
| Publication status | Published - 2006 |
| Series | Roskilde Universitet. Computer Science. Computer Science Research Report |
|---|---|
| ISSN | 0109-9779 |