An Approximation Algorithm for the Traveling Salesman Problem with Backhauls

DOI10.1287/OPRE.45.4.639MaRDI QIDQ4363764zbMATH OpenOpenAlexFDO

Authors Michel Gendreau, G. Laporte, Alain Hertz

Publication date 25 May 1998

Published in Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1287/opre.45.4.639

zbMATH Keywords

approximationbackhaulsleast-cost Hamiltonian cycletraveling salesmanworst-case performance ratio

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Recommendations

• The traveling salesman problem with backhauls
• The traveling salesman problem with delivery and backhauls
• 3-approximation algorithm for a two depot, heterogeneous traveling salesman problem
• An Approximation Algorithm for a Bottleneck Traveling Salesman Problem

Cited in

(17)

• Stochastic single vehicle routing with a predefined customer sequence and multiple depot returns
• A \(\frac{5}{3}\)-approximation algorithm for the clusterd traveling salesman tour and path problems
• Perturbation heuristics for the pickup and delivery traveling salesman problem
• On residual approximation in solution extension problems
• The traveling salesman problem with backhauls
• A general variable neighborhood search for the one-commodity pickup-and-delivery travelling salesman problem
• A Lagrangian relaxation-based heuristic for the vehicle routing with full container load
• Static pickup and delivery problems: a classification scheme and survey. (With comments and rejoinder)
• Approximation algorithms for the min-max clustered \(k\)-traveling salesmen problems
• On Residual Approximation in Solution Extension Problems
• GRASP with path relinking for the symmetric Euclidean clustered traveling salesman problem
• One-to-many-to-one single vehicle pickup and delivery problems
• Stow \& pick: optimizing combined stowing and picking tours in scattered storage warehouses
• A survey on the traveling salesman problem and its variants in a warehousing context
• Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries
• Better approximation algorithms for clustered TSP and subgroup planning
• CLOVES: a cluster-and-search heuristic to solve the vehicle routing problem with delivery and pick-up

This page was built for publication: An Approximation Algorithm for the Traveling Salesman Problem with Backhauls

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4363764)