资源描述：
《基于层次策略的路径规划算法对比研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、基于层次策略的路径规划算法对比研究蔡文学1,郑烟武2,钟慧玲3石永强3,赵娜°,周兴°(华南理工大学，广东省广州市510006)摘要：层次策略是路径规划算法中常用的优化策略。为比较路径规划中某丁•层次策略的分层算法的汁算效率和规划结果的合理性，选取垄于预计算的分层算法和基于道路等级的分层分区算法这两类典型的分层路径规划算法,通过对两类算法基木原理的分析，并引入新分区算法和“虚拟边”等方法改进现冇基于道路等级的分层分区算法以适应实际路网下的路径规划。选取广东省路网数据进行大规模测试，通过寻找“最短路”和“最快路”进行算法效率和路径规划结果的比较分析。测试结果
2、表明改进的基于道路等级的分层分区算法计算效率更高，规划结果更符合出行偏好。关键词：路径规划算法；层次策略；实际路网；最短路；最快路中图分类号：U495引言路径规划是智能交通中交通诱导系统提供导航功能的前提条件，是帮助出行者在出行前或出行中规划行驶路径的过程。计算道路网络中两点之间的路径规划问题可以归结为图论屮求解带权有向图的最短路径问题。解决路径规划问题的算法主要冇Dijkstra算法、Floyd算法等，以及为车辆导航改进的K则最短路算法等⑴。其中，Dijkstra算法是H前公认的求解放短问题的经典算法Z一。但由于算法在最坏的情况下其时间复杂度为0(用)1
3、21,其中n为结点个数。启发式搜索算法，如A*算法，山于不断向目标方向靠近，可以大幅度缩减对网络图的搜索空间从而冇可能节省搜索时间⑶。但在人规模数据的查询中，这些某本的计算算法效率仍无法满足实际应用的要求。因此，产生两大类算法的优化策略：压缩搜索空间的策略和改进算法及实现方式的策略。压缩搜索空间的策峪包括限制搜索范围和层次策略；改进算法及实现方式的策略包括启发式策略、数据结构优化、双向搜索、并行计算等策略l4-5
4、o其中层次策略既可以达到压缩搜索空间的目的，同时也是一种启发式搜索策略，是常用的一种优化策略总叽基于层次策略的路径规划算法的思想來源于地理学的空
5、间层次推理理论和图论的子图划分理论⑺。利用层次策略，通过对路网分层，由于分层可以将人规模的路网进行分别存储，便于对数据进行操作；高层路网可以是底层路网的简化或连接着底层的路网，且数据量远小于底层路网。对于网络细节的关心是分层次逐步深化的，当层次过渡时可以过滤掉无需关心的细节⑷，从而减少搜索量，提高搜索效率。目前基于层次策略的算法可以分为以下两类：第1类是利用空间来换取时间，通过预计算绘短路，并进行分层，力求得到粘确解，文献［8］等提出的基于预计算最短路的分层路径规划算法(HighwayHierarchiesalgorithm,HHs算法)就属于该类；第2类
6、算法基于道路等级进行分层，通过空间层次推理來实时计算得到近似解，以文献［4］和文献［9］提出的分层分区路径规划算法(HierarchicalandPartitionedA-staralgorithm,HPA算法)为代表。该类算法考虑实际道路网络中的道路具冇不同的等级特性，同等距离条件下高筹级道路具冇较强的通行能力(叩通行时间更短)，以及多数駕驶员希望行车过程中能尽可能地走高等级道路，避免在高等级道路和低等级道路间频繁地进行行车切换等问题，4J0,o1算法分析论文采用图论中的“图”來衣示路网，路网模型衣示为G(U,E),其中V={v,l/=l,...,vJ为
7、节点的集合，表示道路的交义口或路的终点，存储节点连接边等信息；而E={eiiviivjeV}为道路边，表示两节点之间的路段，存储路段长度、通行时间、道路等级等信息。为了对比两类基于层次策略的路径规划算法的性能，论文先分析两类某于层次策略的算法的慕本思想，即文献［8］提出的HHs算法和文献
8、9］提出的HPA算法。同时对HPA算法存在的问题进行改进，提出改进分层分区路径规划算法(AdaptiveHierarchicalandPartitionedA-staralgorithm»AHPA算法)。1.1HHs算法HHs算法由Sanders等(2005)提岀，其思
9、想是通过对大规模路网进行预计算，然后提収分层处理，使上一层的路网成为下一层路网的子集，在此基础上开发路径搜索算法,通过不断的转换搜索层次，从最底层搜索到最高层，最后在放高层完成搜索，以减少搜索算法的搜索空间，以此來提高搜索的效率⑻。算法的实现包含两个过程：预处理过程和分层搜索过程。预处理过程的目的是将原始的平面路网分成多层路网，首先对每一个点进行dijsktra搜索找到该点的一个“半径”值/?(即在算法运行过程中第H个被标为P标号的点到起始点的距离值，这里的H为可设参数)，再计算路网中任意点对(S,T)之间的:®短路，在该最短路上，所有到S的距离小于S的半
10、径的边都被去除，所有到T的距离小于T的半径的边都被去除，剩下的边作
