Connection Scan Accelerated

We study the problem of efficiently computing journeys intimetable networks. Our algorithm optimally answers profilequeries, computing all journeys given a time interval. Ourstudy demonstrates that queries can be answered optimallyon large country-scale timetable networks within severalmilliseconds and fast delay integration is possible. Previouswork either had to drop optimality or only consideredcomparatively small timetable networks. Our technique isa combination of the Connection Scan Algorithm and multi-level overlay graphs.