In this paper the authors deal with a single-vehicle scheduling problem on a tree-shaped road network. 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∈V, which is also denoted as v. Each task v has its due date d(v) and processing time p(v). The travel times w(u,v) and w(v,u) are associated with each edge (u,v)∈E. The vehicle starts from an initial vertex v0∈V, visits all tasks v∈V for their processing (no preemption is allowed) and returns to v0. The problem asks to find a routing schedule of the vehicle that minimizes the maximum lateness from the due dates of tasks. This problem is called TREE-VSP(Lmax). The authors prove that TREE-VSP(Lmax) is strongly NP-hard in general, but show that it can be solved in polynomial time if only depth-first routing is allowed for the vehicle.
