An extension of the Christofides heuristic for the generalized multiple depot multiple traveling salesmen problem
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.
Approximation algorithm, Multiple depots, Traveling salesman problem
Operations and Supply Chain Management | Operations Research, Systems Engineering and Industrial Engineering
European Journal of Operational Research
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. Research Collection Lee Kong Chian School Of Business.
Available at: http://ink.library.smu.edu.sg/lkcsb_research/4999
This document is currently not available here.