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.2019.12
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11424/
Go to the corresponding OASIcs Volume Portal

Euler, Ricardo ; Borndörfer, Ralf

A Graph- and Monoid-Based Framework for Price-Sensitive Routing in Local Public Transportation Networks

pdf-format:
OASIcs-ATMOS-2019-12.pdf (0.5 MB)

Abstract

We present a novel framework to mathematically describe the fare systems of local public transit companies. The model allows the computation of a provably cheapest itinerary even if prices depend on a number of parameters and non-linear conditions. Our approach is based on a ticket graph model to represent tickets and their relation to each other. Transitions between tickets are modeled via transition functions over partially ordered monoids and a set of symbols representing special properties of fares (e.g. surcharges). Shortest path algorithms rely on the subpath optimality property. This property is usually lost when dealing with complicated fare systems. We restore it by relaxing domination rules for tickets depending on the structure of the ticket graph. An exemplary model for the fare system of Mitteldeutsche Verkehrsbetriebe (MDV) is provided. By integrating our framework in the multi-criteria RAPTOR algorithm we provide a price-sensitive algorithm for the earliest arrival problem and assess its performance on data obtained from MDV. We discuss three preprocessing techniques that improve run times enough to make the algorithm applicable for real-time queries.

BibTeX - Entry

@InProceedings{euler_et_al:OASIcs:2019:11424,
  author =	{Ricardo Euler and Ralf Bornd{\"o}rfer},
  title =	{{A Graph- and Monoid-Based Framework for Price-Sensitive Routing in Local Public Transportation Networks}},
  booktitle =	{19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)},
  pages =	{12:1--12:15},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-128-3},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{75},
  editor =	{Valentina Cacchiani and Alberto Marchetti-Spaccamela},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11424},
  doi =		{10.4230/OASIcs.ATMOS.2019.12},
  annote =	{Keywords: shortest path, public transit, optimization, price-sensitive, raptor, fare, operations research}
}

Keywords: shortest path, public transit, optimization, price-sensitive, raptor, fare, operations research
Collection: 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)
Issue Date: 2019
Date of publication: 15.11.2019

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