> RAPTOR（Round-based Public Transit Optimized Router）以换乘次数为轮次，逐轮扩展每站的最早到达时间，无需构建庞大的时间展开图，是公共交通路由的工业主流算法，被 Rome2Rio、Navitia、OpenTripPlanner 等系统采用。 相关文章：多标签 Paret…
2026-06-08
> 多标签 Pareto Dijkstra 为每个节点维护一组「非支配标签」（Pareto 前沿），同时优化多个目标（如时间和费用），输出所有满足"没有其他方案在所有维度都更优"的解集，是携程可拼票、OTA 多目标排序的算法基础。 相关文章：RAPTOR · 可拼票 DP · Connection Scan Algor…
2026-06-08
> 可拼票 DP 将「A→B 直达票」与「A→C + C→B 两段票」的组合搜索建模为带时间约束的最短路 DP，通过枚举中转城市并剪枝，找出比直达更便宜的合法组合，是携程「拼票」功能的核心算法。 相关文章：RAPTOR · 多标签 Pareto Dijkstra 目录 | 章节 | 说明 | |------|-----…
2026-06-08
> Connection Scan Algorithm（CSA）按出发时间对所有班次连接排序，从给定出发时间起线性扫描，维护每个站点的最早到达时间；查询复杂度接近线性，对「最早到达」单目标查询比 RAPTOR 更快，被 Rome2Rio 等系统用于快速预过滤。 相关文章：RAPTOR · 多标签 Pareto Dijk…
2026-06-08