On-line single server dial-a-ride problems

In this paper results on the dial-a-ride problem with a single server are presented. Requests for rides consist of two points in a metric space, a source and a destination. A ride has to be made by the server from the source to the destination. The server travels at unit speed in the metric space and the objective is to minimize some function of the delivery times at the destinations. We study this problem in the natural on-line setting. Calls for rides come in while the server is travelling. This models e.g. the taxi problem, or, if the server has capacity more than 1 a minibus or courier service problem. For two versions of this problem, one in which the server has infinite capacity and the other in which the server has capacity 1, both having as objective minimization of the time the last destination is served, we will design algorithms that have competitive ratio's of 2. We also show that these are best possible, since no algorithm can have competitive ratio better than 2 for these problems. Then we study the on-line problem with objective minimization of the sum of completion times of the rides. We prove a lower bound on the competitive ratio of any algorithm of 1 + \sqrt{2} for a server with any capacity and of 3 for servers with capacity 1.