An analysis of the extended Christofides heuristic for the k-depot TSP

DOI10.1016/J.ORL.2011.03.002MaRDI QIDQ635520zbMATH OpenOpenAlexFDO

Authors Zhou Xu, Liang Xu, Brian Rodrigues

Publication date 19 August 2011

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.orl.2011.03.002

zbMATH Keywords

TSPapproximation algorithmsChristofides heuristicmultiple depots

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Recommendations

• An extension of the Christofides heuristic for the generalized multiple depot multiple traveling salesmen problem
• A 3/2-approximation algorithm for the multiple TSP with a fixed number of depots
• A 3/2-Approximation Algorithm for Multiple Depot Multiple Traveling Salesman Problem
• Approximation algorithms for the \(k\)-depots Hamiltonian path problem
• 3-approximation algorithm for a two depot, heterogeneous traveling salesman problem

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A Lagrangian-based algorithm for a multiple depot, multiple traveling salesmen problem
• A tabu search heuristic for the multi-depot vehicle routing problem
• A variation of the generalized assignment problem arising in the New Zealand dairy industry
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• An approximation algorithm for a symmetric generalized multiple depot, multiple travelling salesman problem
• Approximations for minimum and min-max vehicle routing problems
• Arc Routing Problems, Part I: The Chinese Postman Problem
• Combinatorial optimization. Theory and algorithms.
• New assignment algorithms for the multi-depot vehicle routing problem
• \(\frac 32\)-approximation algorithm for two variants of a 2-depot Hamiltonian path problem

Cited in

(12)

• A new crossover approach for solving the multiple travelling salesmen problem using genetic algorithms
• A 3/2-approximation algorithm for the multiple TSP with a fixed number of depots
• Approximation algorithms for multi-vehicle stacker crane problems
• Approximating the multiple-depot multiple-terminal Hamiltonian path problem
• Approximation algorithms for the \(k\)-depots Hamiltonian path problem
• Improved approximation algorithms for multidepot capacitated vehicle routing
• An extension of the Christofides heuristic for the generalized multiple depot multiple traveling salesmen problem
• The \(m\)-Steiner traveling salesman problem with online edge blockages
• Exact and heuristic algorithms for routing AGV on path with precedence constraints
• An asymptotically tight online algorithm for \(m\)-steiner traveling salesman problem
• Local search algorithms for multiple-depot vehicle routing and for multiple traveling salesman problems with proved performance guarantees
• An extension of the Christofides heuristic for a single-depot multiple Hamiltonian path problem

This page was built for publication: An analysis of the extended Christofides heuristic for the \(k\)-depot TSP

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