一种基于方向性诱导的城市路网最短路径获取方法

摘要

本发明公开一种基于方向性诱导的城市路网最短路径获取方法，包括：1.由实时路况信息构建城市网络；2.引入边界内部交叉口集合Un、边界外部交叉口集合行程时间上界及行程时间下界T；3.更新集合Un和集合4.通过标号修正法得到出发点交叉口到目的点交叉口的最短行程时间及路径；5.若出发点到目的点的行程时间等于T或者集合Un不再更新，则结束获得最短路径，否则更新T，转步骤3。本发明考虑在城市路网的导航中加入方向性的诱导并有效地缩小搜索范围，从而能提高导航效率并提供给驾驶员一种更人性化、高效的行驶路径。

说明书

技术领域

本发明属于现有城市路网的导航优化领域，具体的说是一种基于方向性诱导的城市路网最短路径获取方法。

背景技术

随着社会的发展，基于互联网的交通导航给用户带来了越来越大的便利，用户可以在导航开始阶段输入自己的出发地和目的地，就可以获取导航产品自动规划的路径。但随着城市汽车保有量逐步攀升，路网建设相对滞后，交通资源浪费，出行效率低的现象时有发生，不仅给城市居民出行带来不便，也大大降低城市运转效率，给经济发展造成一定的损失。因而,需要研究一种提高出行水平以及城市路网利用率的路径导航方法。随着GPS、网络技术、计算机技术的发展，车辆导航系统建立的条件已经成熟，能否在城市路网范围内实现车辆的道路导航，实现车辆快速、畅通地到达目的地，已经成为当前研究的目标。

现阶段的城市路网中，各个等级道路(快速路、主干道、次干道、支路)交宗错杂，道路等级因素严重影响导航行程各个方面，现阶段的导航产品在导航过程中往往无法有效利用这一因素进而提高导航过程的时效性，严重影响了驾驶员的出行体验以及城市路网的利用效率。此外；在具体导航过程中的路径搜索阶段，已有路径搜索方法往往是在根据实时路网信息在全局范围内进行路径搜索，这种路径搜索的方法没有考虑到导航的中驾驶员行驶的方向性，降低了导航过程的路径搜索的方向性以及区域性。

发明内容

本发明是为了解决上述现有技术存在的不足之处，提出一种基于方向性诱导的城市路网最短路径获取方法，以期能在城市路网导航中加入方向性诱导并缩小搜索范围，从而能提高导航效率并提供给驾驶员一种更人性化、更高效的最短路径，让行驶过程更高效。

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

本发明一种基于方向性诱导的城市路网最短路径获取方法的特点是按如下步骤进行：

步骤1：构建城市网络并获取任意交叉口平面坐标；

获取实时路网数据得到城市道路网络G＝(V,A)，其中，V表示交叉口集合，V＝{v

根据实时路网数据得到城市道路第i个交叉口v

步骤2：假设驾驶员的出发点为第s个交叉口v

步骤3：参数初始化；

定义n为当前迭代次数，则第n次迭代的第s个交叉口v

定义第s个交叉口v

定义第n次迭代的第s个交叉口v

初始化n＝1，

步骤4：更新第n次迭代边界内部交叉口集合U

遍历第s个交叉口v

步骤5：继续更新第n次迭代的边界内部交叉口集合U

如果v

步骤6：通过标号修正法得到出发点的交叉口v

步骤7：判断行程时间最优性并更新行程时间上界

如果T

步骤8：基于行程时间上界

对于第n次迭代的边界外部交叉口集合

步骤9：基于行程时间上界

依次判断扩充边界交叉口集合U

步骤10：判断U

步骤11：通过标号修正法得到出发点的交叉口v

将

步骤12：输出标号修正法所得到的最短路径，如果n＝1，则最终的最短行程时间为T

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

1、本发明可以有效结合现阶段城市路网的特征，在导航初始阶段，遍历城市路网中的交叉口和路段信息，将路段等级，路段长度，交叉口信息融入到导航路径搜索阶段，为用户提供了最短的路径规划方案，节约了用户的出行时间并且提高了城市路网的利用效率。

2、本发明克服了现有导航方法在路径搜索阶段没有考虑到路径搜索的方向性以及区域性，目前的常用的寻求最短路径的方法例如dijkstra，其搜索范围是全局的，对于一个城市路网来说，出发点到目的点的距离较大时搜索范围便变得非常大，同时可能会让驾驶员走许多回头路或者弯路。而本发明考虑了在城市路网导航中加入方向性诱导以及缩小搜索范围，从而能提高导航效率并提供给驾驶员一种更人性化、更高效的最短路径，让行驶过程更高效。

3、本发明通过引用当前交叉口到目的点交叉口与当前交叉口到其邻居交叉口的向量积不小于0来进行方向性诱导，可以理解前进方向的角度限制，本发明是限制前进方向在90度以内，这样可以极大地避免了驾驶员在行程中走回头路或者弯路，可以提供给驾驶员一种更人性化最短路径。

4、本发明所提出的城市路网最短路径获取方法，是在一定的范围里面进行的，并将该搜索范围定义为边界内部交叉口集合，同时定义边界外部交叉口集合，里面包含待定加入到边界内部交叉口集合的交叉口，通过满足向量积公式以及小于行程时间上界不断更新这两个集合，边界内部交叉口集合内的交叉口形成类似椭圆区域，椭圆区域逐步变大，不再变大时，算法终止，通过这样可以极大提高路径搜索的效率，让导航过程更高效、快捷。

附图说明

图1为本发明方法流程图；

图2为本发明初始化边界内外部交叉口集合示意图；

图3为本发明以出发交叉口开始边界内外部交叉口集合扩充图；

图4为本发明边界内外部交叉口集合逐步扩充示意图；

图5为本发明初步形成的类似椭圆的边界内部交叉口集合的最短行程路线示意图；

图6为本发明基于行程时间上界继续更新第n次迭代的边界内部交叉口集合和边界外部交叉口集合示意图；

图7为本发明最终形成的类似椭圆的边界内部交叉口集合的最短行程路线示意图；

图8为目前常用的最短路径算法的路径搜索范围示意图；

图9为本发明提出的E*算法的路径搜索范围示意图。

具体实施方式

如图1所示，一种基于方向性诱导的城市路网最短路径获取方法，始终在一个具有类似椭圆(Ellipse)边界的局部区域内进行，因此该最短路径获取方法可简称为E*算法，具体的说，是按如下步骤进行：

步骤1：构建城市网络并获取任意交叉口平面坐标；

获取实时路网数据得到城市道路网络G＝(V,A)，其中，V表示交叉口集合，V＝{v

根据实时路网数据得到城市道路第i个交叉口v

步骤2：假设驾驶员的出发点为第s个交叉口v

步骤3：参数初始化；

定义n为当前迭代次数，则第n次迭代的第s个交叉口v

定义第s个交叉口v

定义第n次迭代的第s个交叉口v

初始化n＝1，

步骤4：更新第n次迭代边界内部交叉口集合U

如图3所示，将符合向量条件的第s个交叉口v

步骤5：继续更新第n次迭代的边界内部交叉口集合U

如图4所示，第n次迭代的边界内部交叉口集合U

步骤6：如图5所示，初步得到类似椭圆的第n次迭代的边界内部交叉口集合U

步骤7：判断行程时间最优性并更新行程时间上界

如果T

步骤8：基于行程时间上界

如图6所示，对于第n次迭代的边界外部交叉口集合

步骤9：基于行程时间上界

依次判断扩充边界交叉口集合U

步骤10：判断U

步骤11：如图7所示，第n次迭代的边界内部交叉口集合U

将

步骤12：输出标号修正法所得到的最短路径，如果n＝1，则最终的最短行程时间为T

如图8所示，目前常用的寻求最短路径的算法例如dijkstra，其路径搜索是在全局范围内进行的，在一个具有类似圆形边界的区域内进行最短路径的搜索。

如图9所示，本发明所提出的E*算法，是在一定的范围里面进行的，始终在一个具有类似椭圆边界的局部区域内进行最短路径的搜索，对比于目前常用的寻求最短路径的算法，本发明所提出的E*算法在路径搜索过程中效率更高。