An extension of the Christofides heuristic for the generalized multiple depot multiple traveling salesmen problem
Publication Type
Journal Article
Publication Date
3-2017
Abstract
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.
Keywords
Approximation algorithm, Multiple depots, Traveling salesman problem
Discipline
Operations and Supply Chain Management | Operations Research, Systems Engineering and Industrial Engineering
Research Areas
Operations Management
Publication
European Journal of Operational Research
Volume
257
Issue
3
First Page
735
Last Page
745
ISSN
0377-2217
Identifier
10.1016/j.ejor.2016.08.054
Publisher
Elsevier
Citation
XU, Zhou and RODRIGUES, Brian Charles.
An extension of the Christofides heuristic for the generalized multiple depot multiple traveling salesmen problem. (2017). European Journal of Operational Research. 257, (3), 735-745.
Available at: https://ink.library.smu.edu.sg/lkcsb_research/4999
Additional URL
https://doi.org/10.1016/j.ejor.2016.08.054