[go: up one dir, main page]

CN113295177A - 基于实时路况信息的动态路径规划方法及系统 - Google Patents

基于实时路况信息的动态路径规划方法及系统 Download PDF

Info

Publication number
CN113295177A
CN113295177A CN202110479473.4A CN202110479473A CN113295177A CN 113295177 A CN113295177 A CN 113295177A CN 202110479473 A CN202110479473 A CN 202110479473A CN 113295177 A CN113295177 A CN 113295177A
Authority
CN
China
Prior art keywords
road section
path
road
shortest
current
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
CN202110479473.4A
Other languages
English (en)
Other versions
CN113295177B (zh
Inventor
康军
杜锦光
段宗涛
李宜修
黄山
何昊健
马浩森
任国亮
王倩倩
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Changan University
Original Assignee
Changan University
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Changan University filed Critical Changan University
Priority to CN202110479473.4A priority Critical patent/CN113295177B/zh
Publication of CN113295177A publication Critical patent/CN113295177A/zh
Application granted granted Critical
Publication of CN113295177B publication Critical patent/CN113295177B/zh
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • G—PHYSICS
    • G01—MEASURING; TESTING
    • G01C—MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY
    • G01C21/00—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00
    • G01C21/26—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00 specially adapted for navigation in a road network
    • G01C21/34—Route searching; Route guidance
    • G01C21/3446—Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
    • G—PHYSICS
    • G01—MEASURING; TESTING
    • G01C—MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY
    • G01C21/00—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00
    • G01C21/26—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00 specially adapted for navigation in a road network
    • G01C21/34—Route searching; Route guidance
    • G01C21/3453—Special cost functions, i.e. other than distance or default speed limit of road segments
    • G01C21/3492—Special cost functions, i.e. other than distance or default speed limit of road segments employing speed data or traffic data, e.g. real-time or historical
    • Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y02—TECHNOLOGIES OR APPLICATIONS FOR MITIGATION OR ADAPTATION AGAINST CLIMATE CHANGE
    • Y02T—CLIMATE CHANGE MITIGATION TECHNOLOGIES RELATED TO TRANSPORTATION
    • Y02T10/00—Road transport of goods or passengers
    • Y02T10/10—Internal combustion engine [ICE] based vehicles
    • Y02T10/40—Engine management systems

Landscapes

  • Engineering & Computer Science (AREA)
  • Radar, Positioning & Navigation (AREA)
  • Remote Sensing (AREA)
  • Automation & Control Theory (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Navigation (AREA)
  • Traffic Control Systems (AREA)

Abstract

本发明涉及车辆导航以及路径规划领域，公开了一种基于实时路况信息的动态路径规划方法及系统。该方法是车辆在沿已规划好的导航路线行驶过程中，若在车辆行驶前方出现拥堵路段时，在原始路径的基础上尽可能少的替换与拥堵路段相连的一部分路径，而不用偏离原来的行驶方向，就可以完成路径的重新规划，到达预先设定好的目的地，从而能有效的缓解道路交通拥堵状况。同时本发明在重新规划路径时不需要再次在路网中进行路径搜索，而是在本发明中所提到的树形结构中进行搜索，比在路网中进行路径搜索更加快捷，从而能很大程度上缩短因路径搜索而花费的时间。适用于车辆导航以及路径规划等情况，在智能交通领域有重要的应用价值。

Description

基于实时路况信息的动态路径规划方法及系统
技术领域
本发明属于车辆导航以及路径规划领域，具体涉及基于实时路况信息的动态路径规划方法及系统。
背景技术
车辆在沿已规划好的导航路线行驶过程中，由于受到交通流量、天气、突发事故等因素的影响，在汽车的行驶路径中会出现拥堵路段，此时需要合理的路径规划来规避拥堵。现有的路径规划大多是在全局路网的基础上进行搜索，通过使用遗传算法、A*算法、蚁群算法、Dijkstra算法等来解决路径优化问题。其中，遗传算法是指通过模拟自然界中的选择和遗传机制来寻找最优路径。它具有很好的全局搜索能力，但在处理行驶路线问题时，存在路径交叉现象，导致搜索结果次优；A*算法是一种广泛使用的最短路径启发式搜索算法。该算法的搜索结果与启发式函数密切相关。不同的启发式函数会导致不同的搜索路径；蚁群算法是一种现代仿生进化算法，具有很强的鲁棒性，但容易出现算法收敛速度慢和容易陷入局部最优的缺陷；Dijkstra算法用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。它能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。
此外，采用全局路网搜索的方法进行路径规划时，需要在重新遍历路网中的全部路径的基础上进行搜索，且搜索过程中需要利用所有路段的拓扑关系，以此来替换原导航路径中的很大一部分路径，从而使得汽车行驶偏离了原来的行驶方向，同时也增加了路径规划的时间，不满足汽车行驶的及时性要求。
发明内容
本发明的目的在于提供基于实时路况信息的动态路径规划方法及系统，用以解决现有技术中当出现重新规划路径的情况时，需要重新在路网中进行路径搜索，从而导致处理效率低下的问题。
为了实现上述任务，本发明采用以下技术方案：
基于实时路况信息的动态路径规划方法，用于采用建立好的最短树形结构路网地图，对原始路径中的拥堵路段进行替换并对候补替换路径进行寻优，获得最优替换路径；
所述的最短树形结构路网地图包括各个路段的树形结构，每个路段的树形结构包括路段的拓扑结构以及该路段进行最短距离搜索后每个路段到其他路段的最短可达路径和最短距离；该方法包括如下步骤：
步骤1：获取原始规划路径和当前位置，所述原始规划路径中包含拥堵路段；
步骤2：根据拥堵路段的路段ID在最短树形结构路网地图中查找拥堵路段树形结构，获得拥堵路段的相邻上游路段和相邻下游路段，将拥堵路段的相邻上游路段的拓扑路段作为出发路段，将拥堵路段的相邻下游路段作为结束路段，所述的相邻上游路段和相邻下游路段均属于原始规划路径；
步骤3：判断当前的出发路段和当前的结束路段之间是否存在不经过拥堵路段的可达路径，将存在的可达路径保存为候补替换路径，
保留当前的出发路段并将当前的结束路段的相邻下游路段作为当前的结束路段；
步骤4：对当前的结束路段进行判断，若当前的结束路段到拥堵路段之间的路径长度小于等于第二路径距离阈值时，则返回执行步骤3，其中，所述第二路径距离阈值为从拥堵路段出发向下游路段搜索距离的最大上限阈值；
若当前的结束路段到拥堵路段之间的路径长度大于第二路径距离阈值时，则将当前的出发路段中不包含原始轨迹路段的剩余拓扑路段作为当前的出发路段，将拥堵路段的相邻下游路段作为当前的结束路段，返回执行步骤3，直至当前的出发路段中剩余拓扑路段为空，则将当前的出发路段中包含的原始轨迹路段的相邻上游路段的拓扑路段更新为当前的出发路段，将拥堵路段的相邻下游路段作为当前的结束路段，执行步骤5；
步骤5：若当前的出发路段到当前位置的距离大于等于第一路径距离阈值时，则返回执行步骤3，其中，所述第一路径距离阈值为出发路段到当前行驶位置之间距离的最小下限阈值；
否则，停止路径搜索并判断，若候补替换路径为空，则继续按照原始规划路径行驶；若候补替换路径不为空，则执行步骤6；
步骤6：获取候补替换路径中的出发路段和结束路段之间路径长度最短的路径，并判断该路径长度最短的路径中是否包含新的拥堵路段，若存在新的拥堵路段，则更新拥堵路段且将更新后的行驶轨迹路径作为原始轨迹路径并重新执行步骤2；否则将该路径长度最短的路径作为最优替换路径。
进一步的，获取最短树形结构路网地图包括如下子步骤：
步骤a：获得所有路段的路段数据，所述的路段数据包括路段ID、路段起点经度坐标、路段起点纬度坐标、路段终点经度坐标、路段终点纬度坐标和路段长度，将所有路段的路段数据根据起点、终点经纬度坐标是否相同进行关联，获得每个路段的拓扑结构；
步骤b：对每个路段按照拓扑结构进行最短距离搜索，获得每个路段到其他路段的最短可达路径和最短距离，以每个路段的起点和终点为该路段树形结构的Node节点，以每个路段在最短距离搜索算法的时间长度内的可达路径和最短距离为该路段树形结构的Value值建立树形结构，得到所有路段的树形结构，将所有路段的树形结构作为最短树形结构路网地图。
进一步的，所述的第一路径距离阈值根据最短反应时间和汽车的平均行驶速度确定，所述的第二路径距离阈值根据从当前路段出发到达与其相连的下游方向的最远可达路径之间所需的时间和汽车的平均行驶速度确定。
更进一步的，平均行驶速度为50km/s，最短反应时间为40s，从当前路段出发到达与其相连的下游方向的最远可达路径之间所需的时间为2min。
基于实时路况信息的动态路径规划系统，用于采用建立好的最短树形结构路网地图，对原始路径中的拥堵路段进行替换并对候补替换路径进行寻优，获得最优替换路径；
该系统包括路段最短树形结构路网地图和替换路径规划模块；
所述的最短树形结构路网地图包括各个路段的树形结构，每个路段的树形结构包括路段的拓扑结构以及该路段进行最短距离搜索后每个路段到其他路段的最短可达路径和最短距离；
所述的替换路径规划模块包括多个子模块，其中，第一子模块用于获取原始规划路径和当前位置，所述原始规划路径中包含拥堵路段；
第二子模块用于根据拥堵路段的路段ID在最短树形结构路网地图中查找拥堵路段树形结构，获得拥堵路段的相邻上游路段和相邻下游路段，将拥堵路段的相邻上游路段的拓扑路段作为出发路段，将拥堵路段的相邻下游路段作为结束路段，所述的相邻上游路段和相邻下游路段均属于原始规划路径；
第三子模块用于判断当前的出发路段和当前的结束路段之间是否存在不经过拥堵路段的可达路径，将存在的可达路径保存为候补替换路径，
保留当前的出发路段并将当前的结束路段的相邻下游路段作为当前的结束路段；
第四子模块用于对当前的结束路段进行判断，若当前的结束路段到拥堵路段之间的路径长度小于等于第二路径距离阈值时，则返回执行第三子模块，其中，所述第二路径距离阈值为从拥堵路段出发向下游路段搜索距离的最大上限阈值；
若当前的结束路段到拥堵路段之间的路径长度大于第二路径距离阈值时，则将当前的出发路段中不包含原始轨迹路段的剩余拓扑路段作为当前的出发路段，将拥堵路段的相邻下游路段作为当前的结束路段，返回执行第三子模块，直至当前的出发路段中剩余拓扑路段为空，则将当前的出发路段中包含的原始轨迹路段的相邻上游路段的拓扑路段更新为当前的出发路段，将拥堵路段的相邻下游路段作为当前的结束路段，执行第五子模块；
第五子模块用于判断，若当前的出发路段到当前位置的距离大于等于第一路径距离阈值时，则返回执行第三子模块，其中，所述第一路径距离阈值为出发路段到当前行驶位置之间距离的最小下限阈值；
否则，停止路径搜索并判断，若候补替换路径为空，则继续按照原始规划路径行驶；若候补替换路径不为空，则执行第六子模块；
第六子模块用于获取候补替换路径中的出发路段和结束路段之间路径长度最短的路径，并判断该路径长度最短的路径中是否包含新的拥堵路段，若存在新的拥堵路段，则更新拥堵路段且将更新后的行驶轨迹路径作为原始轨迹路径并重新执行第二子模块；否则将该路径长度最短的路径作为最优替换路径。第六子模块用于获取替换路径的出发路段和结束路段之间路径长度最短的路径，并判断该路径长度最短的路径中是否包含新的拥堵路段，若存在新的拥堵路段，则更新拥堵路段并重新执行第二子模块；否则将该路径长度最短的路径作为最优替换路径。
进一步的，获取最短树形结构路网地图包括如下子模块：
子模块a用于获得所有路段的路段数据，所述的路段数据包括路段ID、路段起点经度坐标、路段起点纬度坐标、路段终点经度坐标、路段终点纬度坐标和路段长度，将所有路段的路段数据根据起点、终点经纬度坐标是否相同进行关联，获得每个路段的拓扑结构；
子模块b用于对每个路段按照拓扑结构进行最短距离搜索，获得每个路段到其他路段的最短可达路径和最短距离，以每个路段的起点和终点为该路段树形结构的Node节点，以每个路段在最短距离搜索算法的时间长度内的可达路径和最短距离为该路段树形结构的Value值建立树形结构，得到所有路段的树形结构，将所有路段的树形结构作为最短树形结构路网地图。
进一步的，所述的第一路径距离阈值根据最短反应时间和汽车的平均行驶速度确定，所述的第二路径距离阈值根据从当前路段出发到达与其相连的下游方向的最远可达路径之间所需的时间和汽车的平均行驶速度确定。
更进一步的，平均行驶速度为50km/s，最短反应时间为40s，从当前路段出发到达与其相连的下游方向的最远可达路径之间所需的时间为2min。
本发明与现有技术相比具有以下技术特点：
(1)本发明基于实时路况信息的动态路径规划，车辆在沿已规划好的导航路线行驶过程中，若在车辆行驶前方出现拥堵路段时，在原始路径的基础上尽可能少的替换与拥堵路段相连的一部分路径，而不用偏离原来的行驶方向，就可以完成路径的重新规划，到达预先设定好的目的地。从而能有效的缓解道路交通拥堵状况。
(2)本发明在重新规划路径时不需要再次在路网中进行路径搜索，而是在本发明中所提到的树形结构中进行搜索，比在路网中进行路径搜索更加快捷，从而能很大程度上缩短因路径搜索而花费的时间。
(3)本发明的方法适用于车辆导航以及路径规划等情况，在智能交通领域有重要的应用价值。
附图说明
图1为本发明实时路况信息的动态路径规划的效果图；
图2为路段拓扑结构示意图；
图3为树形的数据结构示意图；
图4为总体流程图；
图5为实施例示意图。
具体实施方式
以下给出本发明的具体实施方式，需要说明的是本发明并不局限于以下具体实施例，凡在本申请技术方案基础上做的等同变换均落入本发明的保护范围。
本发明基于实时路况信息的动态路径规划，采用Scala语言实现，可以根据车辆行驶路径中出现的拥堵路段来进行实时地重新规划路径，从而能有效的缓解道路交通拥堵状况，以及避免因交通拥堵而消耗的时间。
在本实施例中公开了一种基于实时路况信息的动态路径规划方法，用于采用建立好的最短树形结构路网地图，对原始路径中的拥堵路段进行替换并对候补替换路径进行寻优，获得最优替换路径；
在算法的实际运行中不光替换了拥堵路段，还会替换与拥堵路段相连的一部分路段；
所述的最短树形结构路网地图包括各个路段的树形结构，每个路段的树形结构包括路段的拓扑结构以及该路段进行最短距离搜索后每个路段到其他路段的最短可达路径和最短距离；该方法包括如下步骤：
步骤1：获取原始规划路径和当前位置，所述原始规划路径中包含拥堵路段；
步骤2：根据拥堵路段的路段ID在最短树形结构路网地图中查找拥堵路段树形结构，获得拥堵路段的相邻上游路段和相邻下游路段，将拥堵路段的相邻上游路段的拓扑路段作为出发路段，将拥堵路段的相邻下游路段作为结束路段，所述的相邻上游路段和相邻下游路段均属于原始规划路径；
步骤3：判断当前的出发路段和当前的结束路段之间是否存在不经过拥堵路段的可达路径，将存在的可达路径保存为候补替换路径，
保留当前的出发路段并将当前的结束路段的相邻下游路段作为当前的结束路段；
步骤4：对当前的结束路段进行判断，若当前的结束路段到拥堵路段之间的路径长度小于等于第二路径距离阈值时，则返回执行步骤3，其中，所述第二路径距离阈值为从拥堵路段出发向下游路段搜索距离的最大上限阈值；
若当前的结束路段到拥堵路段之间的路径长度大于第二路径距离阈值时，则将当前的出发路段中不包含原始轨迹路段的剩余拓扑路段作为当前的出发路段，将拥堵路段的相邻下游路段作为当前的结束路段，返回执行步骤3，直至当前的出发路段中剩余拓扑路段为空，则将当前的出发路段中包含的原始轨迹路段的相邻上游路段的拓扑路段更新为当前的出发路段，将拥堵路段的相邻下游路段作为当前的结束路段，执行步骤5；
步骤5：若当前的出发路段到当前位置的距离大于等于第一路径距离阈值时，则返回执行步骤3，其中，所述第一路径距离阈值为出发路段到当前行驶位置之间距离的最小下限阈值；
否则，停止路径搜索并判断，若候补替换路径为空，则继续按照原始规划路径行驶；若候补替换路径不为空，则执行步骤6；
步骤6：获取候补替换路径中的出发路段和结束路段之间路径长度最短的路径，并判断该路径长度最短的路径中是否包含新的拥堵路段，若存在新的拥堵路段，则更新拥堵路段且将更新后的行驶轨迹路径作为原始轨迹路径并重新执行步骤2；否则将该路径长度最短的路径作为最优替换路径。
具体的，获取最短树形结构路网地图包括如下子步骤：
步骤a：获得所有路段的路段数据，所述的路段数据包括路段ID、路段起点经度坐标、路段起点纬度坐标、路段终点经度坐标、路段终点纬度坐标和路段长度，将所有路段的路段数据根据起点、终点经纬度坐标是否相同进行关联，获得每个路段的拓扑结构；
步骤b：对每个路段按照拓扑结构进行最短距离搜索，获得每个路段到其他路段的最短可达路径和最短距离，获得每个路段到其他路段的最短可达路径和最短距离，以每个路段的起点或终点为该路段树形结构的Node节点，以每个路段在最短距离搜索算法的时间长度内的可达路径和最短距离为该路段树形结构的Value值建立树形结构，得到所有路段的树形结构，将所有路段的树形结构作为最短树形结构路网地图。
具体的，对于任一个路段进行最短距离搜索时采用如下方法：
选取一个路段，以选取的路段为起始路段，对起始路段按照拓扑结构进行最短距离搜索，获得每个路段到其他路段的最短可达路径和最短距离，
具体的，所述的第一路径距离阈值根据最短反应时间和汽车的平均行驶速度确定，所述的第二路径距离阈值根据从当前路段出发到达与其相连的下游方向的最远可达路径之间所需的时间和汽车的平均行驶速度确定。
具体的，平均行驶速度为50km/s，最短反应时间为40s，从当前路段出发到达与其相连的下游方向的最远可达路径之间所需的时间为2min。
具体的，所述每个路段的拓扑结构包括路段ID和路段拓扑信息，所述路段拓扑信息包括：路段起点经度坐标、路段起点纬度坐标、与路段起点直接相连的路段Id集合、路段终点经度坐标、路段终点纬度坐标、与路段终点直接相连的路段Id集合和路段长度。
具体的，存储时路段的拓扑结构为Map结构，且路段拓扑信息结构如下：
Figure BDA0003048623860000101
具体的，路段的拓扑结构的建立方式如下：
从第一行数据开始，取出RoadId作为Key添加进Map结构中，取出起点经纬度坐标添加进路段拓扑信息中，然后依次与其他的路段数据的起点、终点经纬度坐标进行比较，若是相同，则将其他路段数据的RoadId添加进入与当前路段起点直接相连的路段Id集合中，然后取出终点经纬度坐标，然后依次与其他的路段数据的起点、终点经纬度坐标进行比较，若是相同，则将其他路段数据的Id添加进入与当前路段终点直接相连的路段Id集合中，然后以起点和终点经纬度做地球大圆距离计算，添加进入Distance字段中，然后取出第二行数据做上面的操作，一直到所有的路段数据都构成路段的拓扑结构则结束。
具体的，所述从当前路段出发到达与其相连的下游方向的最远可达路径之间所需的时间长度为2min。该方法是在保存了当前路段相连的下游方向2min之内可达路径的数据集上进行的。为了节省搜索时间，这部分数据集可以通过离线计算得到，提前通过最短距离搜索算法计算出每个路段与其小1667m的所有路段之间的最短路径及最短距离。1667m为汽车在规定时速为50km/s的条件下，在2min的行驶时间内汽车从当前路段出发与其相连的下游方向可达路径的最远距离。
由于最短树形结构路网地图是与当前路段相连的下游方向2min之内可达路径的数据集，所以该方法是在保存了当前路段相连的下游方向2min之内可达路径的数据集上进行的，所以取Threshold2为1667m，1667m为以50km/h速度行驶的并在2min之内从当前路段出发与其相连的下游方向可达路径的最远距离。取Threshold1为560m，560m为汽车在40s的反应时间内，在规定时速为50km/s的条件下，从当前位置出发与其相连的下游方向可达路径的最远距离，如果小于Threshold1的情况下汽车司机来不及做出反应去走到新的规划路线。
具体的，为每个路段构建两个树形结构，分别对应路段的起点和终点。路段的树形结构用Node节点表示，Node节点如下
Figure BDA0003048623860000111
Figure BDA0003048623860000121
其中RoadId代表当前路段的编号，ChildMap(Current ChildRoadId,CurrentNode)表示了该节点的子路段ID和子路段的Node节点，Value(Distance,Path)包含从初始路段到当前子路段之间的最短距离和连通路径。
具体的，路段的树形结构的建立方式如下：
从初始路段出发，取出RoadId作为Key添加进Node节点中，然后将与初始路段相连的子路段的当前子路段ID和当前子路段的Node节点添加进路段树形结构中，通过步骤a中的路段的拓扑结构，以及步骤b中的最短可达路径和最短距离并赋值给Value并保存到路段树形结构中。重复上述步骤，直到将当前路段的所有子路段与对应的Node节点全部添加完为止。路段树形结构示意图如图3所示。
本实施例中还公开了一种基于实时路况信息的动态路径规划系统，用于采用建立好的最短树形结构路网地图，对原始路径中的拥堵路段进行替换并对候补替换路径进行寻优，获得最优替换路径；
该系统包括路段最短树形结构路网地图和替换路径规划模块；
所述的最短树形结构路网地图包括各个路段的树形结构，每个路段的树形结构包括路段的拓扑结构以及该路段进行最短距离搜索后每个路段到其他路段的最短可达路径和最短距离；
所述的替换路径规划模块包括多个子模块，其中，第一子模块用于获取原始规划路径和当前位置，所述原始规划路径中包含拥堵路段；
第二子模块用于根据拥堵路段的路段ID在最短树形结构路网地图中查找拥堵路段树形结构，获得拥堵路段的相邻上游路段和相邻下游路段，将拥堵路段的相邻上游路段的拓扑路段作为出发路段，将拥堵路段的相邻下游路段作为结束路段，所述的相邻上游路段和相邻下游路段均属于原始规划路径；
第三子模块用于判断当前的出发路段和当前的结束路段之间是否存在不经过拥堵路段的可达路径，将存在的可达路径保存为候补替换路径，
保留当前的出发路段并将当前的结束路段的相邻下游路段作为当前的结束路段；
第四子模块用于对当前的结束路段进行判断，若当前的结束路段到拥堵路段之间的路径长度小于等于第二路径距离阈值时，则返回执行第三子模块，其中，所述第二路径距离阈值为从拥堵路段出发向下游路段搜索距离的最大上限阈值；
若当前的结束路段到拥堵路段之间的路径长度大于第二路径距离阈值时，则将当前的出发路段中不包含原始轨迹路段的剩余拓扑路段作为当前的出发路段，将拥堵路段的相邻下游路段作为当前的结束路段，返回执行第三子模块，直至当前的出发路段中剩余拓扑路段为空，则将当前的出发路段中包含的原始轨迹路段的相邻上游路段的拓扑路段更新为当前的出发路段，将拥堵路段的相邻下游路段作为当前的结束路段，执行第五子模块；
第五子模块用于判断，若当前的出发路段到当前位置的距离大于等于第一路径距离阈值时，则返回执行第三子模块，其中，所述第一路径距离阈值为出发路段到当前行驶位置之间距离的最小下限阈值；
否则，停止路径搜索并判断，若候补替换路径为空，则继续按照原始规划路径行驶；若候补替换路径不为空，则执行第六子模块；
第六子模块用于获取候补替换路径中的出发路段和结束路段之间路径长度最短的路径，并判断该路径长度最短的路径中是否包含新的拥堵路段，若存在新的拥堵路段，则更新拥堵路段且将更新后的行驶轨迹路径作为原始轨迹路径并重新执行第二子模块；否则将该路径长度最短的路径作为最优替换路径。第六子模块用于获取替换路径的出发路段和结束路段之间路径长度最短的路径，并判断该路径长度最短的路径中是否包含新的拥堵路段，若存在新的拥堵路段，则更新拥堵路段并重新执行第二子模块；否则将该路径长度最短的路径作为最优替换路径。
进一步的，获取最短树形结构路网地图包括如下子模块：
子模块a用于获得所有路段的路段数据，所述的路段数据包括路段ID、路段起点经度坐标、路段起点纬度坐标、路段终点经度坐标、路段终点纬度坐标和路段长度，将所有路段的路段数据根据起点、终点经纬度坐标是否相同进行关联，获得每个路段的拓扑结构；
子模块b用于对每个路段进行最短距离搜索，获得每个路段到其他路段的最短可达路径和最短距离，以每个路段的起点或终点为该路段树形结构的Node节点，以每个路段在最短距离搜索算法的时间长度内的可达路径和最短距离为该路段树形结构的Value值建立树形结构，得到所有路段的树形结构，将所有路段的树形结构作为最短树形结构路网地图。
实施例1
本实施例公开了一种基于实时路况信息的动态路径规划方法，从与拥堵路段相邻的上一个路段的拓扑结构中遍历与该路段起点或终点的相连路段，并将该路段起点或终点的相连路段作为出发路段，与拥堵路段相邻的下一个路段的次路段作为结束路段，寻找一条连通路径。在上述实施例的基础上，还公开了如下技术特征：
获取出发点和目标点之间的原路径为：
51483708242->51483708239->51483700698->51483708176->51483708175->51483705267->51483705268->51483700685->51483700666(51483708175为拥堵路段)
路段51483708176拓扑结构如下图2所示，与51483708176路段的拓扑结构相连的下游51483708177路段为出发路段，与拥堵路段51483708175相邻的下一个路段的次路段51483705268作为结束路段，可以找到一条不经过拥堵路段51483708175的一条连通路径。
51483708242->51483708239->51483700698->51483708176->51483708177->51483708167->51483705268->51483700685->51483700666
上述实施例示意图如图5所示。

Claims (8)

1.基于实时路况信息的动态路径规划方法，其特征在于，用于采用建立好的最短树形结构路网地图，对原始路径中的拥堵路段进行替换并对候补替换路径进行寻优，获得最优替换路径；
所述的最短树形结构路网地图包括各个路段的树形结构，每个路段的树形结构包括路段的拓扑结构以及该路段进行最短距离搜索后每个路段到其他路段的最短可达路径和最短距离；该方法包括如下步骤：
步骤1：获取原始规划路径和当前位置，所述原始规划路径中包含拥堵路段；
步骤2：根据拥堵路段的路段ID在最短树形结构路网地图中查找拥堵路段树形结构，获得拥堵路段的相邻上游路段和相邻下游路段，将拥堵路段的相邻上游路段的拓扑路段作为出发路段，将拥堵路段的相邻下游路段作为结束路段，所述的相邻上游路段和相邻下游路段均属于原始规划路径；
步骤3：判断当前的出发路段和当前的结束路段之间是否存在不经过拥堵路段的可达路径，将存在的可达路径保存为候补替换路径，
保留当前的出发路段并将当前的结束路段的相邻下游路段作为当前的结束路段；
步骤4：对当前的结束路段进行判断，若当前的结束路段到拥堵路段之间的路径长度小于等于第二路径距离阈值时，则返回执行步骤3，其中，所述第二路径距离阈值为从拥堵路段出发向下游路段搜索距离的最大上限阈值；
若当前的结束路段到拥堵路段之间的路径长度大于第二路径距离阈值时，则将当前的出发路段中不包含原始轨迹路段的剩余拓扑路段作为当前的出发路段，将拥堵路段的相邻下游路段作为当前的结束路段，返回执行步骤3，直至当前的出发路段中剩余拓扑路段为空，则将当前的出发路段中包含的原始轨迹路段的相邻上游路段的拓扑路段更新为当前的出发路段，将拥堵路段的相邻下游路段作为当前的结束路段，执行步骤5；
步骤5：若当前的出发路段到当前位置的距离大于等于第一路径距离阈值时，则返回执行步骤3，其中，所述第一路径距离阈值为出发路段到当前行驶位置之间距离的最小下限阈值；
否则，停止路径搜索并判断，若候补替换路径为空，则继续按照原始规划路径行驶；若候补替换路径不为空，则执行步骤6；
步骤6：获取候补替换路径中的出发路段和结束路段之间路径长度最短的路径，并判断该路径长度最短的路径中是否包含新的拥堵路段，若存在新的拥堵路段，则更新拥堵路段且将更新后的行驶轨迹路径作为原始轨迹路径并重新执行步骤2；否则将该路径长度最短的路径作为最优替换路径。
2.如权利要求1所述的基于实时路况信息的动态路径规划方法，其特征在于，获取最短树形结构路网地图包括如下子步骤：
步骤a：获得所有路段的路段数据，所述的路段数据包括路段ID、路段起点经度坐标、路段起点纬度坐标、路段终点经度坐标、路段终点纬度坐标和路段长度，将所有路段的路段数据根据起点、终点经纬度坐标是否相同进行关联，获得每个路段的拓扑结构；
步骤b：对每个路段按照拓扑结构进行最短距离搜索，获得每个路段到其他路段的最短可达路径和最短距离，以每个路段的起点和终点为该路段树形结构的Node节点，以每个路段在最短距离搜索算法的时间长度内的可达路径和最短距离为该路段树形结构的Value值建立树形结构，得到所有路段的树形结构，将所有路段的树形结构作为最短树形结构路网地图。
3.如权利要求1所述的基于实时路况信息的动态路径规划方法，其特征在于，所述的第一路径距离阈值根据最短反应时间和汽车的平均行驶速度确定，所述的第二路径距离阈值根据从当前路段出发到达与其相连的下游方向的最远可达路径之间所需的时间和汽车的平均行驶速度确定。
4.如权利要求3所述的基于实时路况信息的动态路径规划方法，其特征在于，平均行驶速度为50km/s，最短反应时间为40s，从当前路段出发到达与其相连的下游方向的最远可达路径之间所需的时间为2min。
5.基于实时路况信息的动态路径规划系统，其特征在于，用于采用建立好的最短树形结构路网地图，对原始路径中的拥堵路段进行替换并对候补替换路径进行寻优，获得最优替换路径；
该系统包括路段最短树形结构路网地图和替换路径规划模块；
所述的最短树形结构路网地图包括各个路段的树形结构，每个路段的树形结构包括路段的拓扑结构以及该路段进行最短距离搜索后每个路段到其他路段的最短可达路径和最短距离；
所述的替换路径规划模块包括多个子模块，其中，第一子模块用于获取原始规划路径和当前位置，所述原始规划路径中包含拥堵路段；
第二子模块用于根据拥堵路段的路段ID在最短树形结构路网地图中查找拥堵路段树形结构，获得拥堵路段的相邻上游路段和相邻下游路段，将拥堵路段的相邻上游路段的拓扑路段作为出发路段，将拥堵路段的相邻下游路段作为结束路段，所述的相邻上游路段和相邻下游路段均属于原始规划路径；
第三子模块用于判断当前的出发路段和当前的结束路段之间是否存在不经过拥堵路段的可达路径，将存在的可达路径保存为候补替换路径，
保留当前的出发路段并将当前的结束路段的相邻下游路段作为当前的结束路段；
第四子模块用于对当前的结束路段进行判断，若当前的结束路段到拥堵路段之间的路径长度小于等于第二路径距离阈值时，则返回执行第三子模块，其中，所述第二路径距离阈值为从拥堵路段出发向下游路段搜索距离的最大上限阈值；
若当前的结束路段到拥堵路段之间的路径长度大于第二路径距离阈值时，则将当前的出发路段中不包含原始轨迹路段的剩余拓扑路段作为当前的出发路段，将拥堵路段的相邻下游路段作为当前的结束路段，返回执行第三子模块，直至当前的出发路段中剩余拓扑路段为空，则将当前的出发路段中包含的原始轨迹路段的相邻上游路段的拓扑路段更新为当前的出发路段，将拥堵路段的相邻下游路段作为当前的结束路段，执行第五子模块；
第五子模块用于判断，若当前的出发路段到当前位置的距离大于等于第一路径距离阈值时，则返回执行第三子模块，其中，所述第一路径距离阈值为出发路段到当前行驶位置之间距离的最小下限阈值；
否则，停止路径搜索并判断，若候补替换路径为空，则继续按照原始规划路径行驶；若候补替换路径不为空，则执行第六子模块；
第六子模块用于获取候补替换路径中的出发路段和结束路段之间路径长度最短的路径，并判断该路径长度最短的路径中是否包含新的拥堵路段，若存在新的拥堵路段，则更新拥堵路段且将更新后的行驶轨迹路径作为原始轨迹路径并重新执行第二子模块；否则将该路径长度最短的路径作为最优替换路径。第六子模块用于获取替换路径的出发路段和结束路段之间路径长度最短的路径，并判断该路径长度最短的路径中是否包含新的拥堵路段，若存在新的拥堵路段，则更新拥堵路段并重新执行第二子模块；否则将该路径长度最短的路径作为最优替换路径。
6.如权利要求5所述的基于实时路况信息的动态路径规划系统，其特征在于，获取最短树形结构路网地图包括如下子模块：
子模块a用于获得所有路段的路段数据，所述的路段数据包括路段ID、路段起点经度坐标、路段起点纬度坐标、路段终点经度坐标、路段终点纬度坐标和路段长度，将所有路段的路段数据根据起点、终点经纬度坐标是否相同进行关联，获得每个路段的拓扑结构；
子模块b用于对每个路段按照拓扑结构进行最短距离搜索，获得每个路段到其他路段的最短可达路径和最短距离，以每个路段的起点和终点为该路段树形结构的Node节点，以每个路段在最短距离搜索算法的时间长度内的可达路径和最短距离为该路段树形结构的Value值建立树形结构，得到所有路段的树形结构，将所有路段的树形结构作为最短树形结构路网地图。
7.如权利要求5所述的基于实时路况信息的动态路径规划系统，其特征在于，所述的第一路径距离阈值根据最短反应时间和汽车的平均行驶速度确定，所述的第二路径距离阈值根据从当前路段出发到达与其相连的下游方向的最远可达路径之间所需的时间和汽车的平均行驶速度确定。
8.如权利要求7所述的基于实时路况信息的动态路径规划系统，其特征在于，平均行驶速度为50km/s，最短反应时间为40s，从当前路段出发到达与其相连的下游方向的最远可达路径之间所需的时间为2min。
CN202110479473.4A 2021-04-30 2021-04-30 基于实时路况信息的动态路径规划方法及系统 Active CN113295177B (zh)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN202110479473.4A CN113295177B (zh) 2021-04-30 2021-04-30 基于实时路况信息的动态路径规划方法及系统

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN202110479473.4A CN113295177B (zh) 2021-04-30 2021-04-30 基于实时路况信息的动态路径规划方法及系统

Publications (2)

Publication Number Publication Date
CN113295177A true CN113295177A (zh) 2021-08-24
CN113295177B CN113295177B (zh) 2022-08-19

Family

ID=77320674

Family Applications (1)

Application Number Title Priority Date Filing Date
CN202110479473.4A Active CN113295177B (zh) 2021-04-30 2021-04-30 基于实时路况信息的动态路径规划方法及系统

Country Status (1)

Country Link
CN (1) CN113295177B (zh)

Cited By (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN114137973A (zh) * 2021-11-26 2022-03-04 湖北亿纬动力有限公司 一种路径规划的方法、装置、设备及存储介质
CN114353797A (zh) * 2021-12-13 2022-04-15 哈尔滨工业大学芜湖机器人产业技术研究院 一种实时路径规划方法及agv
CN114964284A (zh) * 2022-04-22 2022-08-30 合众新能源汽车有限公司 一种车辆路径的规划方法及装置

Citations (13)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20040078139A1 (en) * 2001-02-26 2004-04-22 Kornhauser Alain L. Thin-client navigation and route guidance system
CN1670482A (zh) * 2004-03-18 2005-09-21 株式会社查纳位资讯情报 导航装置
CN102169637A (zh) * 2010-12-08 2011-08-31 北京大学 面向城市交通的动态路径诱导方法
CN102542793A (zh) * 2012-01-11 2012-07-04 东南大学 一种交叉口群过饱和交通态势主动控制方法
US20130282272A1 (en) * 2012-04-18 2013-10-24 Harman Becker Automotive Systems Gmbh System for estimating a cruising range of a vehicle
US20140244159A1 (en) * 2004-06-30 2014-08-28 Navteq North America, Llc Method of Operating a Navigation System Using Images
CN105810001A (zh) * 2016-05-19 2016-07-27 东华大学 一种基于车载自组网的实时动态路径规划方法
CN107798079A (zh) * 2017-09-30 2018-03-13 北京泓达九通科技发展有限公司 基于车辆轨迹数据的路段拼接方法及系统
CN108562301A (zh) * 2018-05-21 2018-09-21 北京石油化工学院 一种行驶路径的规划方法及装置
CN110268227A (zh) * 2017-02-17 2019-09-20 爱信艾达株式会社 行驶辅助装置和计算机程序
US20190316925A1 (en) * 2018-04-17 2019-10-17 Here Global B.V. Method, apparatus and computer program product for determining likelihood of a route
CN110579221A (zh) * 2019-09-30 2019-12-17 重庆元韩汽车技术设计研究院有限公司 用于远程控制的轨迹规划方法及系统
CN111982141A (zh) * 2020-07-31 2020-11-24 长安大学 一种面向低频车辆轨迹数据进行路径推断的方法、设备及存储介质

Patent Citations (13)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20040078139A1 (en) * 2001-02-26 2004-04-22 Kornhauser Alain L. Thin-client navigation and route guidance system
CN1670482A (zh) * 2004-03-18 2005-09-21 株式会社查纳位资讯情报 导航装置
US20140244159A1 (en) * 2004-06-30 2014-08-28 Navteq North America, Llc Method of Operating a Navigation System Using Images
CN102169637A (zh) * 2010-12-08 2011-08-31 北京大学 面向城市交通的动态路径诱导方法
CN102542793A (zh) * 2012-01-11 2012-07-04 东南大学 一种交叉口群过饱和交通态势主动控制方法
US20130282272A1 (en) * 2012-04-18 2013-10-24 Harman Becker Automotive Systems Gmbh System for estimating a cruising range of a vehicle
CN105810001A (zh) * 2016-05-19 2016-07-27 东华大学 一种基于车载自组网的实时动态路径规划方法
CN110268227A (zh) * 2017-02-17 2019-09-20 爱信艾达株式会社 行驶辅助装置和计算机程序
CN107798079A (zh) * 2017-09-30 2018-03-13 北京泓达九通科技发展有限公司 基于车辆轨迹数据的路段拼接方法及系统
US20190316925A1 (en) * 2018-04-17 2019-10-17 Here Global B.V. Method, apparatus and computer program product for determining likelihood of a route
CN108562301A (zh) * 2018-05-21 2018-09-21 北京石油化工学院 一种行驶路径的规划方法及装置
CN110579221A (zh) * 2019-09-30 2019-12-17 重庆元韩汽车技术设计研究院有限公司 用于远程控制的轨迹规划方法及系统
CN111982141A (zh) * 2020-07-31 2020-11-24 长安大学 一种面向低频车辆轨迹数据进行路径推断的方法、设备及存储介质

Non-Patent Citations (3)

* Cited by examiner, † Cited by third party
Title
LEI ZUO; NAN ZHANG; YIGANG HE; TINGTING ZHOU: "Research on Dynamic Route Guidance and Navigation System Based on Multi Information Feedback", 《2017 INTERNATIONAL CONFERENCE ON SENSING, DIAGNOSTICS, PROGNOSTICS, AND CONTROL》 *
王润泽，王亮，刘涛，栗斌: "考虑实时路况反馈的动态路径规划算法研究", 《测绘科学》 *
龙科军等: "路网信息不完备条件下的动态最短路搜索", 《计算机应用》 *

Cited By (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN114137973A (zh) * 2021-11-26 2022-03-04 湖北亿纬动力有限公司 一种路径规划的方法、装置、设备及存储介质
CN114137973B (zh) * 2021-11-26 2024-05-07 湖北亿纬动力有限公司 一种路径规划的方法、装置、设备及存储介质
CN114353797A (zh) * 2021-12-13 2022-04-15 哈尔滨工业大学芜湖机器人产业技术研究院 一种实时路径规划方法及agv
CN114964284A (zh) * 2022-04-22 2022-08-30 合众新能源汽车有限公司 一种车辆路径的规划方法及装置

Also Published As

Publication number Publication date
CN113295177B (zh) 2022-08-19

Similar Documents

Publication Publication Date Title
Jagadeesh et al. Heuristic techniques for accelerating hierarchical routing on road networks
CN101694749B (zh) 一种路径推测方法及装置
CN106092111B (zh) 一种车辆路径动态规划方法、服务器及导航系统
CN113295177A (zh) 基于实时路况信息的动态路径规划方法及系统
JP4673530B2 (ja) 出発地から目的地までのルート検出方法およびルート検出装置
US20180149488A1 (en) Guide route setting apparatus and guide route setting method
CN108827335B (zh) 一种基于单向搜索模型的最短路径规划方法
CN110530393A (zh) 车道级路径规划方法、装置、电子设备及可读存储介质
CN109000676B (zh) 一种vanet环境下结合预测信息的路径规划方法
CN108444486B (zh) 一种导航路线排序方法和装置
CN104931063A (zh) 路径规划方法
CN111982141B (zh) 一种面向低频车辆轨迹数据进行路径推断的方法、设备及存储介质
CN103344248B (zh) 一种车辆导航系统的最佳路径计算方法
CN111272187B (zh) 基于改进的a*算法的最优行驶路径规划方法及系统
CN111337047B (zh) 基于多任务点约束的非结构化道路宏观路径规划方法
CN103376116B (zh) 车辆导航中的风景路线规划
CN111879329B (zh) 基于a*算法的定制公交可通行最短路径计算方法
CN109238270A (zh) 基于改进的a星算法的智能导航方法
CN118230581A (zh) 车道级路况的获取方法、装置、设备及车端导航系统
CN113465612B (zh) 一种基于双层索引的并行路径规划方法及系统
CN104596527A (zh) 一种划分各级引导道路和细街路的方法
CN112464517B (zh) 基于已有道路数据的仿真车寻找最短路径的方法
CN107449426B (zh) 导航逻辑方法及其室内ar导航系统
CN114137973A (zh) 一种路径规划的方法、装置、设备及存储介质
CN112185149A (zh) 基于城市路网数据的路径规划方法及系统

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant