Search Results

Documents authored by Knoth, Martin


Document
The Price of Robustness in Timetable Information

Authors: Marc Goerigk, Martin Knoth, Matthias Müller-Hannemann, Marie Schmidt, and Anita Schöbel

Published in: OASIcs, Volume 20, 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2011)


Abstract
In timetable information in public transport the goal is to search for a good passenger's path between an origin and a destination. Usually, the travel time and the number of transfers shall be minimized. In this paper, we consider robust timetable information, i.e. we want to identify a path which will bring the passenger to the planned destination even in the case of delays. The classic notion of strict robustness leads to the problem of identifying those changing activities which will never break in any of the expected delay scenarios. We show that this is in general a strongly NP-hard problem. Therefore, we propose a conservative heuristic which identifies a large subset of these robust changing activities in polynomial time by dynamic programming and so allows us to find strictly robust paths efficiently. We also transfer the notion of light robustness, originally introduced for timetabling, to timetable information. In computational experiments we then study the price of strict and light robustness: How much longer is the travel time of a robust path than of a shortest one according to the published schedule? Based on the schedule of high-speed trains within Germany of 2011, we quantitatively explore the trade-off between the level of guaranteed robustness and the increase in travel time. Strict robustness turns out to be too conservative, while light robustness is promising: a modest level of guarantees is achievable at a reasonable price for the majority of passengers.

Cite as

Marc Goerigk, Martin Knoth, Matthias Müller-Hannemann, Marie Schmidt, and Anita Schöbel. The Price of Robustness in Timetable Information. In 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 20, pp. 76-87, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{goerigk_et_al:OASIcs.ATMOS.2011.76,
  author =	{Goerigk, Marc and Knoth, Martin and M\"{u}ller-Hannemann, Matthias and Schmidt, Marie and Sch\"{o}bel, Anita},
  title =	{{The Price of Robustness in Timetable Information}},
  booktitle =	{11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{76--87},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-33-0},
  ISSN =	{2190-6807},
  year =	{2011},
  volume =	{20},
  editor =	{Caprara, Alberto and Kontogiannis, Spyros},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2011.76},
  URN =		{urn:nbn:de:0030-drops-32680},
  doi =		{10.4230/OASIcs.ATMOS.2011.76},
  annote =	{Keywords: strict and light robustness, delay scenarios, experimental study}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail