Early Pruning for Public Transport Routing

📄 arXiv: 2603.12592v1 📥 PDF

作者: Andrii Rohovyi, Abdallah Abuaisha, Toby Walsh

分类: cs.DS, cs.AI, cs.RO

发布日期: 2026-03-13

💡 一句话要点

提出Early Pruning加速公共交通路径规划，提升RAPTOR算法效率。

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 公共交通 路径规划 RAPTOR算法 换乘优化 剪枝算法

📋 核心要点

  1. 现有公共交通路径规划算法在处理大规模换乘网络时效率低下，限制了换乘距离或模式选择，影响了路径最优性。
  2. Early Pruning通过预排序换乘连接并应用剪枝规则，在不影响最优性的前提下，提前排除不可能产生更优结果的换乘选项。
  3. 实验表明，Early Pruning在多个RAPTOR变体上显著降低了查询时间，最高可达57%，提升了算法效率。

📝 摘要（中文）

公共交通路径规划算法，特别是广泛使用的RAPTOR及其变体，在换乘松弛阶段面临性能瓶颈，尤其是在密集换乘网络和支持无限换乘的情况下。这种低效源于对大量潜在的站点间连接（步行、自行车、电动滑板车等）的迭代。为了保持可接受的性能，从业者通常限制换乘距离或排除某些换乘选项，这会降低路径的最优性并限制提供给旅客的多模式选择。本文介绍了一种低开销的技术Early Pruning，它可以在不影响最优性的前提下加速路由算法。通过按持续时间预先对换乘连接进行排序，并在换乘循环中应用剪枝规则，该方法会在停止时丢弃较长的换乘，因为它们无法产生比当前最佳解决方案更早的到达时间。Early Pruning只需对现有代码库进行最小的更改即可集成，并且只需要一次性的预处理步骤。在多个基于RAPTOR的最先进的解决方案（包括RAPTOR、ULTRA-RAPTOR、McRAPTOR、BM-RAPTOR、ULTRA-McRAPTOR和UBM-RAPTOR）上，并在瑞士和伦敦的交通网络上进行了测试，我们实现了高达57%的查询时间减少。这种方法为交通寻路算法的效率提供了普遍的改进。

🔬 方法详解

问题定义：论文旨在解决公共交通路径规划中，由于大量换乘连接导致的计算效率瓶颈问题。现有方法为了保证性能，通常会限制换乘距离或模式选择，牺牲了路径的最优性和多模式选择的丰富性。RAPTOR算法及其变体在换乘松弛阶段面临着巨大的计算压力。

核心思路：论文的核心思路是在换乘过程中，尽早地排除那些不可能产生更优结果的换乘选项，从而减少不必要的计算。通过预先对换乘连接进行排序，并根据当前已知的最佳到达时间应用剪枝规则，可以有效地过滤掉较长的、无意义的换乘。

技术框架：Early Pruning可以集成到现有的RAPTOR算法框架中，主要包含以下步骤：1. 预处理阶段：对每个站点的换乘连接按照持续时间进行排序。2. 路径搜索阶段：在换乘松弛过程中，按照排序后的顺序遍历换乘连接。3. 剪枝规则应用：对于每个换乘连接，判断其是否可能产生比当前最佳到达时间更早的结果，如果不可能，则跳过该连接。

关键创新：Early Pruning的关键创新在于其低开销和通用性。它不需要对现有算法进行大规模修改，只需要一个预处理步骤和在换乘循环中添加一个简单的剪枝规则。这种方法可以应用于多种基于RAPTOR的算法，并且在不同的交通网络上都有效。

关键设计：关键设计在于剪枝规则的制定。该规则基于当前已知的最佳到达时间，以及换乘连接的持续时间，判断该换乘连接是否可能产生更早的到达时间。具体的实现细节可能取决于具体的RAPTOR变体，但核心思想是相同的：尽早排除不可能产生更优结果的换乘选项。

📊 实验亮点

实验结果表明，Early Pruning在多个基于RAPTOR的算法（包括RAPTOR、ULTRA-RAPTOR、McRAPTOR、BM-RAPTOR、ULTRA-McRAPTOR和UBM-RAPTOR）上，以及在瑞士和伦敦的交通网络上，实现了显著的查询时间减少，最高可达57%。这表明Early Pruning是一种有效的、通用的加速公共交通路径规划算法的技术。

🎯 应用场景

Early Pruning可应用于各种公共交通路径规划系统，尤其是在需要考虑多种换乘方式和较大换乘范围的场景下。该技术能够降低计算成本，使交通机构能够扩展换乘半径，并整合更多出行模式，从而为用户提供更丰富的出行选择。这对于公共交通覆盖不足的地区，如郊区和小城镇，尤为重要，可以鼓励居民选择公共交通而非私家车。

📄 摘要（原文）

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. 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. Beyond algorithmic performance, Early Pruning has practical implications for transport planning. By reducing computational costs, it enables transit agencies to expand transfer radii and incorporate additional mobility modes into journey planners without requiring extra server infrastructure. This is particularly relevant for passengers in areas with sparse direct transit coverage, such as outer suburbs and smaller towns, where richer multimodal routing can reveal viable alternatives to private car use.