Standard
The price of robustness in timetable information. /
Goerigk, Marc; Knoth, Martin; Müller-Hannemann, Matthias et al.
11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. ed. / Alberto Caprara; Spyros Kontogiannis. Dagstuhl: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2011. p. 76-87 (OpenAccess Series in Informatics (OASIcs); Vol. 20).
Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Conference contribution/Paper › peer-review
Harvard
Goerigk, M, Knoth, M, Müller-Hannemann, M, Schmidt, M & Schöbel, A 2011,
The price of robustness in timetable information. in A Caprara & S Kontogiannis (eds),
11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. OpenAccess Series in Informatics (OASIcs), vol. 20, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Dagstuhl, pp. 76-87, 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2011, Saarbrucken, Germany,
8/09/11.
https://doi.org/10.4230/OASIcs.ATMOS.2011.76
APA
Goerigk, M., Knoth, M., Müller-Hannemann, M., Schmidt, M., & Schöbel, A. (2011).
The price of robustness in timetable information. In A. Caprara, & S. Kontogiannis (Eds.),
11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (pp. 76-87). (OpenAccess Series in Informatics (OASIcs); Vol. 20). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing.
https://doi.org/10.4230/OASIcs.ATMOS.2011.76
Vancouver
Goerigk M, Knoth M, Müller-Hannemann M, Schmidt M, Schöbel A.
The price of robustness in timetable information. In Caprara A, Kontogiannis S, editors, 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Dagstuhl: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2011. p. 76-87. (OpenAccess Series in Informatics (OASIcs)). doi: 10.4230/OASIcs.ATMOS.2011.76
Author
Goerigk, Marc ; Knoth, Martin ; Müller-Hannemann, Matthias et al. /
The price of robustness in timetable information. 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. editor / Alberto Caprara ; Spyros Kontogiannis. Dagstuhl : Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2011. pp. 76-87 (OpenAccess Series in Informatics (OASIcs)).
Bibtex
@inproceedings{26bc401ee0c04a4b83393630832acb39,
title = "The price of robustness in timetable information",
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.",
keywords = "Delay scenarios, Experimental study, Strict and light robustness",
author = "Marc Goerigk and Martin Knoth and Matthias M{\"u}ller-Hannemann and Marie Schmidt and Anita Sch{\"o}bel",
year = "2011",
doi = "10.4230/OASIcs.ATMOS.2011.76",
language = "English",
isbn = "9783939897330",
series = "OpenAccess Series in Informatics (OASIcs)",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
pages = "76--87",
editor = "Alberto Caprara and Spyros Kontogiannis",
booktitle = "11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems",
note = "11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2011 ; Conference date: 08-09-2011 Through 08-09-2011",
}
RIS
TY - GEN
T1 - The price of robustness in timetable information
AU - Goerigk, Marc
AU - Knoth, Martin
AU - Müller-Hannemann, Matthias
AU - Schmidt, Marie
AU - Schöbel, Anita
PY - 2011
Y1 - 2011
N2 - 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.
AB - 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.
KW - Delay scenarios
KW - Experimental study
KW - Strict and light robustness
U2 - 10.4230/OASIcs.ATMOS.2011.76
DO - 10.4230/OASIcs.ATMOS.2011.76
M3 - Conference contribution/Paper
AN - SCOPUS:84882979708
SN - 9783939897330
T3 - OpenAccess Series in Informatics (OASIcs)
SP - 76
EP - 87
BT - 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems
A2 - Caprara, Alberto
A2 - Kontogiannis, Spyros
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
CY - Dagstuhl
T2 - 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2011
Y2 - 8 September 2011 through 8 September 2011
ER -