Abstract
We investigate the single vehicle scheduling problems based on tree/cycle networks. Each customer, assumed as a vertex on the given network, has a release time and a service time requirements. The single vehicle starts from the depot and aims to serve all the customers. The objective of the problem is to find the relatively optimal routing schedule so as to minimize the makespan. We provide a \(\frac{16}{9}\)-approximation algorithm and a \(\frac{48}{25}\)-approximation algorithm for the tour-version and the path-version of single vehicle scheduling problem on a tree, respectively. For the tour-version of single vehicle scheduling problem on a cycle, we present a \(\frac{5}{3}\)-approximation algorithm.
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
Tsitsiklis, J.N.: Special cases of traveling salesman and repairman problems with time windows. Networks 22, 263–282 (1992). https://doi.org/10.1002/net.3230220305
Psaraftis, H.N., Solomon, M.M., Magnanti, T.L., Kim, T.-U.: Routing and scheduling on a shoreline with release times. Manage. Sci. 36, 212–223 (1990). https://doi.org/10.1287/mnsc.36.2.212
Karuno, Y., Nagamochi, H., Ibaraki, T.: Better approximation ratios for the single-vehicle scheduling problems on line-shaped networks. Networks 39(4), 203–209 (2002). https://doi.org/10.1002/net.10028
Gaur, D.R., Gupta, A., Krishnamurti, R.: A \(\frac{5}{3}\)-approximation algorithm for scheduling vehicles on a path with release and handling times. Inform. Process. Lett. 86, 87–91 (2003). https://doi.org/10.1016/S0020-0190(02)00474-X
Bhattacharya, B., Carmi, P., Hu, Y., Shi, Q.: Single vehicle scheduling problems on Path/Tree/Cycle Networks with release and handling times. In: Hong, S.-H., Nagamochi, H., Fukunaga, T. (eds.) ISAAC 2008. LNCS, vol. 5369, pp. 800–811. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-92182-0_70
Yu, W., Liu, Z.: Single vehicle scheduling problems with release and service times on a line. Networks 57, 128–134 (2011). https://doi.org/10.1002/net.20393
Karuno, Y., Nagamochi, H.: \(2\)-approximation algorithms for the multi-vehicle scheduling prbolem on a path with release and handling times. Discrete Appl. Math. 129, 433–447 (2003). https://doi.org/10.1016/S0166-218X(02)00596-6
Yu, W., Liu, Z.: Vehicle routing problems on a line-shaped network with release time constraints. Oper. Res. Lett. 37, 85–88 (2009). https://doi.org/10.1016/j.orl.2008.10.006
Karuno, Y., Nagamochi, H., Ibaraki, T.: Vehicle scheduling on a tree with release and handling times. In: Ng, K.W., Raghavan, P., Balasubramanian, N.V., Chin, F.Y.L. (eds.) ISAAC 1993. LNCS, vol. 762, pp. 486–495. Springer, Heidelberg (1993). https://doi.org/10.1007/3-540-57568-5_280
Nagamochi, H., Mochizuki, K., Ibaraki, T.: Complexity of the single vehicle scheduling problem on graphs. Inform. Syst. Oper. Res. 35, 256–276 (1997). https://doi.org/10.1080/03155986.1997.11732334
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). https://doi.org/10.1016/j.tcs.2012.01.046
Augustine, J.E., Seiden, S.S.: Linear time approximation schemes for vehicle scheduling problems. Theoret. Comput. Sci. 324, 147–160 (2004). https://doi.org/10.1016/j.tcs.2004.05.013
Bhattacharya, B., Hu, Y.: Approximation algorithms for the multi-vehicle scheduling problem. In: Cheong, O., Chwa, K.-Y., Park, K. (eds.) ISAAC 2010. LNCS, vol. 6507, pp. 192–205. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-17514-5_17
Acknowledgement
The authors would like to thank the associated editor and the anonymous referees for their constructive comments and kind suggestions. This research was supported by the National Natural Science Foundation of China under Grant No. 11371137.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Wu, Y., Lu, X. (2017). Better Approximation Ratios for the Single-Vehicle Scheduling Problems on Tree/Cycle Networks. In: Gao, X., Du, H., Han, M. (eds) Combinatorial Optimization and Applications. COCOA 2017. Lecture Notes in Computer Science(), vol 10627. Springer, Cham. https://doi.org/10.1007/978-3-319-71150-8_27
Download citation
DOI: https://doi.org/10.1007/978-3-319-71150-8_27
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-71149-2
Online ISBN: 978-3-319-71150-8
eBook Packages: Computer ScienceComputer Science (R0)