| Euler is Standing in Line - Dial-a-Ride Problems with Precedence-Constraints (2000) | |||||||||||||||||
|
|||||||||||||||||
Abstract | |||||||||||||||||
| In this paper we study algorithms for Dial-a-Ride" transportation problems. In the basic version of the problem we are given transportation jobs between the vertices of a graph and the goal is to nd a shortest transportation that serves all the jobs. This problem is known to be NP-hard even on trees. We consider the extension when precedence relations between the jobs with the same source are given. Our results include a polynomial time algorithm on paths and approximation algorithms general graphs and trees with performances of 9=4 and 5=3, respectively. 1 Introduction and Overview Transportation problems where objects are to be transported between given sources and destinations in a metric space are classical problems in combinatorial optimization. Applications include the routing of pick-up-and-delivery vehicles, the control of automatic storage systems and scheduling of elevators. This leads to the following optimization problem (Darp): We are given transportation jobs ... | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||