SC 99-06 Dietrich Hauptmeier, Sven O. Krumke, Jörg Rambau, Hans-Christoph Wirth.: Euler is Standing in Line
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.
Keywords: NP-completeness,
polynomial-time approximation algorithms,
stacker-crane problem,
vehicle routing,
elevator system,
Eulerian Cycle
MSC: 68Q25, 68Q10