Stochastic strategies for public transport journeys based on realtime delay predictions

Abstract

Journey planning in public transport networks is inherently stochastic, not only in case of delays. Classical pareto-optimal algorithms do not take into account reliability of transfers and alternative continuations. In addition to the static timetable, we incorporate discrete departure and arrival time distributions and cancellation probabilities for all connections, which are estimated based on given non-stochastic realtime delay predictions. For a query, given a transfer strategy minimizing the mean destination arrival time, entire destination arrival distributions are propagated through the network. This induces a set of alternative continuations at the origin and all possible intermediate stops. Our stochastic algorithm takes well below one second on the complete timetable of Switzerland when using heuristic approaches, depending on the exact variant. Compared to a user following a fixed journey returned by a classical non-stochastic algorithm, a nimble user may arrive on average 9.5 minutes earlier with our algorithm. However, depending on the assumed transfer times and with continuous updates from the non-stochastic algorithm, the gains may also become negligible. Compared to another stochastic approach, CSA MEAT from Dibbelt et al., about three minutes are gained on average. Our algorithm will be particularly helpful for flexible users in more delay-prone environments. Routenberechnung in öffentlichen Verkehrsnetzen ist grundsätzlich stochastischer Natur, nicht nur im Falle von Verspätungen. Klassische, pareto-optimale Algorithmen berücksichtigen die Zuverlässigkeit von Umstiegen und alternative Anschlüsse nicht. Daher beziehen wir zusätzlich zum statischen Fahrplan diskrete Verteilungen der Abfahrts- und Ankunftszeiten sowie Ausfallwahrscheinlichkeiten für alle Verbindungen mit ein, die auf Basis gegebener nicht-stochastischer Echtzeit-Verspätungsvorhersagen zugewiesen werden. Für eine Anfrage von Start nach Ziel werden anhand einer Umstiegsstrategie, die die durchschnittliche Zielankunftszeit minimiert, vollständige Verteilungen der Zielankunftszeit durch das Netz propagiert. Daraus erwachsen alternative Verbindungen an der Startstation und an allen Zwischenstationen. Unser stochastischer Algorithmus benötigt deutlich weniger als eine Sekunde auf dem gesamten Fahrplan der Schweiz, mit heuristi-schen Ansätzen abhängig von der betrachteten Variante. Verglichen mit einem Benutzer, der einer festen Route laut einem klassischen, nicht-stochastischen Algorithmus folgt, kann ein behänder Benutzer mit unserem Algorithmus durchschnittlich 9,5 Minuten früher ankommen. Allerdings kann die Zeiteinsparung abhängig von den angenommenen Umsteigezeiten und mit fortlaufenden Aktualisierungen des nicht-stochastischen Algorithmus auch vernachlässigbar werden. Verglichen mit einem anderen stochastischen Ansatz, CSA MEAT von Dibbelt et al., können durchschnittlich etwa drei Minuten eingespart werden. Unser Algorithmus wird besonders für flexible Nutzer in verspätungsanfälligeren Umgebungen hilfreich sein.