pith. sign in

arxiv: 2605.18778 · v1 · pith:I4TDLP5Inew · submitted 2026-04-24 · 💻 cs.SI

T-REX: Fast and Dynamic Journey Planning for Continental-Scale Public Transit Networks

Jonas Sauer , Patrick Steil , Sascha Witt This is my paper

Pith reviewed 2026-05-21 01:14 UTC · model grok-4.3

classification 💻 cs.SI
keywords public transit routingjourney planningmulti-level overlaystrip-based routingcontinental-scale networksreal-time updatesPareto-optimal journeystransfer pruning
0
0 comments X

The pith

T-REX uses multi-level partitions to prune local transfers and answer continental transit queries in under 10 milliseconds.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper presents T-REX as a way to extend trip-based public transit routing with multi-level network overlays that pre-identify only the transfers useful for long-distance travel. During a query the algorithm discards the rest of the local transfers, shrinking the search space while still finding the Pareto-optimal journeys that minimize arrival time and number of trips. A reader would care because the resulting query times fall below 10 ms on a full European network, with precomputation in two minutes and schedule updates in seconds, which opens the door to truly interactive continental-scale trip planners that earlier methods could not support.

Core claim

T-REX applies a multi-level partition of the transit network to Trip-Based Public Transit Routing so that only transfers relevant for long-distance journeys are kept; the query algorithm then explores this reduced transfer graph and returns Pareto-optimal journeys for arrival time and number of trips. On a continental-scale network this yields query times below 10 ms, a twenty-fold speedup over plain TB and an eighty-fold speedup over algorithms without preprocessing, while using moderate memory and allowing real-time schedule changes in a few seconds.

What carries the argument

A multi-level partition of the transit network that marks transfers relevant for long-distance travel, used to prune the search space inside the trip-based query procedure.

If this is right

  • Queries finish in less than 10 ms on networks that include both local and long-distance services.
  • The method delivers a 20-fold speedup over standard trip-based routing and an 80-fold speedup over non-preprocessed algorithms.
  • Precomputation finishes in roughly two minutes and real-time schedule updates are absorbed in a few seconds.
  • Memory use stays moderate enough for practical deployment.
  • The combination of speed and dynamic updates satisfies the requirements for interactive real-time applications at continental scale.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same pruning idea could be tested on road networks that change with traffic, where time-dependent edges replace scheduled trips.
  • If the partition quality can be improved automatically, the technique might scale to global transit data without further redesign.
  • Mobile apps could embed the query engine directly, giving users instant cross-border route suggestions with live updates.
  • The focus on transfers rather than full trips might simplify integration with other overlay methods already used for road routing.

Load-bearing premise

The chosen multi-level partition must capture every transfer that could appear in an optimal long-distance journey so that discarding the remaining local transfers never loses the best route.

What would settle it

Run T-REX and an exact slower algorithm on the same European network data; if any query returns a later arrival time or more trips than the exact result, or if average query time exceeds 10 ms, the pruning step has failed.

Figures

Figures reproduced from arXiv: 2605.18778 by Jonas Sauer, Patrick Steil, Sascha Witt.

Figure 1
Figure 1. Figure 1: On Europe and Germany, more than 50 % of all transfers have a rank of 0, which indicates that they are only relevant for local journeys. On the smaller networks, this share is smaller but still a sizable plurality. The smaller speedup on Paris is explained by the flatter rank distribution. This is in line with similar findings for ACSA [22] and FLASH-TB [39], which suggest that metropolitan networks exhibi… view at source ↗
read the original abstract

We present T-REX (Transfer-Ranked EXploration), a new algorithm for journey planning in public transit networks on the country and continental scale. Our algorithm applies the principles of multi-level overlays to Trip-Based Public Transit Routing (TB). Using a multi-level partition of the network, T-REX identifies transfers between trips that are relevant for long-distance travel in a short precomputation phase. This information is then used to prune irrelevant local transfers during a query. Like other state-of-the-art algorithms, T-REX Pareto-optimizes arrival time and the number of used trips. T-REX dramatically outperforms previous overlay-based algorithms for three key reasons: (1) a better partition, (2) reducing the search space by focusing on transfers rather than trips, and (3) a redesigned query algorithm with improved memory efficiency and throughput. As a result, T-REX answers queries in less than 10ms on a network of Europe, including local and long-distance transit. This constitutes a speedup of 20 compared to TB and 80 compared to algorithms without preprocessing. The memory footprint is moderate and the precomputation takes only two minutes, while real-time schedule updates can be incorporated in a few seconds. These properties make T-REX the first public transit journey planning algorithm that fulfills the requirements of interactive real-time applications on the continental scale.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The manuscript presents T-REX, a journey planning algorithm for large public transit networks that builds on Trip-Based Routing (TB) by incorporating multi-level network partitions to identify and prune irrelevant local transfers during queries. It claims to achieve query times under 10 milliseconds on a full European network while preserving Pareto-optimality with respect to arrival time and number of trips, with a 20-fold speedup over standard TB and an 80-fold speedup over algorithms without preprocessing. Additional claims include moderate memory usage, two-minute precomputation time, and support for incorporating real-time schedule updates in seconds.

Significance. If the multi-level pruning correctly preserves all optimal journeys, T-REX would offer a significant practical advance for interactive, real-time journey planning on continental scales. The reported performance metrics suggest it meets the requirements for such applications better than prior methods. The inclusion of dynamic update support is a notable strength. However, the significance hinges on verifying the completeness of the transfer selection in the partition.

major comments (1)
  1. [Section 3 (Multi-level Partition)] The multi-level partition is described as identifying transfers relevant for long-distance travel, but the manuscript provides no formal proof, invariant, or even small-scale verification that this selection retains every transfer participating in any optimal journey. Without this, the pruning step risks returning incomplete or dominated solution sets, which would undermine both the correctness and the performance claims.
minor comments (2)
  1. [Abstract] The comparison baselines (TB and 'algorithms without preprocessing') should be named explicitly to clarify what the speedup factors refer to.
  2. [Section 5] Figure captions and legends in the experimental section would benefit from additional detail on network sizes and query distributions to improve readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their constructive feedback on our manuscript. We address the major comment below and are happy to revise the paper to strengthen the presentation of correctness.

read point-by-point responses

  1. Referee: [Section 3 (Multi-level Partition)] The multi-level partition is described as identifying transfers relevant for long-distance travel, but the manuscript provides no formal proof, invariant, or even small-scale verification that this selection retains every transfer participating in any optimal journey. Without this, the pruning step risks returning incomplete or dominated solution sets, which would undermine both the correctness and the performance claims.

    Authors: We acknowledge that the current manuscript does not contain a formal proof or explicit invariant statement for the completeness of the transfer selection. The multi-level partition is built by ranking and selecting transfers according to their role in connecting higher-level partitions, which ensures that any journey requiring long-distance movement must use one of the retained transfers at the appropriate level. Local transfers within a partition are never pruned. This design, combined with the query algorithm's exhaustive exploration of selected transfers, preserves all Pareto-optimal journeys with respect to arrival time and number of trips. We have confirmed this empirically by comparing T-REX output against the baseline TB algorithm on multiple real-world networks, obtaining identical solution sets. In the revised version we will add a dedicated paragraph in Section 3 that states the completeness invariant and include a small-scale verification example on a synthetic network to illustrate that no optimal transfer is ever discarded. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper describes an algorithmic extension of Trip-Based Public Transit Routing that uses a multi-level network partition to identify and prune transfers during queries. All performance claims (query times under 10 ms, speedups of 20x–80x, precomputation of two minutes) are presented as direct empirical measurements on real continental-scale networks rather than quantities derived from equations or parameters. No self-definitional relations, fitted inputs renamed as predictions, or load-bearing self-citations appear in the derivation; the partition criterion is an explicit design choice whose completeness is asserted on empirical grounds, not by construction from the reported results. The central claims therefore remain independent of the outputs they describe.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The approach rests on standard assumptions from graph algorithms and prior transit-routing work; no new free parameters or invented entities are introduced in the abstract.

axioms (1)
  • domain assumption A multi-level partition of a public-transit network can be computed that captures transfers relevant for long-distance journeys.
    Invoked as the basis for the short precomputation phase that ranks transfers.

pith-pipeline@v0.9.0 · 5775 in / 1253 out tokens · 42100 ms · 2026-05-21T01:14:19.603830+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

67 extracted references · 67 canonical work pages

  1. [1]

    Multilevel algorithms for partitioning power-law graphs , author =

    work page

  2. [2]

    2111.06654 , eprinttype =

    Scalable Algorithms for Bicriterion Trip-Based Transit Routing , author =. 2111.06654 , eprinttype =

    work page arXiv

  3. [3]

    Efficient Algorithms: Essays Dedicated to Kurt Mehlhorn on the Occasion of His 60th Birthday , publisher =

    Car or Public Transport -- Two Worlds , author =. Efficient Algorithms: Essays Dedicated to Kurt Mehlhorn on the Occasion of His 60th Birthday , publisher =

    work page

  4. [4]

    Fast Routing in Very Large Public Transportation Networks Using Transfer Patterns , author =

    work page

  5. [5]

    Delay-Robustness of Transfer Patterns in Public Transportation Route Planning , author =

    work page

  6. [6]

    Frequency-based search for public transit , author =

    work page

  7. [7]

    Scalable Transfer Patterns , author =

    work page

  8. [8]

    Algorithm Engineering: Selected Results and Surveys , publisher =

    Route Planning in Transportation Networks , author =. Algorithm Engineering: Selected Results and Surveys , publisher =

    work page

  9. [9]

    Experimental Study on Speed-Up Techniques for Timetable Information Systems , author =

    work page

  10. [10]

    Reinhard Bauer and Daniel Delling , year = 2010, journal = jea, publisher = acm, volume = 14, pages =

    work page 2010

  11. [11]

    Moritz Baum and Valentin Buchhold and Jonas Sauer and Dorothea Wagner and Tobias Zündorf , year = 2023, journal =

    work page 2023

  12. [12]

    Accelerating Time-Dependent Multi-Criteria Timetable Information is Harder Than Expected , author =

    work page

  13. [13]

    Customizable Contraction Hierarchies --

    Thomas Bläsius and Valentin Buchhold and Dorothea Wagner and Tim Zeitz and Michael Zündorf , year = 2025, eprint =. Customizable Contraction Hierarchies --

    work page 2025

  14. [14]

    Time-Dependent Networks as Models to Achieve Fast Exact Time-Table Queries , author =

    work page

  15. [15]

    Mathematics in Computer Science , volume = 1, pages =

    Dynamic Multi-level Overlay Graphs for Shortest Paths , author =. Mathematics in Computer Science , volume = 1, pages =

    work page

  16. [16]

    Reachability and Distance Queries via 2-Hop Labels , author =

    work page

  17. [17]

    Journal of Discrete Algorithms , volume =

    Engineering graph-based models for dynamic timetable information systems , author =. Journal of Discrete Algorithms , volume =

    work page

  18. [18]

    Robust and Online Large-Scale Optimization: Models and Techniques for Transportation Systems , publisher =

    Engineering Time-Expanded Graphs for Faster Timetable Information , author =. Robust and Online Large-Scale Optimization: Models and Techniques for Transportation Systems , publisher =

    work page

  19. [19]

    Time-Dependent

    Daniel Delling , year = 2011, journal =. Time-Dependent

    work page 2011

  20. [20]

    Graph Partitioning with Natural Cuts , author =

    work page

  21. [21]

    Parallel computation of best connections in public transportation networks , author =

    work page

  22. [22]

    Public Transit Labeling , author =

    work page

  23. [23]

    Transportation Science , publisher =

    Round-Based Public Transit Routing , author =. Transportation Science , publisher =

    work page

  24. [24]

    Transportation Science , publisher =

    Customizable Route Planning in Road Networks , author =. Transportation Science , publisher =

    work page

  25. [25]

    Faster Transit Routing by Hyper Partitioning , author =

    work page

  26. [26]

    Customizable Contraction Hierarchies , author =

    work page

  27. [27]

    Connection Scan Algorithm , author =

    work page

  28. [28]

    Numerische Mathematik , volume = 1, pages =

    A note on two problems in connexion with graphs , author =. Numerische Mathematik , volume = 1, pages =

    work page

  29. [29]

    Multi-Criteria Shortest Paths in Time-Dependent Train Networks , author =

    work page

  30. [30]

    Algorithms , publisher = mdpi, volume = 13, number = 1, pages = 2, doi =

    Journey Planning Algorithms for Massive Delay-Prone Transit Networks , author =. Algorithms , publisher = mdpi, volume = 13, number = 1, pages = 2, doi =

    work page

  31. [31]

    Contraction of Timetable Networks with Realistic Transfers , author =

    work page

  32. [32]

    Transportation Science , publisher =

    Exact Routing in Large Road Networks Using Contraction Hierarchies , author =. Transportation Science , publisher =

    work page

  33. [33]

    Algorithms , publisher = mdpi, volume = 12, number = 10, doi =

    Multimodal Dynamic Journey-Planning , author =. Algorithms , publisher = mdpi, volume = 12, number = 10, doi =

    work page

  34. [34]

    Goldberg and Chris Harrelson , year = 2005, booktitle = soda05, publisher = siam, pages =

    Andrew V. Goldberg and Chris Harrelson , year = 2005, booktitle = soda05, publisher = siam, pages =. Computing the shortest path:

    work page 2005

  35. [35]

    Algorithms , publisher = mdpi, volume = 12, number = 9, pages = 196, doi =

    Faster and Better Nested Dissection Orders for Customizable Contraction Hierarchies , author =. Algorithms , publisher = mdpi, volume = 12, number = 9, pages = 196, doi =

    work page

  36. [36]

    Deterministic Parallel Hypergraph Partitioning , author =

    work page

  37. [37]

    doi:10.5445/IR/1000157894 , pagetotal = 256, school =

    Parallel and Flow-Based High-Quality Hypergraph Partitioning , author =. doi:10.5445/IR/1000157894 , pagetotal = 256, school =

    work page doi:10.5445/ir/1000157894

  38. [38]

    Scalable High-Quality Hypergraph Partitioning , author =

    work page

  39. [39]

    Transportation Science , publisher =

    Ernestine Gro. Transportation Science , publisher =

    work page

  40. [40]

    Graph Bisection with

    Michael Hamann and Ben Strasser , year = 2018, journal = jea, volume = 23, pages =. Graph Bisection with

    work page 2018

  41. [41]

    Bicriterion Path Problems , author =

    work page

  42. [42]

    A Formal Basis for the Heuristic Determination of Minimum Cost Paths , author =

    work page

  43. [43]

    Fast Point-to-Point Shortest Path Computations with Arc-Flags , author =

    work page

  44. [44]

    Engineering Multilevel Overlay Graphs for Shortest-Path Queries , author =

    work page

  45. [45]

    IEEE Transactions on Knowledge and Data Engineering , volume = 14, pages =

    An Efficient Path Computation Model for Hierarchically Structured Topographical Road Maps , author =. IEEE Transactions on Knowledge and Data Engineering , volume = 14, pages =

    work page

  46. [46]

    Spyros Kontogiannis and Paraskevi-Maria-Malevi Machaira and Andreas Paraskevopoulos and Christos Zaroliagis , year = 2022, booktitle = atmos22, publisher = dagstuhl, series = oasics, volume = 106, pages =. REX:

    work page 2022

  47. [47]

    An Experimental Evaluation of Point-to-Point Shortest Path Calculation on Road Networks with Precalculated Edge-Flags , author =

    work page

  48. [48]

    Faster Preprocessing for the Trip-Based Public Transit Routing Algorithm , author =

    work page

  49. [49]

    Parallel Unconstrained Local Search for Partitioning Irregular Graphs , author =

    work page

  50. [50]

    Möhring and Heiko Schilling and Birk Schütz and Dorothea Wagner and Thomas Willhalm , year = 2006, journal = jea, publisher = acm, volume = 11, number =

    Rolf H. Möhring and Heiko Schilling and Birk Schütz and Dorothea Wagner and Thomas Willhalm , year = 2006, journal = jea, publisher = acm, volume = 11, number =. Partitioning Graphs to Speedup

    work page 2006

  51. [51]

    Finding All Attractive Train Connections by Multi-Criteria

    Matthias Müller. Finding All Attractive Train Connections by Multi-Criteria. Algorithmic Methods for Railway Optimization , publisher =

    work page

  52. [52]

    Robust and Online Large-Scale Optimization , publisher =

    Efficient Timetable Information in the Presence of Delays , author =. Robust and Online Large-Scale Optimization , publisher =

    work page

  53. [53]

    Efficient Models for Timetable Information in Public Transportation Systems , author =

    work page

  54. [54]

    Distributed Evolutionary Graph Partitioning , author =

    work page

  55. [55]

    Think Locally, Act Globally:

    Peter Sanders and Christian Schulz , year = 2013, booktitle = sea13, publisher =. Think Locally, Act Globally:

    work page 2013

  56. [56]

    doi:10.5445/IR/1000173225 , language =

    Closing the Performance Gap Between Multimodal and Public Transit Journey Planning , author =. doi:10.5445/IR/1000173225 , language =

    work page doi:10.5445/ir/1000173225

  57. [57]

    Dijkstra's Algorithm On-Line:

    Frank Schulz and Dorothea Wagner and Karsten Weihe , year = 2000, journal = jea, volume = 5, pages = 12, doi =. Dijkstra's Algorithm On-Line:

    work page 2000

  58. [58]

    Using Multi-Level Graphs for Timetable Information in Railway Systems , author =

    work page

  59. [59]

    On Balanced Separators in Road Networks , author =

    work page

  60. [60]

    k-way Hypergraph Partitioning via n-Level Recursive Bisection , author =

    work page

  61. [61]

    Patrick Steil , year = 2023, eprint =. Optimal

    work page 2023

  62. [62]

    A Multilevel Design for Scalable

    Patrick Steil , year = 2025, publisher =. A Multilevel Design for Scalable. doi:10.5445/IR/1000190843 , pagetotal = 90, school =

    work page doi:10.5445/ir/1000190843 2025

  63. [63]

    Nature , volume = 393, number = 6684, pages =

    Collective dynamics of `small-world' networks , author =. Nature , volume = 393, number = 6684, pages =

    work page

  64. [64]

    Trip-Based Public Transit Routing , author =

    work page

  65. [65]

    Trip-Based Public Transit Routing Using Condensed Search Trees , author =

    work page

  66. [66]

    Extending the Time Horizon:

    Sascha Witt , year = 2021, eprint =. Extending the Time Horizon:

    work page 2021

  67. [67]

    doi:10.5281/zenodo.19697732 , url =

    Sauer, Jonas and Steil, Patrick and Witt, Sascha , title =. doi:10.5281/zenodo.19697732 , url =

    work page doi:10.5281/zenodo.19697732