TY - GEN
T1 - A 3/2-approximation algorithm for multiple depot multiple traveling salesman problem (extended abstract)
AU - Xu, Zhou
AU - Rodrigues, Brian
PY - 2010/7/21
Y1 - 2010/7/21
N2 - 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.
AB - 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.
KW - Approximation algorithm
KW - multiple depots
KW - vehicle routing
UR - http://www.scopus.com/inward/record.url?scp=77954630793&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-13731-0_13
DO - 10.1007/978-3-642-13731-0_13
M3 - Conference article published in proceeding or book
SN - 364213730X
SN - 9783642137303
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 127
EP - 138
BT - Algorithm Theory - SWAT 2010 - 12th Scandinavian Symposium and Workshops on Algorithm Theory, Proceedings
T2 - 12th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2010
Y2 - 21 June 2010 through 23 June 2010
ER -