General k-opt submoves for the Lin-Kernighan TSP heuristic

被引：240

作者：

Helsgaun K. ^{[1
]}

机构：

[1] Department of Communication, Business and Information Technologies, Roskilde University

来源：

Mathematical Programming Computation | 2009年 / 1卷 / 2-3期

关键词：

K-opt; Lin-Kernighan; Traveling salesman problem; TSP;

D O I：

10.1007/s12532-009-0004-6

中图分类号：

学科分类号：

摘要：

Local search with k-exchange neighborhoods, k-opt, is the most widely used heuristic method for the traveling salesman problem (TSP). This paper presents an effective implementation of k-opt in LKH-2, a variant of the Lin-Kernighan TSP heuristic. The effectiveness of the implementation is demonstrated with experiments on Euclidean instances ranging from 10,000 to 10,000,000 cities. The runtime of the method increases almost linearly with the problem size. LKH-2 is free of charge for academic and non-commercial use and can be downloaded in source code. © Springer and Mathematical Programming Society 2009.

引用

页码：119 / 163

页数：44

共 34 条

[1]

Applegate D., Bixby R., Chvatal V., Cook W., Concorde: A code for solving traveling salesman problems, (1999)

[2]

Applegate D., Bixby R., Chvatal V., Cook W., Finding tours in the TSP, Technical Report 99885, (1999)

[3]

Applegate D., Bixby R., Chvatal V., Cook W., Implementing the Dantzig-Fulkerson-Johnson algorithm for large traveling salesman problems, Math. Prog., 97, pp. 91-153, (2003)

[4]

Applegate D., Cook W., Rohe A., Chained Lin-Kernighan for large traveling salesman problems, INFORMS J. Comput., 15, pp. 82-92, (2003)

[5]

Bergeron A., A very elementary presentation of the Hannenhalli-Pevzner theory, LNCS, 2089, pp. 106-117, (2001)

[6]

Caprara A., Sorting by reversals is difficult, Proceedings of the First International Conference on Computational Molecular Biology, pp. 75-83, (1997)

[7]

Chandra B., Karloff H., Tovey C., New results on the old k-opt algorithm for the TSP, Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 150-159, (1994)

[8]

Christofides N., Eilon S., Algorithms for large-scale traveling salesman problems, Oper. Res. Quart., 23, pp. 511-518, (1972)

[9]

Fredman M.L., Johnson D.S., McGeoch L.A., Ostheimer G., Data structures for traveling salesmen, J. Algorithms, 18, 3, pp. 432-479, (1995)

[10]

Funke B., Grunert T., Irnich S., Local search for vehicle routing and scheduling problems: Review and conceptual integration, J. Heuristics, 11, pp. 267-306, (2005)

← 1 2 3 4 →