Skip to main content
Log in

Vehicle scheduling on a tree with release and handling times

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

In this paper, we consider a single-vehicle scheduling problem on a tree-shaped road net-work. Let T =(V,E) be a tree, where V is a set of n vertices and E is a set of edges. A task is located at each vertex v, which is also denoted as v. Each task v has release time r(v) and handling time h(v). The travel times c(u, v) and c(v, u) are associated with each edge (u, v) of E. The vehicle starts from an initial vertex v_0 of V, visits all tasks v in V for their processing, and returns to v_0 . The objective is to find a routing schedule of the vehicle that minimizes the completion time, denoted as C (i.e., the time to return to v_0 after processing all tasks). We call this problem TREE-VSP(C). We first prove that TREE-VSP(C) is NP-hard. However, we then show that TREE-VSP(C) with a depth-first routing constraint can be exactly solved in O(n log n) time. Moreover, we show that, if this exact algorithm is used as an approximate algorithm for the original TREE-VSP(C), its worst-case performance ratio is at most two.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. M. Atallah and S. Kosaraju, Efficient solutions to some transportation problems with application to minimizing robot arm travel, SIAM J. Comput. 17(1988)849–869.

    Google Scholar 

  2. I. Averbakh and O. Berman, Sales-delivery man problems on tree-like networks, Networks 25 (1995)45–58.

    Google Scholar 

  3. E. Baker, An exact algorithm for the time-constrained traveling salesman problem, Operations Research 31(1983)938–945.

    Google Scholar 

  4. N. Christofides, Vehicle routing, in: The Traveling Salesman Problem, E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D.B. Shmoys, eds., Wiley, 1985, pp. 431–448.

  5. G. Frederickson, A note on the complexity of a simple transportation problem, SIAM J. Comput. 22(1993)57–61.

    Google Scholar 

  6. G. Frederickson and D. Guan, Preemptive ensemble motion planning on a tree, SIAM J. Comput. 21(1992)1130–1152.

    Google Scholar 

  7. G. Frederickson, M. Hecht and C. Kim, Approximation algorithms for some routing problems, SIAM J. Comput. 7(1978)178–193.

    Google Scholar 

  8. M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, San Francisco, 1979.

    Google Scholar 

  9. Y. Karuno, H. Nagamochi and T. Ibaraki, Vehicle scheduling on a tree with release and handling times, Lecture Notes in Computer Science 762, Springer, 1993, pp. 486–495.

  10. E. Minieka, The delivery man problem on a tree network, Annals of Operations Research 18(1989) 261–266.

    Google Scholar 

  11. H. Psaraftis, M. Solomon, T. Magnanti and T. Kim, Routing and scheduling on a shoreline with release times, Management Science 36(1990)212–223.

    Google Scholar 

  12. M. Solomon, Algorithms for the vehicle routing and scheduling problem with time window constraints, Operations Research 35(1987)254–265.

    Google Scholar 

  13. M. Solomon and J. Desrosiers, Time window constrained routing and scheduling problems: A survey, Transportation Sci. 22(1988)1–13.

    Google Scholar 

  14. J.N. Tsitsiklis, Special cases of traveling salesman and repairman problems with time windows, Networks 22(1992)263–282.

    Google Scholar 

Download references

Authors

Rights and permissions

Reprints and permissions

About this article

Cite this article

Karuno, Y., Nagamochi, H. & Ibaraki, T. Vehicle scheduling on a tree with release and handling times. Annals of Operations Research 69, 193–207 (1997). https://doi.org/10.1023/A:1018928911513

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1018928911513

Keywords

Navigation