一种基于任意两节点间行程时间的车辆智能导航方法

摘要

本发明涉及一种基于任意两节点间行程时间的车辆智能导航方法，包括如下步骤：(1)时间拓扑网络重新构建请求；(2)构建时间拓扑网络；(3)构建时间拓扑与道路拓扑网络的映射；(4)在时间拓扑网络上计算时间最优的路径；(5)时间拓扑网络的规划路径向道路拓扑网络的还原。本发明是一种基于时间拓扑网络的智能导航方法。这个拓扑网络节点数可控，利用通行时间作为权值，使用规划算法计算出时间最优路径，即规避拥堵的路径。

权利要求

1.一种基于任意两节点间行程时间的车辆智能导航方法，其特征在于：包括如下步骤：

(1)时间拓扑网络重新构建请求：基于将一天划分为几个时间节点，时间节点的划分是基于时间拓扑网络变化规律，时间拓扑网络的规律是通过对路网信息的分布及交通历史数据的数据挖掘而统计出的，每个时间节点对应一个时间拓扑网络；

(2)构建时间拓扑网络；

(3)构建时间拓扑与道路拓扑网络的映射；

(4)在时间拓扑网络上计算时间最优的路径；

(5)时间拓扑网络的规划路径向道路拓扑网络的还原；

其中，所述(2)构建时间拓扑网络包括如下步骤：

1)依据供应商提供的路网信息和交通历史数据，分析出城市路网中的关键节点，关键节点是其在道路拓扑网络上，并通过设备采集数据结合算法可以统计出任意关键节点间是否可通行和通行的时间，关键节点分析过程中需要控制单位地理范围内的总数量和均衡性；

2)将城市范围内的关键节点集合起来，并依据设备采集数据结合算法统计出任意关键节点间的通行时间；

3)结合1)和2)的数据，构建出基于通行时间的拓扑网络数据；

其中，所述(3)构建时间拓扑与道路拓扑网络的映射包括如下步骤：

1)建立时间拓扑网络上的节点在道路拓扑网络上的映射关系；

2)对可通行的节点间利用规划算法建立时间拓扑网络上节点间在道路拓扑网络的还原路径，并记录；

3)若某两个节点间的还原路径超过一条，那么不记录路径。

2.根据权利要求1所述的车辆智能导航方法，其特征在于：所述(4)在时间拓扑网络上计算时间最优的路径，利用规划路径算法在时间拓扑网络上进行路径规划，包括如下特征：

1)若时间拓扑网络的总节点数小于一定数量，那么使用Dijkstra算法；

2)若时间拓扑网络的总节点数大于一定数量，那么使用A*；

3)将基于时间拓扑网络的规划路径展开成节点列。

3.根据权利要求1所述的车辆智能导航方法，其特征在于：所述(5)时间拓扑网络的规划路径向道路拓扑网络的还原，利用规划路径算法在时间拓扑网络上进行路径规划，包括如下步骤：

1)时间拓扑网络的规划路径展开的节点列，按顺序两两展开；

2)展开某两个节点时，利用权利要求1中构建的时间拓扑与道路拓扑网络的映射，判断节点间的还原路径是否唯一，如果唯一那么将唯一的还原路径接续到已展开的基于道路拓扑网络的路径中；

3)依据2)判断后，如果节点间的路径不唯一，那么将这两个节点按规划路径列表中出现的顺序分别作为路径规划算法的起点和终点，利用规划算法在道路拓扑网络基础上考虑拥堵计算出唯一的路径，之后接续到之前展开的道路列中；

4)重复步骤3)直到展开到最后一个节点，形成基于道路拓扑网络的规划路径。

说明书

一种基于任意两节点间行程时间的车辆智能导航方法

技术领域

[0001] 本发明涉及导航路径规划技术研究领域，尤其涉及构建新的参考系，即基于任意两节点间行程时间的车辆智能导航方法。

背景技术

[0002] 随着社会和经济的发展，大中城市的汽车保有率越来越高，城市交通变得越来越拥堵。为了解决城市拥堵问题，政府推出了各项经济及行政领域的政策，这些政策或者通过限制新车的增加，或者通过增加汽车使用成本，或者通过行政命令直接实行限行，这些方式都或多或少的牺牲了汽车产业的发展和降低了人民生活水平。正因如此，诸多车厂、汽车电子厂商、互联网厂商、导航地图软件厂商从技术层面提出了很多监控城市实时交通、推荐用户规避拥堵、提高路网的使用效率的解决方案。

[0003] 拓扑算法作为数据结构中的基本算法，在很多领域中都有所应用，在导航领域中也不例外。在导航领域中拓扑算法的主要有以下两个基本特点：

[0004] 首先，由于导航基于的拓扑网络需要反应客观路网及其通行情况造成了拓扑网络节点数量庞大并且权值体系复杂；

[0005] 其次，由于算法需要部署到车机或者服务器上，算法的复杂度需要控制在可控范围内。

[0006] 拓扑算法在导航领域的这两个基本特点(复杂的拓扑网络和可控的拓扑算法)本身就是一对矛盾。

[0007] 基于前面的矛盾目前导航算法的基本解决方案如下：

[0008] 使用图商发布的道路拓扑网络作为参考系；

[0009] 使用A*或者双向A*算法进行路径规划，其中A*(A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法；

[0010] 道路拥堵信息在A*算法的权值评价体系中使用。

[0011] 分别说明各基本特点的缺点及限制，如下：

[0012] 1.使用图商发布的道路拓扑网络作为参考系的缺点：

[0013] 1)道路拓扑网络的节点数过多，造成了2的算法只能采用较为不准确的A*或者双向A*；

[0014] 2)随着城市交通的发展，每次地图升级后，之前的预装的导航算法也需要升级才能保证效率；

[0015] 3)因为道路拓扑网络的特征的复杂性，造成了2的权值体系过于复杂，导航算法只能部署到性能较强的设备上；

[0016] 4)因为道路拓扑网络的数据的数量级基本都是G级别或者10G级别的，所以造成在线升级的费用过高，时间过慢；

[0017] 5)因为4)，造成了真实道路的变更不能及时反映到道路拓扑网络中。

[0018] 2.使用A*或者双向A*算法进行路径规划的缺点：

[0019] 由于1的限制，算法不准确，权值体系过于复杂。

[0020] 3.道路拥堵信息在A*算法的权值评价体系中使用的缺点：

[0021] 1)可扩展性差：拥堵的判定固化在算法中，对道路拥堵信息的适配性较差，只能适配特定协议的拥堵信息；

[0022] 2)评价体系复杂。

发明内容

[0023] 为了解决上述问题，本发明的目的是提供了一种基于任意两节点间行程时间的车辆智能导航方法，构造一个基于时间的拓扑网络，这个拓扑网络节点数可控，利用通行时间作为权值，使用规划算法计算出时间最优路径。

[0024] 本发明技术解决方案：一种基于任意两节点间行程时间的车辆智能导航方法，其基本步骤如下：

[0025] 1.时间拓扑网络重新构建请求；

[0026] 2.构建时间拓扑网络；

[0027] 3.构建时间拓扑与道路拓扑网络的映射；

[0028] 4.在时间拓扑网络上计算时间最优的路径；

[0029] 5.时间拓扑网络的规划路径向道路拓扑网络的还原。

[0030] 关于基本步骤1：时间拓扑网络重新构建请求，其特征在于该方法的主要特征是基于将一天划分为几个时间节点，时间节点的划分是基于时间拓扑网络变化规律，时间拓扑网络的规律是通过对路网信息的分布及交通历史数据的数据挖掘而统计出的，每个时间节点对应一个时间拓扑网络。

[0031] 结合对基本步骤1的分析，关于基本步骤2：构建时间拓扑网络，其特征在于该方法包括如下详细步骤：

[0032] 1)依据供应商提供的路网信息和交通历史数据，分析出城市路网中的关键节点，关键节点的特征是其在道路拓扑网络上，并通过设备采集数据结合算法可以统计出任意关键节点间是否可通行和通行的时间，关键节点分析过程中需要控制单位地理范围内的总数量和均衡性；

[0033] 2)将城市范围内的关键节点集合起来，并依据设备采集数据结合算法统计出任意关键节点间的通行时间；

[0034] 3)结合1)和2)的数据，构建出基于通行时间的拓扑网络数据。

[0035] 结合对基本步骤1和2的分析，关于基本步骤3：构建时间拓扑与道路拓扑网络的映射，其特征在于该方法特征是：

[0036] 1)建立时间拓扑网络上的节点在道路拓扑网络上的映射关系；

[0037] 2)对可通行的节点间利用规划算法建立时间拓扑网络上节点间在道路拓扑网络的还原路径，并记录；

[0038] 3)若某两个节点间的还原路径超过一条，那么不记录路径。

[0039] 结合对基本步骤2的分析，关于基本步骤4：在时间拓扑网络上计算时间最优的路径，其本质是利用规划路径算法在时间拓扑网络上进行路径规划，其特征在于该方法包括如下特征：

[0040] 1)若时间拓扑网络的总节点数小于一定数量，那么使用Dijkstra算法；

[0041] 2)若时间拓扑网络的总节点数大于一定数量，那么使用A*；

[0042] 3)将基于时间拓扑网络的规划路径展开成节点列。

[0043] 结合对基本步骤2和3的分析，关于基本步骤5：时间拓扑网络的规划路径向道路拓扑网络的还原，其本质是利用规划路径算法在时间拓扑网络上进行路径规划，其特征在于该方法包括如下步骤：

[0044] 1)时间拓扑网络的规划路径展开的节点列，按顺序两两展开；

[0045] 2)展开某两个节点时，利用构建的时间拓扑与道路拓扑网络的映射，判断节点间的还原路径是否唯一，如果唯一那么将唯一的还原路径接续到已展开的基于道路拓扑网络的路径中；

[0046] 3)依据2)判断后，如果节点间的路径不唯一，那么将这两个节点按规划路径列表中出现的顺序分别作为路径规划算法的起点和终点，利用规划算法在道路拓扑网络基础上考虑拥堵计算出唯一的路径，之后接续到之前展开的道路列中；

[0047] 4)重复步骤3)直到展开到最后一个节点，形成基于道路拓扑网络的规划路径。

[0048] 本发明与现有技术相比的有益的效果和优点：

[0049] 1)本发明所采用的规划算法是基于时间拓扑网络的，构建时间拓扑网络的参考因素可以是多样融合的，排除了单一来源的缺点，排除了人为因素造成的影响。其数据来源广，可信度高，更新快，为规避拥堵提供了可靠的数据支持。

[0050] 2)本发明所使用的规划路径算法是可变的，可以根据网络复杂度调整使用的导航算法，可以采用经典的Dijkstra算法也可以采用A*，其关键在于改变了导航算法所依赖的道路拓扑网络而采用时间拓扑网络。这样的变化避免了传统基于道路拓扑网络的各种算法的弊端和局限性。

[0051] 本发明将交通拥堵的权值放到了构建时间拓扑网络过程中，而不是传统的放到路径规划算法的权值评价体系中，揭示了规避拥堵的路径规划算法的核心问题：时间最短，提供了一个全新的路径规划的参考系，并融合传统道路拓扑网络，提高了导航规划算法的效率及灵活性。本发明还提出了对于城市内的不同时间段内，路径规划算法采用的时间拓扑网络是可变的，更加准确的反应了城市交通的本质，提高了导航算法的准确性。本方法可以为驾驶员规划最快到达目的地的路径，在一定程度上缓解城市交通拥堵。

[0052] 本发明提出了一个新的导航规划算法的参考系：基于时间的拓扑网络，将交通拥堵的权值放到了构建时间拓扑网络过程中，而不是传统的放到路径规划算法的权值评价体系中，揭示了规避拥堵的路径规划算法要解决的核心矛盾：时间最短，提高了导航算法的效率；还融合了传统道路拓扑网络，增加导航规划算法的灵活性。本发明还提出了对于城市内的不同时间段，路径规划算法采用的时间拓扑网络是可变的，更加准确的反应了城市交通的本质，提高了导航算法的准确性。在此应用下，本发明为缓解交通拥堵提高城市道路使用率提供了一个新的解决方向。

[0053] 总而言之，本发明提出的时间拓扑网络坐标系能够真实反映道路流通情况，真实路网情况和拥堵信息在构造时间拓扑网络过程中得以考虑，将算法的复杂度从路径规划算法本身转移到构建时间拓扑网络过程中，提供了一种新的算法部署方案，使得路径规划算法可控；本发明提出的对于不同的时间段，时间拓扑网络是可变的，解决了道路拓扑网络中数据更新困难，进而解决了由于数据更新不及时造成的路径规划算法的不准确问题。

附图说明

[0054] 图1是本发明的基本特征步骤流程图；

[0055] 图2是本发明的规划算法详细步骤流程图；

[0056] 图3是基于城市摄像头的具体实施部署图。

具体实施方式

[0057] 以下将结合附图对本发明技术方案做进一步的阐述。

[0058] 下面结合一个典型的节点抽取方式对本发明的具体实施方式作进一步说明：

[0059] 这里我们以服务器采用城市交通主管部门发布的摄像头分布作为时间拓扑网络的典型节点，摄像头间的流动时间作为时间拓扑网络的权值，具体步骤如下：

[0060] 如图1所示，本发明主要包括以下五个步骤：时间拓扑网络重新构建请求，构建时间拓扑网络，构建时间拓扑与道路拓扑网络的映射，在时间拓扑网络上计算时间最优的路径，时间拓扑网络的规划路径向道路拓扑网络的还原，具体实施方案如下：

[0061] 1.时间拓扑网络重新构建请求(21)：

[0062] 云端服务器以整点作为时间节点，在每个时间节点上，云端服务器重新构造时间拓扑网络。

[0063] 2.构建时间拓扑网络(22)：

[0064] 城市的交通主管部门，将城市内的摄像头分布详细资料共享给云端服务器。云端服务器利用交通历史数据分析出当前时间节点上的基于道路拓扑网络的路口关键热点，路口关键热点和城市摄像头对应的并集，得到网络的关键节点。

[0065] 结合基于摄像头拍摄的车牌所计算出来的摄像头间的流动时间和基于道路拓扑网络的浮动车模型所测量出的关键热点间的流动时间这两种信息，进行融合得到时间拓扑网络的权值。

[0066] 最后以矩阵形式给出任意两个节点间的联通关系，矩阵是n*n矩阵，其中n是摄像头总数，第m*n节点对应的值代表从m到n的通行时间，-1代表不能通行。

[0067] 3.构建时间拓扑与道路拓扑网络的映射(23)：

[0068] 云端服务器在构造时间拓扑网络过程中，记录时间拓扑网路节点与道路拓扑网络节点间的对应关系，然后记录每两个可以联通的节点间的还原路径，构建以下模型：

[0069] 时间拓扑网络与道路拓扑网络间的映射关系，描述任意一个节点关联的道路，每一个节点唯一的对应一个道路，使用一个4*(n*n)矩阵代表这个对应关系，矩阵的具体含义如下：

[0070] 第一列代表某两个节点m*n；

[0071] 第二列代表节点m所对应的道路；

[0072] 第三列代表节点n所对应的道路；

[0073] 4)第四列是一个指针，若从节点m到节点n有唯一的基于道路拓扑网络的还原路径时，指向一个还原路径队列；若从节点m到节点n的还原路径不唯一时，指向null(无效)。

[0074] 4.在时间拓扑网络上计算时间最优的路径(24)：

[0075] 1)考虑时间拓扑网络节点的数量，当大于一定的数量时，采用A*算法；否则直接采用Dijkstra；

[0076] 迪科斯彻算法(英语：Dijkstra's algorithm)是由荷兰计算机科学家艾兹赫尔·戴克斯特拉于1959年提出的，因此又叫狄克斯特拉算法。迪杰斯特拉算法是典型最短路径算法，用于计算图或网中某个特定顶点到其他所有顶点的最短路径。主要特点是以起始点为中心向外，层层扩展，直到扩展覆盖所有顶点。

[0077] 2)计算的结果采用队列形式存储，按照开始点到目的地的顺序，队列中的成员是时间拓扑网络上的节点。

[0078] 5.时间拓扑网络的规划路径向道路拓扑网络的还原(25)：

[0079] 1)对基于时间拓扑网络的最优化路径，结合时间拓扑网络与道路拓扑网络间的映射关系矩阵4*(n*n)进行展开：例如展开到从x到y的路径，那么在矩阵中找到4*(x*y)的指针，若指针非空，将指针指向的还原路径直接接续到最优化路径上；

[0080] 2)若1)中的例子，4*(x*y)的指针为空，那么说明对于某两个摄像头间不是唯一的情况。那么分别查找2*(x*y)得到x节点对应的道路信息和3*(x*y)得到y节点对应的道路信息，以这两个道路信息作为开始和结束节点，在道路拓扑网络上考虑当前的交通拥堵信息采用Dijkstra进行推算，得到唯一的路径，然后还原到最优化路径上。

[0081] 本发明未详细阐述部分属于导航领域公知技术。

[0082] 如图2所示，本发明的详细规划算法如下：

[0083] 城市内建立基于时间拓扑的网络(41)，按照类似基于摄像头的时间模型构造出时间拓扑网络；

[0084] 建立时间拓扑网络与道路拓扑网络间的映射(42)，依据时间拓扑网络中关键节点的坐标与传统的道路拓扑网络建立关联；

[0085] 规划算法计算出时间最优的规划路径(43)，此部分工作是在云端服务器完成的，规划算法基于时间拓扑网络，当节点数大于一定阈值时，使用A*否则采用Dijkstra算法，计算出时间最优的规划路径；

[0086] 规划路径节点展开循环(44)，此循环从时间最优的规划路径的首作为开始，规划路径上的相邻节点按顺序展开，以规划路径的末作为结束，也就是如果时间最优的规划路径中含有N个节点，那么展开循环的次数是N-1；

[0087] 两节点间展开成道路列(45)，按照时间拓扑网络和传统的道路拓扑网络建立的关联，还原两节点间的道路拓扑网络，还原时存在对应道路列唯一和不唯一的情况；

[0088] 如果两节点间的道路列不唯一(46)，那么首先将两节点还原到道路拓扑网络上(47)，再以这2个节点作为起点和终点使用Dijkstra算法计算出区间内规划路径(48)，最后将区间内的道路列接续到已展开的路径中(49)；

[0089] 如果两节点间的道路列唯一(46)，那么2节点展开的道路列接续到已展开路径列中(50)。

[0090] 如图3所示，基于城市摄像头的具体实施部署如下：

[0091] 车(30)：带有上网功能的汽车，包含车牌(31)和可上网的车载终端(32)；

[0092] 摄像头(33)：城市交通主管部门在城市内部署的摄像头，采集车牌(31)，并将信息通过路测通信专用网络(35)传递给云端服务器(36)；

[0093] 云端服务器(36)：在系统中负责部署算法，包含基于摄像头的时间拓扑网络构造，本发明的规划路径算法等，通过车载网络(34)与车载终端(32)实现信息的交互；

[0094] 车载网络(34)：3G、4G等；

[0095] 路测通信专用网络(35)：光纤等。

[0096] 以上所述，仅为本发明部分具体实施方式，但本发明的保护范围不局限于此，任何导航本领域人员或者单位在本发明技术范围内可以轻易想到的变化或替换，都应涵盖在本发明保护范围内。