AN APPROXIMATION ALGORITHM FOR THE TRAVELING SALESMAN PROBLEM WITH BACKHAULS

The Traveling Salesman Problem with Backhauls (TSPB) is defined on a g raph 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 ineq uality 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 vi sited contiguously after v(1), followed by all vertices of B. Followin g a result by Christofides for the Traveling Salesman Problem, we prop ose an approximation algorithm with worst-case performance ratio of 3/ 2 for the TSPB.