In this paper, the authors consider 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, 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)∈E. The vehicle starts from an initial vertex v0∈V, visits all tasks v∈V for their processing, and returns to v0. 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 v0 after processing all tasks). The authors call this problem TREE-VSP(C). They first prove that TREE-VSP(C) is NP-hard. However, the authors then show that TREE-VSP(C) with a depth-first routing constraint can be exactly solved in O(nlogn) time. Moreover, they 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.
