DSpace Repository

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

Show simple item record

dc.contributor.author Anthony, Barbara M.
dc.contributor.author Boyd, Sara
dc.contributor.author Birnbaum, Ricky
dc.contributor.author Christman, Ananya
dc.contributor.author Chung, Christine
dc.contributor.author Davis, Patrick
dc.contributor.author Dhimar, Jigar
dc.contributor.author Yuen, David
dc.date.accessioned 2019-11-19T15:28:02Z
dc.date.available 2019-11-19T15:28:02Z
dc.date.issued 2019
dc.identifier.citation 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 en_US
dc.identifier.uri http://hdl.handle.net/11214/235
dc.description.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. en_US
dc.publisher OASIcs en_US
dc.subject Dial-a-ride en_US
dc.subject Revenue maximization en_US
dc.subject Approximation algorithm en_US
dc.subject Vehicle routing en_US
dc.title Maximizing the Number of Rides Served for Dial-a-Ride
dc.type Article en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record



My Account