A 3/2-Approximation Algorithm for the Multiple TSP with a Fixed Number of Depots
Publication Type
Conference Proceeding Article
Publication Date
6-2010
Abstract
As an important extension of the classical traveling salesman problem (TSP), the multiple depot multiple traveling salesman problem (MDMTSP) is to minimize the total length of a collection of tours for multiple vehicles to serve all the customers, where each vehicle must start or stay at its distinct depot. Due to the gap between the existing best approximation ratios for the TSP and for the MDMTSP in literature, which are 3/2 and 2, respectively, it is an open question whether or not a 3/2-approximation algorithm exists for the MDMTSP. We have partially addressed this question by developing a 3/2-approximation algorithm, which runs in polynomial time when the number of depots is a constant.
Keywords
Approximation algorithm, multiple depots, vehicle routing
Discipline
Operations and Supply Chain Management
Research Areas
Operations Management
Publication
Algorithm Theory - SWAT 2010: 12th Scandinavian Symposium and Workshops on Algorithm Theory, Bergen, Norway, June 21-23, 2010. Proceedings
Volume
6139
First Page
127
Last Page
138
ISBN
9783642137303
Identifier
10.1007/978-3-642-13731-0_13
Publisher
Springer Verlag
City or Country
Cham
Citation
XU, Zhou and RODRIGUES, Brian.
A 3/2-Approximation Algorithm for the Multiple TSP with a Fixed Number of Depots. (2010). Algorithm Theory - SWAT 2010: 12th Scandinavian Symposium and Workshops on Algorithm Theory, Bergen, Norway, June 21-23, 2010. Proceedings. 6139, 127-138.
Available at: https://ink.library.smu.edu.sg/lkcsb_research/3036
Additional URL
https://doi.org/10.1007/978-3-642-13731-0_13