基于动态路网的层级优先最优路径计算方法

摘要

本发明公开了一种基于动态路网的层级优先最优路径计算方法，包括：步骤1，根据道路等级将路网划分层级，分别生成各层级路网对应的Voronoi图；步骤2，采用层次化的搜索策略进行路径搜索，基于最短路径搜索法分别搜索最优路径的主体部分和分支部分；步骤3，根据最优路径的主体部分和分支部分生成最优路径。本发明可大大减少出行车辆在道路上的行驶时间，并且可响应路网中交通流状态的变化，进而为车辆出行的路径选择提供可靠的实时解决方案，从而使得出行方案更具适应性和可靠性。

说明书

技术领域

本发明属于智能交通技术领域，尤其涉及一种基于动态路网的层级优先最优路径计算方法。

背景技术

近年来，如何在出行的起点和终点间寻找一条最优路径已成为智能交通的热门研究话题。它不仅直接影响了人们的出行效率，同时也涉及到诸如城市发展和环境污染等问题。例如，车辆在一条路况较差的道路上行驶，不仅会增加出行成本，并进一步加剧道路交通堵塞的状况，以及随之而来的尾气污染问题。许多专业的地理信息系统软件(如ArcGIS)都提供了在道路网中求解由源点位置到目标位置的最短路径的功能，但是常规方法都是基于静态交通流信息，并没有结合城市路网上交通流随时空变化的特点来对出行车辆进行有效诱导。

随着信息通信技术的进步和GPS传感器的广泛应用，有学者开始利用移动物体的轨迹来对其行为进行分析，并对其进行动态的监测。其中，出租车的GPS轨迹数据因其包含的即时行车速度可准确反映道路通行状态而备受学者关注。例如，有一些研究学者通过计算每一段道路的通行频率来提取驾驶员的经验进而为他人提供有效的导航服务。还有学者从GPS轨迹数据中来研究大件运输车辆的行车特性。最近有学者开始着手于了解车辆实际的运行路线和GPS模拟线路之间的关系。尽管如此，如何从大量的GPS轨迹数据中提炼出更有用的信息，一直是路线规划行业中一个悬而未决的问题。

此外，在规划车辆出行路线的过程中，能够结合人类的认知行为的研究还不多见，虽然有研究认为人们在出行过程中更倾向于从转向较少的路线上通过，而不仅仅局限于物理意义上的距离最短，因为这将大大减少人们认知的负担，但没有进一步对这些道路的特点进行详细的分析。实际上，路网的等级是道路的一个基本属性，它是根据道路的功能、位置和行车容量而将整个城市的路网划分成了不同的子集。对于距离较长的出行路线，利用路网等级对出行者进行指引会大大降低其认知的负担。另一个重要的原因是由于高等级路网往往对应了较好的行车路况，出行者从高等级路网通行可以大幅度节省出行的时间。

文中涉及如下参考文献：

[1]Chen,B.Y.,et al.,2014.Map-matching algorithm for large-scale low-frequency floating car data.International Journal of Geographical InformationScience,28(1),22–38.doi:10.1080/13658816.2013.816427

[2]Daltona A.M.,Jones A.P.,Panter J.,and Ogilvie D.(2015),Are GIS-modeled routes a useful proxy for the actual routes followed by commuters,Journal of Transport &Health,2,219-229

[3]Geisberger R,Sanders P,Schultes D,and Vetter C 2012Exact routingin large road networks using contraction hierarchies.Transportation Science46:388–404

[4]Hess S.,Quddus M.,Rieser-Schussler N.,Daly A.(2015),Developingadvanced route choice models for heavy goods vehicles using GPS data,Transportation Research Part E,77,29-44

[5]Hu J.H.,Huang Z.,Deng J.(2013),A hierarchical path planning methodusing the experience of taxi drivers,Procedia-Social and Behavioral Sciences,96,1898-1909

[6]Jia T.and Jiang B.(2012),Exploring human activity patterns usingtaxicab static points,ISPRS International Journal of Geo-Information,1(1),89-107.

[7]Jiang B.and Liu X.(2011),Computing the fewest-turn map directionsbased on the connectivity of natural roads,International Journal ofGeographical InformationScience,25(7),1069-1082

[8]Jung S.and Pramanik S.(2002),An efficient path computationmodelfor hierarchically structured topographical road maps,IEEETransactionson Knowledge and Data Engineering,14(5):1029-1046.

[9]Meng L.K.,Hu Z.H.,Huang C.Q.,Zhang W.,and Jia T.(2015),OptimizedRoute Selection Method based on the Turns of Road Intersections:A Case StudyonOversized Cargo Transportation,ISPRS Int.J.Geo-Inf.4(4),2428-2445

[10]Nejad M.M.,Lena Mashayekhy L.,RatnaBabuChinnamR.B.,and PhillipsA.(2016),Hierarchicaltime-dependent shortestpathalgorithms for vehicleroutingunder ITS,IIE Transactions,48(2),158-169

发明内容

本发明的目的是提供一种基于动态路网的层级优先最优路径计算方法。

本发明模仿人类设计出行路径的思维过程，即出行者首先选择高等级道路，而先不考虑道路在物理位置上是否相连。然后利用低等级的路网来逐步连接未连接的高等级道路，直到所有的道路完全相连为止。具体来说，本发明构建了一个随时间变化的路网及与之相应的Voronoi图，Voronoi图不仅可显著提高道路的连接性，进而改善最优路径的可靠性。其次，本发明还提出了一种基于全局和局部的分层路径搜索方法，即从高层级路网递归地向低层级路网搜索出一条首尾相连的路径。

为达到上述目的，本发明采用如下技术方案：

基于动态路网的层级优先最优路径计算方法，包括：

步骤1，根据道路等级将路网划分成K个等级的路网，对K个等级的路网进行分层，获得K个层级的路网，分别生成各层级路网对应的Voronoi图；其中，第k层级的路网由第k等级、第k-1等级……第1等级的路网构成，k＝1，2…K，K值取路网的道路等级数量；

步骤2，基于Voronoi图进行路径搜索，本步骤包括搜索最优路径的主体部分和分支部分；

所述的搜索最优路径的主体部分进一步包括：

2.1利用线性搜索算法由源点O和目标点D匹配路网的起始搜索层级，将起始搜索层级路网对应的Voronoi图作为当前Voronoi图，O和D所在的V区分别记为起点V区和终点V区，V区即Voronoi区域；

2.2基于当前Voronoi图进行最短路径搜索；

2.3顺次检查最短路径所包含路段的连通性，对不连通的前后两路段，以前后两路段所在V区的并集的最小外接矩形为搜索范围，执行子步骤2.4；若所包含所有路段均连通，结束，执行子步骤2.5；

2.4判断当前搜索层级路网是否为最低层级路网，若是，基于搜索范围内的所有层级路网数据进行最短路径搜索，将搜索到的路径保存到候选路径数据集；否则，将当前搜索层级路网的下一层级路网所对应的Voronoi图作为当前Voronoi图，搜索范围内遍历当前Voronoi图的所有V区，根据当前Voronoi图中道路路段间的空间关系确定当前Voronoi图中的起点V区和终点V区，执行子步骤2.2；

所述的搜索最优路径的分支部分进一步包括：

2.5当前搜索层级路网初始化为子步骤2.1所匹配的起始搜索层级路网的下一层级路网；

2.6基于当前搜索层级路网对应的Voronoi图，以O或D所在的V区为搜索范围，在当前搜索层级路网中寻找与该搜索范围相交的V区；

2.7判断该相交的V区是否为主体部分所在的V区，若是，将当前搜索层级路网的下一层级路网作为当前搜索层级路网，执行子步骤2.6；否则，基于当前搜索层级路网对应的Voronoi图，以O所在的V区为起点V区或以D所在的V区为终点V区，以主体部分所在V区为终点V区或起点V区；

2.8基于当前搜索层级路网对应的Voronoi图进行最短路径搜索；

2.9将当前搜索层级路网的下一层级路网作为当前搜索层级路网，基于当前搜索层级路网对应的Voronoi图，以O所在的V区为起点V区或以D所在的V区为终点V区，以所搜索的最短路径所在的V区为终点V区或起点V区，执行子步骤2.8；

2.10重复子步骤2.8～2.9直至O或D落至最短路径或当前搜索层级路网为最低层级路网；

步骤3，根据步骤2所获得最优路径的主体部分和分支部分生成最优路径。

步骤1中所述的对K个等级的路网进行分层，具体为：

(1)采用如下规则对路段进行分裂和合并：

所述的分裂原则为：

当多条路段相交于一交点，且该交点不同时为该多条路段的端点时，对该多条路段进行分裂，分裂时遵循“低等级路网被高等级路网打断，高等级路网不被低等级路网打断”；

所述的合并原则为：

对仅有一个交点的两条路段，若该交点同时为两条路段的端点，对该两条路段进行合并；

(2)基于路段分裂和合并后的路网进行分层，其中，第k层级的路网由第k等级、第k-1等级……第1等级的路网构成。

子步骤2.1中所述的利用线性搜索法确定搜索路网的起始层级，具体为：

将源点O和目标点D的连线延长至连线总长度的10％，即得到搜索算子，获取与搜索算子相交的所有路段的层级，最高层级即起始层级。

子步骤2.1中，若O和D所在的V区相同，将该相同V区中路段保存到候选路径数据集后，结束，然后执行子步骤2.5。

子步骤2.2中，以车辆通过各V区的历史平均时间为各V区的权重，基于当前Voronoi图进行最短路径搜索获得最短路径。

所述的车辆通过各V区的历史平均时间采用如下方法获得：

获取V区内的采样轨迹点，利用采样轨迹点计算V区内车辆的历史平均行车速度，V区内所包含路段的实际长度除以历史平均行车速度，即车辆通过V区的历史平均时间。

子步骤2.3中，将连通的前后两路段中的前一路段保存到候选路径数据集；若连通的两条路段中后一条路段为最后一条路段，则将后一条路段也保存到候选路径数据集。

步骤3具体为：

对主体部分和分支部分所包含路段进行如下操作：

(1)移除重叠路段；

(2)利用路段间的空间关系计算前后路段的交点；

(3)对首尾两路段进行修剪，去除首尾路段上不合理部分；

(4)依次连接前后两个交点，即得最优路径。

步骤3还包括：

找到首尾两路段上源点和/或目标点的最近邻点，将其作为最优路径的真实源点和/或目标点。

和现有技术相比，本发明具有如下优点和有益效果：

本发明不仅可很好地反映人类认知的思维方式，并且还有机地结合了经典Dijkstra算法和基于层级路网的搜索算法。实验证明，本发明可大大减少出行车辆在道路上的行驶时间，并且本发明可响应路网中交通流状态的变化，进而为车辆出行的路径选择提供可靠的实时解决方案，从而使得出行方案更具适应性和可靠性。

附图说明

图1为路网及其Voronoi图的示意图，其中，图(a)为路网及其Voronoi图，图(b)为各层级路网中各路段间的拓扑关系，图(c)为各层级路网中各路段Voronoi图的拓扑关系；

图2为Voronoi图的具体生成流程示意图；

图3为路网的道路连通度分布示意图；

图4为Voronoi图的道路连通度分布示意图；

图5为不同时段内城市路网的历史平均行车速度分布图；

图6为图5中b时段、c时段、d时段和e时段的城市道路网行车速度时空分布示意图，其中，图(a)为b时段的城市道路网行车速度时空分布示意图，图(b)为时段c相对于时段b城市路网上行车速度的变化示意图，图(c)为时段d相对于时段c城市路网行车速度的变化示意图，图(d)为时段e相对于时段d城市路网行车速度的变化示意图；

图7为本发明流程示意图；

图8为实施例所获得的最优路径示意图；

图9为实施例所获得最优路径结果中各级道路的使用情况，其中，图(a)为实施例中采用方法A所获得最优路径结果中各级道路的使用情况；图(b)为实施例中采用方法B所获得最优路径结果中各级道路的使用情况；图(c)为实施例中采用方法C所获得最优路径结果中各级道路的使用情况；

图10为实施例所获得最优路径结果中路段长度和路段数量占比的统计图，其中，图(a)为实施例所获得最优路径结果中路段长度占比的统计图；图(b)为实施例所获得最优路径结果中路段数量占比的统计图；

图11为实施例中三种方法的计算效率对比图。

具体实施方式

路网实际上是一个与路网等级相关联的具有层次化结构的数据集合。数学上，平面道路网络表示为G(V,E)，V表示道路交叉口的集合，E表示路段的集合。例如，有三个等级的路网可以表示为HG(V',E')，V'是由V¹、V²和V³构成的集合，E'是由E¹、E²和E³构成的集合，V¹、V²、V³分别表示不同层级的道路交叉口端点的集合，E¹、E²、E³分别表示不同层级的路段的集合。其中：

E¹＝{e|e∈E>

E²＝{e|e∈E>

E³＝{e|e∈E>

e.class表示路段e的等级，E¹表示第一层级的路段的集合，该集合由第一等级的路段构成；E²表示第二层级的路段的集合，该集合由第一等级和第二等级的路段构成；E³表示第三层级的路段的集合，该集合由第一等级、第二等级和第三等级的路段构成。

V¹＝{v|v∈V>

V²＝{v|v∈V>

V³＝{v|v∈V>

e(v).class表示道路交叉口端点v所在道路的等级，V¹表示第一层级的道路交叉口端点的集合，该集合由第一等级道路的交叉口端点构成；V²表示第二层级的道路交叉口端点的集合，该集合由第一等级道路和第二等级道路的交叉口端点构成；V³表示第三层级的道路交叉口端点的集合，该集合由第一等级道路、第二等级道路和第三等级道路的交叉口端点构成。

一旦HG(V',E')构造完成，其相应的Voronoi图也可以相应得到。图1为一个三级路网及其Voronoi图的示意图。其中，图1(a)显示了第一层级、第二层级和第三层级的路网及其Voronoi图，需要注意的是每一条道路对应一个Voronoi区域，低等级路网被高等级路网所打断，但高等级路网不会被低等级路网打断。图1(b)显示了各层级路网中各路段之间的拓扑关系。图1(c)显示了各层级路网中各路段对应的Voronoi图的拓扑关系。从图中可以看出，基于Voronoi图的数据结构大大改善了路网之间的连通性。

因此，Voronoi图的生成过程可以被描述为以下三个步骤，参考图2：

首先，根据道路等级对平面路网数据进行过滤，将路网划分成三个子网络，分别记为第一等级路网、第二等级路网、第三等级路网。

其次，按照分层规则对路网进行分层，获得三个层级的路网，分别记为第一层级路网、第二层级路网、第三层级路网。

所采用的分层规则如下：

(1)当多条路段相交于一交点，且该交点不同时为该多条路段的端点时，对该多条路段进行分裂，分裂时遵循“低等级路网被高等级路网打断，高等级路网不被低等级路网打断”。

路段相交时，低等级路网被高等级路网所打断，而高等级路网不被低等级路网打断，这主要是为了避免在低等级路网搜索路径时产生失败，进而提高路径搜索的可靠性。打断路网的操作主要是为了确保低等级路网可以将高等级路网进行有效连接，见图1(a)。

(2)当两条路段有且只有一交点，且该交点同时是这两条路段的端点，此时合并这两条路段，这样可有效减少路段数量。

(3)基于路段分裂和合并后的路网进行分层，其中，第三层级路网由第一等级路网、第二等级路网和第三等级路网构成，第二层级路网由第一等级路网和第二等级路网构成，第一层级路网即第一等级路网。

最后，基于各层级路网分别生成相应的Voronoi图。通过对路网生成相应的Voronoi图，道路的连通性会大大增强，见图3～4。

本发明中，通过对各路段生成对应的Voronoi区域，使得线状的道路图层数据转换为面状数据，使得原始路段间的连通性发生了改变。原先不连通但在空间范围内相邻的路段在面状图层中却成为了相邻的要素，而原先连通的道路在面状图层中仍然保持连通性，这就大大增加了路径选择的可能性。

当Voronoi区域连通，而实际路段不连通时，将相应路段所在的Voronoi区域作为搜索范围去寻找下一层级的路网数据，在找到的路网数据上进行最优路径搜索过程。以此类推，直至Voronoi区域内的路段两两连通或获取了最底层级路网数据。最后，在各层级路网中找到的路段片段拼接，即得到最终的最优路径。

一旦基于Voronoi图的分层路网构造完成后，通过为各路段分配不同时段下的行车速度值，即可得到随时间变化的行车速度路网模型。本具体实施方式中，将一周分成工作日和周末，将一天划分为12个时段，所分配的行车速度为对应Voronoi区域内所有采样轨迹点在各时段下的历史行车速度的平均值。图5所示为不同时段内，城市路网的历史平均行车速度分布图，从中不难发现，不同等级的路网呈现出相似的速度分布模式，即在白天拥有较慢的行车速度而在晚上拥有较快的行车速度。其次，高等级路网比低等级路网的平均行车速度要快的多，这就说明引导车辆在高等级路网上行驶将有利于提高其出行效率。通过截取四个时段上路网的速度分布发现，时段b上，大多数最高等级路网拥有行车速度的最大值，而靠近城中心的道路的行车速度相对较慢，显得道路非常拥挤，见图6(a)。图6(b)显示了时段c相对于时段b城市路网上行车速度的变化值，总得看来，行车速度平均下降了0.89km/h，并且大多数的一级路网上的行车速度有了明显的下降。图6(c)显示了时段d相对于时段c城市路网上行车速度的变化值，可以发现路网中的行车速度均值下降了大约0.66公里/小时，大部分的变化仍然发生在主干道路上。图6(d)表明时段e相对于时段d，路网的平均行车速度大约下降了0.7km/h，并且发生变化的路段主要集中在第三等级的路网上。

本发明采用层次化的搜索策略进行路径搜索，包括全局搜索和局部搜索两部分。全局搜索是利用Voronoi图来构建由高层级路网所形成的路网骨架，全局搜索所计算的路径不一定真实相连。局部搜索则利用低层级路网来解决高层级路网不相连的问题。事实上，这是一个利用低层级路网来不断缝合高层级路网间缝隙的递归过程，最终形成一条最佳的出行路径。由此可见，本发明搜索方法非常适合处理大规模道路网中最优路径的计算问题，其填补了传统Dijkstra算法和在ArcGIS中基于层级路网搜索算法之间的差距。

本发明搜索方法主要包括如下三大步骤：

一、搜索最优路径的主体部分

本步骤是为了寻找最优路径的主体部分。给定源点O和目标点D，利用线性搜索法确定搜索路网的初始搜索层级，将源点O和目标点D的连线延长其总长度的10％，即得到搜索算子。获取与搜索算子相交的所有路段的层级，最高层级即起始层级；获取起始搜索层级的路网及对应的Voronoi图，将起始搜索层级路网对应的Voronoi图作为当前Voronoi图，确定源点O和目标点D所在的Voronoi区域。

若源点O和目标点D所在的Voronoi区域相同，将该相同Voronoi区域中路段保存到候选路径数据集。若源点O和目标点D所在的Voronoi区域不相同，将O和D所在的Voronoi区域分别作为起点Voronoi区域和终点Voronoi区域，以车辆通过各Voronoi区域的历史平均时间为各Voronoi区域的权重，基于当前Voronoi图进行最短路径搜索，以获得最短路径。

顺次检查所获得最短路径包含路段的连通性，若前后两条路段连通，则将前一条路段保存到候选路径数据集。若连通的两条路段中后一条路段为最后一条路段，则将后一条路段也保存到候选路径数据集。若前后两条路段不连通，求该前后两条路段所在Voronoi区域的并集，以该并集的最小外接矩形作为搜索范围。

搜索范围内遍历当前搜索层级路网的下一层级路网所对应Voronoi图中的所有Voronoi区域，此时，将下一层级路网作为当前搜索层级路网，下一层级路网对应的Voronoi图即当前Voronoi图。根据当前Voronoi图中道路路段间的空间关系确定当前Voronoi图中的起点Voronoi区域和终点Voronoi区域，并基于当前Voronoi图进行最短路径搜索。判断搜索得到的最短路径中相邻的两个Voronoi区域内的真实路径是否相交，若相交，则将该相邻Voronoi区域中路段保存到候选路径数据集。若不相交，将该相邻Voronoi区域中前一Voronoi区域和后一Voronoi区域的并集的最小外接矩形作为搜索范围，递归该最短路径搜索过程。

根据深度优先检索策略，本步骤搜索过程将重复进行直至真实路段相连通或者已搜索到最低层级的路网。各Voronoi区域包含一条真实路段，但Voronoi区域相邻并不代表真实路段也连通，只有在源点和目标点间存在了连通的路径，则表明真实道路已相连通。

车辆通过Voronoi区域的历史平均时间这样获得：

获取Voronoi区域内的采样轨迹点，利用采样轨迹点计算Voronoi区域内车辆的历史平均行车速度，Voronoi区域内所包含路段的实际长度除以历史平均行车速度，即车辆通过Voronoi区域的历史平均时间。

二、搜索路径的分支部分

本步骤是寻找从主体部分到源点O或目标点D的最优路径，其本质上是由主体部分分别向源点O或目标点D逐步逼近的搜索过程。具体来说，首先，以源点O或目标D点所在的Voronoi区域为搜索范围，在起始搜索层级路网的下一层级路网所对应的Voronoi图中寻找与该搜索范围相交的Voronoi区域。判断该相交的Voronoi区域是否为主体部分所在的Voronoi区域，若是，继续在当前搜索层级路网的下一层级路网所对应的Voronoi图中寻找与搜索范围相交的Voronoi区域，直到所寻找到的相交的Voronoi区域不是主体部分所在的Voronoi区域或当前搜索层级路网已为最低层级路网。此时，在当前搜索层级路网对应的Voronoi图中进行最短路径搜索。

循环上述过程，直至源点O或目标点D所在的Voronoi区域为最低层级路网对应的Voronoi区域，或源点O或目标点D已落在最短路径上。每次递归计算得到的路段均保存于候选路径数据集。

三、最优路径的生成

通过步骤二和三可获得有序的基于路网层级的路段集，即候选路径数据集。基于候选路径数据集，首先，移除候选路径数据集中的重叠路段。然后，利用路段间的空间关系，计算前后路段的交点。然后，对首尾两条路段进行修剪，并去除首尾路段上不合理部分。最后，依次连接前后两个交点，即得到了真实的最优路径。

若步骤二所得分支部分中，源点O和/或目标点D未落在分支部分的任何路段上，还需进行操作：通过邻域分析，找到首尾路段中离源点和/或目标点最接近的点作为最优路径的真实源点和/或目标点。

图7为本发明搜索路径的简单示意图，图中采用不同粗细的线条表示不同层级的路网数据，两个黑色实心点分别代表源点O和目标点D。首先，按照路网层级从高到低搜索最优路径的主体部分，包括粗实线的第一等级路段、中粗实线的第二等级路段和细实线的第三等级路段。接着，搜索最优路径的分支部分，对于O点，搜索到最低层级路网时，O点所在Voronoi区域一直属于主体部分的Voronoi区域，将O点在主体部分首路段上的投影点作为最优路径的一个端点。对于D点，可看到最短路径逐渐从最近的主体部分通过第二等级路段和第三等级路段向D点逼近，最后找到D点在最短路径上投影点作为最优路径的另一个端点，这样就得到了最终的最优路径。

为验证本发明的优越性，将武汉市道路网络作为实验数据，选取四个典型时段作为研究对象，并与传统方法(经典Dijkstra算法和ArcGIS中基于层级路网搜索算法)进行比较。应当注意的是，本发明采用车辆行驶时间作为权重，而传统方法中则利用道路实际长度作为权重。因此，行程时间(T)和行程长度(D)是两个作为基准的参数。同时，对其中12组随机选择的O/D点及其之间的最优路径做了详细的比较与分析。

表1所示的是在四个典型时段下三种方法的路径分析结果比较，从行程长度方面来看，本发明方法比传统的Dijkstra算法计算得到的路径要长大约23％，但是比ArcGIS中基于层级路网搜索算法计算得到的路径要短30％。从行程时间来看，本发明方法在四个典型时段下计算得到的路径比其他两种方法得到的路径分别要快41％和21％、34％和10％、39％和19％、39％和19％。此外还可以发现，方法C所耗费的旅行时间比方法B更少，因为高等级的道路得到了更好的利用。这些结果是令人鼓舞的，因为它表明本发明正好处于方法B和C之间，而且还有效地避免了交通拥堵的路段，有效地降低了出行时间。我们还发现对于同一对O/D来说，在不同时段下出行的时间耗费变化较小，因此选择时段b作为具体分析的时段，见图8所示，其为表1中12组实验的最优路径，其中浅灰色、深灰色、黑色路径分别表示方法A、B、C得到的最优路径。

表1三种实验结果中行程长度和行程时间的对比

表2中，D表示行程长度，T表示行程时间，A表示本发明方法，B表示传统的Dijkstra算法，C表示ArcGIS中基于层级路网的搜索算法，B(+)表示本发明方法相对于方法B的增量百分比，B(-)表示本发明方法相对于方法B的减量百分比，C(-)表示本发明方法相对于方法C的减量百分比。

分析由本发明方法求得的最优路径结果中各级道路的使用情况(不同级别道路的长度占比和路段数量占比)，见图9所示。从图中可以看出，本发明方法得到的最优路径中二级路网占据了72％，这几乎是传统Dijkstra方法的两倍，是ArcGIS中基于层级路网的搜索算法的四倍。而由传统的Dijkstra方法计算得到的路径中三级路网占据了大约66％的比重。在ArcGIS中基于层级路网的搜索算法中一级路占据了大约78％的比重。对于路段数量而言，也得到了类似的结果。这些实验数据进一步证明了本发明方法介于传统方法和ArcGIS中基于层级路网的搜索算法之间。因此，本发明方法可有效防止传统算法偏向与从低级路网上通过的弊端，这些低等级的路网往往会发生交通拥堵。同时，又通过间断性地访问低级路网，显著降低了路程的长度来提高基于层级路网的搜索算法的可靠性。

为了增强论证，本发明又在时段b上选择了1000组O/D点进行了对比实验，对于路线的长度，本发明方法比方法B要长28％，但是比方法C要短11％。这与前面实验结果基本保持一致。同时，与方法C相比，本发明方法对路径长度更敏感。对于行程时间而言，本发明方法得到的路径其行程时间比方法B和方法C少了26％和9％，这也与前面的实验结果相吻合，同时也证明了本发明方法结果的稳定性。另外见图10所示，对比道路的利用情况基本与前面的实验结果保持一致，其中二级道路占据了主要比重，路径总长度达到63％，路段总数量达到61％。而方法B中主要占据比重的是三级路网，方法C中主要占据比重的是一级路网。更有趣的是，我们发现，方法C对路网的数据质量有一定的要求，导致了在本实验中产生了7.3％的分析失败。

将以上三种方法的计算效率进行对比分析，下面通过逐渐增加的道路网络规模，测试计算效率的变化趋势。

见图11，当路网规模较小时(例如包含了500条路段的路网数据)，三种方法的计算效率没有太大差异。然而，随着网络规模增加，方法B的计算效率呈现出指数级增长，这是远超出其他两种方法且不能满足实时路由分析的需要。而本发明方法和方法C在路网规模较大时，能提供实时的导航服务，体现出了明显的优势。分析结果表明，本发明方法比传统方法更加有效，而本发明方法和方法C保持在一个相近的水平上，这主要归因于本发明方法采用了空间层次的思维模式以及与之相应的全局和局部搜索的计算方法，因此将该方法应用于一个大型的路网上进行最优路径的分析是可行的也是有效的。

总之，利用本发明方法计算得到的路径长度比Dijkstra算法得到的路径要长，但是基本比由基于层级路网搜索算法得到的路径长度要短。但是从行程时间上看均比两者要短；因此，本发明方法优于其他两种方法。