改进迪杰斯特拉算法,精准处理公交换乘缓冲时间。
Adapting Dijkstra for Buffers and Unlimited Transfers
- 提出TAD算法,按完整行程序列搜索,避免错误过滤
- 在伦敦和瑞士数据集上速度超MR两倍以上
- 适合需精确换乘调度的交通规划场景
近年来,基于RAPTOR的算法被视为无需预处理的无限换乘路径查找最优方案。然而这一地位主要源于路由研究演进,而未经过系统性对比。本文重新审视经典的基于迪杰斯特拉的公共交通路径规划方法,证明时间依赖型迪杰斯特拉(TD-Dijkstra)优于MR。但高效实现依赖预处理中剔除被支配连接,这假设乘客总能切换到更快班次。当站点存在缓冲时间时,该假设不成立,因无法区分可继续乘坐的乘客与需等待换乘的乘客。为此,我们提出转移感知迪杰斯特拉(TAD),通过扫描完整行程序列,正确处理缓冲时间,同时保持对MR的性能优势。在伦敦和瑞士网络上的实验表明,TAD在有无缓冲时间条件下均实现超过两倍于MR的速度提升,并获得最优解。
原文摘要 · Abstract (English)
In recent years, RAPTOR based algorithms have been considered the state-of-the-art for path-finding with unlimited transfers without preprocessing. However, this status largely stems from the evolution of routing research, where Dijkstra-based solutions were superseded by timetable-based algorithms without a systematic comparison. In this work, we revisit classical Dijkstra-based approaches for public transit routing with unlimited transfers and demonstrate that Time-Dependent Dijkstra (TD-Dijkstra) outperforms MR. However, efficient TD-Dijkstra implementations rely on filtering dominated connections during preprocessing, which assumes passengers can always switch to a faster connection. We show that this filtering is unsound when stops have buffer times, as it cannot distinguish between seated passengers who may continue without waiting and transferring passengers who must respect the buffer. To address this limitation, we introduce Transfer Aware Dijkstra (TAD), a modification that scans entire trip sequences rather than individual edges, correctly handling buffer times while maintaining performance advantages over MR. Our experiments on the London and Switzerland networks show that we can achieve more than a twofold speedup over MR while producing optimal results on both networks, with and without buffer times.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。