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

Title

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

Creator

Anthony, Barbara M.

Boyd, Sara

Birnbaum, Ricky

Christman, Ananya

Chung, Christine

Davis, Patrick

Dhimar, Jigar

Yuen, David

Date

2019-11-19

Date Available

2019-11-19

Date Issued

2019

Identifier

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

uri

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

Abstract

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.

Publisher

OASIcs

Subject

Dial-a-ride

Revenue maximization

Approximation algorithm

Vehicle routing

Type

Article