RAPTOR

RAPTOR（Round-based Public Transit Optimized Router）以换乘次数为轮次，逐轮扩展每站的最早到达时间，无需构建庞大的时间展开图，是公共交通路由的工业主流算法，被 Rome2Rio、Navitia、OpenTripPlanner 等系统采用。

相关文章：多标签 Pareto Dijkstra · Connection Scan Algorithm

目录

与道路路由的本质差异

道路路由和公共交通路由是两个不同的问题：

时间展开图（Time-Expanded Graph）虽然理论上能用 Dijkstra 求解，但将每个（站点，班次）对建成节点后图规模极大（全国高铁+城轨约 10 亿节点），不实用。

RAPTOR 完全避开了时间展开图的构建。

核心思想：按轮次展开

RAPTOR 的关键洞察：换乘次数是自然的迭代层次。

第 0 轮：从出发站出发，不换乘，能最早到达哪些站？
第 1 轮：在第 0 轮可达站换乘，再走一段，能最早到达哪些站？
第 2 轮：在第 1 轮可达站换乘，再走一段...
...
直到终点站的最早到达时间不再改善，或达到最大换乘次数

每轮维护一个数组 τ[k][p] = 恰好换乘 k 次时，站点 p 的最早到达时间。

算法流程

初始化

τ[0][source] = departure_time   // 出发站出发时间
τ[0][p] = ∞   for p ≠ source
τ*[p] = ∞     for all p         // 任意换乘次数下的最早到达（优化用）

marked = {source}               // 本轮有改善的站点集合

每轮迭代（第 k 轮）

for k in range(1, max_transfers + 1):
    # Step 1：收集所有经过 marked 站点的线路
    Q = {}   # 线路 → 该线路中最早"上车站"
    for stop in marked:
        for route in routes_through(stop):
            if stop comes before Q[route] in route:
                Q[route] = stop

    # Step 2：沿每条线路向前扫描
    for route, boarding_stop in Q.items():
        t = None   # 当前搭乘的班次
        for stop in route.stops_from(boarding_stop):
            if t is not None:
                # 能否更早到达 stop？
                arrival = t.arrival_at(stop)
                if arrival < min(τ[k][stop], τ*[stop]):
                    τ[k][stop] = arrival
                    τ*[stop] = arrival
                    marked.add(stop)
            # 在 stop 能否换乘更早的班次？
            if τ[k-1][stop] <= t.departure_at(stop):
                t = earliest_trip(route, stop, τ[k-1][stop])

    if not marked:
        break   // 没有改善，提前终止

脚注路径记录

每次更新 τ[k][stop] 时，记录：

parent[k][stop] = (boarding_stop, trip, k-1)

数据结构

时刻表表示

record Trip(String id, List<StopTime> stopTimes) {}
record StopTime(String stopId, LocalTime arrival, LocalTime departure) {}
record Route(String id, List<String> stops, List<Trip> trips) {}

关键操作：earliestTrip(route, stop, minDeparture) — 找到在 stop 不早于 minDeparture 出发的最早班次。 预处理为每条 (route, stop) 按出发时间排序，二分搜索 O(log T)。

数组布局

路径重建

从终点 target 开始，k = 使 τ[k][target] 最小的轮次
while k > 0:
    (boarding, trip, k_prev) = parent[k][target]
    输出换乘段：boarding → target，搭乘 trip
    target = boarding
    k = k_prev

复杂度分析

实际性能（Delling 2014 基准，GTFS 数据）：

比时间展开图 + Dijkstra 快 100x 以上。

与 Dijkstra 对比

不能直接用 Dijkstra 的原因：

1. 等待时间依赖出发时间：边权不是固定值，等 10 分钟还是等 2 小时取决于你何时到站
2. 换乘约束：同一站内换乘需要最短步行时间（通常 3～10 分钟）
3. 多目标优化：最早到达 vs 最少换乘是 Pareto 目标，不能单一最小化

RAPTOR 天然解决了 1 和 3：轮次 = 换乘次数，每轮找当轮最早到达，自动形成 Pareto 前沿。

实际应用

Rome2Rio

Rome2Rio 是全球最大的多模式出行规划网站，其后端使用 RAPTOR + CSA 混合方案，覆盖飞机、火车、巴士、渡轮等模式。

Navitia

法国 Kisio Digital 开源的公共交通路由引擎，是欧洲多个城市 MaaS（Mobility as a Service）平台的基础，核心算法基于 RAPTOR。

OpenTripPlanner

OTP 是开源多模式出行规划器，v2.0 起将核心路由引擎从 A* 升级为 RAPTOR，查询速度提升 10x。

参考资料

参考资料

• Delling et al., Round-Based Public Transit Routing (Transportation Science, 2015) — RAPTOR 原论文
• 多标签 Pareto Dijkstra（多目标优化：同时最小化时间和费用）
• Connection Scan Algorithm（按时间顺序扫描班次，最早到达查询更快）