文章基本信息

标题：Revenue Maximization in Online Dial-A-Ride
本地全文：下载
作者：Ananya Christman ; Christine Chung ; Nicholas Jaczko 等
期刊名称：OASIcs : OpenAccess Series in Informatics
电子版ISSN：2190-6807
出版年度：2017
卷号：59
页码：1-15
DOI：10.4230/OASIcs.ATMOS.2017.1
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：online algorithms; dial-a-ride; competitive analysis; vehicle routing; metric space