| Euler is Standing in Line - Dial-a-Ride Problems with FIFO-Precedence-Constraints (1970) | |||||||||||||||||
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 find 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 an approximation algorithm on general graphs with a performance of 9=4. For trees we improve the performance to 5=3. 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 trans... | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||