Accelerating Time-Dependent Multi-Criteria Timetable Information is Harder Than Expected

Abstract

Speeding up multi-criteria search in real timetable information systems
remains a challenge in spite of impressive progress achieved in recent years
for related problems in road networks.
Our goal is to perform multi-criteria range queries, that is, to find all 
Pareto-optimal connections with respect to travel time and number of transfers 
within a given start time interval. This problem can be modeled as a path 
search problem in a time- and event-dependent graph. In this paper, we investigate two key speed-up techniques for a multi-criteria variant of \textsc{Dijkstra}'s algorithm --- arc flags and contraction --- which seem to be strong candidates for railway networks, too. 
We describe in detail how these two techniques have to be adapted for a multi-criteria scenario and explain why we can expect only marginal speed-ups (compared to observations in road networks) from a direct implementation. Based on these insights we extend traditional arc-flags to \emph{time-period flags} and introduce \emph{route contraction} as a substitute for node contraction.
A computational study on real queries demonstrates that these techniques 
combined with goal-directed search lead to a speed-up of factor 13.08 over the baseline variant for range queries for a full day.