2026-07-20T01:24:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18366 2024-03-06T11:01:37Z ddc:004 open_access

Arc-Flags Meet Trip-Based Public Transit Routing Großmann, Ernestine Sauer, Jonas Schulz, Christian Steil, Patrick Public transit routing graph algorithms algorithm engineering We present Arc-Flag TB, a journey planning algorithm for public transit networks which combines Trip-Based Public Transit Routing (TB) with the Arc-Flags speedup technique. Compared to previous attempts to apply Arc-Flags to public transit networks, which saw limited success, our approach uses stronger pruning rules to reduce the search space. Our experiments show that Arc-Flag TB achieves a speedup of up to two orders of magnitude over TB, offering query times of less than a millisecond even on large countrywide networks. Compared to the state-of-the-art speedup technique Trip-Based Public Transit Routing Using Condensed Search Trees (TB-CST), our algorithm achieves similar query times but requires significantly less additional memory. Other state-of-the-art algorithms which achieve even faster query times, e.g., Public Transit Labeling, require enormous memory usage. In contrast, Arc-Flag TB offers a tradeoff between query performance and memory usage due to the fact that the number of regions in the network partition required by our algorithm is a configurable parameter. We also identify a previously undiscovered issue in the transfer precomputation of TB, which causes both TB-CST and Arc-Flag TB to answer some queries incorrectly. We provide discussion on how to resolve this issue in the future. Currently, Arc-Flag TB answers 1-6% of queries incorrectly, compared to over 20% for TB-CST on some networks. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ernestine Großmann and Jonas Sauer and Christian Schulz and Patrick Steil 2023 Is Part Of LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SEA.2023.16 urn:nbn:de:0030-drops-183664 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.16 eng https://creativecommons.org/licenses/by/4.0/legalcode