2026-07-23T10:34:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11423 2024-03-06T10:30:48Z ddc:004 open_access

Maximizing the Number of Rides Served for Dial-a-Ride Anthony, Barbara M. Birnbaum, Ricky Boyd, Sara Christman, Ananya Chung, Christine Davis, Patrick Dhimar, Jigar Yuen, David dial-a-ride revenue maximization approximation algorithm vehicle routing 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Barbara M. Anthony and Ricky Birnbaum and Sara Boyd and Ananya Christman and Christine Chung and Patrick Davis and Jigar Dhimar and David Yuen 2019 Is Part Of OASIcs, Volume 75, 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.ATMOS.2019.11 urn:nbn:de:0030-drops-114237 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2019.11 eng https://creativecommons.org/licenses/by/3.0/legalcode