Title: Connection Scan Algorithm,
Abstract: We introduce the Connection Scan Algorithm (CSA) to efficiently answer
queries to timetable information systems. The input consists, in the simplest
setting, of a source position and a desired target position. The output consist
is a sequence of vehicles such as trains or buses that a traveler should take
to get from the source to the target. We study several problem variations such
as the earliest arrival and profile problems. We present algorithm variants
that only optimize the arrival time or additionally optimize the number of
transfers in the Pareto sense. An advantage of CSA is that is can easily adjust
to changes in the timetable, allowing the easy incorporation of known vehicle
delays. We additionally introduce the Minimum Expected Arrival Time (MEAT)
problem to handle possible, uncertain, future vehicle delays. We present a
solution to the MEAT problem that is based upon CSA. Finally, we extend CSA
using the multilevel overlay paradigm to answer complex queries on nation-wide
integrated timetables with trains and buses.