License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.26
URN: urn:nbn:de:0030-drops-147197
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14719/
Go to the corresponding LIPIcs Volume Portal

Bhawalkar, Kshipra ; Kollias, Kostas ; Purohit, Manish

Revenue Maximization in Transportation Networks

pdf-format:
LIPIcs-APPROX26.pdf (0.8 MB)

Abstract

We study the joint optimization problem of pricing trips in a transportation network and serving the induced demands by routing a fleet of available service vehicles to maximize revenue. Our framework encompasses applications that include traditional transportation networks (e.g., airplanes, buses) and their more modern counterparts (e.g., ride-sharing systems). We describe a simple combinatorial model, in which each edge in the network is endowed with a curve that gives the demand for traveling between its endpoints at any given price. We are supplied with a number of vehicles and a time budget to serve the demands induced by the prices that we set, seeking to maximize revenue. We first focus on a (preliminary) special case of our model with unit distances and unit time horizon. We show that this version of the problem can be solved optimally in polynomial time. Switching to the general case of our model, we first present a two-stage approach that separately optimizes for prices and routes, achieving a logarithmic approximation to revenue in the process. Next, using the insights gathered in the first two results, we present a constant factor approximation algorithm that jointly optimizes for prices and routes for the supply vehicles. Finally, we discuss how our algorithms can handle capacitated vehicles, impatient demands, and selfish (wage-maximizing) drivers.

BibTeX - Entry

@InProceedings{bhawalkar_et_al:LIPIcs.APPROX/RANDOM.2021.26,
  author =	{Bhawalkar, Kshipra and Kollias, Kostas and Purohit, Manish},
  title =	{{Revenue Maximization in Transportation Networks}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{26:1--26:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14719},
  URN =		{urn:nbn:de:0030-drops-147197},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.26},
  annote =	{Keywords: Pricing, networks, approximation algorithms}
}

Keywords: Pricing, networks, approximation algorithms
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Issue Date: 2021
Date of publication: 15.09.2021

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