Can I read Arc-Flags Meet Trip-Based Public Transit Routing on EtoBox?

Arc-Flags Meet Trip-Based Public Transit Routing by Großmann, Ernestine; Sauer, Jonas; Schulz, Christian; Steil, Patrick is a scholarly article available to read on EtoBox.

What is Arc-Flags Meet Trip-Based Public Transit Routing about?

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 an issue in the transfer precomputation of TB that affects both TB-CST and Arc-Flag TB, lead

Author

Großmann, Ernestine; Sauer, Jonas; Schulz, Christian; Steil, Patrick

Published

2023

Language

EN