Search Results

Documents authored by Witt, Sascha

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.ESA.2017.9
In-Place Parallel Super Scalar Samplesort (IPSSSSo)

Authors: Michael Axtmann, Sascha Witt, Daniel Ferizovic, and Peter Sanders

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract
We present a sorting algorithm that works in-place, executes in parallel, is cache-efficient, avoids branch-mispredictions, and performs work O(n log n) for arbitrary inputs with high probability. The main algorithmic contributions are new ways to make distribution-based algorithms in-place: On the practical side, by using coarse-grained block-based permutations, and on the theoretical side, we show how to eliminate the recursion stack. Extensive experiments shw that our algorithm IPSSSSo scales well on a variety of multi-core machines. We outperform our closest in-place competitor by a factor of up to 3. Even as a sequential algorithm, we are up to 1.5 times faster than the closest sequential competitor, BlockQuicksort.
Cite as

Michael Axtmann, Sascha Witt, Daniel Ferizovic, and Peter Sanders. In-Place Parallel Super Scalar Samplesort (IPSSSSo). In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{axtmann_et_al:LIPIcs.ESA.2017.9,
  author =	{Axtmann, Michael and Witt, Sascha and Ferizovic, Daniel and Sanders, Peter},
  title =	{{In-Place Parallel Super Scalar Samplesort (IPSSSSo)}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{9:1--9:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.9},
  URN =		{urn:nbn:de:0030-drops-78542},
  doi =		{10.4230/LIPIcs.ESA.2017.9},
  annote =	{Keywords: shared memory, parallel sorting, in-place algorithm, comparison-based sorting, branch prediction}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2016.10
Trip-Based Public Transit Routing Using Condensed Search Trees

Authors: Sascha Witt

Published in: OASIcs, Volume 54, 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016)

Abstract
We study the problem of planning Pareto-optimal journeys in public transit networks. Most existing algorithms and speed-up techniques work by computing subjourneys to intermediary stops until the destination is reached. In contrast, the trip-based model focuses on trips and transfers between them, constructing journeys as a sequence of trips. In this paper, we develop a speed-up technique for this model inspired by principles behind existing state-of-the-art speed-up techniques, Transfer Patterns and Hub Labelling. The resulting algorithm allows us to compute Pareto-optimal (with respect to arrival time and number of transfers) 24-hour profiles on very large real-world networks in less than half a millisecond. Compared to the current state of the art for bicriteria queries on public transit networks, this is up to two orders of magnitude faster, while increasing preprocessing overhead by at most one order of magnitude.
Cite as

Sascha Witt. Trip-Based Public Transit Routing Using Condensed Search Trees. In 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016). Open Access Series in Informatics (OASIcs), Volume 54, pp. 10:1-10:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{witt:OASIcs.ATMOS.2016.10,
  author =	{Witt, Sascha},
  title =	{{Trip-Based Public Transit Routing Using Condensed Search Trees}},
  booktitle =	{16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016)},
  pages =	{10:1--10:12},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-021-7},
  ISSN =	{2190-6807},
  year =	{2016},
  volume =	{54},
  editor =	{Goerigk, Marc and Werneck, Renato F.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2016.10},
  URN =		{urn:nbn:de:0030-drops-65341},
  doi =		{10.4230/OASIcs.ATMOS.2016.10},
  annote =	{Keywords: Public Transit, Routing, Public Transport, Route Planning}
}

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