An approximation algorithm for a symmetric generalized multiple depot, multiple travelling salesman problem

DOI10.1016/j.orl.2007.02.001zbMath1169.90436OpenAlexW2016583826MaRDI QIDQ2467447

Sivakumar Rathinam, Swaroop Darbha, W. A. Malik

Publication date: 21 January 2008

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

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

zbMATH Keywords

vehicle routingtravelling salesmanapproximation algorithms

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Traffic problems in operations research (90B20)

Related Items

Approximation algorithms for the \(k\)-depots Hamiltonian path problem ⋮ Approximation algorithms and heuristics for a 2-depot, heterogeneous Hamiltonian path problem ⋮ A primal-dual approximation algorithm for a two depot heterogeneous traveling salesman problem ⋮ Improved algorithms for joint optimization of facility locations and network connections ⋮ Multi-depot multiple TSP: a polyhedral study and computational results ⋮ An Approximation Algorithm for the Three Depots Hamiltonian Path Problem ⋮ An extension of the Christofides heuristic for a single-depot multiple Hamiltonian path problem ⋮ A hyper-heuristic based artificial bee colony algorithm for \(k\)-interconnected multi-depot multi-traveling salesman problem ⋮ An analysis of the extended Christofides heuristic for the \(k\)-depot TSP ⋮ Local search algorithms for multiple-depot vehicle routing and for multiple traveling salesman problems with proved performance guarantees ⋮ A Lagrangian-Based Algorithm for a Combinatorial Motion Planning Problem ⋮ An extension of the Christofides heuristic for the generalized multiple depot multiple traveling salesmen problem ⋮ Approximation algorithms for multiple terminal, Hamiltonian path problems ⋮ 3-approximation algorithm for a two depot, heterogeneous traveling salesman problem ⋮ Approximating the multiple-depot multiple-terminal Hamiltonian path problem ⋮ \(\frac 32\)-approximation algorithm for two variants of a 2-depot Hamiltonian path problem ⋮ A 3/2-Approximation Algorithm for the Multiple TSP with a Fixed Number of Depots ⋮ An approximation algorithm for vehicle routing with compatibility constraints ⋮ New approximation algorithms for the heterogeneous weighted delivery problem ⋮ New approximation algorithms for the heterogeneous weighted delivery problem ⋮ The \(m\)-Steiner traveling salesman problem with online edge blockages ⋮ An asymptotically tight online algorithm for \(m\)-steiner traveling salesman problem

Uses Software

• TSPLIB

Cites Work

• Unnamed Item
• Degree-bounded minimum spanning trees
• Transformation of multidepot multisalesmen problem to the standard travelling salesman problem
• The traveling salesman. Computational solutions for RSP applications
• The traveling salesman problem and its variations
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Delegate and Conquer: An LP-Based Approximation Algorithm for Minimum Degree MSTs
• A Push-Relabel Algorithm for Approximating Degree Bounded MSTs
• Technical Note—A Note on the Multiple Traveling Salesmen Problem
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• Technical Note—A Note on the Symmetric Multiple Traveling Salesman Problem with Fixed Charges
• The constrained minimum spanning tree problem
• Primal-Dual Meets Local Search: Approximating MSTs With Nonuniform Degree Bounds
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques