Customizable Contraction Hierarchies

Customizable Contraction Hierarchies（CCH）将 CH 的「图结构预处理」与「边权定制化」分离为两个独立阶段，图骨架一次性离线计算，路况变化时只需毫秒级重算权重层，从而同时兼顾 CH 的极速查询（< 1ms）和实时路况支持，是 Mapbox、必应地图的核心导航算法。

相关文章：Contraction Hierarchies · Hub Labeling

目录

CH 的根本局限

Contraction Hierarchies 的快捷边在预处理阶段被固化：

预处理时：shortcut(A→C) = dist(A,B) + dist(B,C) = 2 + 3 = 5

当 A→B 因拥堵从 2 变成 10 时，快捷边 A→C = 5 已经失效，但更新它需要重新收缩节点 B——进而影响其他节点的收缩……最终必须重跑整个预处理流程（5～30 分钟）。

这使 CH 无法支持实时路况：

实时路况更新频率：每分钟
CH 预处理时间：5～30 分钟

矛盾不可调和 → 需要新方案

CCH 的核心创新：解耦

CCH 的洞察：CH 预处理中有两件性质完全不同的事被混在一起做了：

CCH 将它们分开：

① 预处理（离线）：只处理图结构 → 确定骨架（order + shortcut 存在性）
② 定制化（在线）：将当前边权填入骨架 → 计算快捷边实际权重
③ 查询（在线）：双向层级搜索（同 CH）

路况变化 → 只重跑 ② → 毫秒级完成。

三阶段流程详解

① 预处理阶段（离线，一次性）

输入：道路拓扑图（节点 + 边，不含权重）

操作：

1. 计算节点重要性（只看拓扑，不看权重）
2. 按重要性从低到高收缩节点
3. 记录：收缩后每条快捷边对应哪条原始路径（中间节点）
4. 不计算快捷边的具体权重，只记录它的「存在」

输出：层级图骨架（节点 order + shortcut 路径结构）

耗时：5～30 分钟（欧洲路网约 15 分钟）

② 定制化阶段（在线，毫秒级）

输入：当前道路权重（实时路况速度）

操作：将当前边权填入骨架，用「下三角松弛」自底向上更新快捷边权重

耗时：< 100ms（欧洲路网约 50ms）

触发时机：路况更新（每 1～5 分钟）

③ 查询阶段（在线，< 1ms）

与 CH 查询完全相同，使用②输出的带权层级图做双向层级搜索。

定制化阶段的算法

定制化阶段的核心是下三角松弛（Lower Triangle Relaxation）：

快捷边权重更新

快捷边 u→w（跳过节点 v）的权重应等于当前 dist(u,v) + dist(v,w)。

在层级图中，按照节点 order 从低到高（从叶节点往根节点）依次处理：

按 order 从小到大处理每个节点 v：
  for 每条进入 v 的边 u→v（原始边或快捷边）：
    for 每条离开 v 的边 v→w（原始边或快捷边）：
      if order[u] < order[v] < order[w]：   ← 构成下三角
        candidate = weight(u→v) + weight(v→w)
        if shortcut(u→w) 存在 and candidate < weight(u→w)：
          weight(u→w) = candidate            ← 更新快捷边权重

正确性：由于按 order 从低到高处理，当处理节点 v 时，其所有低层级邻居的权重已经更新完毕（自底向上保证依赖关系）。

时间复杂度

定制化阶段的时间复杂度为 O(|E_overlay|)，其中 E_overlay 是层级图（含快捷边）的边数。实测约为原始边数的 3～5 倍，远小于重跑全量预处理。

查询阶段

与 CH 查询完全相同：

双向层级搜索：
  前向搜索：从 S 出发，只向 order 更高节点扩展
  后向搜索：从 G 出发，只向 order 更高节点扩展
  相遇条件：同双向 Dijkstra 终止条件

查询使用②阶段刚刚更新的带权层级图
→ 自动反映最新路况

查询延迟：< 1ms（与 CH 相同）

性能对比

以欧洲路网（约 1.8 亿节点）为基准：

CCH 在查询速度上与 CH 持平，同时将路况更新延迟从「分钟级」降至「毫秒级」，代价仅是略多的内存（× 3 vs × 2.5）。

实际应用

Mapbox Navigation

Mapbox 的导航 SDK 基于 CCH：

• 开源实现：[OSRM 的 CH 分支 + Mapbox 自研 CCH 层]
• 每 5 分钟从 Mapbox Traffic API 拉取路况更新
• 定制化阶段在后台线程运行，不阻塞查询服务
• 支持 turn cost（转弯代价），通过对 CCH 的扩展实现

微软必应地图（Bing Maps）

必应使用 CCH 支持其驾车路线和 ETA（预计到达时间）服务：

• 将 CCH 定制化集成到实时流量处理管道
• 全球路网分区域预处理，按需加载

RoutingKit（开源参考实现）

KIT 大学提供的开源 CCH 实现，是学术和工业界的标准参考：

• 支持完整的预处理 → 定制化 → 查询流水线
• 文档详尽，适合作为自研导航引擎的起点

参考资料

参考资料

• Delling et al., Customizable Contraction Hierarchies (ACM JEA 2017) — CCH 原论文
• Contraction Hierarchies（CCH 的前身，理解 CCH 必须先理解 CH）
• Hub Labeling（另一种极速查询方案，与 CCH 的权衡对比）