An approximation algorithm for the traveling salesman problem with backhauls

An approximation algorithm for the traveling salesman problem with backhauls

0.00 Avg rating0 Votes
Article ID: iaor20003810
Country: United States
Volume: 45
Issue: 4
Start Page Number: 639
End Page Number: 641
Publication Date: Jul 1997
Journal: Operations Research
Authors: , ,
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.