基于分层路网的路径规划算法

开篇：润墨网以专业的文秘视角，为您筛选了一篇基于分层路网的路径规划算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要：为了提高路径规划的效率，提出了一种基于分层路网的二叉堆管理开启列表启发搜索算法。首先根据路网分级特点的存在，建立分层地图数据库，然后以启发式A*算法为主搜索方式，结合优先队列二叉堆来管理开启列表，完成路径规划。通过实验对比不同路径规划算法的平均耗时显示：启发式A*算法的效率是盲目式Dijkstra算法的4倍左右，同时在算法中引入二叉堆至少节省5%的规划时间。分层策略使快速路段所占比例达到90%以上，且将路径规划耗时控制在3s以内。实现结果表明，所提算法具有很高的运行效率，同时能满足驾驶者多走快速路段的行车心理。

关键词：分层路网；拓扑结构提取；路径规划；A算法；二叉堆

0引言

路径规划是车载导航系统最重要的功能之一[1]。根据图论中最短路径理论，不管是最短路径规划、最短时间规划还是最低消费规划，都可以通过赋予图中的边以相应的权值来满足用户的不同需求。

通常情况下，路径搜索可以分为平面搜索和分层搜索两大类。平面搜索算法中最经典的是20世纪60年代初期由Dijkstra提出的Dijkstra算法，非常适合在带权有向图中解决最短路径问题。但是该算法的时间复杂度为O（n2），效率比较低，因此在实际应用时受到了很大的限制。后来许多学者在存储结构和排序算法上对Dijkstra算法进行了改进[2-3]，通常改进算法的时间复杂度与节点数成正比，如O（mlbn）或O（m+nlbn）[4]。也有学者通过引入启发函数的方式进行改进，启发式搜索以1968年Hart等提出的A*算法为代表，现在仍被广泛应用，但这些改进算法的效率会随节点数的增加而急剧下降。此外，平面搜索算法计算出的“最短”路径并不一定是“最优”路径，最短路径中可能存在大量的窄小拥挤的小巷，而最优路径要尽可能多地包括主干道等快速路段[5]，这就有了分层思想。文献[6]首先提出了层次空间的推理过程，文献[7]又将层次空间推理法则引入到行车最优路径搜索中，但这两篇文献均没有给出具体的路网层次拓扑结构的表达方法[8]。有代表性的分层算法有最近E节点法[9]和最佳E节点法[10]，其中最近E节点法简单但准确率不高，最佳E节点法能够得到最优解，但效率低[11]。

本文试图设计一种实用的分层路径规划算法。首先建立分层路网的拓扑结构，然后从搜索空间、搜索策略和数据结构三个方面进行研究，采用启发式的A*算法作为主搜索方式，引入优先队列二叉堆作为数据存储结构，最后通过实验验证每项措施的改善效果。

1分层路网拓扑结构提取

为完成最优路径规划，首先应构建路网间的拓扑结构。由于道路普遍存在的分级特点，以及驾驶者出行习惯走高级路段的心理，可以对路网进行分层处理。对于一个城市合理的层数是两层[12]，常见的分层模型有两种模型[13]，分别如图1和图2所示。

以上两个模型的高层路网都是低层路网的真子集。模型一的特点是高层路网中保留高、低层路网间的交叉口点，不需重建，但抽象程度低。而模型二只保留高层路网自身的交叉口点，这将急剧缩减高层路网的数据规模，有利于降低路径规划算法的时间复杂度。本文将哈尔滨市区MapInfo格式电子地图分为两层：首先合并“国道、省道、县道、高速、高架引桥”等快速路段图层，作为高层路网，并保留在需要时可以将部分低层路网中的道路扩充到高层路网中的能力，以保证高层网络的连通性。然后再将高层路网作为低层路网的子集，继续合并“市区道路、市区杂路”图层。同时添加道路等级，行车方向等重要的属性信息，并根据模型二提取道路的拓扑结构。