An extension of the Christofides heuristic for the generalized multiple depot multiple traveling salesmen problem

DOI10.1016/j.ejor.2016.08.054zbMath1394.90504OpenAlexW2509664953MaRDI QIDQ1752857

Zhou Xu, Brian Rodrigues

Publication date: 24 May 2018

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2016.08.054

zbMATH Keywords

approximation algorithmtraveling salesman problemmultiple depots

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Discrete location and assignment (90B80)

Related Items (5)

Approximation algorithms for the \(k\)-depots Hamiltonian path problem ⋮ Sufficient and necessary conditions for an edge in the optimal Hamiltonian cycle based on frequency quadrilaterals ⋮ Approximating the multiple-depot multiple-terminal Hamiltonian path problem ⋮ The \(m\)-Steiner traveling salesman problem with online edge blockages ⋮ An asymptotically tight online algorithm for \(m\)-steiner traveling salesman problem

Uses Software

• Blossom IV

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A survey of recent research on location-routing problems
• An analysis of the extended Christofides heuristic for the \(k\)-depot TSP
• Combined location-routing problems: A synthesis and future research directions
• \(\frac 32\)-approximation algorithm for two variants of a 2-depot Hamiltonian path problem
• An approximation algorithm for a symmetric generalized multiple depot, multiple travelling salesman problem
• A 3/2-Approximation Algorithm for the Multiple TSP with a Fixed Number of Depots
• Primal-Dual Schema and Lagrangian Relaxation for the k-Location-Routing Problem
• Solving a Family of Multi-Depot Vehicle Routing and Location-Routing Problems
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• A minimum spanning tree algorithm with inverse-Ackermann type complexity
• Computing Minimum-Weight Perfect Matchings
• A General Approximation Technique for Constrained Forest Problems

This page was built for publication: An extension of the Christofides heuristic for the generalized multiple depot multiple traveling salesmen problem