THE TRAVELING SALESMAN PROBLEM - AN OVERVIEW OF EXACT AND APPROXIMATE ALGORITHMS

被引：524

作者：

LAPORTE, G

机构：

[1] Universite de Montreal, Montreal, Canada

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 1992年 / 59卷 / 02期

关键词：

TRAVELING SALESMAN PROBLEM; SURVEY;

D O I：

10.1016/0377-2217(92)90138-Y

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this paper, some of the main known algorithms for the traveling salesman problem are surveyed. The paper is organized as follows: 1) definition; 2) applications; 3) complexity analysis; 4) exact algorithms; 5) heuristic algorithms; 6) conclusion.

引用

页码：231 / 247

页数：17

共 83 条

[1] Aho A. V., 1974, DESIGN ANAL COMPUTER, V1st
[2] A RESTRICTED LAGRANGEAN APPROACH TO THE TRAVELING SALESMAN PROBLEM
BALAS, E
CHRISTOFIDES, N
[J]. MATHEMATICAL PROGRAMMING, 1981, 21 (01) : 19 - 46
[3] BALAS E, 1985, TRAVELING SALESMAN P, P361
[4] PATHOLOGY OF TRAVELING-SALESMAN SUBTOUR-ELIMINATION ALGORITHMS
BELLMORE, M
MALONE, JC
[J]. OPERATIONS RESEARCH, 1971, 19 (02) : 278 - &
[5] LARGE TRAVELING SALESMAN PROBLEMS ARISING FROM EXPERIMENTS IN X-RAY CRYSTALLOGRAPHY - A PRELIMINARY-REPORT ON COMPUTATION
BLAND, RG
SHALLCROSS, DF
[J]. OPERATIONS RESEARCH LETTERS, 1989, 8 (03) : 125 - 128
[6] THE N-CITY TRAVELING SALESMAN PROBLEM - STATISTICAL-MECHANICS AND THE METROPOLIS ALGORITHM
BONOMI, E
LUTTON, JL
[J]. SIAM REVIEW, 1984, 26 (04) : 551 - 568
[7] NEW LOWER BOUNDS FOR THE SYMMETRIC TRAVELING SALESMAN PROBLEM
CARPANETO, G
FISCHETTI, M
TOTH, P
[J]. MATHEMATICAL PROGRAMMING, 1989, 45 (02) : 233 - 254
[8] SOME NEW BRANCHING AND BOUNDING CRITERIA FOR THE ASYMMETRIC TRAVELING SALESMAN PROBLEM
CARPANETO, G
TOTH, P
[J]. MANAGEMENT SCIENCE, 1980, 26 (07) : 736 - 743
[9] CARPANETO G, 1988, FORTRAN CODES NETWOR, V13, P193
[10] SHORTEST HAMILTONIAN CHAIN OF A GRAPH
CHRISTOFIDES, N
[J]. SIAM JOURNAL ON APPLIED MATHEMATICS, 1970, 19 (04) : 689 - +

← 1 2 3 4 5 6 7 8 9 →