

















Abstract:Routing algorithms for public transport, particularly the widely used RAPTOR and its variants, often face performance bottlenecks during the transfer relaxation phase, especially on dense transfer graphs, when supporting unlimited transfers. This inefficiency arises from iterating over many potential inter-stop connections (walks, bikes, e-scooters, etc.). To maintain acceptable performance, practitioners often limit transfer distances or exclude certain transfer options, which can reduce path optimality and restrict the multimodal options presented to travellers.
This paper introduces Early Pruning, a low-overhead technique that accelerates routing algorithms without compromising optimality. By pre-sorting transfer connections by duration and applying a pruning rule within the transfer loop, the method discards longer transfers at a stop once they cannot yield an earlier arrival than the current best solution.
Early Pruning can be integrated with minimal changes to existing codebases and requires only a one-time preprocessing step. The technique preserves Pareto-optimality in extended-criteria settings whenever the additional optimization criteria are monotonically non-decreasing in transfer duration. Across multiple state-of-the-art RAPTOR-based solutions, including RAPTOR, ULTRA-RAPTOR, McRAPTOR, BM-RAPTOR, ULTRA-McRAPTOR, and UBM-RAPTOR and tested on the Switzerland and London transit networks, we achieved query time reductions of up to 57\%. This approach provides a generalizable improvement to the efficiency of transit pathfinding algorithms.
| Subjects: | Data Structures and Algorithms (cs.DS); Artificial Intelligence (cs.AI); Robotics (cs.RO) |
| Cite as: | arXiv:2603.12592 [cs.DS] |
| (or arXiv:2603.12592v4 [cs.DS] for this version) | |
| https://doi.org/10.48550/arXiv.2603.12592 arXiv-issued DOI via DataCite |
From: Andrii Rohovyi [view email]
[v1]
Fri, 13 Mar 2026 02:49:32 UTC (18 KB)
[v2]
Tue, 21 Apr 2026 14:12:50 UTC (19 KB)
[v3]
Sun, 17 May 2026 09:47:46 UTC (19 KB)
[v4]
Tue, 26 May 2026 09:01:21 UTC (19 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。