Maximizing the Number of Rides Served for Dial-a-Ride

Anthony, Barbara M.

Boyd, Sara

Birnbaum, Ricky

Christman, Ananya

Chung, Christine

Davis, Patrick

Dhimar, Jigar

Yuen, David

2019-11-19

2019-11-19

2019

Barbara M. Anthony, S. B. (2019). Maximizing the Number of Rides Served for Dial-a-Ride. DROPS Dagstuhl Research Online Publication Server. https://doi.org/10.4230/OASIcs.ATMOS.2019.11

https://collections.southwestern.edu/s/suscholar/item/265

We study a variation of offline Dial-a-Ride, where each request has not only a source and destination, but also a revenue that is earned for serving the request. We investigate this problem for the uniform metric space with uniform revenues. While we present a study on a simplified setting of the problem that has limited practical applications, this work provides the theoretical foundation for analyzing the more general forms of the problem. Since revenues are uniform the problem is equivalent to maximizing the number of served requests. We show that the problem is NP-hard and present a 2/3 approximation algorithm. We also show that a natural generalization of this algorithm has an approximation ratio at most 7/9.

OASIcs

Dial-a-ride

Revenue maximization

Approximation algorithm

Vehicle routing

Article

Faculty Scholarship