Multicriteria Trip-Based Public Transit Routing on Bitfield-Encoded Annual Timetables

Trip-based public transit routing (TBTR) [1] is a route planning algorithm that finds Pareto-optimal journeys in a public transit network based on a precomputed set of transfers. TBTR optimizes the two criteria of arrival time and number of transfers. To increase the supported time span of the timetable, [2] proposes the use of TBTR with bitfield-encoded timetables. However, no algorithmic details are given on how this approach can be realized. We address this issue by developing algorithms for TBTR on bitfield-encoded timetables in the form of pseudocode. To reduce the required preprocessing time, we show how line-based pruning (LB) [3], a preprocessing variant for TBTR, can be adapted for bitfield-encoded timetables. Since two criteria are insufficient to represent the diverse demands of passengers on the journey planning, we also present how the algorithms can be extended to allow for the optimization of the additional criteria of walking time and transfer class. To evaluate our approach, we use real-world annual timetables of Aachen, Berlin and Germany. LB preprocessing can be applied to bitfield-encoded TBTR to compute similar-sized transfer sets faster. On the Germany dataset it achieves a speedup of ≈ 3.9. Even though running time increases when a criterion is added, preprocessing for a whole year can still be done within hours. In comparison to a pre-existing implementation of RAPTOR [4], TBTR shows comparable median response times and longer worst-case response times for earliest arrival queries. However, the scaling behavior of TBTR is advantageous for profile queries. On the Germany dataset, TBTR answers 12 and 24-hour profile queries in approximately half the time of RAPTOR. While response times of queries with additional criteria are long on the Germany dataset, for the cities of Aachen and Berlin, they can be answered in under 2 seconds.

Trip-based public transit routing (TBTR) [1] ist ein Routenplanungsalgorithmus, der Pareto-optimale Reisen basierend auf einer vorberechneten Menge von Umstiegen findet. TBTR optimiert die beiden Kriterien Ankunftszeit und Anzahl der Umstiege. Um die unterstützte Zeitspanne des Fahrplans zu erhöhen, schlägt [2] vor TBTR mit bitfeldkodierten Fahrplänen zu verwenden. Es werden jedoch keine algorithmischen Einzelheiten angegeben wie dieser Ansatz realisiert werden kann. Wir gehen auf diese Frage ein, indem wir die Algorithmen für TBTR auf bitfeldkodierten Fahrplänen in Form von Pseudocode entwickeln. Um die notwendige Vorverarbeitungszeit zu reduzieren, zeigen wir wie Line-based Pruning (LB) [3], eine Variante der Vorverarbeitung für TBTR, an bitfeldkodierte Fahrpläne angepasst werden kann. Da zwei Kriterien nicht ausreichen, um die vielfältigen Anforderungen der Fahrgäste an die Reiseplanung abzubilden, zeigen wir auch, wie die Algorithmen erweitert werden können, um die Optimierung der zusätzlichen Kriterien Gehzeit und Umstiegsklasse zu ermöglichen. Zur Evaluierung unseres Ansatzes verwenden wir reale Jahresfahrpläne von Aachen, Berlin und Deutschland. LB kann auf bitfeldkodiertes TBTR angewendet werden, um eine gleich große Menge von Umstiegen schneller zu berechnen. Auf dem Datensatz Deutschlands erreicht es einen Speedup von ≈ 3.9. Zwar erhöht sich die Laufzeit, wenn ein Kriterium hinzugefügt wird, die Vorverarbeitung für ein ganzes Jahr kann aber immernoch innerhalb von Stunden erledigt werden. Im Vergleich mit einer bereits existierenden Implementierung von RAPTOR [4] zeigt TBTR vergleichbare Antwortzeiten im Median und längere maximale Antwortzeiten auf Anfragen nach der frühestmöglichen Ankunft. Jedoch ist das Skalierungsverhalten von TBTR bei Intervallanfragen vorteilhaft. Auf dem Datensatz Deutschlands beantwortet TBTR 12 und 24-Stunden-Intervallanfragen in ungefähr der Hälfte der Zeit von RAPTOR. Die Antwortzeiten auf Anfragen mit zusätlichen Kriterien sind lang auf den Datensatz Deutschlands, aber für die Städte Aachen und Berlin können sie in unter 2 Sekunden beantwortet werden.