DROPS

Document

DOI: 10.4230/OASIcs.ATMOS.2019.4

Routing in Stochastic Public Transit Networks

Authors: Barbara Geissmann and Lukas Gianinazzi

Published in: OASIcs, Volume 75, 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)

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.

Cite as

Barbara Geissmann and Lukas Gianinazzi. Routing in Stochastic Public Transit Networks. In 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019). Open Access Series in Informatics (OASIcs), Volume 75, pp. 4:1-4:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{geissmann_et_al:OASIcs.ATMOS.2019.4,
  author =	{Geissmann, Barbara and Gianinazzi, Lukas},
  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 =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-128-3},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{75},
  editor =	{Cacchiani, Valentina and Marchetti-Spaccamela, Alberto},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2019.4},
  URN =		{urn:nbn:de:0030-drops-114167},
  doi =		{10.4230/OASIcs.ATMOS.2019.4},
  annote =	{Keywords: Route Planning, Public Transit Network, Temporal Graphs}
}

Search Results

Documents authored by Gianinazzi, Lukas

Routing in Stochastic Public Transit Networks

Abstract

Cite as

Thanks for your feedback!

Could not send message