An approximation algorithm for the traveling salesman problem with backhauls

被引：23

作者：

Gendreau, M ^{[1
]}

Laporte, G ^{[1
]}

Hertz, A ^{[1
]}

机构：

[1] ECOLE POLYTECH FED LAUSANNE, LAUSANNE, SWITZERLAND

来源：

OPERATIONS RESEARCH | 1997年 / 45卷 / 04期

关键词：

D O I：

10.1287/opre.45.4.639

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

The Traveling Salesman Problem with Backhauls (TSPB) is defined on a graph G = (V, E). The vertex set is partitioned into V = ({v(2)}, L, B), where v(1) is a depot, L. is a set of linehaul customers, and B is a set of backhaul customers. A cost matrix satisfying the triangle inequality is defined on the edge set E. The TSPB consists of determining a least-cost Hamiltonian cycle on G such that all vertices of L are visited contiguously after v(1), followed by all vertices of B. Following a result by Christofides for the Traveling Salesman Problem, we propose an approximation algorithm with worst-case performance ratio of 3/2 for the TSPB.

引用

页码：639 / 641

页数：3

共 16 条

[1] APPROXIMATING THE TREE AND TOUR COVERS OF A GRAPH [J].

ARKIN, EM ;

HALLDORSSON, MM ;

HASSIN, R .

INFORMATION PROCESSING LETTERS, 1993, 47 (06) :275-282

[2]

Casco DO, 1988, Vehicle Routing: Methods and Studies, V16, P127

[3]

Chisman J. A., 1975, Computers & Operations Research, V2, P115, DOI 10.1016/0305-0548(75)90015-5

[4]

Christofides N., 1976, P S NEW DIR REC RES

[5] TIGHT BOUNDS FOR CHRISTOFIDES TRAVELING SALESMAN HEURISTIC [J].

CORNUEJOLS, G ;

NEMHAUSER, GL .

MATHEMATICAL PROGRAMMING, 1978, 14 (01) :116-121

[6]

Deif I., 1984, P BABS C SOFTW US TR, P75

[7] APPROXIMATION ALGORITHMS FOR SOME POSTMAN PROBLEMS [J].

FREDERICKSON, GN .

JOURNAL OF THE ACM, 1979, 26 (03) :538-554

[8]

GELINAS S, 1992, G9213 EC HAUT ET COM

[9] The traveling salesman problem with backhauls [J].

Gendreau, M ;

Hertz, A ;

Laporte, G .

COMPUTERS & OPERATIONS RESEARCH, 1996, 23 (05) :501-508

[10]

GENDREAU M, 1996, COMBINATORIAL OPTIMI, V1, P41

← 1 2 →