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.2013.27
URN: urn:nbn:de:0030-drops-42428
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2013/4242/
Go to the corresponding OASIcs Volume Portal

Böhmová, Katerina ; Mihalák, Matús ; Pröger, Tobias ; Srámek, Rastislav ; Widmayer, Peter

Robust Routing in Urban Public Transportation: How to Find Reliable Journeys Based on Past Observations

pdf-format:
4.pdf (0.6 MB)

Abstract

We study the problem of robust routing in urban public transportation
networks. In order to propose solutions that are robust for typical delays, we assume that we have past observations of real traffic situations available. In particular, we assume that we have "daily records" containing the observed travel times in the whole network for a few past days. We introduce a new concept to express a solution
that is feasible in any record of a given public transportation network. We adapt the method of Buhmann et al. [Buhmann et al., ITCS 2013] for optimization under uncertainty, and develop algorithms that allow its application for finding a robust journey from a given source to a given destination. The performance of the algorithms and the quality of the predicted journey are evaluated in a preliminary
experimental study. We furthermore introduce a measure of reliability of a given journey, and develop algorithms for its computation. The robust routing concepts presented in this work are suited specially for public transportation networks of large cities that lack clear hierarchical structure and contain services that run with high frequencies.

BibTeX - Entry

@InProceedings{bhmov_et_al:OASIcs:2013:4242,
  author =	{Katerina B{\"o}hmov{\'a} and Mat{\'u}s Mihal{\'a}k and Tobias Pr{\"o}ger and Rastislav Sr{\'a}mek and Peter Widmayer},
  title =	{{Robust Routing in Urban Public Transportation: How to Find Reliable Journeys Based on Past Observations}},
  booktitle =	{13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{27--41},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-58-3},
  ISSN =	{2190-6807},
  year =	{2013},
  volume =	{33},
  editor =	{Daniele Frigioni and Sebastian Stiller},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2013/4242},
  URN =		{urn:nbn:de:0030-drops-42428},
  doi =		{10.4230/OASIcs.ATMOS.2013.27},
  annote =	{Keywords: Algorithms, Optimization, Robustness, Route planning, Public transportation}
}

Keywords: Algorithms, Optimization, Robustness, Route planning, Public transportation
Collection: 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems
Issue Date: 2013
Date of publication: 05.09.2013

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