Customizable Contraction Hierarchies（CCH）将 CH 的「图结构预处理」与「边权定制化」分离为两个独立阶段，图骨架一次性离线计算，路况变化时只需毫秒级重算权重层，从而同时兼顾 CH 的极速查询（< 1ms）和实时路况支持，是 Mapbox、必应地图的核心导航算法。
相关文章：Contraction Hierarchies · Hub Labeling
目录
| 章节 | 说明 |
|---|---|
| CH 的根本局限 | 静态权重，无法支持实时路况 |
| CCH 的核心创新：解耦 | 图结构与边权分离 |
| 三阶段流程详解 | 预处理、定制化、查询 |
| 定制化阶段的算法 | 快捷边权重更新，下三角松弛 |
| 查询阶段 | 与 CH 查询相同，< 1ms |
| 性能对比 | CH、CCH、HL 三者横向比较 |
| 实际应用 | Mapbox、必应、RoutingKit |
| 参考资料 | 论文与文档 |
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）
路况变化 → 只重跑 ② → 毫秒级完成。
三阶段流程详解
① 预处理阶段（离线，一次性）
输入：道路拓扑图（节点 + 边，不含权重）
操作：
- 计算节点重要性（只看拓扑，不看权重）
- 按重要性从低到高收缩节点
- 记录：收缩后每条快捷边对应哪条原始路径（中间节点）
- 不计算快捷边的具体权重，只记录它的「存在」
输出：层级图骨架（节点 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 亿节点）为基准：
| 算法 | 结构预处理 | 权重更新 | 查询延迟 | 内存 | 实时路况 |
|---|---|---|---|---|---|
| CH | 15 分钟（含权重） | 需重跑全量 | < 1ms | × 2.5 | ❌ |
| CCH | 15 分钟（无权重） | ~50ms | < 1ms | × 3 | ✅ |
| Hub Labeling | 1 小时 | 需重建标签 | ~0.1ms | × 20 | ❌ |
| Dijkstra | 无 | 无 | ~30s | × 1 | ✅ |
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 的权衡对比）
评论 (0)
发表评论