常见路径规划算法介绍

1.Query

2. Path Unpack

将shortcut解压为原始路径

使用Inertial Flow算法计算node order，可离线运行，保存到文件供在线定制查询使用。

权值变化时使用变化后的权值更新权值相关的metric（定制化），支持并行更新和增量更新

和CH算法相同，双向搜索然后unpack path。

CCH特点：

预处理数分钟到数小时，定制化秒级，查询毫秒级

可以很好地适应权值变化，支持多套权值，易于扩展

分为三个阶段：

? ? ? ? 3.Query: 查询阶段

2.3.1?Overlay Graph(覆盖图)

覆盖图的特点：

level-l中的所有boundary arc以及所有shortcut是level-(l-1)的覆盖图

2.3.2?覆盖图剪枝

保存cell中每一个clique有些浪费，很多不在最短路径上，可以对其剪枝

reduction: 针对每两个boundary vertex在本层graph上进行Dijkstra搜索，把不是shortcut 的边删除。

skeleton graph:针对每个boundary vertex计算到当前cell内其他boundary vertex的最短路径树，最后对所有的最短路径树求并集构造为 skeleton graph。

? 2.3.3?预处理阶段

使用PUNCH算法将图分割为多层overlay graph,存储为辅助数据，供定制化和查询使用
图分割的目标是overlay graph中boundary arc的数目尽量少，这会使定制化阶段耗费的时间和空间更少，路径查询更快
PUNCH算法的原理是利用路网中自然分割(河流，山川，高速公路)作为启发因子进行分割。
预处理结果为一个多层的overlay graph, 每一个node都存在于各个level的cell中，每个level中boundary vertex不同。一个cell有p个入口节点，q个出口节点，就会有p*q个shortcut。

? 2.3.4 定制化阶段?

采用自底向上的方式更新各个level中每个cell的shortcut权值
定制化与查询同时进行，因此定制化需要足够快
加速定制化的方法：

2.3.5?查询阶段

找出node v与起终点没有交集的最大level（query level），迭代搜索。

crp 为了节省内存，没有存储shortcut 对应的原始路径,需要双向搜索计算出shortcut中的原始路径

Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks

Customizable Route Planning in Road Networks?

Customizable Route Planning

Customizable Contraction Hierarchies

Graph Partitioning with Natural Cuts