NEW INSERTION AND POSTOPTIMIZATION PROCEDURES FOR THE TRAVELING SALESMAN PROBLEM

被引：311

作者：

GENDREAU, M

HERTZ, A

LAPORTE, G

机构：

[1] UNIV MONTREAL,MONTREAL H3C 3J7,QUEBEC,CANADA

[2] ECOLE POLYTECH FED LAUSANNE,CH-1007 LAUSANNE,SWITZERLAND

来源：

OPERATIONS RESEARCH | 1992年 / 40卷 / 06期

关键词：

D O I：

10.1287/opre.40.6.1086

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

This paper describes a new insertion procedure and a new postoptimization routine for the traveling salesman problem. The combination of the two methods results in an efficient algorithm (GENIUS) which outperforms known alternative heuristics in terms of solution quality and computing time.

引用

收藏

页码：1086 / 1094

页数：9

相关论文

共 28 条

[1] HEURISTICS BASED ON SPACEFILLING CURVES FOR COMBINATORIAL PROBLEMS IN EUCLIDEAN-SPACE [J].

BARTHOLDI, JJ ;

PLATZMAN, LK .

MANAGEMENT SCIENCE, 1988, 34 (03) :291-305

[2] LARGE TRAVELING SALESMAN PROBLEMS ARISING FROM EXPERIMENTS IN X-RAY CRYSTALLOGRAPHY - A PRELIMINARY-REPORT ON COMPUTATION [J].

BLAND, RG ;

SHALLCROSS, DF .

OPERATIONS RESEARCH LETTERS, 1989, 8 (03) :125-128

[3] THERMODYNAMICAL APPROACH TO THE TRAVELING SALESMAN PROBLEM - AN EFFICIENT SIMULATION ALGORITHM [J].

CERNY, V .

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 1985, 45 (01) :41-51

[4]

CHAUNY F, 1987, INFOR, V25, P26

[5] SOLVING LARGE-SCALE SYMMETRIC TRAVELING SALESMAN PROBLEMS TO OPTIMALITY [J].

CROWDER, H ;

PADBERG, MW .

MANAGEMENT SCIENCE, 1980, 26 (05) :495-509

[6]

FIECHTER CN, 1990, 901 EC POL FED LAUS

[7]

Glover F., 1977, DECIS SCI, V8, P156, DOI [10.1111/j.1540-5915.1977.tb01074.x, DOI 10.1111/J.1540-5915.1977.TB01074.X]

[8]

Golden BL, 1985, TRAVELING SALESMAN P, P207

[9] VIA MINIMIZATION WITH PIN PREASSIGNMENTS AND LAYER PREFERENCE [J].

GROTSCHEL, M ;

JUNGER, M ;

REINELT, G .

ZEITSCHRIFT FUR ANGEWANDTE MATHEMATIK UND MECHANIK, 1989, 69 (11) :393-399

[10] OPTIMIZATION BY SIMULATED ANNEALING [J].

KIRKPATRICK, S ;

GELATT, CD ;

VECCHI, MP .

SCIENCE, 1983, 220 (4598) :671-680