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

Annabell Berger, Daniel Delling, Andreas Gebhardt & Matthias Müller-Hannemann
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...