An Approximation Algorithm for the Traveling Salesman Problem with Backhauls

DOI10.1287/opre.45.4.639zbMath0887.90173OpenAlexW2044449536MaRDI QIDQ4363764

Alain Hertz, Gilbert Laporte, Michel Gendreau

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

traveling salesmanapproximationbackhaulsworst-case performance ratioleast-cost Hamiltonian cycle

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items (13)

On residual approximation in solution extension problems ⋮ GRASP with path relinking for the symmetric Euclidean clustered traveling salesman problem ⋮ Static pickup and delivery problems: a classification scheme and survey. (With comments and rejoinder) ⋮ CLOVES: a cluster-and-search heuristic to solve the vehicle routing problem with delivery and pick-up ⋮ A general variable neighborhood search for the one-commodity pickup-and-delivery travelling salesman problem ⋮ Approximation algorithms for the min-max clustered \(k\)-traveling salesmen problems ⋮ On Residual Approximation in Solution Extension Problems ⋮ A Lagrangian relaxation-based heuristic for the vehicle routing with full container load ⋮ One-to-Many-to-One Single Vehicle Pickup and Delivery Problems ⋮ Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries ⋮ 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

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