RECORD
Arc-Flags Meet Trip-Based Public Transit Routing
Data Structures and Algorithms · Submitted 14 Feb 2023
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim 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.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
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, leading to incorrect answers for some queries. This has not been previously recognized by the author of TB-CST. 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.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | 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. | contribution 0.99 | 0.88 | 0.08 | asserted 1.00 |
| s1 | 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. | contribution 0.64 | 0.43 | 0.06 | asserted 1.00 |
| s2 | 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. | result 1.00 | 0.97 | 0.49 | asserted 1.00 |
| s3 | 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. | result 1.00 | 0.91 | 0.19 | asserted 1.00 |
| s4 | Other state-of-the-art algorithms which achieve even faster query times, e.g., Public Transit Labeling, require enormous memory usage. | background 0.60 | 0.18 | 0.05 | asserted 1.00 |
| s5 | 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. | interpretation 0.64 | 0.78 | 0.14 | asserted 1.00 |
| s6 | We also identify an issue in the transfer precomputation of TB that affects both TB-CST and Arc-Flag TB, leading to incorrect answers for some queries. | limitation 0.47 | 0.94 | 0.12 | asserted 1.00 |
| s7 | This has not been previously recognized by the author of TB-CST. | gap 0.89 | 0.28 | 0.03 | asserted 1.00 |
| s8 | We provide discussion on how to resolve this issue in the future. | future work 0.98 | 0.75 | 0.04 | asserted 0.59 |
| s9 | Currently, Arc-Flag TB answers 1-6% of queries incorrectly, compared to over 20% for TB-CST on some networks. | result 0.71 | 0.90 | 0.13 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
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, leading to incorrect answers for some queries. This has not been previously recognized by the author of TB-CST. 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.
Human review
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.