一种面向交通热点规避的路径规划方法

1.一种面向交通热点规避的路径规划方法，其特征在于：通过采集交通热点信息，利用动态规避算法，在地图上将用户所需要的行车路线展示，为用户提供一条以时间最优为主导的导航路线，具体实现如下：
步骤一：确定出发地、目的地及途经点信息；
步骤二：根据获得的行车目的地信息，从票务网站、微博、交通网站、实时上报的交通信息及数据库中存储的历史规律性信息多个数据源获取交通热点信息即可能造成交通拥堵的交通信息供采集，并根据交通热点信息的影响范围及程度用不同大小及颜色绘制到矢量地图上；
步骤三：通过步骤二中实时采集到的交通热点信息，结合道路最高时速限制、路宽、交叉口延时及干道是否含有非机动车车带，根据美国交通局路阻函数即路段行驶时间与路段交通负荷之间的关系函数，为行车过程中三条常规行驶时间最短路线赋权值，并加入邻接表存储结构中作为最初的交通路网；
步骤四：为步骤三获得的最初的路网实施以SPFA为基础的动态逼近式最短路优先算法，遍历每条路段，直到执行至受交通热点信息影响的路段；
步骤五：以受到交通热点信息影响的路段的前一路段的入口为起点，目的地为终点获得新的三条常规行驶时间最短路线赋权值后加入邻接表存储结构中，并继续执行动态逼近式最短路优先算法；
步骤六：重复上述步骤三至步骤五，直到动态逼近式最短路优先算法执行到终点，将行车路线绘制在矢量地图上；
步骤七：根据当前速度判断是否开始行车，开始行车后，上报当前位置信息、当前车速及转向角，在行车过程中，每隔一段时间采集一次交通热点信息，并判断当前用户是否在规定的行驶路线当中，如果偏离路线便根据当前采集到的实时交通热点信息重复步骤(二)至步骤(六)动态的进行实时路径规划及规避。
2.根据权利要求1所述的面向交通热点规避的路径规划方法，其特征在于：所述第一步中，确定出发地信息，即默认为当前用户位置信息；还可选择加入途经点，在规划路径过程中，从出发点首先经过途经点，最终到达目的地。
3.根据权利要求1所述的面向交通热点规避的路径规划方法，其特征在于：所述第二步中，通过挖掘互联网当前及未来一小时内可能导致交通拥堵的交通热点信息，来源包含票务网站、交通局网站，气象网站、微博数据以及动态上报的交通信息，其中获取到的交通热点信息属性包括：事件的地理位置：地名和经纬度、影响时间：事件开始和预计结束时间；交通热点信息影响内容即事件包括道路拥堵、交通事故、体育赛事、大型演唱会、路面塌陷；交通热点信息影响程度包括无法通行、拥堵、缓行，获取到交通热点信息后根据它对道路造成的影响程度在矢量地图上标注该热点，其中标注颜色是根据影响严重程度从小到大分为绿、橙、红三种，标注的大小是根据交通热点信息影响范围大小进行标注，标注上会显示该热点的地址、事件及影响时间。
4.根据权利要求1所述面向交通热点规避的路径规划方法，其特征在于：所述第三步中，根据美国交通局路阻函数即路段行驶时间与路段交通负荷之间的关系函数，为该行车过程中三条常规行驶时间最短路线赋权值的具体过程为：
(1)依据国家统计局大量的道路交通流量数据测试拟合出符合该方法的拥堵影响因子并确定路阻函数的待定参数；
(2)得到路阻函数的待定参数后，根据交通热点信息属性、影响内容和影响程度，对三条常规行驶时间最短的路线影响进行建模，其中交通热点信息对道路的影响判定是根据该道路上离交通热点最近的点到交通热点的行驶距离，而非两点间直线距离，交通热点离道路的行驶距离越大对道路的影响程度越低；
(3)根据步骤(2)中得到的交通热点对路段影响，再依据美国联邦公路局路阻函数，即路段行驶时间与路段交通负荷之间的关系函数确定热点对道路的影响因子，拟合出符合该方法的时间依赖函数；
(4)通过该时间依赖函数为三条常规行驶时间最短的路线中每条路段赋权值。
5.根据权利要求1所述面向交通热点规避的路径规划方法，其特征在于：所述第四、五、六步中动态逼近式最短路优先算法过程如下：
(1)通过最短路径优先算法(SPFA)遍历当前邻接表中存储的路段，其中邻接表中顶点为路口拐点位置经纬度，边结点中保存与该顶点直接相连的路口拐点经纬度，另外边结点中还存储当前相邻俩路况之间路段的权值、是否受交通热点影响标记、该路段距离及该路段中的部分点位置经纬度；
(2)遍历到受交通热点影响的路段时，将当前路段的入口加入SPFA算法的队列的队尾，保存当前SPFA算法执行过程中队列里面的结点，将该路段的前一路段入口设置为出发点，目的地为终点重新获得新的行驶路线，至多三条，加入之前已有最初路网的邻接表结构中，继续执行SPFA算法；
(3)重复以上步骤(1)和(2)通过多次迭代，迭代次数为SPFA算法执行过程中遇到受影响的路段次数，直到遇到交通热点后已经无法获得更新的路段或者SPFA算法将邻接表结构中的所有路段遍历完结束；
SPFA算法执行过程中记录下最短路线，即最终得到最佳行驶路线，并将最佳线路显示在矢量地图上。
6.根据权利要求1所述面向交通热点规避的路径规划方法，其特征在于：所述第七步中：开始行车后通过GPS获得当前用户位置信息，通过位置差和时间差获得当前用户速度，根据当前速度判断用户是否已经开始行车，如果开始则触发上报事件，每隔1分钟上报用户位置信息、速度信息及方向角，根据速度及所处位置这些信息中的部分信息将被整理成交通热点信息；动态上报的当前位置用来检验是否在预设行车路线当中，如果偏离导航路线，则做出提示，并以用户当前位置出发点，以目的地为终点，重新规划导航线路，并隔一段时间采集一次实时交通热点信息，以供规划行车路线。

一种面向交通热点规避的路径规划方法\n技术领域\n[0001] 本发明关于一种面向交通热点规避的路径规划方法，属于导航路径规划技术研究领域。\n背景技术\n[0002] 在机动车总量极具增加的今天，道路拥堵情况愈为严重，特别是像北京、上海这样的大城市，在早晚高峰期间出行已经成为一件非常领人头疼的事情，如果在车辆行驶途中，遇到有重大交通事故或者人群集结的路段更是让司机朋友们苦不堪言。随着科学的发展，面对解决人们出行难问题，本方法通过采集行车中可能遇到的造成交通拥堵的交通热点信息、数据库中的规律性历史信息及实时上报的交通信息，实时的动态规划行车路线，以耗费时间最短为目的，提供给用户具有规避交通热点功能的智能路径规划方法，在此应用下，不仅为用户出行带来方便，同时也起到了缓解城市交通道路压力的目的，利用起“闲路段”以缓解“忙路段”的车流压力。\n[0003] 目前的路径规划方法可以避开带有收费站或者高速路等特定路段，其应用价值有限。随着科学技术的发展，智能导航也被很多学者研究并做了大量的工作，但是还存在一些弊端，例如：规划路线单一、无法根据当前交通状况实时规划路径、可适用的区域小等。造成上述问题的原因主要在于地理数据不够全面、无后台数据库数据支持、路径规划过程中与网络不能交互，不能获得交通热点信息、无行车路线预判动态规划行驶路线等，严重影响出行。对于目前很多专家学者研究的一些带有规避功能的导航方法，其也主要是针对某个特定的区域，通过对该区域进行调研获得路况数据并利用较为单一的数据来源，进行路况预判，其实用范围局限性高，数据不够全面，无法对突发事件进行捕捉及时的向用户反应当前的路况信息，以至于导航路径不能针对多元数据实时规避。\n发明内容\n[0004] 本发明的技术问题：克服现有技术的不足，提供一种面向交通热点规避的路径规划方法，根据多元交通热点规避，实现动态的路径规划方法，以行车最短耗时为目的，提供时间最优算法下的导航线路。\n[0005] 本发明技术解决方案：一种面向交通热点规避的路径规划方法，其步骤如下：\n[0006] 步骤一：确定出发地、目的地及途经点信息；\n[0007] 步骤二：根据获得的行车目的地信息，从票务网站、微博、交通网站、实时上报的交通信息及数据库中存储的历史规律性信息等多个数据源获取交通热点信息既可能造成交通拥堵的交通信息供采集，并根据交通热点信息的影响范围及程度用不同大小及颜色绘制到矢量地图上；\n[0008] 步骤三：通过步骤二中实时采集到的交通热点信息，结合道路最高时速限制、路宽、交叉口延时及干道是否含有非机动车车带，根据美国交通局路阻函数即路段行驶时间与路段交通负荷之间的关系函数，为该行车过程中三条常规行驶时间最短路线赋权值，并加入邻接表存储结构中作为最初的交通路网；\n[0009] 步骤四：为步骤三获得的路网实施以SPFA为基础的动态逼近式最短路优先算法，算法遍历每条路段，直到执行至受交通热点信息影响的路段；\n[0010] 步骤五：以受到交通热点信息影响的路段的前一路段的入口为起点，目的地为终点获得新的三条常规行驶最短路线赋权值后加入邻接表存储结构中，并继续执行最短路优先算法；\n[0011] 步骤六：重复上述步骤（3）至（5）直到算法执行到终点，将行车路线绘制在矢量地图上；\n[0012] 步骤七：根据当前速度判断是否开始行车，开始行车后，上报当前位置信息、当前车速及转向角，在行车过程中，如5分钟采集一次热点信息，如果偏离路线便根据当前采集到的实时交通热点信息重复步骤（2）至（6）动态的进行实时路径规划及规避；\n[0013] 所述第一步中：所述第一步中：确定出发地信息（默认为当前用户位置）和目的地信息，还可选择加入途经点，在规划路径过程中，从出发点首先经过途经点，最终到达目的地。\n[0014] 所述第二步中：根据权利要求1所述的面向交通热点规避的路径规划方法，其特征在于：所述第二步中，通过挖掘互联网当前及未来一小时内可能导致交通拥堵的交通热点信息，来源包含票务网站、交通局网站，气象网站、微博数据以及动态上报的交通信息，其中获取到的交通热点信息属性包括：事件的地理位置：地名和经纬度、影响时间：事件开始和预计结束时间；交通热点信息影响内容（事件）包括道路拥堵、交通事故、体育赛事、大型演唱会、路面塌陷；交通热点信息影响程度包括无法通行、拥堵、缓行。获取到交通热点信息后根据它对道路造成的影响程度在矢量地图上标注该交通热点，其中标注颜色是根据影响严重程度从小到大分为绿、橙、红三种，标注的大小是根据交通热点信息影响范围大小进行标注，标注上会显示该交通热点的地址、事件及影响时间。\n[0015] 所述第三步中：结合步骤二的交通热点信息和数据库中的信息，这些信息包括各学校等大型单位上下学或上下班时间、各路段最高时速限制、路宽、是否含有非机动车带、交叉口交通灯延时信息的规律性历史数据，通过重新定制美国联邦公路局路阻函数并计算每条路段的当前可能行驶时间（单位：秒），为常规行驶时间最短的三条道路赋权值，其中路阻函数定制步骤如下：\n[0016] （1）依据国家统计局大量的道路交通流量数据测试拟合出符合该方法的拥堵影响因子并确定路阻函数的待定参数；\n[0017] （2）得到路阻函数的待定参数后，根据交通热点信息属性、影响内容和影响程度，对三条常规行驶时间最短的路线影响进行建模，其中交通热点信息对道路的影响判定是根据该道路上离交通热点（交通热点是指交通热点信息中对交通带来影响的事件地理位置，可能是某个建筑或者某个事件发生的地点）最近的点到交通热点的行驶距离，而非两点间直线距离，交通热点离道路的行驶距离越大对道路的影响程度越低；\n[0018] （3）根据步骤（2）中得到的交通热点对路段影响，再依据美国联邦公路局路阻函数，即路段行驶时间与路段交通负荷之间的关系函数确定热点对道路的影响因子，拟合出符合该方法的时间依赖函数；\n[0019] （4）通过该时间依赖函数为三条常规行驶时间最短的路线中每条路段赋权值。\n[0020] 所述第四、五、六步中：逼近式的最短路径规划过程如下：\n[0021] （1）通过最短路径优先算法（SPFA）遍历当前邻接表中存储的路段，其中邻接表中顶点为路口拐点位置经纬度，边结点中保存与该顶点直接相连的路口拐点经纬度，另外边结点中还存储当前相邻俩路况之间路段的权值、是否受交通热点影响标记（布尔变量表示：\n受影响为true，不受影响为false）、该路段距离、及该路段中的部分点位置经纬度（用于绘制导航线路）；\n[0022] （2）遍历到受交通热点影响的路段时，将当前路段的入口加入SPFA算法的队列的队尾，保存当前SPFA算法执行过程中队列里面的结点，将该路段的前一路段入口设置为出发点，目的地为终点重新获得新的行驶路线，至多三条，加入之前已有最初路网的邻接表结构中，继续执行SPFA算法；\n[0023] （3）重复以上步骤（1）和（2）通过多次迭代，迭代次数为SPFA算法执行过程中遇到受影响的路段次数，直到遇到交通热点后已经无法获得更新的路段或者SPFA算法将邻接表结构中的所有路段遍历完结束；\n[0024] SPFA算法执行过程中记录下最短路线，即最终得到最佳行驶路线，并将最佳线路显示在矢量地图上。\n[0025] 所述第七步中：开始行车后通过GPS获得当前用户位置信息，通过位置差和时间差获得当前用户速度，根据当前速度判断用户是否已经开始行车，如果开始则触发上报事件，每隔一段时间，如1分钟上报用户位置信息、速度信息及方向角，根据速度及所处位置这些信息中的部分信息将被整理成交通热点信息。动态上报的当前位置用来检验是否在预设行车路线当中，如果偏离导航路线，则做出提示，并以用户当前位置出发点，以目的地为终点，重新规划导航线路。并隔一段时间，如5分钟采集一次实时交通热点信息，以供规划行车路线。\n[0026] 本发明与现有技术相比有益效果及优点：\n[0027] （1）本发明所述的规避交通热点方法，采用的是多元交通热点信息，是对互联网中的涉及影响交通的信息实时抓取、并结合实时上报的交通信息及数据库中的规律性历史数据。其数据来源广，可信度高，更新快，为规避方法提供了可靠地数据支持。\n[0028] （2）本发明所述的路径规划过程中不需要一开始便得到从起点到目的地的全部路段，而是在首先获取三条常规行驶时间最短路线的基础上进行初步选路，根据路况来判断是否需要得到更多路段信息，在算法执行的基础上再次添加新路径结点进行选路，这样可以在不必一下知道当前所有可行路段的情况下，进行动态逼近式的选路方法，提高路径规划效率。\n[0029] （3）本发明采用的路段赋权值方法是以美国联邦公路局路阻函数（路段行驶时间与路段交通负荷之间的关系函数）为基础，进行大量的数据测试拟合出符合该方法的拥堵影响因子并确定路阻函数，为受到交通热点影响的路段利用路阻函数赋高权值，形成科学的选路方法。\n附图说明\n[0030] 图1为方法流程图\n[0031] 图2为交通热点信息挖掘示意图；\n[0032] 图3为路径规划方法流程图；\n[0033] 图4为热点标注图；\n[0034] 图5为普通导航建议路线图；\n[0035] 图6为规避热点路径图；\n[0036] 图7为带有途经点的导航线路图。\n具体实施方式\n[0037] 下面结合附图对本发明的具体实施方式作进一步说明：\n[0038] 如图1所示，本发明方法主要包括交通热点信息采集、动态路径规划、行驶时间预判及交通影响范围界定四项核心技术，具体实施方案如下：\n[0039] 1、设定出发地、目的地及途经点地址信息：\n[0040] 进行路径规划前，第一步需要确定出发点和目的地信息，出发地址默认为当前位置，也可根据需要改变，设定完成后可以依据需要设定途经点地址，路径规划过程中，首先由出发点经过途经点，最后到达目的地。\n[0041] 2、采集交通热点信息：\n[0042] 首先依据当前设置出发地、目的地及途经点采集交通热点信息，其来源如下：\n[0043] 在图2本方法的示意图中，网络信息来源的获取和数据库信息如下：\n[0044] （1）.网页信息抓取：通过对基于JSOUP的特定网页解析，包括票务网站、交通部发布路况信息网站等；\n[0045] （2）.数据库：学校等大型单位上下学（班）时间，各路段最高时速限制、路宽、是否含有非机动车带及交叉口延时时间等规律性历史信息；\n[0046] （3）.微博信息：基于微博API对微博上关于交通的信息抓取和人工筛选；\n[0047] 其中数据库信息在为道路赋权值的时候使用。\n[0048] 获得信息后需要对信息内容进行分类抽取和学习，其应用技术主要有三点：1.基于模式识别的交通热点发现；2.基于统计模型的交通热点预测；3.基于领域语义的交通热点数据关联和准确性验证。进行挖掘后，对于有用的交通信息将其组成交通热点信息的形式，信息中包括该热点的影响时间、严重程度、影响范围，并根据事件类型进行分类，将这些交通热点信息依据严重程度标注在矢量地图上，最严重的为红色，其次为橙色，相对影响较低的为绿色，其中事件类型可分为：道路拥堵、交通事故、体育赛事、大型演唱会、路面塌陷；\n影响程度包括无法通行、拥堵、缓行；这些信息会在标注中体现。\n[0049] 3、结合采集到的交通热点信息及数据库规律性历史数据进行路径规划：在图3本方法的示意图中所示路径规划过程对应说明内容的第三步至第六步具体执行过程如下：\n[0050] S1：开始；\n[0051] S2：获得从起点到目的地以常规行驶时间最短为准的三条行车路线，并为每条路段赋权值，加入邻接表中存储；\n[0052] S3：对当前邻接表中存储的数据执行SPFA（最短路径优先算法）；\n[0053] S4：判断算法执行过程中是否遇到受当前交通热点信息影响的路段；\n[0054] YES：执行S5；\n[0055] NO：跳转至S7；\n[0056] S5：存储当前遍历结果既为：将受影响路段的入口位置加入SPFA算法队列的队尾，并保存当前队列；\n[0057] S6：将起点设置为当前受到热点影响的路段的前一路段入口，目的地不变，跳转至S2；\n[0058] S7：绘制导航线路；\n[0059] S8：结束。\n[0060] 本发明中S2中路段权值以美国联邦交通局路阻函数为基础通过计算路段行驶时间获得，其中权值计算方法如下：\n[0061] （1）从出发点到目的地间总共行驶时间公式为：\n[0062] \n[0063] 参数：T为两地时间距离（单位：秒），ti为每条路段（干道）的行驶时间（单位：秒），dj为交叉口延时时间（单位：秒）；\n[0064] （2）公式（1）ti干道行驶时间，计算公式为：\n[0065] \n[0066] \n[0067] 式中：（2）式为美国交通局路阻函数（路段行驶时间与路段交通负荷之间的关系函数），其中t0为干道常规行驶时间（单位：秒），Q为当前交通量（单位：pcu/h），C为路段实际通行能力（单位：pcu/h），α、β为该函数的待定系数，建议取值分别为0.15,4。但是考虑到我国道路交通情况与美国的不同，所以该值将根据国家统计局提供的大量统计数据进行拟合得出。\n[0068] （3）式是根据（2）式而来，其中L为路段长度（单位：米）；U为路段零流量时的车速（即该路段最高时速）（单位：米/秒）；Q为当前交通量（单位：pcu/h），通过采集该路段上报交通数据量获得；C为当前车流量（通常取2000辆/h）；γ根据路段是否有非机动车带而定（有分隔带取1，没有分隔带取0.8）；w是路宽（单位：米）；s为交叉路口延时影响系数；\n为当前路段上所有交通热点影响阻抗系数，其中hk为每个交通热点的阻抗系数，根据交通热点的影响程度、范围及影响时间通过建模拟合得出。\n[0069] dj为信号交叉口延误时间（单位：秒），根据经典交叉口延误计算公式Webster给出，公式中主要涉及到的信号灯延误时间在数据库中可以得到。\n[0070] 在为道路赋权值后该过程中将首次获得的三条常规行驶时间最短路线作为基础路网加入邻接表中存储，其中邻接表中顶点为路口拐点位置经纬度，边结点中保存与该顶点直接相连的路口拐点经纬度，另外边结点中还存储当前相邻俩路段之间的权值、是否受交通热点影响标记（布尔变量表示：受影响为true，不受影响为false）、该路段长度、及该路段中的部分点位置经纬度（用于绘制导航线路），该路网图所具有的的特征为单向性和稀疏性，单向性是指图中无回路，此特性可以在SPFA算法的执行过程中在邻接表中加入新结点和路段，由于SPFA算法的逼近求解特征，使得该加入操作不影响算法之前的执行结果，这样算法和邻接表的加入操作交替执行，保证了以通过检索最少的路段数据来获得最优的选路策略；由于路网图的稀疏特征，该路径规划算法选择对于稀疏图执行效率最优的SPFA算法，该算法时间复杂度仅为对每条边遍历一遍的时间，在寻找最短路算法中该算法时间复杂度最低且对于稀疏图执行效率最高。\n[0071] 在路径规划完成后，将路线绘制在矢量地图上，起点，途经点及终点分别进行标注。\n[0072] 4、上报速度、当前经纬度、方向角及实时路径规划过程如下：\n[0073] 当前速度如果达到行车速度，便会每隔10秒钟上报当前经纬度信息，速度信息及方向角，其中当前经纬度信息由GPS获得，速度和方向角由相邻上报的两次经纬度和间隔时间求得。在行驶过程中，每隔5分钟便对当前实时的交通热点信息进行采集，重新在地图上标注交通热点，并根据当前最新交通热点信息实时的规划导航线路，在行驶的过程中，如果当前位置不在预设的行驶路线上，会根据当前位置为起点，目的地为终点重新规划新的导航线路，绘制在矢量地图上。\n[0074] 在图4本方法的示意图中：测试环境为移动终端设备，其中红色标注为造成周围路段阻塞的交通热点，严重程度最高；橙色为造成周围路段拥堵的交通热点，严重等级为中等；绿色标注为造成路段缓行的交通热点，严重程度最低。\n[0075] 在图5和图6本发明的示意图中：图5所展示的是普通静态导航方法所提供的的三条最快建议行车路线，这三条路线在道路完全顺畅的情况下可视为最优行车路线，但是可以看出这三条路线均有路段在交通热点影响范围之内，图6所示的行车路线为用到了面向交通热点规避的路径规划方法的路线，可以看出该路线比普通导航路线拥有更智能的规避功能，在以时间最优为目的的行车过程中避开了交通热点。图7为设置带有途经点的导航线路图，起点途经点和终点分别进行了标注，路线首先由起点到达途经点，接着从途经点到达目的地。\n[0076] 本发明未详细阐述部分属于本领域公知技术。\n[0077] 以上所述，仅为本发明部分具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本领域的人员在本发明揭露的技术范围内，可轻易想到的变化或替换，都应涵盖在本发明的保护范围之内。