TY - JOUR

T1 - The price of strict and light robustness in timetable information

AU - Goerigk, Marc

AU - Schmidt, Marie

AU - Schöbel, Anita

AU - Knoth, Martin

AU - Müller-Hannemann, Matthias

PY - 2014

Y1 - 2014

N2 - 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, we consider robust timetable information; i.e., we want to identify a path that 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 transfer activities that 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 strictly robust transfer activities in polynomial time by dynamic programming and so allows us to efficiently find strictly robust paths. 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 2011 train schedule within Germany, 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, whereas 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 path between an origin and a destination. Usually, the travel time and the number of transfers will be minimized. In this paper, we consider robust timetable information; i.e., we want to identify a path that 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 transfer activities that 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 strictly robust transfer activities in polynomial time by dynamic programming and so allows us to efficiently find strictly robust paths. 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 2011 train schedule within Germany, 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, whereas 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.1287/trsc.2013.0470

DO - 10.1287/trsc.2013.0470

M3 - Journal article

AN - SCOPUS:84902689847

VL - 48

SP - 225

EP - 242

JO - Transportation Science

JF - Transportation Science

SN - 0041-1655

IS - 2

ER -