Optimal routing in public transportation networks using PHAST

Abstract

Finding optimal routes in public transportation networks is a challenging and complex algorithmic task. Compared to routing in road networks, public transportation routing algorithms also have to take factors like schedules and transfer times into consideration. Because of this, shortest-path-algorithms that are used in road networks have to be modified in order to be useable in public transportation networks. One method that is used to calculate shortest paths in road maps is the PHAST approach. It makes use of hierarchical structures in transport networks to allow a fast and efficient computation. As shown in the study "A Fast and Tight Heuristic for A*" by Strasser and Zeitz, it can also be used as a heuristic for the A*-algorithm. Given that PHAST has been observed to have a good performance in road networks and A* being an algorithm that provides great flexibility, the question rises whether a combination of both could also be used in public transportation networks. This thesis presents the new algorithm PUBPHAST which combines the A*-Search Algorithm with the PHAST heuristic in a public transportation network context. It is experimentally explored whether A* in combination with PHAST also has similar performance advantages in public transportation networks as in road networks. To this end, openly available public transportation data in format of the GTFS is transformed into a fitting graph structure which serves as foundation for the algorithm. PUBPHAST is then compared to public transportation adjusted implementations of Dijkstra's algorithm and the Connection Scan Algorithm. It became clear that PUBPHAST is both faster than the Connection Scan Algorithm and Dijkstra's Algorithm, suggesting that hierarchical routing has performance advantages in public transportation networks.

Das Finden von optimalen Pfaden im öffentlichen Personenverkehr ist ein komplexer Themenbereich und aus algorithmischer Sicht eine herausfordernde Aufgabe. Im Gegensatz zur Routenplanung im Straßenverkehr müssen zum Beispiel auch Fahrpläne und Umstiegszeiten in Betracht gezogen werden. Deswegen können herkömmliche Distanzberechnungsverfahren für den Straßenverkehr nicht ohne weitere Modifizierung auch für den öffentlichen Personenverkehr verwendet werden. Eine Methode, die für die Distanzberechnung im Straßenverkehr entwickelt wurde, nennt sich PHAST. Dieses Verfahren nutzt hierarchische Strukturen im Transportnetz aus, um eine effiziente Distanzberechnung zu gewährleisten. Im Paper "A Fast and Tight Heuristic for A*" von Strasser und Zeitz wurde PHAST dazu verwendet, die Heuristikfunktion im A*-Algorithmus zu berechnen. Dieses Verfahren verknüpft die Flexibilät des A*-Algorithmus mit der Schnelligkeit des PHAST-Ansatzes. Ziel dieser Arbeit ist es daher, diese Kombination im Kontext von öffentlichen Personenverkehrnetzen zu implementieren. Es wird der neue Algorithmus PUBPHAST vorgestellt, der die beiden Ansätze A* und PHAST vereint. PUBPHAST wurde mittels GTFS-Daten getestet und anschließend mit anderen Routenplanungsverfahren für den öffentlichen Personenverkehr verglichen. Es hat sich herausgestellt, dass PUBPHAST sowohl im Vergleich zum Connection Scan Algorithmus als auch genenüber Dijsktra's Algorithmus Geschwindigkeitsvorteile bietet.