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

武娟+高正东

摘要：针对移动导航设备内存小、运算能力相对弱的特点，以分级分幅路网模型为基础，设计了一种新的以“路网跃迁”为核心思想的高效最优路径搜索算法，并应用到实际产品中。实践表明，该搜索算法具有计算速度快、消耗内存低、路线质量总体接近最优等优点。

关键词：分级；分幅；路网跃迁；路径搜索算法

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2015）30-0073-02

An Efficient Route Search Algorithm Based on Road Transition

WU Juan， GAO Zheng-dong

（SCTV， Shucheng 231300， China）

Abstract： Corresponding to the shortage of having less memory and weaker compute capability within mobile navigation device， a new efficient best route search algorithm based on road classification and map sheet， which takes “road transition” as key point， is implemented and has being applied to the real products. Practice has shown that it has advantage of faster speed， less memory occupation， and perfect route quality， etc.

Key words： road classification； map sheet； road transition； route search algorithm

1 概述

为了适应车载设备内存低、运算能力相对较弱的特点，我们对路网进行了分级和分幅处理。分级指的是将路网根据道路属性分成多个等级，如将地区内路网分成三级（0级，1级，2级），将全国路网分成两个等级（3级、4级）；分幅指的是将整个路网网格化，每个网格覆盖路网一定的区域，如10公里*10公里区域范围。分级的好处是允许搜索过程从低级路网跃迁到高级路网，加快搜索速度；分幅的好处是降低搜索的节点空间，降低内存占用率。关于分级分幅路网数据组织格式的详细介绍可参阅文献[1]。

在分级分幅路网数据做支撑的基础上，我们改进了经典的Dijkstra算法，引入路网跃迁机制，设计了高效的双向启发式最优路径搜索算法。经典的Dijkstra算法已产生许多变体[2-3]，总的来说，现有最优路径搜索算法基于的均不是分级和分幅的地图数据，因此本算法首先在基础数据层次上对时空效率的提高提供了有力保证。

2 算法描述

为了保证快速的搜索过程和良好的路线质量，我们对算法做了多方面的改进，主要有：利用四叉堆进行节点排序、双向搜索、优化的代价函数、路网跃迁以及路网图幅化。通过将地区内路网和全国路网进行分级分幅化处理，在所有类型路网上都支持路网跃迁操作。以下详细描述算法的搜索过程，算法原理示意图如图1所示：

搜索算法用到三个地图数据：发源地区路网、目的地区路网、全国路网。根据出发点和目的点所在地区位置，将搜索算法分为以下三类：

1）地区内搜索：出发点和目的点都在同一地区内，则搜索仅在本地区范围内进行，不需要搜索全国路网，搜索过程相对最简单。

2） 相邻地区搜索：出发点和目的点不在同一地区，但地区内搜索到达的边界点存在重合，即一个地区的地区边界点同时也是另一个地区的地区边界点，此时也不需要搜索全国路网。

3） 跨地区搜索：当出发点和目的点既不在同一地区，也不发生两个地区边界点重合时，就必须借助全国路网搜索两个地区之外的路线。

以下给出跨地区算法描述，地区内搜索和相邻地区搜索是跨地区搜索的特例情况，不再详述。

1） 由发源点经纬度找到发源最近路段；

2） 由发源最近路段选择某个端点作为出发点；

3） 由目的点经纬度找到目的最近路段；

4） 由目的最近路段选择某个端点作为到达点；

5） 以到达点为目的点，从发源地区正向搜索到一条到达节点是地区边界点S的路线L1；

6） 以出发点为出发点，从目的地区逆向搜索到一条前驱节点是地区边界点D的路段L2；

7） 将源地区边界点S向全国路网投影，找到其在全国路网上的投影节点 Sp；

8） 将目的地区边界点D向全国路网投影，找到其在全国路网上的投影节点Dp；

9） 设置投影节点Sp的所有前趋节点为回避点，防止起始回头路；

10） 设置投影节点Dp的所有后继节点为回避点，防止到达回头路；

11） 在全国路网上，双向搜索一条路线L3；

12） 合并总路线：L = L1 + L3 + L2；

13） 剔除重复路段，组成最终路线。

跃迁过程如图2所示，搜索起始阶段，搜索过程在等级最低的路网中进行，随着搜索的进行，不断地有新的节点加入，其中必定包括跃点（此特性由数据源保证）。当跃点成为最小代价节点从OPEN表弹出时，按照跃迁条件判断其是否符合跃迁条件，如符合则记录跃点在高等级路网上的投影点，退出当前等级路网，并载入允许跃入的最大等级路网继续进行搜索。

3 几个问题

3.1 尽量走高等级路

由于实际路网中，等级相同的道路，往往路况却相差很大，因此，在实际应用中，为了有更好的通行质量，在容许的路线长度范围内，客户常常要求尽量多走高等级的道路。为此我们设计了新的启发函数，核心思想是以高等级路网所占比例作为启发条件。

对于某个节点n，其总代价函数为：

f（n） = W（g）G（n） + W（h）H（n） – n * R（n）

其中，f：节点总代价；G：实际代价，为实际已走路线长度；H：估计代价，为当前点到目的点的直线距离；R：已经过的高等级路段长度；n：高等级路段比例调整因子；

需要说明的是，引入高等级路网比例启发因子后，总代价函数f（n）仍满足完备性要求。

通过合理地改变调整因子n的值，可得到不同质量的搜索路线。n越大，路线中的高等级道路所占比例越大，通行性越好。但n也不可过大，否则会容易出现为了尽量走高速而避开距离短但等级较低的“过度绕路”的现象。据实际经验，n通常取0.2～0.6较合适。

3.2 跃迁时机

为了解决路网跃迁可能带来的走回头路、找不到路等现象，跃迁点的选择必须符合如下三个条件：

1）已经过一定距离的高等级路段，且跃迁点在高等级路段；

2）无转向限制约束；

3）当前节点所在路网等级小于最大允许跃迁等级；

同时为了最大程度提高路径计算效率，取节点最大跃迁等级跃迁。

3.3 实验和性能分析

将搜索算法移植到PC上，在实际路网上进行运算，记录每次搜索载入的图幅数、运算时间和生成路线，并将路线导入到MapInfo中人工评判路线质量，如图3所示。

表1为真实路网下跃迁与非跃迁对搜索性能的比较，其中地区内搜索时节点表示为图幅号和节点号，跨地区搜索时节点表示为经纬度。统计分析表明：

1） 在较近的距离范围内，跃迁与非跃迁两种搜索算法的效率大致相等，因为不需要跃迁到高等级路网。分级算法的效率偶尔还略微下降，这是由于增加了跃迁点判断和处理的开销。

2） 当搜索距离较远，需跨越多个图幅时，分级算法体现出了其优越性。表现在两个方面：

① 搜索的效率更高。由于可以跃迁到更高等级路网，需载入的0级路网图幅数量大大减少，且更高等级路网的搜索空间较小，因而搜索的时空开销大大降低。而对于跨地区大范围搜索，性能提升最为明显，通常跃迁时载入的图幅数目要比没有跃迁时载入的图幅数目少50%以上，效率提高1倍以上。

② 搜索的路线可能更佳。由于高级路网中的路段具有更佳的通行特性，因而分级算法有可能得到具有更佳通行质量的搜索路线。

4 结论

车载导航设备内存小、CPU运算速度较低，因此必须设计高效的路网存储模型和路线搜索，本文在自主研发的分级分幅路网模型的基础上，开发了一种基于路网跃迁高效的最优路径搜索算法，详细描述了算法的基本原理和几个关键问题点的处理。统计分析表明，该算法计算速度快、消耗内存低，且得到的路线总体质量接近最优，具有良好的实用性。

参考文献：

[1] 胥锐. 车载导航电子地图的路网模型[J]. 电脑知识与技术， 2008（25）.

[2] 严寒冰，刘迎春. 基于GIS的城市道路网最短路径算法探讨[J]. 计算机学报，2000，23（2）：210.

[3] 唐文武，施晓东，朱大奎. GIS中使用改进的Dijkstra算法实现最短路径的计算[J]. 中国图像图形学报，2000，5A（12）：1019.