TY - GEN
T1 - Vehicle scheduling on a graph revisited
AU - Yu, Wei
AU - Golin, Mordecai
AU - Zhang, Guochuan
PY - 2012
Y1 - 2012
N2 - We consider a generalization of the well-known Traveling Salesman Problem, called the Vehicle Scheduling Problem (VSP), in which each city is associated with a release time and a service time. The salesman has to visit each city at or after its release time. Our main results are three-fold. First, we devise an approximation algorithm for VSP with performance ratio less than 5/2 when the number of distinct release times is fixed, improving the previous algorithm proposed by Nagamochi et al. [12]. Then we analyze a natural class of algorithms and show that no performance ratio better than 5/2 is possible unless the Metric TSP can be approximated with a ratio strictly less than 3/2, which is a well-known longstanding open question. Finally, we consider a special case of VSP, that has a heavy edge, and present an approximation algorithm with performance ratio less than 5/2 as well.
AB - We consider a generalization of the well-known Traveling Salesman Problem, called the Vehicle Scheduling Problem (VSP), in which each city is associated with a release time and a service time. The salesman has to visit each city at or after its release time. Our main results are three-fold. First, we devise an approximation algorithm for VSP with performance ratio less than 5/2 when the number of distinct release times is fixed, improving the previous algorithm proposed by Nagamochi et al. [12]. Then we analyze a natural class of algorithms and show that no performance ratio better than 5/2 is possible unless the Metric TSP can be approximated with a ratio strictly less than 3/2, which is a well-known longstanding open question. Finally, we consider a special case of VSP, that has a heavy edge, and present an approximation algorithm with performance ratio less than 5/2 as well.
UR - https://www.scopus.com/pages/publications/84871570699
U2 - 10.1007/978-3-642-35261-4_39
DO - 10.1007/978-3-642-35261-4_39
M3 - Conference Paper published in a book
AN - SCOPUS:84871570699
SN - 9783642352607
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 362
EP - 371
BT - Algorithms and Computation - 23rd International Symposium, ISAAC 2012, Proceedings
PB - Springer Verlag
T2 - 23rd International Symposium on Algorithms and Computation, ISAAC 2012
Y2 - 19 December 2012 through 21 December 2012
ER -