专利名称：基于路况预测的智能导航方法及系统的制作方法
基于路况预测的智能导航方法及系统
技术领域：
本发明涉及导航系统，特别涉及一种基于路况预测的智能导航方法及系统。
背景技术：
在导航路网中规划最佳的驾车路线是地图的一个基本功能。常用的驾车导航策略有最短时间、最短路线等，这些算法一般是在静态路网中进行路线搜索。实际的最优驾车路线往往和路况的关系很大，传统的优化方法是结合实时路况选择最优路线，其工作方法为:根据用户的起始地和目的地获取备选路线；获取相关路段的固有属性的权值；根据实时监控信息对搜索到的路线进行加权评分，根据加权评分选择行车路线。然而，因需获取实时路况，无法根据确定的出行时间提早进行路线规划，缺乏灵活性，由于实时路况只能获得当前的路况，而在行车过程中路况会发生变化，则预先计算的路线不够准确。

发明内容基于此，有必要提供一种能灵活安排出行的导航路线且提高导航路线准确性的基于路况预测的智能导航方法。一种基于路况预测的智能导航方法，包括以下步骤:获取用户输入的起点、终点及出行时间；获取起点到终点之间的各邻接节点之间路段在出行时间的预测拥堵权值，以及从基础路网信息中获取起点到终点之间的各邻接节点之间路段的导航代价及行驶时间；根据所述预测拥堵权值、导航代价及节点到终点的估值代价计算该节点的总导航估值代价，并根据出行时间及行驶时间计算到达该节点的时间，依次计算得到各节点的总导航估值代价及达到各节点的时间；根据各节点的总导航估值代价、到达各节点的时间及各邻接节点之间的路段确定从起点到终点的最佳导航路线。 优选地，还包括步骤:根据路况统计生成各邻接节点之间路段在预定时间点的预测拥堵权值；从所述预定时间点的预测拥堵权值中获取所述起点到终点之间的各邻接节点之间路段在出行时间的预测拥堵权值；所述根据路况统计生成各邻接节点之间路段在预定时间点的预测拥堵权值的具体步骤包括:预先对路况拥堵进行分级，并根据分级设定相应的拥堵权值；统计各邻接节点之间路段的历史路况信息，并得到各邻接节点之间路段在预定时间点相应的历史拥堵权值；对所述各邻接节点之间路段的历史拥堵权值分配权重，并通过加权平均求得各邻接节点之间路段在预定时间点的预测拥堵权值。优选地，还包括步骤:定时更新所述各邻接节点之间路段在预定时间点的预测拥堵权值。优选地，所述根据所述预测拥堵权值、导航代价及节点到终点的估值代价计算该节点的总导航估值代价，并根据出行时间及行驶时间计算到达该节点的时间的步骤具体为:获取到达前驱节点的实际代价、到达前驱节点的时间以及前驱节点与当前节点之间路段在到达前驱节点的时间的预测拥堵权值；从基础路网信息中获取前驱节点与当前节点之间路段的导航代价及行驶时间；将前驱节点与当前节点之间路段的导航代价与预测拥堵权值求积，再将该积与前驱节点的实际代价求和得到当前节点的实际代价；计算当前节点的估值代价，并将当前节点的估值代价及实际代价求和得到当前节点的总导航估值代价；将前驱节点与当前节点之间路段的预测拥堵权值与行驶时间求积，再将该积与到达前驱节点的时间求和，得到到达当前节点的时间。优选地，在获取到达前驱节点的实际代价、到达前驱节点的时间以及前驱节点与当前节点之间路段在到达前驱节点的时间的预测拥堵权值的步骤之前，还包括:创建用于存储当前待考察的节点的第一表和用于存储已考察过的节点的第二表，并初始化第一表及第二表；判断所述第一表是否为空，若是，则结束，若否，则从所述第一表中取出总导航估值代价最小的节点，将所述节点作为前驱节点；判断该前驱节点是否为终点，若是，则根据各节点的总导航估值代价、到达节点的时间及各邻接节点之间路段确定从起点到终点的最佳导航路线，并结束，若否，则取出该前驱节点的下一个邻接节点作为当前节点；在得到当前节点的总导航估值代价和达到当前节点的时间后，还包括步骤:判断所述前驱节点是否还存在邻接节点，若是，则返回到取出该前驱节点的下一个邻接节点作为当前节点的步骤，若否，则将所述前驱节点加入所述第二表中。优选地，在判断所述前驱节点是否还存在邻接节点时，还包括步骤:当所述当前节点在所述第一表中，比较计算得到的所述当前节点的总导航估值代价是否小于所述第一表中的所述当前节点的总导航估值代价，若是，则将计算得到的所述当前节点的总导航估值代价和到达当前节点的时间更新到所述第一表中；当所述当前节点在所述第二表中，比较计算得到的所述当前节点的总导航估值代价是否小于所述第二表中的所述当前节点的总导航估值代价，若是，则将计算得到的所述当前节点的总导航估值代价和到达当前节点的时间更新到所述第二表中；当所述当前节点 不在所述第一表和第二表中，将当前节点插入所述第一表中。此外，还有必要提供一种能灵活安排出行的导航路线且提高导航路线准确性的基于路况预测的智能导航系统。一种基于路况预测的智能导航系统，包括:输入模块，用于获取用户输入的起点、终点及出行时间；
查询模块，用于获取起点到终点之间的各邻接节点之间路段在出行时间的预测拥堵权值，以及从基础路网信息中获取起点到终点之间的各邻接节点之间路段的导航代价及行驶时间；处理模块，用于根据所述预测拥堵权值、导航代价及节点到终点的估值代价计算该节点的总导航估值代价，并根据出行时间及行驶时间计算到达该节点的时间，依次计算得到各节点的总导航估值代价及达到各节点的时间；导航模块，用于根据各节点的总导航估值代价、到达各节点的时间及各邻接节点之间路段确定从起点到终点的最佳导航路线。优选地，还包括生成模块，用于根据路况统计生成各邻接节点之间路段的在预定时间点的预测拥堵权值；所述查询模块还用于从所述预定时间点的预测拥堵权值中获取所述起点到终点之间的各邻接节点之间路段在出行时间的预测拥堵权值；所述生成模块包括:分级单元，用于预先对路况拥堵进行分级，并根据分级设定相应的拥堵权值；统计单元，用于统计各邻接节点之间路段的历史路况信息，并得到各邻接节点之间路段在预定时间点相应的历史拥堵权值；权值预测单元，用于对所述各邻接节点之间路段的历史拥堵权值分配权重，并通过加权平均求得各邻接节点之间路段在预定时间点的预测拥堵权值。优选地，还包括更新模块，用于定时更新所述各邻接节点之间路段在预定时间点的预测拥堵权值。优选地，所述处理模块包括:获取单元，用于获取到达前驱节点的实际代价、到达前驱节点的时间以及前驱节点与当前节点之间路段在到达前驱节点的时间的预测拥堵权值；提取单元，用于从基础路网信息中获取前驱节点与当前节点之间路段的导航代价及行驶时间；第一计算单元，用于将前驱节点与当前节点之间路段的导航代价与预测拥堵权值求积，再将该积与前驱节点的实际代价求和得到当前节点的实际代价；第二计算单元，用于计算当前节点的估值代价，并将当前节点的估值代价及实际代价求和得到当前节点的总导航估值代价；时间计算单元，用于将前驱节点与当前节点之间路段的预测拥堵权值与行驶时间求积，再将该积与到达前驱节点的时间求和，得到到达当前节点的时间。优选地，所述处理模块还包括创建单元、判断单元和更新单元；所述创建单元用于创建用于存储当前待考察的节点的第一表和用于存储已考察过的节点的第二表，并初始化第一表及第二表；所述判断单元用于判断所述第一表是否为空；所述获取单元还用于在所述判断单元判断出所述第一表不为空时，从所述第一表中取出总导航估值代价最小的节点，并将所述节点作为前驱节点；所述判断单元还用于判断该前驱节点是否为终点，若是，则所述导航模块根据各节点的总导航估值代价、 到达节点的时间及各邻接节点之间路段确定从起点到终点的最佳导航路线，若否，则所述获取单元取出该前驱节点的下一个邻接节点作为当前节点；在得到当前节点的总导航估值代价和达到当前节点的时间后，所述判断单元还用于判断所述前驱节点是否还存在邻接节点，若是，则所述获取单元重新取出该前驱节点的下一个邻接节点作为当前节点，若否，则所述更新单元将所述前驱节点加入所述第二表中。优选地，当所述判断单元判断出所述当前节点在所述第一表中，且比较计算得到的所述当前节点的总导航估值代价小于所述第一表中的所述当前节点的总导航估值代价时，所述更新单元还用于将计算得到的所述当前节点的总导航估值代价和到达当前节点的时间更新到所述第一表中；当所述判断单元判断出所述当前节点在所述第二表中，且比较计算得到的所述当前节点的总导航估值代价小于所述第二表中的所述当前节点的总导航估值代价，所述更新单元还用于将计算得到的所述当前节点的总导航估值代价和到达当前节点的时间更新到所述第二表中；当所述判断单元判断出所述当前节点不在所述第一表和第二表中，所述更新单元还用于将当前节点插入 所述第一表中。上述基于路况预测的智能导航方法及系统，采用读取根据路况统计生成的各邻接节点之间路段的预测拥堵权值，以及基础路网信息中的各邻接节点之间路段的导航代价及行驶时间，分别计算得出各节点的总导航估值代价及达到各节点的时间，从而确定得到从起点到终点的最佳导航路线，如此可根据确定的出行时间提早进行路线规划，不需到临出行前才能获取实时路况进行路线规划，提高了灵活性，因预测的路况变化不会很大，提高了导航路线的准确性。

图1为一个实施例中基于路况预测的智能导航方法的流程图；图2为操作界面示意图；图3为一个实施例中根据路况统计生成各邻接节点之间路段的预测拥堵权值的具体流程图；图4为根据该预测拥堵权值、导航代价及节点到终点的估值代价计算该节点的总导航估值代价，并根据出行时间及行驶时间计算到达该节点的时间的步骤的具体流程图；图5为根据该预测拥堵权值、导航代价及节点到终点的估值代价计算该节点的总导航估值代价，并根据出行时间及行驶时间计算到达该节点的时间的步骤的另一个具体流程图；图6为一个实施例中基于路况预测的智能导航系统的内部结构示意图；图7为另一个实施例中基于路况预测的智能导航系统的内部结构不意图；图8为图7中生成模块的内部结构示意图；图9为图7中处理模块的内部结构示意图。
具体实施方式下面结合具体的实施例及附图对基于路况预测的智能导航方法及系统的技术方案进行详细的描述。
如图1所示，在一个实施例中，一种基于路况预测的智能导航方法，包括以下步骤:步骤S110，获取用户输入的起点、终点及出行时间。用户在操作界面上输入起点、终点及出行的时间，如图2所示，起点为北京市-通惠河北路，终点为北京市-东单，出行时间为星期三的17:00，也可选择不考虑避开拥堵、按当前路况避开拥堵和按路况预测避开拥堵等。步骤S120，获取起点到终点之间的各邻接节点之间路段在出行时间的预测拥堵权值，以及从基础路网信息中获取起点到终点之间的各邻接节点之间路段的导航代价及行驶时间。基础路网信息包括路段和节点，每个路段都有长度、道路等级、路线坐标点串、通行状况等属性，同时也表示了节点之间的连接关系，且路段与节点组成一个有向图。同时，基础路网信息中包括邻接节点之间路段的导航代价及行驶时间。在一个实施例中，在步骤S120之前还包括:根据路况统计生成各邻接节点之间路段在预定时间点的预测拥堵权值；从预定时间点的预测拥堵权值中获取所述起点到终点之间的各邻接节点之间路段在出行时间的预测拥堵权值。具体的，预先根据路况统计生成各邻接节点之间路段在预定时间点的预测拥堵权值，其中，预定 时间点是指统计的一组时间，如O点、O点30分，以30分为间隔的一组时间，预定时间点也可为任意时间间隔的一组时间。生成了在预定时间点的预测拥堵权值，可从中查询得到出行时间的预测拥堵权值，也可查询得到任意时间的预测拥堵权值。

在一个实施例中，如图3所示，根据路况统计生成各邻接节点之间路段在预定时间点的预测拥堵权值的具体步骤包括:步骤S310，预先对路况拥堵进行分级，并根据分级设定相应的拥堵权值。可根据获取的所有路段上行驶车辆的平均速度来判断拥堵状况。以统计结果中通行状况最好的时间段的平均速度作为参考车速，以监控的当前平均车速除以参考车速作为通畅度指标，对该通畅度进行分级，即是对路况拥堵进行分级，然后根据分级对监控路况进行赋予拥堵权值。如表I中所示，不同通畅度对应不同的拥堵权值，描述不同的路况，此表仅为一种描述路况拥堵状况设定的拥堵权值，可根据需要自行设定。表I
权利要求
1.一种基于路况预测的智能导航方法，包括以下步骤: 获取用户输入的起点、终点及出行时间； 获取起点到终点之间的各邻接节点之间路段在出行时间的预测拥堵权值，以及从基础路网信息中获取起点到终点之间的各邻接节点之间路段的导航代价及行驶时间； 根据所述预测拥堵权值、导航代价及节点到终点的估值代价计算该节点的总导航估值代价，并根据出行时间及行驶时间计算到达该节点的时间，依次计算得到各节点的总导航估值代价及达到各节点的时间； 根据各节点的总导航估值代价、到达各节点的时间及各邻接节点之间的路段确定从起点到终点的最佳导航路线。
2.根据权利要求1所述的基于路况预测的智能导航方法，其特征在于，还包括步骤: 根据路况统计生成各邻接节点之间路段在预定时间点的预测拥堵权值； 从所述预定时间点的预测拥堵权值中获取所述起点到终点之间的各邻接节点之间路段在出行时间的预测拥堵权值； 所述根据路况统计生成各邻接节点之间路段在预定时间点的预测拥堵权值的具体步骤包括: 预先对路况拥堵进行分级，并根据分级设定相应的拥堵权值； 统计各邻接节点之间路段 的历史路况信息，并得到各邻接节点之间路段在预定时间点相应的历史拥堵权值； 对所述各邻接节点之间路段的历史拥堵权值分配权重，并通过加权平均求得各邻接节点之间路段在预定时间点的预测拥堵权值。
3.根据权利要求2所述的基于路况预测的智能导航方法，其特征在于，还包括步骤:定时更新所述各邻接节点之间路段在预定时间点的预测拥堵权值。
4.根据权利要求1至3中任一项所述的基于路况预测的智能导航方法，其特征在于，所述根据所述预测拥堵权值、导航代价及节点到终点的估值代价计算该节点的总导航估值代价，并根据出行时间及行驶时间计算到达该节点的时间的步骤具体包括: 获取到达前驱节点的实际代价、到达前驱节点的时间以及前驱节点与当前节点之间路段在到达前驱节点的时间的预测拥堵权值； 从基础路网信息中获取前驱节点与当前节点之间路段的导航代价及行驶时间； 将前驱节点与当前节点之间路段的导航代价与预测拥堵权值求积，再将该积与前驱节点的实际代价求和得到当前节点的实际代价； 计算当前节点的估值代价，并将当前节点的估值代价及实际代价求和得到当前节点的总导航估值代价； 将前驱节点与当前节点之间路段的预测拥堵权值与行驶时间求积，再将该积与到达前驱节点的时间求和，得到到达当前节点的时间。
5.根据权利要求4所述的基于路况预测的智能导航方法，其特征在于，在获取到达前驱节点的实际代价、到达前驱节点的时间以及前驱节点与当前节点之间路段在到达前驱节点的时间的预测拥堵权值的步骤之前，还包括: 创建用于存储当前待考察的节点的第一表和用于存储已考察过的节点的第二表，并初始化第一表及第二表；判断所述第一表是否为空，若是，则结束，若否，则从所述第一表中取出总导航估值代价最小的节点，将所述节点作为前驱节点； 判断该前驱节点是否为终点，若是，则根据各节点的总导航估值代价、到达节点的时间及各邻接节点之间路段确定从起点到终点的最佳导航路线，并结束，若否，则取出该前驱节点的下一个邻接节点作为当前节点； 在得到当前节点的总导航估值代价和达到当前节点的时间后，还包括步骤: 判断所述前驱节点是否还存在邻接节点，若是，则返回到取出该前驱节点的下一个邻接节点作为当前节点的步骤，若否，则将所述前驱节点加入所述第二表中。
6.根据权利要求5所述的基于路况预测 的智能导航方法，其特征在于，在判断所述前驱节点是否还存在邻接节点时，还包括步骤: 当所述当前节点在所述第一表中，比较计算得到的所述当前节点的总导航估值代价是否小于所述第一表中的所述当前节点的总导航估值代价，若是，则将计算得到的所述当前节点的总导航估值代价和到达当前节点的时间更新到所述第一表中； 当所述当前节点在所述第二表中，比较计算得到的所述当前节点的总导航估值代价是否小于所述第二表中的所述当前节点的总导航估值代价，若是，则将计算得到的所述当前节点的总导航估值代价和到达当前节点的时间更新到所述第二表中； 当所述当前节点不在所述第一表和第二表中，将当前节点插入所述第一表中。
7.一种基于路况预测的智能导航系统，包括: 输入模块，用于获取用户输入的起点、终点及出行时间； 查询模块，用于获取起点到终点之间的各邻接节点之间路段在出行时间的预测拥堵权值，以及从基础路网信息中获取起点到终点之间的各邻接节点之间路段的导航代价及行驶时间； 处理模块，用于根据所述预测拥堵权值、导航代价及节点到终点的估值代价计算该节点的总导航估值代价，并根据出行时间及行驶时间计算到达该节点的时间，依次计算得到各节点的总导航估值代价及达到各节点的时间； 导航模块，用于根据各节点的总导航估值代价、到达各节点的时间及各邻接节点之间路段确定从起点到终点的最佳导航路线。
8.根据权利要求7所述的基于路况预测的智能导航系统，其特征在于，还包括生成模块，用于根据路况统计生成各邻接节点之间路段在预定时间点的预测拥堵权值； 所述查询模块还用于从所述预定时间点的预测拥堵权值中获取所述起点到终点之间的各邻接节点之间路段在出行时间的预测拥堵权值； 所述生成模块包括: 分级单元，用于预先对路况拥堵进行分级，并根据分级设定相应的拥堵权值； 统计单元，用于统计各邻接节点之间路段的历史路况信息，并得到各邻接节点之间路段在预定时间点相应的历史拥堵权值； 权值预测单元，用于对所述各邻接节点之间路段的历史拥堵权值分配权重，并通过加权平均求得各邻接节点之间路段在预定时间点的预测拥堵权值。
9.根据权利要求8所述的基于路况预测的智能导航系统，其特征在于，还包括更新模块，用于定时更新所述各邻接节点之间路段在预定时间点的预测拥堵权值。
10.根据权利要求7至9中任一项所述的基于路况预测的智能导航系统，其特征在于，所述处理模块包括: 获取单元，用于获取到达前驱节点的实际代价、到达前驱节点的时间以及前驱节点与当前节点之间路段在到达前驱节点的时间的预测拥堵权值； 提取单元，用于从基础路网信息中获取前驱节点与当前节点之间路段的导航代价及行驶时间； 第一计算单元，用于将前驱节点与当前节点之间路段的导航代价与预测拥堵权值求积，再将该积与前驱节点的实际代价求和得到当前节点的实际代价； 第二计算单元，用于计算当前节点的估值代价，并将当前节点的估值代价及实际代价求和得到当前节点的总导航估值代价； 时间计算单元，用于将前驱节点与当前节点之间路段的预测拥堵权值与行驶时间求积，再将该积与到达前驱节点的时间求和，得到到达当前节点的时间。
11.根据权利要求10所述的基于路况预测的智能导航系统，其特征在于，所述处理模块还包括创建单元、判断单元和更新单元； 所述创建单元用于创建用于存储当前待考察的节点的第一表和用于存储已考察过的节点的第二表，并初始化第一表及第二表； 所述判断单元用于判断所述第一表是否为空； 所述获取单元还用于在所述判断单元判断出所述第一表不为空时，从所述第一表中取出总导航估值代价最小的节点，并将所述节点作为前驱节点； 所述判断单元还用于判断该前驱节点是否为终点，若是，则所述导航模块根据各节点的总导航估值代价、到达节点的时间及各邻接节点之间路段确定从起点到终点的最佳导航路线，若否，则所述获取单元取出该前驱节点的下一个邻接节点作为当前节点； 在得到当前节点的总导航估值代价和达到当前节点的时间后，所述判断单元还用于判断所述前驱节点是否还存在邻接节点，若是，则所述获取单元重新取出该前驱节点的下一个邻接节点作为当前节点，若否，则所述更新单元将所述前驱节点加入所述第二表中。
12.根据权利要求11所述的基于路况预测的智能导航系统，其特征在于， 当所述判断单元判断出所述当前节点在所述第一表中，且比较计算得到的所述当前节点的总导航估值代价小于所述第一表中的所述当前节点的总导航估值代价时，所述更新单元还用于将计算得到的所述当前节点的总导航估值代价和到达当前节点的时间更新到所述第一表中； 当所述判断单元判断出所述当前节点在所述第二表中，且比较计算得到的所述当前节点的总导航估值代价小于所述第二表中的所述当前节点的总导航估值代价，所述更新单元还用于将计算得到的所述当前节点的总导航估值代价和到达当前节点的时间更新到所述第二表中； 当所述判断单元判断出所述当前节点不在所述第一表和第二表中，所述更新单元还用于将当前节点插入所述第一表中。
全文摘要
本发明涉及一种基于路况预测的智能导航方法及系统。该方法包括以下步骤获取用户输入的起点、终点及出行时间；获取起点到终点之间的各邻接节点之间路段在出行时间的预测拥堵权值，以及从基础路网信息中获取起点到终点之间的各邻接节点之间路段的导航代价及行驶时间；根据所述预测拥堵权值、导航代价及节点到终点的估值代价计算该节点的总导航估值代价，并根据出行时间及行驶时间计算到达该节点的时间，依次计算得到各节点的总导航估值代价及达到各节点的时间；根据各节点的总导航估值代价、到达各节点的时间及各邻接节点之间的路段确定得到从起点到终点的最佳导航路线。能提高了灵活性及导航路线的准确性。
文档编号G01C21/34GK103245347SQ20121003155
公开日2013年8月14日 申请日期2012年2月13日 优先权日2012年2月13日
发明者彭蔚, 林夏祥, 熊科浪, 江红英 申请人:腾讯科技(深圳)有限公司