Search Results

Documents authored by Steil, Patrick

Artifact
Software
DOI: 10.4230/artifacts.27611
PatrickSteil/TREX

Authors: Jonas Sauer, Patrick Steil, and Sascha Witt

Abstract
Cite as

Jonas Sauer, Patrick Steil, Sascha Witt. PatrickSteil/TREX (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@misc{githubGitHubPatrickSteilTREX,
   title = {{PatrickSteil/TREX}}, 
   author = {Sauer, Jonas and Steil, Patrick and Witt, Sascha},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:098c3810dedbdf093d9ae741f0b3183c5fbd65e8;origin=https://github.com/PatrickSteil/TREX;visit=swh:1:snp:cb8162a048ffb76342d2404c1e0d39464a2f01c6;anchor=swh:1:rev:5bb80b427759862608a959821341ca3a8b2a2612}{\texttt{swh:1:dir:098c3810dedbdf093d9ae741f0b3183c5fbd65e8}} (visited on 2026-08-25)},
   url = {https://github.com/PatrickSteil/TREX},
   doi = {10.4230/artifacts.27611},
}
Document
DOI: 10.4230/LIPIcs.ESA.2026.9
T-REX: Fast and Dynamic Journey Planning for Continental-Scale Public Transit Networks

Authors: Jonas Sauer, Patrick Steil, and Sascha Witt

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

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.
Cite as

Jonas Sauer, Patrick Steil, and Sascha Witt. T-REX: Fast and Dynamic Journey Planning for Continental-Scale Public Transit Networks. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 9:1-9:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{sauer_et_al:LIPIcs.ESA.2026.9,
  author =	{Sauer, Jonas and Steil, Patrick and Witt, Sascha},
  title =	{{T-REX: Fast and Dynamic Journey Planning for Continental-Scale Public Transit Networks}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{9:1--9:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.9},
  URN =		{urn:nbn:de:0030-drops-271458},
  doi =		{10.4230/LIPIcs.ESA.2026.9},
  annote =	{Keywords: Public transit routing, graph algorithms, algorithm engineering}
}
Document
DOI: 10.4230/LIPIcs.SEA.2023.16
Arc-Flags Meet Trip-Based Public Transit Routing

Authors: Ernestine Großmann, Jonas Sauer, Christian Schulz, and Patrick Steil

Published in: LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023)

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 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.
Cite as

Ernestine Großmann, Jonas Sauer, Christian Schulz, and Patrick Steil. Arc-Flags Meet Trip-Based Public Transit Routing. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{gromann_et_al:LIPIcs.SEA.2023.16,
  author =	{Gro{\ss}mann, Ernestine and Sauer, Jonas and Schulz, Christian and Steil, Patrick},
  title =	{{Arc-Flags Meet Trip-Based Public Transit Routing}},
  booktitle =	{21st International Symposium on Experimental Algorithms (SEA 2023)},
  pages =	{16:1--16:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-279-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{265},
  editor =	{Georgiadis, Loukas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.16},
  URN =		{urn:nbn:de:0030-drops-183664},
  doi =		{10.4230/LIPIcs.SEA.2023.16},
  annote =	{Keywords: Public transit routing, graph algorithms, algorithm engineering}
}

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact