出行规划算法 #04：Connection Scan Algorithm

Connection Scan Algorithm（CSA）按出发时间对所有班次连接排序，从给定出发时间起线性扫描，维护每个站点的最早到达时间；查询复杂度接近线性，对「最早到达」单目标查询比 RAPTOR 更快，被 Rome2Rio 等系统用于快速预过滤。

相关文章：RAPTOR · 多标签 Pareto Dijkstra

目录

核心思想

CSA 的洞察极其简单：

按时间顺序扫描所有班次，维护每站最早可达时间。比当前时间早的连接跳过，比目标时间晚的连接停止扫描。

不需要构建图，不需要优先队列，不需要 Dijkstra——一次线性扫描即可回答「最早到达」查询。

排序后的连接数组（按出发时间）：

时间轴 ─────────────────────────────────────────────►
 8:00  8:30  9:00  9:30 10:00 10:30 11:00 ...
  │     │     │     │     │     │     │
 C1    C2    C3    C4    C5    C6    C7  ...

查询：从站点 S 出发，出发时间 ≥ 09:00，到站点 G 最早几点到？
→ 跳过 C1、C2（出发时间 < 09:00）
→ 从 C3 开始扫描，更新各站最早到达时间
→ 直到所有连接扫描完或提前终止

数据结构与预处理

连接（Connection）

一个连接代表「乘坐某趟班次，从站 A 到站 B 的一段」：

record Connection(
    int    depStop,       // 出发站 ID
    int    arrStop,       // 到达站 ID
    int    depTime,       // 出发时间（秒，距当天 0 点）
    int    arrTime,       // 到达时间
    String tripId         // 所属班次 ID（用于换乘判断）
) {}

预处理：全局排序

connections.sort(Comparator.comparingInt(Connection::depTime));

一次性离线完成，O(N log N)，N 为总连接数（全国高铁约 50 万条）。

辅助数组

int[] T  = new int[numStops];     // T[s] = 站点 s 的最早到达时间（初始 ∞）
String[] inTrip = new String[numStops];  // 当前搭乘的班次（用于判断是否需要换乘）

算法流程

输入：出发站 src，目标站 dst，出发时间 depTime

初始化：
  T[src] = depTime
  其余 T[s] = ∞

二分定位：
  start = 二分查找第一个 depTime >= depTime 的连接索引

扫描：
  for i from start to len(connections)-1:
    c = connections[i]

    // 若出发站不可达，或出发时间比已知到达时间早 → 跳过
    if T[c.depStop] > c.depTime:
      continue

    // 更新到达站最早到达时间
    if c.arrTime < T[c.arrStop]:
      T[c.arrStop] = c.arrTime

    // 提前终止：若目标站已有确定到达时间，且当前连接出发时间 > T[dst]
    // （后续连接更晚出发，不可能更早到达）
    if c.depTime > T[dst]:
      break

返回 T[dst]

关键剪枝

• 出发站不可达剪枝：T[c.depStop] > c.depTime 时跳过
• 早终止：目标站已到达，且后续连接出发时间更晚

Java 实现

import java.util.*;

public class CSA {

    record Connection(int depStop, int arrStop, int depTime, int arrTime, String tripId) {}

    private final List<Connection> connections;  // 已按 depTime 排序
    private final int numStops;

    public CSA(List<Connection> connections, int numStops) {
        this.connections = connections;
        this.numStops = numStops;
        this.connections.sort(Comparator.comparingInt(Connection::depTime));
    }

    /**
     * 查询从 src 出发（时间 >= departureTime）到 dst 的最早到达时间
     * @return 最早到达时间（秒），不可达返回 Integer.MAX_VALUE
     */
    public int earliestArrival(int src, int dst, int departureTime) {
        int[] T = new int[numStops];
        Arrays.fill(T, Integer.MAX_VALUE);
        T[src] = departureTime;

        // 二分定位起始索引
        int start = lowerBound(departureTime);

        for (int i = start; i < connections.size(); i++) {
            Connection c = connections.get(i);

            // 出发站不可达，跳过
            if (T[c.depStop] == Integer.MAX_VALUE || T[c.depStop] > c.depTime) {
                continue;
            }

            // 更新到达站最早到达时间
            if (c.arrTime < T[c.arrStop]) {
                T[c.arrStop] = c.arrTime;
            }

            // 提前终止
            if (T[dst] != Integer.MAX_VALUE && c.depTime > T[dst]) {
                break;
            }
        }

        return T[dst];
    }

    // 二分查找第一个 depTime >= target 的连接索引
    private int lowerBound(int target) {
        int lo = 0, hi = connections.size();
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (connections.get(mid).depTime < target) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }
}

与 RAPTOR 对比

实践搭配：CSA 做快速最早到达预过滤，RAPTOR 做精确多目标规划。

扩展：换乘与路径

换乘时间约束

// 需要换乘判断：若当前连接的 tripId 与上一段不同，则需要换乘时间
if (!c.tripId.equals(currentTrip[c.depStop])) {
    // 需要至少 MIN_TRANSFER 分钟换乘时间
    if (T[c.depStop] + MIN_TRANSFER > c.depTime) continue;
}

路径重建

// 记录父连接
Connection[] parent = new Connection[numStops];

// 在更新 T[c.arrStop] 时同步记录
if (c.arrTime < T[c.arrStop]) {
    T[c.arrStop] = c.arrTime;
    parent[c.arrStop] = c;
}

// 回溯路径
List<Connection> path = new ArrayList<>();
int cur = dst;
while (parent[cur] != null) {
    path.add(0, parent[cur]);
    cur = parent[cur].depStop;
}

实际应用

Rome2Rio

Rome2Rio 在首次展示出行方案时，用 CSA 快速计算各模式（飞机/火车/巴士）的最早到达时间，生成"可行方案候选集"。然后对候选集用完整 RAPTOR 做精确多目标规划。

Deutsche Bahn（德国铁路）DB Navigator

DB 的路线规划后端使用 CSA 变体，在全欧铁路时刻表（约 5000 万条连接）上实现 < 100ms 的最早到达查询。

参考资料

参考资料

• Dibbelt et al., Connection Scan Algorithm (ACM Journal of Experimental Algorithmics, 2018) — CSA 原论文
• RAPTOR（多目标路由首选，CSA 的功能超集）
• 多标签 Pareto Dijkstra（扩展 CSA 到多目标的理论基础）