We consider the following online dial-a-ride problem (
OlDarp): Objects are to be transported between points in a metric space. Transportation requests arrive online, specifying the objects
to be transported and the corresponding source and destination. These requests are to be handled by a server which starts
its work at a designated origin and which picks up and drops objects at their sources and destinations. The server can move
at constant unit speed. After the end of its service the server returns to its start in the origin. The goal of
OlDarp is to come up with a transportation schedule for the server which finishes as early as possible, i.e., which minimizes the
makespan.
We analyze several competitive algorithms for OlDarp and establish tight competitiveness results. The first two algorithms, REPLAN and IGNORE are very simple and natural: REPLAN
completely discards its (preliminary) schedule and recomputes a new one when a new request arrives. IGNORE always runs a (locally
optimal) schedule for a set of known requests and ignores all new requests until this schedule is completed. We show that
both strategies, REPLAN and IGNORE, are 5/2-competitive.
We then present a somewhat less natural strategy SMARTSTART, which in contrast to the other two strategies may leave the server
idle from time to time although unserved requests are known. The SMARTSTART-algorithm has an improved competitive ratio of
2, which matches our lower bound.
Research supported by the German Science Foundation (grant 883/5-2)