License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2017.1
URN: urn:nbn:de:0030-drops-78886
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7888/
Go to the corresponding OASIcs Volume Portal

Christman, Ananya ; Chung, Christine ; Jaczko, Nicholas ; Milan, Marina ; Vasilchenko, Anna ; Westvold, Scott

Revenue Maximization in Online Dial-A-Ride

pdf-format:
OASIcs-ATMOS-2017-1.pdf (0.5 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{christman_et_al:OASIcs:2017:7888,
  author =	{Ananya Christman and Christine Chung and Nicholas Jaczko and Marina Milan and Anna Vasilchenko and Scott Westvold},
  title =	{{Revenue Maximization in Online Dial-A-Ride}},
  booktitle =	{17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)},
  pages =	{1:1--1:15},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-042-2},
  ISSN =	{2190-6807},
  year =	{2017},
  volume =	{59},
  editor =	{Gianlorenzo D'Angelo and Twan Dollevoet},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7888},
  URN =		{urn:nbn:de:0030-drops-78886},
  doi =		{10.4230/OASIcs.ATMOS.2017.1},
  annote =	{Keywords: online algorithms, dial-a-ride, competitive analysis, vehicle routing, metric space}
}

Keywords: online algorithms, dial-a-ride, competitive analysis, vehicle routing, metric space
Collection: 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)
Issue Date: 2017
Date of publication: 04.09.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI