基于骨干路网分层的多路径选择方法

摘要

本发明公开了一种基于骨干路网分层的多路径选择方法，包括如下步骤：a.抽取城市路网中的骨干路网，并对骨干路网立交桥区进行连接简化处理；b.判断给定的起终点对的直线距离与设定的路程远近阈值的大小，分别根据步骤c生成近程路径集，根据步骤d生成远程路径集；c.用Dijkstra搜索算法以近程综合效用最小生成近程路径集；d.用Dijkstra搜索算法以远程路径的综合效用最小分别得到骨干路网的进节点集和出节点集；将进节点和出节点组合配对后用搜索每组进节点和出节点之间的最快路径，得到骨干路径集；组合得到远程路径集。本发明方法可生成合理的驾驶路径集合，能准确地反映出行路径状况。

说明书

技术领域

本发明涉及智能交通应用技术领域，具体地说是一种基于骨干路 网分层的多路径选择方法。

背景技术

随着我国城市化、现代化、机动化的同步快速发展，各大城市人 口迅速增长，机动车保有量更是增长迅猛，交通拥堵日益严重。城市 道路的供给增长远远跟不上生活水平提高后人们对于小汽车舒适出行 的需求增长。北京、上海等特大城市市区内道路交通流量已呈现超饱 和状态，如果再遇上大雨大雪等恶劣天气，交通面临瘫痪的危险。

动态路径选择作为智能交通的一个重要应用，依据城市道路网中 路段的拓扑关系和实时交通信息为出行者规划最优出行策略，从而能 够减少车辆在路网中的延误，最大限度地利用道路资源。另一方面， 动态路径选择也是交通规划模型中的重要环节，通过模拟出行者的出 行路径选择行为，分析交通出行在路网中的时空分布，从而对交通规 划、政策进行有效的预测和评估。因此，对城市中车辆出行的动态路 径选择方法进行深入研究，准确计算生成一定城市路网结构和出行环 境下的合理的路径选择集合，对出行者动态路径导航、城市交通规划 分析模型都有巨大的理论意义和实际应用价值。

路径集的生成问题，已经在计算机科学领域获得较多的研究，尤 其是最短路的生成，在图论中获得了较深入的分析。从历史的角度来 看，最为经典的最短路生成算法毫无疑问是Dijkstra(1959)，用于解 决在一个权重非负的网络G(N,E)中的单源最短路问题。值得注意的是， 采用不同的数据结构和优先队列实现方式，能使得Dijkstra算法达到 不同的计算效率。基于Dijkstra算法有若干变种，以使用在应用场景 下。Dijkstra算法的变种主要通过扩展网络节点的标签，记录路径到 达某一节点的转弯数、路口数等信息，从而通过各节点标签的加权综 合效果，按照设计者的要求，生成符合效用函数最优的最短路。但是 将这些路径搜索算法往往适用于拓扑结构简单的高速公路网，用于城 市路网中时，往往其搜索结果都不是理想的或者说驾驶员常规会使用 的驾驶路径。

另一方面，在生成最短路之后，为了生成一个较好的路径集，接 下来的主要工作是继续生成次短路、第三短路，直到总共生成n条路 （n为建模人员预定义的一个最短路阈值）。相比于最短路算法，路径 集生成算法关注的是怎样充分利用已计算的最短路径集，来进一步获 得新的最短路。鉴于城市路网中根据不同时间路况的最短路选择都难 以搜索到合理的驾驶路径，进一步生成合理的路径选择集合更加困难。

传统最短路或多条路算法多立足于理论角度，保证了解的最优和 无环，而无法保证路径的“合理性”。这里的“合理性”是指在路径 生成过程中，能否涵盖多种人真实选择的行驶路径。每个城市的路网 都拥有自身的静态特征，单纯的最短路或者最快路，并不能很好地对 “合理性”进行体现。

因此，为了提供更好的出行者动态路径导航服务，为了更合理准 确地模拟城市车辆出行行为以支撑决策支持分析工作，急迫需要研发 合适的方法，以实现在城市路网中，给定任意出发时间下的起点和终 点，生成“合理”的驾驶路径集合，尽量准确地反映真实司机对于出 行路径的判断或者提出更为可靠的路径规划建议。有鉴于此，本发明 人积极加以研究和创新，最终研发出一种基于骨干路网分层的多路径 选择方法，以解决上述问题。

发明内容

为了解决现有技术中存在的上述问题，本发明提供了一种基于骨 干路网分层的多路径选择方法，以实现在城市路网中，给定任意出发 时间下的起点和终点，生成合理的驾驶路径集合，尽量准确地反映真 实司机对于出行路径的判断或者提出更为可靠的路径规划建议。

为了解决上述技术问题，本发明采用了如下技术方案：

基于骨干路网分层的多路径选择方法，包括如下步骤：

a.抽取城市路网中的骨干路网，并对骨干路网立交桥区进行连接 简化处理；

b.对给定的起终点对计算出行起终点间的直线距离，并比较起终 点间的直线距离与设定的路程远近阈值的大小，如果起终点间的直线 距离小于路程远近阈值，则根据步骤c生成近程路径集；如果起终点 间的直线距离大于等于路程远近阈值，则根据步骤d生成远程路径集；

c.以转弯数量和旅行时间的加权和作为路径的近程综合效用U₁， 并以近程综合效用U₁最小代替Dijkstra搜索算法中的距离最短进行计 算，从而生成近程路径集；

d.以转弯数量和旅行时间的加权和作为起点到骨干路网进节点间 的综合效用U₂，并用该综合效用U₂最小代替Dijkstra搜索算法中的距 离最短进行计算，从而得到进节点路径集和相应的骨干路网进节点集； 以转弯数量和旅行距离的加权和作为骨干路网出节点到终点间的综合 效用U₃，并用该综合效用U₃最小代替Dijkstra搜索算法中的距离最短 进行计算，从而得到出节点路径集和相应的骨干路网出节点集；将进 节点和出节点组合配对后用Dijkstra搜索算法搜索骨干路网上每组进 节点和出节点之间的最快路径，得到骨干路径集；进节点路径、骨干 路径和出节点路径组合得到远程路径集。

进一步，所述步骤a中：

抽取骨干路网包括：a1.对城市路网数据进行编码处理，其中每个 节点赋值唯一编号，每个路段赋值唯一编号，明确路段起终节点编号； a2.根据城市道路等级以及参考城市具体道路的功能重要性，抽取城市 重要道路网，形成单独的骨干路网层数据。

进一步，所述步骤a中的骨干路网立交桥区的连接简化为，a3.生 成虚拟连接匝道，使一个方向进入路段直接连接到其它方向的驶出路 段。

进一步，所述步骤c中，所述近程综合效用U₁通过如下公式获得： U₁=β₁×转弯数+β₂×旅行时间，其中β₁、β₂分别为近程路径选择的 转弯系数和旅行时间系数。

进一步，所述步骤c中，以近程综合效用U₁最小代替Dijkstra搜 索算法中的距离最短进行计算获得起终点间近程综合效用U₁最小的路 径L₁，对路径L₁中的路段逐个进行打断，并分别以近程综合效用U₁最 小代替Dijkstra搜索算法中的距离最短进行计算，对打断路段的起点 至终点D间进行路径搜索，从而获得打断路段的起点到终点间的近程 综合效用U₁最小的路径，并分别与路径L₁起点到打断路段起点的原路 径组合得到起点至终点的路径L₂-L_n，路径L₁-L_n组成近程路径集。

进一步，所述步骤c中，对路径L₂-L_n中近程综合效用U₁最小的路 径L_i重复对路径L₁的操作，从而获得路径L_n+1-L_m以增加近程路径集中 路径的个数。

进一步，所述近程路径集中的路径按照各自的近程综合效用U₁值 从小到大排序。

进一步，所述步骤d中，U₂=β₃×转弯数+β₄×旅行时间；U₃=β₃×转弯数+β₅×旅行距离；其中β₃、β₄和β₅分别为远程路径选择的 转弯系数、旅行时间系数和旅行距离系数。

进一步，对所述步骤d中骨干路径集中的每个路径分别进行如下 处理以增加骨干路径集中的路径个数：对每个路径中的每一路段依次 打断，并分别用Dijkstra搜索算法搜索骨干路网上打断路段的起点到 对应的出节点之间的旅行时间最短的路径，并将新搜索得到的路径与 进节点至打断路段起点间的路径组成的路径加入骨干路径集。

进一步，将远程路径集中的路径按各自的全路经综合效用U₄的值 从小到大排序，U₄=β₃×转弯数+β₄×旅行时间+β₆×骨干网里程比例， 其中β₃、β₄和β₆分别为远程路径选择的转弯系数、旅行时间系数和 骨干网里程比例系数。

进一步，步骤a中所述城市路网为已经处理好的具备连通性和方 向性拓扑规则的城市路网矢量数据。

进一步，所述转弯数是指该路径中左转弯、右转弯和调头的总次 数；所述旅行时间是根据不同的出发时间，根据各个路段在该时刻的 实时或历史参考旅行速度计算的该路径所需旅行时长；所述旅行距离 是指该路径的实际长度。

进一步，所述Dijkstra搜索算法为典型的Dijkstra单源最短路 径算法。

进一步，所述骨干网里程比例是指该路径中在骨干网上的里程占 路径总里程的比例。

与现有技术相比，本发明的有益效果在于：

本发明的基于骨干路网分层的多路径选择方法实现在城市路网 中，给定任意出发时间下的起点和终点，生成合理的驾驶路径集合， 尽量准确地反映真实司机对于出行路径的判断或者提出更为可靠的路 径规划建议。

附图说明

图1为本发明的基于骨干路网分层的多路径选择方法的流程图；

图2为实施例中北京市中心城区骨干路网分层示意图；

图3为立交桥区复杂匝道连接简化方法示意图；

图4为北京市基于骨干网分层的城市综合效用最优动态多路径选 择系统界面图；

图5A-图5D为高德导航路径结果、谷歌自驾导航路径结果和本发 明方法结果的路径图。

具体实施方式

下面结合附图和具体实施例对本发明作进一步详细描述，但不作 为对本发明的限定。

本发明中，城市路网是指已经处理好的具备连通性和方向性拓扑 规则的城市路网矢量数据。

转弯数是指该路径中左转弯、右转弯和调头的总次数。

旅行时间是根据不同的出发时间，根据各个路段在该时刻的实时 或历史参考旅行速度计算的该路径所需旅行时长。

旅行距离是指该路径的实际长度。

骨干网里程比例是指该路径中在骨干网上的里程占路径总里程的 比例。

Dijkstra搜索算法是指典型的Dijkstra单源最短路径算法。

北京市城区的路网结构以矩形环状加放射线为主，道路多以此为 依托，与经纬线平行网状分布。先后依托城市扩展，建设了二、三、 四、五和六环路。总长度超过五百公里的北京新“七环路”已经形成 半圆。全市立交桥数共有381座，京哈、京沈、京津塘、京石、八达 岭、京承、京开等多条高速公路流经北京。北京机动车保有量突破500 万辆，城市交通面临更大考验。

目前北京市中心城区面积1085平方公里，快速路里程263公里， 主干路里程861公里，次干路里程629公里，道路总里程6258公里。 北京市城市路网密集，结构复杂，各条高速路、城市快速路以及部分 主干道都设有主辅路，车辆出行经常上下主辅路，过立交，且北京市 拥堵严重，早晚高峰时为避开严重拥堵路段，经常绕行小路更为合适。 另一方面，北京是国际化大都市，地域面积又广，居民日常出行距离 长，起终点间往往存在非常多的连通路径，这些实际情况都使得在北 京市城市路网中，对给定任意出发时间下的起点和终点，生成“合理” 的驾驶路径集合，尽量准确地反映真实司机对于出行路径的判断或者 提出更为可靠的路径规划建议，具有相当的难度。

以北京市为例，图1为本发明的基于骨干路网分层的多路径选择 方法的流程图。如图1所示，基于骨干路网分层的多路径选择方法， 包括如下步骤：

步骤a、对城市路网分层处理，抽取北京市中心城区的骨干路网， 并完成对立交桥区的连接简化处理。抽取骨干路网具体如下：

a1.对路网数据进行编码处理，每个节点赋值唯一编号，每个路段 赋值唯一编号，明确每一路段起终节点编号；

a2.根据城市的道路现状等级以及参考某些具体道路的功能重要 性，抽取中心城区的重要道路网，形成单独的骨干路网层数据；参见 如2，图2为北京市中心城区骨干路网分层示意图；图中的粗线条为提 取出的中心城区的骨干路网。

立交桥区的连接简化处理如下：

a3.对骨干路网层数据中的立交桥区的复杂匝道连接进行简化，生 成虚拟连接匝道，从而将一个方向进入路段直接连接到其它方向的驶 出路段；一个方向进入路段一般连接三个或多个方向的驶出路段。参 见如图3A、图3B和图3C，图3A、图3B和图3C分别为新兴桥西-北、 西-南和西-东的立交桥区复杂匝道连接简化方法示意图。图中的粗实 线为实际连接匝道，虚线为虚拟连接匝道。

步骤b、对给定的起终点对（O，D）计算出行起终点间的直线距离， 并比较起终点间的直线距离与设定的路程远近阈值的大小，如果起终 点间的直线距离小于路程远近阈值，则根据步骤c生成近程路径集； 如果起终点间的直线距离大于等于路程远近阈值，则根据步骤d生成 远程路径集；路程远近阈值的设定根据城市规模等实际情况确定。北 京将路程远近阈值设定为4公里。

步骤c、以转弯数量和旅行时间的加权和作为路径的近程综合效用 U₁，并以近程综合效用U₁最小代替Dijkstra搜索算法中的距离最短进 行计算，从而生成近程路径集，具体如下：

c1.近程综合效用U₁通过如下公式获得：U₁=β₁×转弯数+β₂×旅行 时间，其中β₁为近程路径选择的转弯系数，β₂为近程路径选择的旅 行时间系数；上述系数及本发明中的其他系数可根据对城市出行路径 选择调查数据标定结果确定。针对北京市上述系数的取值为：β₁＝-0.2， β₂=-0.7。

c2.以近程综合效用U₁最小代替Dijkstra搜索算法中的距离最短 进行计算获得起终点间近程综合效用U₁最小的路径L₁。

c3.对路径L₁中的路段逐个进行打断，并以近程综合效用U₁最小代 替Dijkstra搜索算法中的距离最短，对打断路段的起点至终点D间进 行路径搜索，从而获得打断路段的起点到终点间的近程综合效用U₁最 小的路径，并分别与路径L₁起点到打断路段起点的原路径组合得到起 点至终点的路径L₂-L_n，路径L₁-L_n组成近程路径集。

c4.上述L₁-L_n组成近程路径集即构成该近程起终点对（O,D）之间 的可选路径集。

c5.为了增加近程路径集中路径的数量，可对L₂-L_n中的近程综合效 用U₁最小的路径L_i继续步骤c3中对路径L₁操作，即依次打断路径L_i的各个路段，再用Dijkstra搜索算法搜索，得到从打断路段的起点处 到终点D的近程综合效用U₁最小的路径L_n+1-L_m，将路径L_n+1-L_m加入近程 路径集以增加可选路径的个数。

c6.上述所有路径L₁-L_n和路径L_n+1-L_m合起来即为该近程起终点对 （O,D）之间的可选的近程路径集；可设定近程路径集中路径的个数， 当近程路径集中路径的个数达到设定的个数时即停止搜索，以减少不 必要的计算，提高效率。以北京市为例，可设定为50条。

c7.计算近程路径集中每条路径的近程综合效用U₁的值，并从小到 大排序，提供前几条路径供司机等用户选择即可。一般提供近程综合 效用U₁的值最小的前5条路径即可。

步骤d、以转弯数量和旅行时间的加权和作为起点到骨干路网进节 点间的综合效用U₂，并用该综合效用U₂最小代替Dijkstra搜索算法中 的距离最短进行计算，从而得到进节点路径集和相应的骨干路网进节 点集；以转弯数量和旅行距离的加权和作为骨干路网出节点到终点间 的综合效用U₃，并用该综合效用U₃最小代替Dijkstra搜索算法中的距 离最短进行计算，从而得到出节点路径集和相应的骨干路网出节点集； 将进节点和出节点组合配对后用Dijkstra搜索算法搜索骨干路网上每 组进节点和出节点之间的最快路径，得到骨干路径集；进节点路径、 骨干路径和出节点路径组合得到远程路径集。具体如下：

d1.起点O到骨干路网进节点间的综合效用U₂通过如下公式得到， U₂=β₃×转弯数+β₄×旅行时间，其中β₃为远程路径选择的转弯系数， β₄为远程路径选择的旅行时间系数；上述系数针对北京市的取值为： β₃＝-0.3，β₄＝-0.5；

d2.骨干路网出节点到终点D间的综合效用U₃通过如下公式得到， U₃=β₃×转弯数+β₅×旅行距离，其中β₃为远程路径选择的转弯系数， β₅为远程路径选择的旅行距离系数，上述系数针对北京市的取值为： β₃=-0.3，β₅=-0.001；

d3.用该综合效用U₂最小代替Dijkstra搜索算法中的距离最短进 行计算，得到起点O到骨干路网进节点间的综合效用U₂最小的路径构 成进节点路径集，进节点路径集中的路径相应的进节点构成骨干路网 进节点集E_O1-E_Op。可以设置进节点数量p，当达到进节点数量p时，停 止搜索，以便减少计算，提高效率。针对北京市取值p=5，所以在本实 施例中当得到的进节点数达到5个时，终止搜索，此时找到的进节点 E_O1-E_O5构成骨干路网进节点集。

d4.用该综合效用U₃最小代替Dijkstra搜索算法中的距离最短进 行计算，得到骨干路网出节点到终点D间的综合效用U₃最小的路径构 成出节点路径集，出节点路径集中的路径相应的出节点构成骨干路网 出节点集E_D1-E_Dq。可以设置进节点数量q，当达到进节点数量q时，停 止搜索，以便减少计算，提高效率。针对北京市取值q=5，所以在本实 施例中当得到的出节点数达到5个时，终止搜索，此时找到的出节点 E_D1-E_D5构成骨干路网出节点集。

d5.将进节点和出节点进行组合配对：（E_O1-E_D1），（E_O1-E_D2）… （E_O5-E_D5），共25组，用旅行时间最短代替Dijkstra搜索算法中的距 离最短进行计算，得到骨干路网上对每组进节点和出节点间最快路径 L_i1-L_i25，得到骨干路径集。

d6.对上述骨干路径集中的每个路径中的每一个路段依次打断，并 分别用Dijkstra搜索算法搜索骨干路网上打断路段的起点到对应的出 节点之间的旅行时间最短的路径L_ii1-L_iin，并将新搜索得到的路径与进 节点至打断路段起点间的路径组成的路径加入骨干路径集，以增加骨 干路径集中的路径个数。

d7.上述进节点路径、骨干路径和出节点路径组合得到起终点对 （O,D）之间的远程路径集。

d8.如果远程路径集中的路径数量还不够，可对L_ii1-L_iin中骨干路网 进出节点间旅行时间最短的路径L_s继续步骤d5中的操作，即依次打断 L_s在骨干路网上的各个路段，并分别用Dijkstra搜索算法搜索骨干路 网上打断路段的起点到对应的出节点之间的最快路径L_s1-L_sm，并将新搜 索得到的路径与进节点至打断路段起点间的路径组成的路径加入骨干 路径集。

d9.可设定生成远程起终点对（O,D）之间的远程路径集中的路径 个数，达到设定个数时，停止搜索，以减少计算量，提高效率。北京 市远程路径集中包含路径达到200条停止搜索。

d10.通过下式获得远程路径集中的路径的全路径综合效用 U₄,U₄=β₃×转弯数+β₄×旅行时间+β₆×骨干网里程比例，分别计算远 程路径集中每条路径的综合效用U₄的值，并将路径按U₄的值从小到大 排序，提供前几条供用户选择。β₆为远程路径选择的骨干网里程比例 系数，对北京取值：β₆=1.0。一般设定供选择的路径数为10条即可。

本发明中的Dijkstra搜索算法是指典型的Dijkstra单源最短路 径算法。但在本发明中用两点间的综合效用值最小代替两点间的距离 最短进行计算。用综合效用最小代替单纯的距离最短进行搜索，以使 提供的路径贴合实际路况。

按按本发明方法完成的北京市基于骨干网分层的城市综合效用最 优动态多路径选择系统界面如图4所示。系统可以任意从图上选择出 行的起终点，选择出发时间，以历史数据平均的对应时间段的各条道 路的旅行时间作为旅行时间值，根据基于骨干网分层的城市综合效用 最优动态多路径选择方法算法，依次显示系统计算的各条路径结果。

为了验证上述方法的可行性及实际运行效果，下面利用从典型起 终点（从北京市华威桥东-六里桥长途客运站），分别对比了高德导航 路径结果、谷歌自驾导航路径结果和本发明的选择方法的结果，选择 的路径图如图5A至图5d所示：

（1）图5A是高德公司导航软件搜索得到的最佳路径，显示为直 接上三环，绕南三环到六里桥出三环到达目的地，高德导航软件不分 出发时间统一计算；

（2）图5B1和图5B2是谷歌地图自驾车路径规划的两种方案，谷 歌地图自驾车路径规划按照不同的出发时间，综合考虑道路拥堵情况 进行路径规划计算，在早高峰8:30出发的情况下，路径规划显示2种 推荐选择：参见图5B1，一种还是直接上三环，绕南三环到六里桥出三 环到达目的地；参见图5B2，另一种是上南二环，往西走莲花池西路快 速路到西三环，再沿西三环往南绕回六里桥出三环到达目的地，其原 因是早高峰期间，从丽泽桥经六里桥往北的西三环南向北方向路段拥 堵十分严重，因此路径规划会有意绕开此方向路段；

（3）图5C和图5D是本发明方法对不同的出发时间计算得到的路 径选择结果。图5C1和图5C2是凌晨3点完全畅通情况下的路径选择 计算结果中排名最前的两种路径规划，参见图5C1，方案一还是直接上 三环，绕南三环到六里桥出三环到达目的地；参见图5C2，方案二是南 三环接丽泽路到西三环到目的地，基本都是快速路系统最短路径；图 5D1和图5D2是早高峰8:30出发的情况下的路径选择计算结果中排名 最前的两种路径规划，参见图5D1，方案一绕南三环，到最堵的丽泽桥 开始的南向北西三环路段（图中箭头方向所指），选择了从丽泽桥往西 走万丰路绕过最堵段到达目的地；参见图5D2，其次方案二才是直接沿 三环到达目的地。

根据北京的实际驾驶，早高峰时最好的路径就是走南三环然后从 丽泽桥往西绕行到六里桥，而完全畅通的情况下最好的路径是直接沿 三环到达目的地，从实际搜索情况来看，北京市基于骨干网分层的城 市综合效用最优动态多路径选择系统能得到最好的路径计算结果。该 算法计算结果比较理想。

以上实施例仅为本发明的示例性实施例，不用于限制本发明，本 发明的保护范围由权利要求书限定。本领域技术人员可以在本发明的 实质和保护范围内，对本发明做出各种修改或等同替换，这种修改或 等同替换也应视为落在本发明的保护范围内。