arXiv:2603.12592cs.DScs.AI2026-03被引 1

通过提前剪枝优化公交路线搜索,提速超50%且不损失最优性。

Early Pruning for Public Transport Routing

  • 预排序换乘路径并动态剪枝冗余选项,减少无效计算。
  • 在瑞士与伦敦数据集上实现最高57%的查询加速。
  • 兼容主流算法,适配多模式交通规划系统部署。

针对公共出行路线算法(如RAPTOR及其变体)在密集换乘图中因支持无限换乘而导致的性能瓶颈,本文提出一种低开销的早期剪枝(Early Pruning)技术。该方法通过预先按换乘时长排序,并在换乘循环中应用剪枝规则,在某站点的当前最优解已优于某换乘路径时,直接剔除耗时更长的后续换乘,从而避免无效计算。该方法仅需一次预处理,可无缝集成至现有代码库,且在附加优化目标随换乘时间单调非递减的情况下,保持帕累托最优性。在基于RAPTOR的多种先进方案(包括ULTRA-RAPTOR、McRAPTOR、BM-RAPTOR、ULTRA-McRAPTOR、UBM-RAPTOR)上,于瑞士和伦敦交通网络测试中,查询时间最高降低57%。该方法为公共交通路径规划算法提供了通用高效的性能提升。

原文摘要 · Abstract (English)

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.

路径规划公交路由剪枝优化RAPTOR

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。