Abstract
In this paper, we study a distance constrained vehicle routing problem with time windows (DVRPTW). DVRPTW is defined as follows: given a metric space on a set of vertices, a release time and a deadline for each vertex, a length bound D, find a minimum cardinality set of tours originating at the depot that covers all vertices, such that each tour has length at most D, and visit as many vertices as possible within their time windows. We give a bicriteria approximation algorithm for DVRPTW on the metric plane, and all the distances satisfy the triangle inequality.
Heijiao Huang: This work was financially supported by National Natural Science Foundation of China with Grants No.11071271, No. 11371004, No. 61100191 and No. 61370216, and Shenzhen Strategic Emerging Industries Program with Grants No. ZDSY20120613125016389, No. JCYJ20120613151201451 and No. JCYJ20130329153215152.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Laporte, G., Desrochers, M., Nobert, Y.: Two exact algorithms for the distance constrained vehicle routing problem. Networks 14, 47–61 (1984)
Dantzig, G.B., Ramser, J.H.: The truck dispatching problem. Manage. Sci. 6, 80 (1959)
Li, C., Simchi-Levi, D., Desrochers, M.: On the distance constrained vehicle routing problem. Oper. Res. 40, 790–799 (1992)
Nagarajan, V., Ravi, R.: Approximation algorithms for distance constrained vehicle routing problems. Networks 3, 209–214 (2012)
Thangiah, S.: Vehicle routing with time windows using genetic algorithms. In: Chambers, L. (ed.) Application Handbook of Genetic Algorithms: New Frontiers, vol. II. CRC Press, Boca Raton (1995)
Bao, X., Liu, Z.: Approximation algorithms for single vehicle scheduling problems with release and service times on a tree or cycle. Theoret. Comput. Sci. 434, 1–10 (2012)
Nagamochi, H., Ohnishi, T.: Approximating a vehicle scheduling problem with time windows and handling times. Theoret. Comput. Sci. 393, 133–146 (2008)
Karuno, Y., Nagamochi, H.: An approximability result of the multi-vehicle scheduling problem on a path with release and handling times. Theoret. Comput. Sci. 312, 267–280 (2004)
Desrochers, M., Desrosiers, J., Solomon, M.: A new optimization algorithm for the vehicle routing problem with time windows. Oper. Res. 40, 342–354 (1992)
Savelsbergh, M.: Local search for routing problems with time windows. Ann. Oper. Res. 4, 285–305 (1985)
Bansal, N., Blum, A., Chawla, S., Meyerson, A.: Approximation algorithms for deadline-TSP and vehicle routing with time-windows. In: STOC ’04 Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, pp. 166–174 (2004)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Gu, H., Song, L., Huang, H., Du, H. (2014). A Bicriteria Approximation Algorithm for DVRP with Time Windows. In: Zhang, Z., Wu, L., Xu, W., Du, DZ. (eds) Combinatorial Optimization and Applications. COCOA 2014. Lecture Notes in Computer Science(), vol 8881. Springer, Cham. https://doi.org/10.1007/978-3-319-12691-3_18
Download citation
DOI: https://doi.org/10.1007/978-3-319-12691-3_18
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-12690-6
Online ISBN: 978-3-319-12691-3
eBook Packages: Computer ScienceComputer Science (R0)