An Approximation Algorithm for the Traveling Salesman Problem with Backhauls

Michel Gendreau, Gilbert Laporte and Alain Hertz
Additional contact information
Michel Gendreau: Université Montréal, Montréal, Canada
Gilbert Laporte: Université Montréal, Montréal, Canada
Alain Hertz: Ecole Polytechnique Fédérale de Lausanne, Lausanne, Switzerland

Operations Research, 1997, vol. 45, issue 4, 639-641

Abstract: The Traveling Salesman Problem with Backhauls (TSPB) is defined on a graph G = ( V , E ). The vertex set is partitioned into V = ({ v 1 }, 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.

Keywords: analysis of algorithms; combinatorial problems (search for similar items in EconPapers)
Date: 1997
References: Add references at CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.45.4.639 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:45:y:1997:i:4:p:639-641

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().