New results on the old k-opt algorithm for the traveling salesman problem

被引：56

作者：

Chandra, B ^{[1
]}

Karloff, H

Tovey, C

机构：

[1] Univ New Haven, Dept Comp Sci, W Haven, CT 06516 USA

[2] Georgia Tech, Coll Comp, Atlanta, GA 30332 USA

[3] Georgia Tech, Sch Ind & Syst Engn, Atlanta, GA 30332 USA

来源：

SIAM JOURNAL ON COMPUTING | 1999年 / 28卷 / 06期

关键词：

graph algorithms; analysis of algorithms; explicit machine computation and programs; (in optimization heading); explicit machine computation and programs (in computer science heading);

D O I：

10.1137/S0097539793251244

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Local search with k-change neighborhoods is perhaps the oldest and most widely used heuristic method for the traveling salesman problem, yet almost no theoretical performance guarantees for it were previously known. This paper develops several results, some worst-case and some probabilistic, on the performance of 2- and k-opt local search for the traveling salesman problem, with respect to both the quality of the solution and the speed with which it is obtained.

引用

页码：1998 / 2029

页数：32

共 17 条

[1]

Alon N., 1992, Proceedings of the Eighth Annual Symposium on Computational Geometry, P337, DOI 10.1145/142675.142744

[2]

BENTLE JL, 1990, 1 SIAM S DISCR ALG S

[3]

Bentley J. L., 1980, P 18 ANN ALL C COMM, P41

[4]

Bollobas B., 1978, EXTREMAL GRAPH THEOR

[5]

Chandra B., 1992, Proceedings of the Eighth Annual Symposium on Computational Geometry, P192, DOI 10.1145/142675.142717

[6] LOCAL SEARCH AND THE LOCAL-STRUCTURE OF NP-COMPLETE PROBLEMS [J].

GROVER, LK .

OPERATIONS RESEARCH LETTERS, 1992, 12 (04) :235-243

[7] HOW EASY IS LOCAL SEARCH [J].

JOHNSON, DS ;

PAPADIMITRIOU, CH ;

YANNAKAKIS, M .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1988, 37 (01) :79-100

[8]

Karp RM, 1985, The traveling salesman problem: a guided tour of combinatorial optimization, P181

[9] A PROBABILISTIC ANALYSIS OF THE SWITCHING ALGORITHM FOR THE EUCLIDEAN TSP [J].

KERN, W .

MATHEMATICAL PROGRAMMING, 1989, 44 (02) :213-219

[10]

Krentel M. W., 1989, P 30 ANN S FDN COMP, P216

← 1 2 →