Maximizing the number of rides served for time-limited Dial-a-Ride*

We consider a variant of the offline Dial-a-Ride problem on weighted graphs with a single server where each request has a source and destination. The server's goal is to serve requests so as to maximize the total number of requests served within a given time limit. We first prove that no polynomial-time algorithm will always serve the optimal number of requests, even when the algorithm's time limit is augmented by any factor c≥1, unless P = NP. We also show that the approximation ratio is unbounded for a reasonable class of algorithms for this problem. We then present k-Sequence, an algorithm that repeatedly serves the fastest set of k remaining requests. We show that k-Sequence has approximation ratio at most 2+⌈λ⌉/k and at least 1+λ/k, where λ denotes the aspect ratio of the graph, and that the ratio 1+λ/k is tight when 1+λ/k≥k. We also show that even as k grows beyond the size of λ, the ratio never improves below 9/7.