2026-09-26T14:47:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7888 2026-09-22T15:04:55Z ddc:004 open_access

Revenue Maximization in Online Dial-A-Ride Christman, Ananya Chung, Christine Jaczko, Nicholas Milan, Marina Vasilchenko, Anna Westvold, Scott online algorithms dial-a-ride competitive analysis vehicle routing metric space We study a variation of the Online-Dial-a-Ride Problem where each request comes with not only a source, destination and release time, but also has an associated revenue. The server's goal is to maximize its total revenue within a given time limit, T. We show that the competitive ratio is unbounded for any deterministic online algorithm for the problem. We then provide a 3-competitive algorithm for the problem in a uniform metric space and a 6-competitive algorithm for the general case of weighted graphs (under reasonable assumptions about the input instance). We conclude with an experimental evaluation of our algorithm in simulated settings inspired by real-world Dial-a-Ride data. Experimental results show that our algorithm performs well when compared to an offline version of the algorithm and a greedy algorithm. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ananya Christman and Christine Chung and Nicholas Jaczko and Marina Milan and Anna Vasilchenko and Scott Westvold 2017 Is Part Of OASIcs, Volume 59, 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.ATMOS.2017.1 urn:nbn:de:0030-drops-78886 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2017.1 eng https://creativecommons.org/licenses/by/3.0/legalcode