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

被引：559
作者：
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 [J].
BALAS, E ;
CHRISTOFIDES, N .
MATHEMATICAL PROGRAMMING, 1981, 21 (01) :19-46
[3]  
BALAS E, 1985, TRAVELING SALESMAN P, P361
[4]   PATHOLOGY OF TRAVELING-SALESMAN SUBTOUR-ELIMINATION ALGORITHMS [J].
BELLMORE, M ;
MALONE, JC .
OPERATIONS RESEARCH, 1971, 19 (02) :278-&
[5]   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
[6]   THE N-CITY TRAVELING SALESMAN PROBLEM - STATISTICAL-MECHANICS AND THE METROPOLIS ALGORITHM [J].
BONOMI, E ;
LUTTON, JL .
SIAM REVIEW, 1984, 26 (04) :551-568
[7]   NEW LOWER BOUNDS FOR THE SYMMETRIC TRAVELING SALESMAN PROBLEM [J].
CARPANETO, G ;
FISCHETTI, M ;
TOTH, P .
MATHEMATICAL PROGRAMMING, 1989, 45 (02) :233-254
[8]   SOME NEW BRANCHING AND BOUNDING CRITERIA FOR THE ASYMMETRIC TRAVELING SALESMAN PROBLEM [J].
CARPANETO, G ;
TOTH, P .
MANAGEMENT SCIENCE, 1980, 26 (07) :736-743
[9]  
CARPANETO G, 1988, FORTRAN CODES NETWOR, V13, P193
[10]   SHORTEST HAMILTONIAN CHAIN OF A GRAPH [J].
CHRISTOFIDES, N .
SIAM JOURNAL ON APPLIED MATHEMATICS, 1970, 19 (04) :689-+
123456789