In this paper we study algorithms for "Dial-a-Ride" transportation problems
. In the basic version of the problem we are given transportation jobs betw
een the vertices of a graph and the goal is to find a shortest transportati
on that serves all the jobs. This problem is known to be NP-hard even on tr
ees. We consider the extension when precedence relations between the jobs w
ith the same source are given. Our results include a polynomial time algori
thm on paths and approximation algorithms for general graphs and trees with
performances of 9/4 and 5/3, respectively. (C) 2001 Elsevier Science B.V.
All rights reserved.