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

Geissmann, Barbara ; Gianinazzi, Lukas

Routing in Stochastic Public Transit Networks

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

Abstract

We present robust, adaptive routing policies for time-varying networks (temporal graphs) in the presence of random edge-failures. Such a policy answers the following question: How can a traveler navigate a time-varying network where edges fail randomly in order to maximize the traveler's preference with respect to the arrival time? Our routing policy is computable in near-linear time in the number of edges in the network (for the case when the edges fail independently of each other).
Using our robust routing policy, we show how to travel in a public transit network where the vehicles experience delays. To validate our approach, we present experiments using real-world delay data from the public transit network of the city of Zurich. Our experiments show that we obtain significantly improved outcomes compared to a purely schedule-based policy: The traveler is on time 5-11 percentage points more often for most destinations and 20-40 percentage points more often for certain remote destinations. Our implementation shows that the approach is fast enough for real-time usage. It computes a policy for 1-hour long journeys in around 0.1 seconds.

BibTeX - Entry

@InProceedings{geissmann_et_al:OASIcs:2019:11416,
  author =	{Barbara Geissmann and Lukas Gianinazzi},
  title =	{{Routing in Stochastic Public Transit Networks}},
  booktitle =	{19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)},
  pages =	{4:1--4:18},
  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/11416},
  doi =		{10.4230/OASIcs.ATMOS.2019.4},
  annote =	{Keywords: Route Planning, Public Transit Network, Temporal Graphs}
}

Keywords: Route Planning, Public Transit Network, Temporal Graphs
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