SC 99-09 Martin Grötschel, Dietrich Hauptmeier, Sven O. Krumke, Jörg Rambau.: Simulation Studies for the Online-Dial-a-Ride Problem
Abstract: In a large distribution center of Herlitz AG, Berlin, we
invesigated
the elevator subsystem of the fully automated pallet
transportation
system. Each elevator may carry one pallet and has to
serve eight
levels. The goal is to minimize the average resp. the
maximum flow
time. The variants of this elevator control problem have
been
subject of recent theoretical research and are known as
online-dial-a-ride problems. In this paper we investigate
several
online algorithms for several versions of
online-dial-a-ride
problems by means of a simulation program, developed on
the basis of
the simulation library AMSEL. We draw statistics from
samples of
randomly generated data providing for different load
situations.
Moreover, we provide preliminary studies with real
production data
for a system of five elevators connected by a conveyor
circuit, as
can be found at the Herlitz plant. We show which
algorithms are
best under certain load situations and which lead to break
downs
under particular circumstances.
Keywords: online optimization,
competitive analysis,
elevator,
simulation studies
MSC: 90C27, 90B06
CR: F.1.2