当前动态路网上连续路径规划的问题对于许多基于位置的服务（location-based services, LBS）至关重要，越来越多的车辆出行依赖导航路线，希望在行驶过程中避免拥堵，尽可能快地到达目的地. 现实中，主流导航软件虽然会根据路况变化为行驶中的用户更新导航路线，但是考虑到计算代价和用户驾驶习惯，这些导航软件并不会根据频繁变化的路况为用户及时更新导航路线.当前自动驾驶车辆技术发展迅猛，自动驾驶车辆在行驶过程中能够对导航指令实时响应，这对导航路线的快速优化提出了较高的要求. 如果导航算法能够根据持续变化的路况对导航路线进行实时优化，那么自动驾驶车辆就能够及时优化行驶路线，尽可能节省行驶成本. 现实中，道路的行驶时间通常是在不断变化的，因此，将道路网络称为动态路网. 在动态路网上对导航路线进行实时持续优化并非易事，原因是在大型路网（顶点数通常超过100万个）上处理大规模并发导航路线查询将产生巨大的计算代价. 此时，如何对每个导航路线查询都能够进行实时优化响应是一个巨大的挑战.

近年来，路径规划问题一直受到持续的关注，但是上述挑战并未被完全解决^[1-12]. 过去的许多工作都在研究动态路网上的路线问题，根据行驶时间找到最短的路径，为了保证规划的路线始终是最短的，须在动态路网上重复计算最短路径，这对于动态的超大型路网来说，计算代价很大. 此外，大多数现有的工作集中于处理单个路径规划查询，而较少关注大量并发查询的处理. 与反复计算从用户位置到目的地之间最短路径的精确计算相比，在较小的响应时间内自适应调整基于当前路况的近似最优路线更为可行. 基于这一思想，并考虑到大量并发查询的需求，提出路径规划的并行算法（parallel optimization of route planning，PORP），旨在通过Master-Worker模式，实现基于动态路网路径规划的并行优化策略.

本研究的主要贡献包括以下2点：1）提出PORP算法，将整个路网的导航路线持续优化问题转化为多个子网的局部最优路线查找问题，降低了计算复杂度，持续并行地优化导航路线；提高了响应速度，从而在计算成本和计划路线的可用性之间取得平衡. 2）提出双层网格索引（dual-level grid-index，DLG-index），为PORP提供两级级联剪枝，有利于实现将复杂任务分解为多个轻量级的子任务，易于分布式实现，可以通过增加硬件资源提升响应速度和吞吐量，使整个系统具备良好的可扩展性，从而加速并发路径规划查询的处理.

基于位置服务LBS的时空查询问题已经引起学者们的广泛关注^[13]. 在导航路径推荐服务中，基于复杂变化的路况^[14]，为正在使用导航的用户及时调整导航路径，能够在很大程度上规避突发拥堵、节约出行成本，其本质是基于动态路网的导航路径持续查询问题.

A*算法是静态图中最短路线的经典算法^[15]，已经被广泛应用在许多工作中. Demiryurek等^[8]提出基于双向A*搜索算法的方法.R3系统^[9]基于A*算法计算最佳导航路径，与Demiryurek等^[8]所提方法不同的是，R3系统引入了历史数据以提高路径规划效率. 除了对最短路径的计算进行研究以外，一些工作还研究了路径规划中的其他因素. 刘晓倩等^[16]提出改进的RRT（rapid-exploration random tree）路径规划算法，该算法引入贪心剪枝思想，对冗余节点进行剪枝，可以提高路径规划效率. 有向D*算法^[17]通过引入导向函数缩小路径规划的搜索空间，从而减少规划时间，同时引入路径平滑度函数以保证算法的全局最优性. Ouyang等^[18]设计了辅助结构SS-Graph，并基于此结构提出动态道路网络上的最短路径索引，该索引可以通过理论上的保证得到有效更新.Wu等^[19]提出以路段密度为主要交通状态测度的动态路径规划方法，通过分析车辆的行驶时间和等待时间来决定是否修正当前的路径.

以上工作均重复计算从用户位置到目的地的最短路径，这使得路径规划的成本较高.为了解决这个问题，一些工作^[10-11,20]着重于寻找近似的最佳路线. Malviya等^[10]提出2种基于不断变化的交通状况来计算近似最佳路线的方法. Xu等^[11]研究基于动态路网的导航路线的优化，在起点和目标之间选择几个固定的中间目标，以减少重新计算的复杂性. Dai等^[20]提出一种连续路径规划算法，该算法根据变化的交通状况实时不断调整推荐路线. Holzer等^[21]引用多层地图来加速路径规划查询的过程. 还有一些工作专注于路网交通状况的预测，Wang等^[22]提出多任务对抗时空网络模型，该模型能够同时预测起点到目标点的人群流量. 此外，该团队最近提出了sequence-to-sequence对抗网模型来预测多步人群流动^[23]. Ghafouri等^[1]提出基于高斯过程的故障交通传感器检测模型，而Rezaei等^[24]在搜索最优规划路线时，同时考虑当前和未来的交通状况. 一些研究试图在规划路径时考虑未来的交通状况^[25-26]，且只有当足够多的司机遵照算法调度时，这些研究才有效. 另外，大数据和机器学习在减少交通拥堵、改善道路安全、提高驾驶舒适性方面也发挥着重要的作用^[27-28]. 除此以外，李博涵等^[29]提出多目标优化算法DSP-Topk，该算法利用基于最大夹角差的可视区域方法，提高计算距离的效率，并通过剪枝策略提高运算效率，但是该算法是基于某种度量的方法，且受限于室内查询.

上述解决方案主要是集中式路径规划模式，这种模式很难支持并行查询. 为了解决这个问题，文献[12]提出了CANDS，一种基于动态路网的分布式连续路径规划算法. CANDS将整个图划分为多个子图，并为所有子图形内的每对边界点之间的最短路径构建索引，依靠最短路径索引，CANDS持续为动态图上的用户计算最佳路径. 然而，最短路径索引维护的代价较高，因为随着路网的行驶代价的不断变化，边界点之间的最短路径须频繁更新. 为了解决这个问题，Yu等^[30]提出称为DTLP的分布式边界路径索引，该索引有助于Top-k最短路径的计算，从而避免了权重不断变化的影响，但是这项工作并未考虑如何连续计算从用户位置到目标的最短路径.

优化计划路线的朴素方法是重复计算动态图G上从用户的位置到目的地的最短路径. 然而，路网的规模和动态性以及大量的并发查询都使得以这种方式处理路径查询变得不可行. 因此，本研究引入索引结构DLG-index.

在设计DLG-index时，须满足以下3个要求. 1）动态路网维护成本合理. 索引选定的标志顶点对之间的最短路径，对于处理路线规划查询具有较大的帮助. 但当图的边权重不断变化时，其维护成本较高. 因此，图的索引结构必须易于维护，并且在图动态变化时要尽可能减少开销. 2）适用于并行架构. 随着图的大小和并发查询的数量不断增加，对比集中式索引，并行索引具有良好的扩展性，因此更加适合. 图G在集群中进行网格划分和存储，因此图的索引结构须在不同的处理器上独立维护. 3）支持并行路径规划算法. 对于索引来说，须快速辅助每个查询的对应子图的标识以及处理每个处理器上查询的分配，同时索引应提供足够的剪枝能力，并且须在较大程度上保证导航路径的可用性.

鉴于上述需求，提出DLG-index.基于图G的划分，DLG-index具有2级结构. 第1级通过维护每一对边界点之间的Top-k频繁路径来索引每个网格，Top-k频繁路径是指在给定的一对边界顶点之间轨迹最频繁的k条路径. 第2层是一个骨架图，由所有网格中的边界顶点组成，其中网格中的每对边界顶点通过一条边直接相连，该边的权重设置为相应边界顶点之间的Top-k频繁路径中的最小权重. 为了支持并行的路径规划查询，将DLG-index部署在Master-Worker模式的处理器集群上.

将动态路网抽象成一个有向图G={V, E}，其中V表示顶点集合，E表示顶点之间的边集合. DLG-index的构建从网格划分开始，首先，从任意顶点开始遍历图G={V, E}，使用广度优先策略生成网格，且每个网格内顶点个数不超过z. 将网格集合记为 $ S=\{{\mathrm{S}\mathrm{G}}_{1},{\mathrm{S}\mathrm{G}}_{2}, \cdots ,{\mathrm{S}\mathrm{G}}_{n}\}$，满足SG_i = {V_i, E_i}， $ i\in [1,\; n] $ ，n为网格数量. 定义 ${V}_{1}\cup \cdots $ $ \cup {V}_{n}=V $且 $ {E}_{1}\cup \cdots $ $\cup {E}_{n}=E $.

定义1　边界点. 对于边界点 $ {v}_{x}\in V $,存在 $ {v}_{y}\in V $，同时满足：1） $ {v}_{x} $与 $ {v}_{y} $在同一条边；2） $ {v}_{x} $与 $ {v}_{y} $分别位于不同的2个网格中. 显然，对于一条从网格 $ {{\rm{SG}}}_{i} $中的非边界点到网格 $ {{\rm{SG}}}_{j} $中的非边界点的路径，必然经过网格 $ {\mathrm{S}\mathrm{G}}_{i} $与 $ {\mathrm{S}\mathrm{G}}_{j} $，因此这些边界点是不同网格间的唯一“交通节点”. 其中，边界点有利于在骨架图中计算全局路径，提供粗粒度导航方向. 对于同一网格内的每一对边界点，索引其Top-k频繁路径.

定义2　Top-k频繁路径. 假设 $ {v}_{x} $到 $ {v}_{y} $存在N条轨迹（ $ {J}_{1} $, $ {J}_{2},\cdots , {J}_{N} $）， $ {n}_{i} $表示轨迹 $ {J}_{i} $的数量，则Top-k频繁路径为{ $ {J}_{1} $, $ {J}_{2} ,\cdots , {J}_{k} $}，其中 $ {n}_{1}\geqslant {n}_{2}\geqslant \cdots \geqslant {n}_{k} $.

首先引入一个前缀路径树（prefix path tree, PPT）结构以支持确定Top-k频繁路径. 对于每一个子图 $ {{\rm{SG}}}_{i} $，初始化前缀路径树 $ {T}_{i} $，以边界点 $ {v}_{x} $作为 $ {T}_{i} $的根结点，创建一个结点列表L，将轨迹 $ {J}_{i}=\left\{{v}_{x},\cdots ,{v}_{y}\right\} $（ $ {v}_{y} $为 $ {{\rm{SG}}}_{i} $的边界点，且 $ {v}_{x}\ne {v}_{y} $）插入 $ {T}_{i} $，将 $ {J}_{i} $中顶点视为 $ {T}_{i} $的结点.具体地，在T中查找 $ {J}_{i} $的最长公共前缀，并在公共前缀后添加 $ {J}_{i} $剩余部分，叶结点表示边界点 $ {v}_{y} $，若L中不存在 $ {v}_{y} $，则在L中创建 $ {v}_{y} $项，并链接该叶结点. 每个叶结点维护一个队列Q，用以保存轨迹名 $ {J}_{i} $. 当所有轨迹插入T后，从L中依次访问边界点 $ {v}_{y} $，按照|Q|的大小选取Top-k条路线.

如图1所示为以边界点 $ {v}_{1} $为根结点的前缀路径树，该树分别存储了从 $ {v}_{1} $到边界顶点 $ {v}_{13} $和 $ {v}_{15} $的路径. 匹配轨迹的 $ {v}_{1} $和 $ {v}_{13} $之间的路径为 $ {p}_{i} $（ $ i\in \left[\mathrm{1,6}\right] $），而 $ {p}_{j} $( $ j\in \left[\mathrm{7,10}\right] $)是匹配轨迹的 $ {v}_{1} $和 $ {v}_{15} $之间的路径. 在此仅以边界点 $ {v}_{13} $的Top-k频繁路径的计算为例. 基于PPT，可以确定从 $ {v}_{1} $到 $ {v}_{13} $最频繁路径（Top-1）为 $ {p}_{3} $，次频繁路径（Top-2）为 $ {p}_{1} $. 在选取k的取值时，若k过大，将导致创建、维护PPT时间成本增加；若k较小，在通过每一对边界点之间的Top-k频繁路径索引每个网格时，边界点间权重的选择减少，相应的权重偏大，即骨架图中网格内节点间权重偏大. 针对不同路网图，通过广泛实验选取相应合适的k.

为了支持路径规划查询的并行处理，在Master-Worker模式的集群中将DLG-index并行化，该框架如图2所示.该模型包括3种角色：Master、GridWorker和QueryWorker.每个角色本质上都是如线程一样的虚拟处理器，图G和网格划分信息由Master负责，每个QueryWorker维护一个骨架图的副本，而划分的网格则分布在GridWorker上.

Master会定期将变化的交通路况发送给所有GridWorker，GridWorker在接收到边的新权重后，首先会查找所处网格，然后立即更新这些网格中边界点之间的旅行成本. 随后，GridWorker将每个网格中边界点之间的新旅行成本返回给每个QueryWorker，随后更新骨架图上的边权重.

PORP须在较短的响应时间内持续优化动态图上的规划路径. 由于无法准确预测未来的交通状况，无法在动态图上为用户计算绝对最佳路径. 因此，随着交通状况的变化，反复计算从用户当前位置到目的地的最短路径是没有必要的，因为这种方式只会消耗大量计算资源，且不能保证规划的路径是最佳路径.

还有另一个重要问题，即如何正确评估离用户位置较远区域的交通状况对当前路径规划的影响. 如果忽略此影响，用户可能会沿着规划的路径陷入拥堵的道路中. 相反，若过多地考虑该影响，规划的路线可能须频繁地调整，这会带来巨大的计算代价. 而且，巨大的计算代价势必延长查询的响应时间，无法提前避免用户进入拥堵区域，从而导致路径优化工作毫无意义.

考虑到上述问题，PORP算法不再计算每次优化中精确的最短路径，而更加倾向于以较快速度连续计算近似最佳路径，因为近似最佳路径往往也可以满足用户的需求，同时可以大大节省计算成本. 在进行路径规划时，PORP算法根据骨架图计算全局路径 $ {p}_{\mathrm{g}} $，沿着路径 $ {p}_{\mathrm{g}} $在用户位置周围的局部区域中不断优化规划的路径.

对于路径规划查询，PORP算法基于DLG-index自适应地优化规划路径. 首先在骨架图 $ {G}_{\mathrm{s}} $上计算从起点到终点的全局路径 $ {p}_{\mathrm{g}} $，以及 $ {p}_{\mathrm{g}} $所经过的候选网格. 然后，当用户沿着全局路径 $ {p}_{\mathrm{g}} $移动时，在每个候选网格中依次进行局部路径优化. PORP算法总体框架如图3所示.

对于查询q， $ {v}_{\mathrm{s}} $与 $ {v}_{\mathrm{t}} $分别为起点与终点，当查询q到达QueryWorker( $ {\mathrm{q}\mathrm{w}}_{i} $)时， $ {\mathrm{q}\mathrm{w}}_{i} $基于骨架图计算从 $ {v}_{\mathrm{s}} $到 $ {v}_{\mathrm{t}} $的全局路径 $ {p}_{\mathrm{g}} $，算法过程描述如下.

算法 1　识别全局路径算法

输入：骨架图 $ {G}_{\mathrm{s}} $，查询q( $ {v}_{\mathrm{s}} $, $ {v}_{\mathrm{t}} $)，划分网格.

输出：从 $ {v}_{\mathrm{s}} $到 $ {v}_{\mathrm{t}} $的全局路径 $ {p}_{\mathrm{g}} $.

1. $ {\mathrm{q}\mathrm{w}}_{i} $确定 $ {\mathrm{S}\mathrm{G}}_{\mathrm{s}} $和 $ {\mathrm{S}\mathrm{G}}_{\mathrm{t}} $

2. if $ {v}_{\mathrm{s}} $和 $ {v}_{\mathrm{t}} $不是边界点

3. $ {\mathrm{q}\mathrm{w}}_{i} $发送q( $ {v}_{\mathrm{s}} $, $ {v}_{\mathrm{t}} $)到 $ {\mathrm{g}\mathrm{w}}_{\mathrm{s}} $和 $ {\mathrm{g}\mathrm{w}}_{\mathrm{t}} $

4. $ {\mathrm{g}\mathrm{w}}_{\mathrm{s}} $和 $ {\mathrm{g}\mathrm{w}}_{\mathrm{t}} $计算Top-k频繁路径

5. $ {\mathrm{g}\mathrm{w}}_{\mathrm{s}} $和 $ {\mathrm{g}\mathrm{w}}_{\mathrm{t}} $向 $ {\mathrm{q}\mathrm{w}}_{i} $返回路径信息

6. $ {\mathrm{q}\mathrm{w}}_{i} $将 $ {v}_{\mathrm{s}} $和 $ {v}_{\mathrm{t}} $加入到 ${{G}}_{\mathrm{s}}$

7. end if

8. 在 $ {G}_{\mathrm{s}} $上计算 $ {v}_{\mathrm{s}} $到 $ {v}_{\mathrm{t}} $最短路径 $ {p}_{\mathrm{g}} $

9. return $ {p}_{\mathrm{g}} $

具体步骤如下. 1）若 $ {v}_{{\rm{s}}} $与 $ {v}_{{\rm{t}}} $为边界点，执行第3）步（算法第8行）. 否则，首先由QueryWorker确定 $ {v}_{\mathrm{s}} $和 $ {v}_{\mathrm{t}} $所处的网格，分别记为 $ {\mathrm{S}\mathrm{G}}_{\mathrm{s}} $和 $ {\mathrm{S}\mathrm{G}}_{\mathrm{t}} $（算法第1行）. 然后，将查询q发送给GridWorker $({\mathrm{g}\mathrm{w}}_{\mathrm{s}}$与 ${\mathrm{g}\mathrm{w}}_{\mathrm{t}})$（算法第2、3行）.2） $ {\mathrm{g}\mathrm{w}}_{\mathrm{s}}$与 $ {\mathrm{g}\mathrm{w}}_{\mathrm{t}} $分别在网格 $ {\mathrm{S}\mathrm{G}}_{\mathrm{s}} $和 $ {\mathrm{S}\mathrm{G}}_{\mathrm{t}} $中计算从 $ {v}_{{\rm{s}}} $和 $ {v}_{{\rm{t}}} $到各相应网格内边界点的Top-k频繁路径，并更新旅行代价（算法第4、5行）. 然后将更新的旅行代价发送到 $ {\mathrm{q}\mathrm{w}}_{i} $，在对应骨架图中加入 $ {v}_{\mathrm{s}} $和 $ {v}_{\mathrm{t}} $（算法第6行）. 3）QueryWorker $ ({\mathrm{q}\mathrm{w}}_{i}) $基于骨架图计算从 $ {v}_{\mathrm{s}} $到 $ {v}_{\mathrm{t}} $的全局路径 $ {p}_{\mathrm{g}} $（算法第8行）.

在确定了从 $ {v}_{\mathrm{s}} $到 $ {v}_{\mathrm{t}} $的全局路径 $ {p}_{\mathrm{g}} $之后，便确定了该路径经过的候选网格.然后，PORP算法在每个候选网格中连续进行局部路径优化.

假设 $S=\{{\mathrm{S}\mathrm{G}}_{1}, {\mathrm{S}\mathrm{G}}_{2},\cdots ,$ ${\mathrm{S}\mathrm{G}}_{n}\}$为全局路径 $ {p}_{\mathrm{g}} $经过的候选网格序列，在网格 $ {\mathrm{S}\mathrm{G}}_{i} $（ $i\in [1,\;n]$）内依次进行局部路径优化，算法过程描述如下.

算法 2　局部路径优化算法

输入：q( $ {v}_{\mathrm{s}} $, $ {v}_{\mathrm{t}}) $， $S=\{{\mathrm{S}\mathrm{G}}_{1},{\mathrm{S}\mathrm{G}}_{2},\cdots ,{\mathrm{S}\mathrm{G}}_{n}\}$.

输出：局部优化路径.

1. for each $ {\mathrm{S}\mathrm{G}}_{r}\in S $ do

2. if $ {l}_{j} $处于 $ {\mathrm{S}\mathrm{G}}_{r} $

3. LocalOptimize（ $ {l}_{j} $， $ {\mathrm{S}\mathrm{G}}_{r} $， $ {v}_{x} $）

// $ {v}_{x} $为 $ {p}_{\mathrm{g}} $上位于 $ {\mathrm{S}\mathrm{G}}_{r} $的边界点

4. end if

5. end for

局部路径优化的目的是沿对应网格（算法第1行），基于全局路径 $ {p}_{\mathrm{g}} $，计算从用户位置到下一个边界点的最短路线，这是由算法2中LocalOptimize函数实现的（算法第3行）. 候选网格由不同的Worker维护，因此每个候选网格中的局部路径优化由这些Worker执行. 因此，大量查询的局部路径优化可以由不同的Worker同时进行，以减少每个查询的响应时间.

如果在所规划的路径前方有一个拥堵区域，那么用户会希望避免陷入前方的拥堵区域，基于该想法引入slot.

定义3　slot. 对于给定的一条路径的分段，slot为分段中最后一个节点.

将slot设置为拥挤路段的后一个节点，通过路径优化算法来绕开拥挤路段. 对于用户实时发送的位置 $ {l}_{j} $，在对应的网格中，很容易找到距离 $ {l}_{j} $最近的边界点 $ {v}_{x} $，并在网格内计算 $ {l}_{j} $到 $ {v}_{x} $的最短路径作为基准路径.然后，定义一个旅行代价变化函数：

(1) $R\left(x\right)={C\left({v}_{\mathrm{s}},{v}_{\mathrm{d}}\right)}/{{C}'\left({v}_{\mathrm{s}},{v}_{\mathrm{d}}\right)} .$

式中： $ C({v}_{\mathrm{s}},{v}_{\mathrm{d}}) $、 $ {C'}({v}_{\mathrm{s}},{v}_{\mathrm{d}}) $分别为从 $ {v}_{\mathrm{s}} $到 ${v}_{{\rm{d}}}$的更新前、后的旅行代价. 如果 $ R\left(x\right) $大于阈值 $ \gamma $，则 ${{{v}}}_{{\rm{d}}}$被设置为slot. 最后，在基准路径上依次遍历寻找slot，若在 $ \eta $步内 $ R\left(x\right) $均超过阈值 $ \gamma $，则将第 $ \eta $步访问的节点作为slot. 一旦slot被确定，连续计算 ${{v}_{{\rm{s}}}}$到slot的最短路径，当到达slot后，计算下一个slot，重复上述步骤，当到达网格内边界点后，在下一个网格中进行上述步骤，直至到达终点.

PORP算法主要涉及以下2个主要操作：1）基于骨架图计算一条全局路径，2）网格内局部路径优化. 对于操作1），一条全局路径由Dijkstra算法计算，则其时间复杂度为 $O\left(\right|\varepsilon _{{\rm{s}}}\left|{\mathrm{log}}_{2} \; \left|{{ Y}}_{{\rm{s}}}\right|\right)$，其中 ${|{{ Y}}}_{{\rm{s}}}|$与 $|\varepsilon _{{\rm{s}}}|$分别为骨架图 ${{G}}_{{\rm{s}}}$顶点与边的数量. PORP将规划任务划分成多个局部优化任务，在每个局部优化任务2）中，首先计算一条基准路径，然后通过slot将基准路径划分成多个分段，在每个分段中计算用户位置到slot的最短路径. 假设网格内最大的顶点数与边数分别为 ${|{{Y}}}_{{\rm{g}}}|$和 $|\varepsilon _{{\rm{g}}}|$，网格内slot个数为m，局部路径优化操作在 $ {N}_{{\rm{g}}} $处理器内进行，且执行 ${N}_{{\rm{r}}}$次，则局部路径优化的时间复杂度为O $\left({N}_{{\rm{g}}} \left(m+1\right) \left|\varepsilon _{{\rm{g}}}\right|\left(\mathrm{log_2} \; \left|{{Y}}_{{\rm{g}}}\right|\right)/{N}_{{\rm{r}}}\right)$. 因此PORP算法的总体时间复杂度为 $O\left(\left|\varepsilon _{{\rm{s}}}\right|\mathrm{log_2} \; \left|{{Y}}_{{\rm{s}}}\right|+{N}_{{\rm{g}}} \left(m+1\right)\left|\varepsilon _{{\rm{g}}}\right| \left( \mathrm{log_2} \; \left|{{{ Y}}}_{{\rm{g}}}\right| \right)/{N}_{{\rm{r}}}\right)$.

在多个模拟Master-Worker模型的线程上实现DLG-index和PORP算法. 实验设备系统环境采用Windows10的64位操作系统，计算机硬件配置16 GB内存，1TB ROM，处理器2.00 GHz，4核Intel Corei5. 使用16个线程来模拟Master-Worker模型，其中1个线程作为Master，5个线程作为QueryWorker，10个线程作为GridWorker.

在以下3个真实路网上进行实验：Beijing（BJ）^①、New York（NY）^②和Florida（FLA）^②. 基于实际和模拟旅行时间，将每条道路上的行驶时间转化为边的权重.其中，获取了北京在2008年2月2日—8日的T-drive数据集^[31-32]，包含10357辆出租车的17662998条GPS轨迹，但是T-drive的轨迹无法覆盖北京图的每条边，因此选择北京的最大连通加权子图作为实验数据集，其中包含188229个顶点和436648条边.

采用文献[30]中的路网模型，对道路网络上的边权值进行动态变化，使用 $ \alpha $表示路网上边权重变化的比例，并使用[ $ -\tau ,\; \tau $]表示权重变化的范围.根据文献[30]，设定 $\alpha =$35%以及 $ \tau = $30%，路网信息如表1所示.

为了验证算法的有效性，采用Naive和CANDS^[12]作为基准方法. 1）Naive：朴素方法采用暴力搜索模式，不断优化动态图上的规划路径.具体来说，一旦用户移动到新的位置，它就会重复计算从用户位置到目标的最短路径，一直重复计算直至用户到达目的地. 2）CANDS：CANDS是一项连续最优最短路径查询的算法，基于分布式流处理模式来不断优化动态图上的导航路径. 须遵循其分布式原则，在多个模拟Master-Worker模型的线程上实现CANDS.

与实验中的性能评估有关的一些标准如下所示.

1）基准路径（benchmark path）. 对于某时刻给定查询q，基于该时刻的路网快照，起点到目标点的最短路径称为基准路径.

2）路径规划改进比例 $ \lambda $. 定义改进比例以表示规划路径的优化程度：

(2) $\lambda ={C\left({p}_{{\rm{s}}}\right)}/{C\left({p}_{{\rm{r}}}\right)} .$

式中： $p_{\rm{s}}$为基准路径， $p_{\rm{r}}$为所用PORP算法计算的推荐路径， ${{C}}(p_{\rm{s}})$、 ${{C}}(p_{\rm{r}})$分别为用户在 $p_{\rm{s}} $与 $p_{\rm{r}} $上的旅行代价.

测试网格大小对DLG-index的创建时间和维护代价的影响. 同时，也与CANDS进行相应的比较.由于Naive方法没有辅助索引，不对Naive方法进行测试.

首先比较DLG-index和CANDS在不同网格大小z下索引的构造时间t_c，如表2所示. 可以看出，DLG-index的构建时间随着图的规模的增大而增加，即对于较大规模的图，须构造更多的网格，同时计算更多的Top-k频繁路径，从而消耗更多的时间. 同时，DLG-index的构建时间大约为CANDS的2.0~3.0倍，因为DLG-index须构造前缀路径树来计算边界顶点间的Top-k频繁路径，而CANDS只须计算每个网格中边界顶点间的最短路径. 一旦建立了路径索引，DLG-index中的更新开销比CANDS中频繁计算最短路径的开销要小得多，这将在下面的实验中得到验证.

测试不同网格大小对索引维护的影响，并与CANDS进行比较，如表3所示. 表中，t_m为索引维护时间. 可以看出，CANDS的维护成本几乎是DLG-index维护成本的4倍. 这是因为当路况变化时，CANDS须频繁地计算边界点之间的最短路径，而DLG-index的Top-k频繁路径的变化频率要低得多，并且很容易使用PPT索引进行相应的权重更新.

如式(2)所示， $ \lambda $越大，表明PORP算法在降低旅行代价中效果越明显. 如表4所示为不同slot步数与拥挤度阈值对改进比例的影响. 可以看出，当 $ \eta $增大时， $ \lambda $首先增大，随后缓慢降低，同时 $ \gamma $也有着相似的影响，可以从实验结果看出， $ \eta $与 $ \gamma $不能过大或过小.

查询的响应时间r是指每次优化所消耗的平均时间. 对应不同的网格大小，测试PORP、CANDS和Naive在每个图上响应时间r，结果如图4所示. 首先发送一批查询，然后测量这些查询的平均响应时间. 从结果可以看出，PORP的响应时间明显小于CANDS，此外，当网格大小增加时，PORP的响应时间首先会略微减少，然后逐渐增加. 这是因为网格太小，在路径规划查询中会进行更多的局部路径优化.在这种情况下，调度多个线程的代价也会增加，每次优化的平均响应时间也会增加. 随着网格大小的增加，查询的局部优化次数将减少，线程分配成本也将下降，从而缩短响应时间. 当网格大小增长到某个阈值以上（例如，在BJ上为80）时，每个局部优化中最短路径的计算造成更多代价，并在总代价中起着主导作用. 随着网格变大，响应时间开始增加. 由于Naive不涉及网格划分，网格大小对Naive的响应时间没有影响.

分别比较3种方法的吞吐量.吞吐量是指在查询的每次优化响应时间不超过指定阈值β的条件下，每种方法所能支持的最大查询数 $ {N}_{{\rm{q}}} $. 如图5所示，随着β增大，每种方法在所有数据集上的吞吐量都会显著提高.在并行运行的条件下，PORP总是拥有最大的吞吐量.

测试这3种方法中路径规划查询的处理时间. 处理时间T是指处理查询所消耗的时间的总和. 输入一批查询（ $ {N}_{{\rm{q}}} $=100），测量这些查询的平均处理时间. 由图6中的结果可以看出，每种方法的处理时间都随着查询数量的增加而增加，Naive的处理时间明显大于PORP和CANDS的，且PORP的略优于CANDS的.

如图7所示为路径查询长度l对规划路径实际旅行代价C的影响. 可以看出，旅行代价随着路径长度的增加而明显增加. 尽管CANDS和Naive总是重新计算最短路径，而PORP都会优化局部区域中部分，但是这3种方法的规划路径的旅行代价几乎相等. 这是因为在路况不断变化的情况下，PORP利用局部路径优化，可以较好地提前绕开阻塞的道路，从而使PORP达到与CANDS和Naive相近的旅行代价，但同时PORP计算成本却低很多.

提出并行路径规划算法PORP，结合双层网格索引DLG-index，将整个路网的导航路线持续优化问题转化为多个子网的局部最优路线查找问题，降低了计算复杂度，持续并行地优化导航路线，提高了响应速度，从而在计算成本和计划路线的可用性之间取得平衡.

与CANDS算法相比，PORP的响应时间平均减少了49.6%，处理时间平均减少了28.5%. 可以看出，基于动态路网的路径规划算法给自动驾驶汽车的研究提供了新的机遇，但同时也存在着很多挑战.

在下一步工作中，结合深度学习技术，将考虑未来道路交通状况的变化，同时可以考虑解决多个并发查询共享计算的问题，研究既考虑未来道路交通状况，同时优化多个并发查询共享路径的解决方案.