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

Bast, Hannah ; Sternisko, Jonas ; Storandt, Sabine

Delay-Robustness of Transfer Patterns in Public Transportation Route Planning

pdf-format:
5.pdf (0.7 MB)

Abstract

Transfer pattern routing is a state-of-the-art speed-up technique for finding optimal paths which minimize multiple cost criteria in public transportation networks. It precomputes sequences of transfer stations
along optimal paths. At query time, the optimal paths are searched among the stored transfer patterns, which allows for very fast response times even on very large networks. On the other hand, even a minor change to the timetables may affect many optimal paths,
so that, in principle, a new computation of all optimal transfer patterns becomes necessary. In this paper, we examine the robustness of transfer pattern routing towards delay, which is the most common source of such updates. The intuition is that the deviating paths caused by typical updates are already covered by original
transfer patterns. We perform experiments which show that the transfer patterns are remarkably robust even to large and many delays, which underlines the applicability and reliability of transfer pattern routing in realistic routing applications.

BibTeX - Entry

@InProceedings{bast_et_al:OASIcs:2013:4243,
  author =	{Hannah Bast and Jonas Sternisko and Sabine Storandt},
  title =	{{Delay-Robustness of Transfer Patterns in Public Transportation Route Planning}},
  booktitle =	{13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{42--54},
  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/4243},
  URN =		{urn:nbn:de:0030-drops-42434},
  doi =		{10.4230/OASIcs.ATMOS.2013.42},
  annote =	{Keywords: Route planning, public transportation, transfer patterns, delay, robustness}
}

Keywords: Route planning, public transportation, transfer patterns, delay, robustness
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