T-REX algorithm plans European transit routes in under 10ms

T-REX (Transfer-Ranked EXploration) is a new algorithm for journey planning in public transit networks that achieves unprecedented speed on continental scales. Developed by Jonas Sauer, Patrick Steil, and Sascha Witt, T-REX builds on Trip-Based Public Transit Routing (TB) by applying multi-level overlays. It precomputes relevant transfers between trips for long-distance travel in just two minutes, then during a query prunes local transfers that are irrelevant for the journey. The algorithm Pareto-optimizes arrival time and number of trips used, matching the output quality of existing methods while dramatically reducing search space. On the full European public transit network (including local and long-distance services), T-REX answers queries in less than 10 milliseconds—a 20x speedup over TB and an 80x speedup over algorithms without any preprocessing. Memory footprint is moderate, and real-time schedule updates (e.g., for delays or cancellations) can be incorporated in a few seconds.

Three key innovations set T-REX apart from prior overlay-based approaches: (1) a superior partition of the network that better isolates local and long-distance travel, (2) focusing precomputation on transfers between trips rather than on trips themselves, which reduces the size of the overlay graph, and (3) a redesigned query algorithm with improved memory efficiency and throughput. These properties make T-REX the first public transit journey planning algorithm that meets the requirements of interactive real-time applications on a continental scale. Potential use cases include powering journey planners in apps like Google Maps, Transit, or city-specific apps, where users expect instant responses even for cross-border trips. The algorithm also opens the door to dynamic features like live delay updates without recomputing the entire database.