The dial-a-ride problem requires an algorithm for satisfying a set P of requests for “rides” in a minimum time. A request r specifies a source sr and a destination dr, which are points in a fixed metric space with a distinguished point o called the origin. A solution will be a path x beginning and ending at o. One is to imagine the transportation vehicle (server) tracing out the path at unit speed, picking up and dropping off passengers in order to satisfy P. Let us say that the request r becomes active at t = t1 (the pickup, x(t1) = sr) and becomes inactive (satisfied) at t = t2 (the drop-off, x(t2) = dr). Thus the request is active when t satisfies t1 ≤ t < t2. The number of active requests will be denoted by ℓ(t). Rides can have the same source and destination, in which case the site must be visited, but the request never contributes to ℓ(t). One of the parameters of the problem is the capacity of the server, which is an upper bound on the number of requests that can be active simultaneously.
The length L of the path is considered equivalent to the total time required to satisfy P. Thus, the parameter range of x is [0, L]. However, the definition of length depends on the underlying properties of the metric space. Unfortunately, the authors never give a proper mathematical definition of the class of metric spaces being considered, but mention some of the properties they would expect to make use of. A safe guess of two classes of metric spaces to which the results apply would be Riemannian manifolds (in particular, Euclidean spaces); and finite connected graphs with edges of length 1 and the “shortest path” metric. In the former case, paths would travel along geodesics, while in the latter case, paths would be sequences of edges.
In the traditional (offline) version of the problem, P is known in advance. The paper under review is concerned with the online version, in which requests can occur while the path is being traversed. In the case of Riemannian manifolds, requests are allowed at any time (and paths can change direction instantaneously), while in the other case, requests can be recognized only at nonnegative integer times. Algorithms are analyzed using the competitive ratio, which is the worst-case ratio between time taken by the algorithm in satisfying P and the minimum time required to satisfy P with full knowledge (offline).
In a previous paper [1], the authors (jointly with others) discussed the online traveling sales man problem, which can be seen as a special case of the dial-a-ride problem, in which each ride has the same source and destination. Having proven in this work that any (deterministic) algorithm for the online TSP has a competitive ratio of at least 2, they observe here that the same applies to the dial-a-ride problem. They present an algorithm for the online dial-a-ride problem with a competitive ratio of 2.5. The idea is very simple: whenever the server is at the origin, it follows an optimal route for the requests that currently exist, ignoring requests that may occur while traveling. When it returns to the origin, it repeats the process with the requests that have occurred in the meantime. The authors assert that the competitive ratio of 2.5 holds for any metric space.
For the case of infinite capacity and the restricted class of metric spaces mentioned earlier, the authors present an algorithm with a competitive ratio of 2 (the best possible ratio). The algorithm starts out as before. If a new request is received with both source and destination as close to the origin as the server’s current position, the new request is (temporarily) ignored. However, if either the source or destination is further away, the server returns directly to the origin and starts the next iteration.
The authors continue to consider the same problem with different objective functions, obtaining analogous lower bounds and algorithms, and computing their competitive ratios. In summary, the paper contains several remarkable results in a problem area where there is still much to be done.
