Improvements to the Or-opt heuristic for the symmetric travelling salesman problem

被引：29

作者：

Babin, G. ^{[1
]}

Deneault, S. ^{[1
]}

Laporte, G. ^{[1
]}

机构：

[1] HEC Montreal, Informat Technol, Montreal, PQ H3T 2A7, Canada

来源：

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY | 2007年 / 58卷 / 03期

基金：

加拿大自然科学与工程研究理事会;

关键词：

symmetric travelling salesman problem; local search heuristics; edge and chain exchanges;

D O I：

10.1057/palgrave.jors.2602160

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

Several variants and generalizations of the Or-opt heuristic for the Symmetric Travelling Salesman Problem are developed and compared on random and planar instances. Some of the proposed algorithms are shown to significantly improve upon the standard 2-opt and Or-opt heuristics.

引用

页码：402 / 407

页数：6

共 16 条

[1] Implementing the Dantzig-Fulkerson-Johnson algorithm for large traveling salesman problems [J].

Applegate, D ;

Bixby, R ;

Chvátal, V ;

Cook, W .

MATHEMATICAL PROGRAMMING, 2003, 97 (1-2) :91-153

[2]

Bentley J. L., 1992, ORSA Journal on Computing, V4, P387, DOI 10.1287/ijoc.4.4.387

[3] A METHOD FOR SOLVING TRAVELING-SALESMAN PROBLEMS [J].

CROES, GA .

OPERATIONS RESEARCH, 1958, 6 (06) :791-812

[4] SOLUTION OF A LARGE-SCALE TRAVELING-SALESMAN PROBLEM [J].

DANTZIG, G ;

FULKERSON, R ;

JOHNSON, S .

JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF AMERICA, 1954, 2 (04) :393-410

[5]

Golden BL, 1985, TRAVELING SALESMAN P, P207

[6]

Gutin G., 2002, TRAVELING SALESMAN P

[7] First vs. best improvement: An empirical study [J].

Hansen, P ;

Mladenovic, N .

DISCRETE APPLIED MATHEMATICS, 2006, 154 (05) :802-817

[8] An effective implementation of the Lin-Kernighan traveling salesman heuristic [J].

Helsgaun, K .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2000, 126 (01) :106-130

[9]

Johnson DS., 1997, Local search in combinatorial optimization, P215, DOI DOI 10.1108/01445150910987763

[10]

JOHNSON DS, 2002, COMB OPT (SER), V12, P445

← 1 2 →