出行规划算法 #01：RAPTOR

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

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

raptor rounds

章节	说明
与道路路由的本质差异	时刻表约束，离散换乘
核心思想：按轮次展开	每轮 = 一次额外换乘
算法流程	初始化、扫描线路、处理换乘
数据结构	时刻表、轮次标记、最早到达数组
路径重建	从终点回溯换乘链
复杂度分析	O(K × T) 时间，K 为最大换乘次数
与 Dijkstra 对比	为什么不能直接用 Dijkstra
实际应用	Rome2Rio、Navitia、OpenTripPlanner
参考资料	论文与文档

与道路路由的本质差异

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

维度	道路路由	公共交通路由
出发时间	随时可走	必须等班次（时刻表约束）
边的权重	距离 / 时速	班次出发时间 + 行驶时间
换乘	无（随时转向）	有最短换乘时间，需等待
优化目标	最短距离 / 时间	最早到达 / 最少换乘
图规模	静态路网	时间维度爆炸（班次数 × 站点数）

时间展开图（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)。

数组布局

数据	含义	大小
`τ[k][p]`	恰好 k 次换乘到达站点 p 的最早时间	K × P
`τ*[p]`	任意换乘次数到达 p 的最早时间（剪枝用）	P
`marked`	本轮有改善的站点	P（位图）
`parent[k][p]`	路径重建的父节点记录	K × P

路径重建

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

复杂度分析

操作	复杂度	说明
每轮线路收集	O(\|marked\| × avg_routes_per_stop)	marked 通常远小于 P
每轮线路扫描	O(T × avg_stops_per_route)	T 为线路数
总时间	O(K × T)	K 为最大换乘次数（通常 ≤ 5）
空间	O(K × P)	P 为站点数

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

网络规模	查询时间
德国全国公共交通	< 50ms
欧洲铁路网络	< 200ms

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

与 Dijkstra 对比

不能直接用 Dijkstra 的原因：

等待时间依赖出发时间：边权不是固定值，等 10 分钟还是等 2 小时取决于你何时到站
换乘约束：同一站内换乘需要最短步行时间（通常 3～10 分钟）
多目标优化：最早到达 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（按时间顺序扫描班次，最早到达查询更快）