本项目公开了一种基于路链的快速最短路径规划方法,针对现有A*算法中open表中所含节点多、耗时多和规划出来的路径转弯次数多的问题进行改进。其步骤包括:1)根据城市道路网生成节点拓扑表K;2)根据节点拓扑表K生成路链拓扑表U;3)创建open表和closed表;4)初始化open表,并根据路链拓扑表U维护open表和close表,划分出行驶的最短路径。本发明减少了路径规划所需处理的数据单元,降低了路径规划所需的时间,保持了道路的整体性和视觉上的连贯性,降低了输出路径中转弯的次数,可用于车辆或者步行导航。
1.基于路链的快速最短路径规划方法,其特征在于,包括以下步骤:
1)根据道路网生成节点拓扑表K,该节点拓扑表K包含节点的相邻节点、节点与相邻节点之间弧段的长度;
2)创建一张路链拓扑表U,用以保存路链的拓扑关系,该路链拓扑表U包含路链的相邻路链、路链与相邻路链的交点、路链所包含的节点以及相邻节点之间的距离,所述相邻路链,是指与路链有且仅有一个交点的路链;
3)通过节点拓扑表K中每一对相邻的节点生成路链,保存到路链拓扑表U,并将路链拓扑表U中以相同节点为端点且夹角大于120度的两条路链合并成一条新的路链,若多条路链与同一条路链夹角都大于120度,则选取夹角最大的两条路链组合成一条路链;
4)根据路链拓扑表U进行路径规划:
具体实施方式的场景示意图中,其道路网由18个节点组成,即节点n1至n18,其中任意一对相邻节点之间的距离为1,路径规划的初始节点为节点n1,路径规划的目标节点为节点n18
康等人在其发表的论文“基于路网拓扑层次性表达的驾车路径规划方法”(《地球信息科学学报》2015年9月第17卷)中提出一种将路链应用于路径规划中的方法。该方法通过构建基于路链的对偶图来获取路链的拓扑结构指标,并将其赋予组成该路链的路段。综合考虑路段长度、路网拓扑结构特征及道路交通状态3个因素通过Dijkstra算法进行路径规划。该方法存在的不足之处是:首先,该方案只是将路链转换成路段的一个指标,用来反映路段的重要程度,但仍旧基于“节点-路段”的拓扑网络关系进行路径规划,没有考虑到基于“节点-路段”的拓扑网络关系会将每一条自然道路人为分割为若干条路段,进而导致算法处理数据单元较多,其次,该方法采用Dijkstra算法进行路径规划,并没有采用时间复杂度更低的A*算法。
重庆邮电大学在其申请的专利“基于二叉堆节点排序的A星寻路方法及系统”(公开号CN 104268420A,申请号CN 201410531309.3)中公开了一种基于二叉堆节点排序的A*寻路方法及系统。该方法在普通A*算法中引入堆排序,以此大幅提高A*算法执行效率。该方法虽然克服了传统A*算法需要频繁维护open和close表。但是,open表中元素过多,单次维护open表的时间较长,使得路径规划整体所用时间较长。
具有如下创新点:
1.本发明由于将节点拓扑表转换成路链拓扑表,依据路链拓扑表进行路径规划,减少了路径规划所需处理的数据单元,从而降低了路径规划所需的时间。
2.本发明的输出路径由于通过路链拼接而成,保持了道路的整体性和视觉上的连贯性,从而降低了输出路径中转弯的次数。
如您想进一步了解本项目的详细信息,可以直接拨打大市场服务部了解详情或者可在下方填写相关资讯信息及您的联系方式,我们会有专家对您的咨询进行回复。