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 \ge 1 $ 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+\lceil \lambda \rceil /k $ 2 + ⌈ λ ⌉ / k and at least $ 1 + \lambda /k $ 1 + λ / k , where λ denotes the aspect ratio of the graph, and that the ratio $ 1 + \lambda /k $ 1 + λ / k is tight when $ 1 + \lambda /k \ge k $ 1 + λ / k ≥ k. We also show that even as k grows beyond the size of λ, the ratio never improves below 9/7. [ABSTRACT FROM AUTHOR]