The Price of Strict and Light Robustness in Timetable Information

In timetable information in public transport the goal is to search for a good path between an origin and a destination. Usually, the travel time and the number of transfers will be minimized. In this paper, the authors consider robust timetable information; i.e., they want to identify a path that will bring the passenger to the planned destination even in the case of delays. The classic no`tion of strict robustness leads to the problem of identifying those transfer activities that will never break in any of the expected delay scenarios. The authors show that this is, in general, a strongly non-deterministic polynomial-time (NP)-hard problem. Therefore, the authors propose a conservative heuristic which identifies a large subset of these strictly robust transfer activities in polynomial time by dynamic programming and so allows us to efficiently find strictly robust paths. The authors also transfer the notion of light robustness, originally introduced for timetabling, to timetable information. In computational experiments the authors 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 2011 train schedule within Germany, the authors 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, whereas light robustness is promising: a modest level of guarantees is achievable at a reasonable price for the majority of passengers.

• Record URL:
  https://doi.org/10.1287/trsc.2013.0470
• Record URL:
  http://pubsonline.informs.org/doi/abs/10.1287/trsc.2013.0470
• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/oclc/1767714
• Supplemental Notes:
  • Abstracts reprinted with permission of INFORMS (Institute for Operations Research and the Management Sciences, http://www.informs.org).
• Authors:
  • Goerigk, Marc
  • Schmidt, Marie
  • Schöbel, Anita
  • Knoth, Martin
  • Müller-Hannemann, Matthias
• Publication Date: 2014-5

Language

• English

Media Info

• Media Type: Web
• Features: Figures; References; Tables;
• Pagination: pp 225-242
• Serial:
  • Transportation Science
  • Volume: 48
  • Issue Number: 2
  • Publisher: Institute for Operations Research and the Management Sciences (INFORMS)
  • ISSN: 0041-1655
  • Serial URL: http://transci.journal.informs.org/

Subject/Index Terms

• TRT Terms: Dynamic programming; Prices; Public transit; Timetables; Travel time
• Geographic Terms: Germany
• Subject Areas: Planning and Forecasting; Public Transportation; I72: Traffic and Transport Planning;

Filing Info

• Accession Number: 01526735
• Record Type: Publication
• Files: TRIS
• Created Date: May 29 2014 10:15AM