An approximation algorithm for the traveling salesman problem with backhauls
成果类型：
Article
署名作者：
Gendreau, M; Laporte, G; Hertz, A
署名单位：
Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.45.4.639
发表日期：
1997
页码：
639-641
关键词：
摘要：
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.