一种基于路网跃迁的高效路径搜索算法

《一种基于路网跃迁的高效路径搜索算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、一种基于路网跃迁的高效路径搜索算法摘要：针对移动导航设备内存小、运算能力相对弱的特点，以分级分幅路网模型为基础，设计了一种新的以“路网跃迁”为核心思想的高效最优路径搜索算法，并应用到实际产品中。实践表明，该搜索算法具有计算速度快、消耗内存低、路线质量总体接近最优等优点。关键词：分级；分幅；路网跃迁；路径搜索算法中图分类号：TP311文献标识码：A文章编号：1009-3044（2015）30-0073-02AnEfficientRouteSearchAlgorithmBasedonRoadTransitionWUJuan，GAOZheng-d

2、ong（SCTV，Shucheng231300，China）Abstract：Correspondingtotheshortageofhavinglessmemoryandweakercomputecapabilitywithinmobilenavigationdevice，anewefficientbestroutesearchalgorithmbasedonroadclassificationandmapsheet，whichtakes“roadtransition”askeypoint，isimplementedandhasbeing

3、appliedtotherealproducts.Practicehasshownthatithasadvantageoffasterspeed，lessmemoryoccupation，andperfectroutequality，etc.Keywords：roadclassification；mapsheet；roadtransition；routesearchalgorithm61概述为了适应车载设备内存低、运算能力相对较弱的特点，我们对路网进行了分级和分幅处理。分级指的是将路网根据道路属性分成多个等级，如将地区内路网分成三级（0级，

4、1级，2级），将全国路网分成两个等级（3级、4级）；分幅指的是将整个路网网格化，每个网格覆盖路网一定的区域，如10公里10公里区域范围。分级的好处是允许搜索过程从低级路网跃迁到高级路网，加快搜索速度；分幅的好处是降低搜索的节点空间，降低内存占用率。关于分级分幅路网数据组织格式的详细介绍可参阅文献[1]。在分级分幅路网数据做支撑的基础上，我们改进了经典的Dijkstra算法，引入路网跃迁机制，设计了高效的双向启发式最优路径搜索算法。经典的Dijkstra算法已产生许多变体[2-3]，总的来说，现有最优路径搜索算法基于的均不是分级和分幅的地图数

5、据，因此本算法首先在基础数据层次上对时空效率的提高提供了有力保证。2算法描述为了保证快速的搜索过程和良好的路线质量，我们对算法做了多方面的改进，主要有：利用四叉堆进行节点排序、双向搜索、优化的代价函数、路网跃迁以及路网图幅化。通过将地区内路网和全国路网进行分级分幅化处理，在所有类型路网上都支持路网跃迁操作。以下详细描述算法的搜索过程，算法原理示意图如图1所示：搜索算法用到三个地图数据：发源地区路网、目的地区路网、全国路网。根据出发点和目的点所在地区位置，将搜索算法分为以下三类：61）地区内搜索：出发点和目的点都在同一地区内，则搜索仅在本地区

6、范围内进行，不需要搜索全国路网，搜索过程相对最简单。2）相邻地区搜索：出发点和目的点不在同一地区，但地区内搜索到达的边界点存在重合，即一个地区的地区边界点同时也是另一个地区的地区边界点，此时也不需要搜索全国路网。3）跨地区搜索：当出发点和目的点既不在同一地区，也不发生两个地区边界点重合时，就必须借助全国路网搜索两个地区之外的路线。以下给出跨地区算法描述，地区内搜索和相邻地区搜索是跨地区搜索的特例情况，不再详述。1）由发源点经纬度找到发源最近路段；2）由发源最近路段选择某个端点作为出发点；3）由目的点经纬度找到目的最近路段；4）由目的最近路段

7、选择某个端点作为到达点；5）以到达点为目的点，从发源地区正向搜索到一条到达节点是地区边界点S’的路线L1；6）以出发点为出发点，从目的地区逆向搜索到一条前驱节点是地区边界点D’的路段L2；7）将源地区边界点S’向全国路网投影，找到其在全国路网上的投影节点Sp；8）将目的地区边界点D’向全国路网投影，找到其在全国路网上的投影节点Dp；9）设置投影节点Sp的所有前趋节点为回避点，防止起始回头路；10）设置投影节点Dp的所有后继节点为回避点，防止到达回头路；611）在全国路网上，双向搜索一条路线L3；12）合并总路线：L=L1+L3+L2；13）

8、剔除重复路段，组成最终路线。跃迁过程如图2所示，搜索起始阶段，搜索过程在等级最低的路网中进行，随着搜索的进行，不断地有新的节点加入，其中必定包括跃点（此特性由数据源保证）。当跃点