2026-07-21T12:28:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7896 2024-03-06T10:30:12Z ddc:004 open_access

Faster Transit Routing by Hyper Partitioning Delling, Daniel Dibbelt, Julian Pajor, Thomas Zündorf, Tobias Routing speed-up techniques public transport partitioning We present a preprocessing-based acceleration technique for computing bi-criteria Pareto-optimal journeys in public transit networks, based on the well-known RAPTOR algorithm [Delling et al 2015]. Our key idea is to first partition a hypergraph into cells, in which vertices correspond to routes (e.g., bus lines) and hyperedges to stops, and to then mark routes sufficient for optimal travel across cells. The query can then be restricted to marked routes and those in the source and target cells. This results in a practical approach, suitable for networks that are too large to be efficiently handled by the basic RAPTOR algorithm. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Daniel Delling and Julian Dibbelt and Thomas Pajor and Tobias Zündorf 2017 Is Part Of OASIcs, Volume 59, 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.ATMOS.2017.8 urn:nbn:de:0030-drops-78962 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2017.8 eng https://creativecommons.org/licenses/by/3.0/legalcode