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

Zhou Xu, Brian Rodrigues

Research output: Journal article publicationJournal articleAcademic researchpeer-review

11 Citations (Scopus)


We study a generalization of the classical traveling salesman problem, where multiple salesmen are positioned at different depots, of which only a limited number (k) can be selected to service customers. For this problem, only two 2-approximation algorithms are available in the literature. Here, we improve on these algorithms by showing that a non-trivial extension of the well-known Christofides heuristic has a tight approximation ratio of 2−1/(2k). In doing so, we develop a body of analysis which can be used to build new approximation algorithms for other vehicle routing problems.
Original languageEnglish
Pages (from-to)735-745
Number of pages11
JournalEuropean Journal of Operational Research
Issue number3
Publication statusPublished - 16 Mar 2017


  • Approximation algorithm
  • Multiple depots
  • Traveling salesman problem

ASJC Scopus subject areas

  • Modelling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Cite this