Connection Scan Accelerated
Ben Strasser, Dorothea Wagner · Society for Industrial and Applied Mathematics eBooks · 2013
We study the problem of efficiently computing journeys in timetable networks. Our algorithm optimally answers profile queries, computing all journeys given a time interval. Our study demonstrates that queries can be answered optimally on large country-scale timetable networks within several milliseconds and fast delay integration is possible. Previous work either had to drop optimality or only considered comparatively small timetable networks. Our technique is a combination of the Connection Scan Algorithm and multilevel overlay graphs.