Browsing by Author "Bruns, David"

Now showing 1 - 1 of 1

Open Access
Optimal routing in public transportation networks using PHAST
(2024) Bruns, David
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.