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 traveling. This models, e.g. the taxi problem, or, if the server has capacity more than 1 a minibus or courier service problem. For the version of this problem in which the server has infinite capacity having as objective minimization of the time the last destination is served, we design an algorithm that has competitive ratio 2. We also show that this is best possible, since no algorithm can have competitive ratio better than 2 independent of the capacity of the server. Besides, we give a simple 2.5-competitive algorithm for the case with finite capacity. 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 + root2 for a server with any capacity and of 3 for a server with capacity 1. Finally, we present the first competitive algorithm for the case the server has infinite capacity and the metric space is the real line. The algorithm has competitive ratio 15. (C) 2001 Elsevier Science B.V. All rights reserved.