基于改进A*算法的高速公路互联网地图最短路径搜索研究

聂易彬， 谭明军， 刘 刚， 马 璐

(1.招商局公路网络科技控股股份有限公司， 北京 100022； 2.招商局重庆交通科研设计院有限公司， 重庆 400067)

国内外学者对最短路径问题进行了大量研究，产生了许多经典算法，如Dijkstra算法[1]、Floyd算法[2]、Johnson算法[3]、A*算法[4]、D*算法[5]等，但其往往耗时较长，难以满足高速公路静态网络的时效性要求。A*算法是一种静态路网中求解最短路径最有效的直接搜索方法[6]，国内众多学者进行了研究，但主要集中在离线地图的最短路径搜索上[7-14]。鉴于此，本文通过高德地图自带的API开发功能，创建了高速公路互联网地图。在传统A*算法的基础上，结合高速公路互联网地图的特点，对传统A*算法中的网络节点、数据库、启发式函数进行了改进，并通过重庆高速公路互联网地图实例对改进A*算法进行了应用，验证了该算法的可行性和高效性。本文提出的改进A*算法在确保能搜索到最短路径的前提下，可大大提高搜索的效率，可应用于大区域高速公路互联网地图的最短路径搜索。

1 A*算法

1.1 基本原理

A*算法是一种启发式搜索算法，常被用来解决静态网络中的最短路径问题。A*算法的估价函数如下：

f(n)=g(n)+h(n)

(1)

式中：f(n)是从初始节点经由任意节点n到目标节点的估价函数；g(n)是从初始节点到节点n的实际代价；h(n)为启发式函数，表示节点n到目标节点的最优路径估计代价。

当h(n)比实际代价小或相等时，A*算法确定能找到一条最短路径。

1.2 算法流程

A*算法的实现流程[15]如下：

1) 建立2个列表，分别命名为开放列表和关闭列表，把当前节点周围可到达的节点加入到开放列表中，已访问过的节点加入到关闭列表中。

2) 当从当前节点开始搜索到下一个节点时，均是从开放列表中进行比较f值的大小，把f值最小的节点作为下一步搜索的起点。

3) 所有当前节点可到达的节点再次加入到开放列表中，重新比较f值，并根据f值的大小按升序进行排列队列。在搜索过程中，使用广度优先算法依次选取队列的首元素，计算可能子节点的g、h和f值，直到找到目标节点或虽然没有找到目标节点但开放列表已为空时，算法结束。

2 改进A*算法

2.1 互联网地图创建

2.1.1 网络数据结构

一个路段由多个相邻坐标点数组构成，相邻坐标点的通行规则有3种，根据路段的方向属性direction值加以判断。判断准则如下：

1) 如果路段direction=0，表示首节点至尾节点之间可双向通行。

2) 如果路段direction=1，表示首节点至尾节点之间可单向通行。

3) 如果路段direction=-1，表示尾节点至首节点之间可单向通行。

考虑到网络路段可能存在3种通行方向，如果逐一去判断路段的方向属性，会造成路径搜索时间较长。为减少路径搜索时间，本文对方向属性direction=-1和direction=0的路段统一作如下处理：

1) 将direction=-1的路段坐标进行坐标反转，即direction=-1的路段m=[(x1，y1),(x2，y2)，…，(xn-1，yn-1)，(xn，yn)]反转为direction=1的路段m′=[(xn，yn),(xn-1，yn-1)，…，(x2，y2)，(x1，y1)]。

2) 将direction=0的路段克隆一份，并对其进行坐标反转处理，即direction=0的路段m=[(x1，y1),(x2，y2)，…，(xn-1，yn-1)，(xn，yn)]变成了路段m=[(x1，y1),(x2，y2)，…，(xn-1，yn-1)，(xn，yn)]和路段m′=[(xn，yn),(xn-1，yn-1)，…，(x2，y2)，(x1，y1)]。

经过上述处理后，高速公路网络中所有路段的通行方向均为从首节点至尾节点的单向通行。

2.1.2 互联网地图创建

互联网地图的创建步骤如下：

1) 坐标转换。通过互联网地图API坐标工具，将高速公路网络节点的GPS坐标转换成火星坐标。

2) 绘制路网。根据网络节点的火星坐标，通过互联网地图API画线工具绘制路网。

3) 存储路网数据库。存储网络各路段属性列表和节点属性列表，路段属性列表包含路段长度、方向、路段名称、通车年份、车道数、通行能力、通行速度、通行时间等字段信息，节点属性列表包含节点坐标、节点邻接信息等。

2.2 A*算法改进

2.2.1 节点改进

单个路段内可包含多个节点，少则几个，多则几十个，逐点搜索效率低下。本文在建立节点集合时，只提取路段的首节点和尾节点，如图1所示，可大大提高路径搜索的效率。

图1 节点改进处理

2.2.2 数据库改进

高速公路互联网地图通常以省(直辖市)为单位，各省(直辖市)高速公路网络基础数据库一般有5～10年数据(包括现状路网和未来特征年路网)，且每年路网路段数据和节点数据分别在1万条以上，传统方法是直接读取数据库中的每条数据，但效率较低，本文将数据库加载到内存上，分年度存储路段数据和节点数据，从缓存上读取该数据，从而大大提高数据查询和搜索的效率。

2.2.3 启发式函数改进

本文以行程时间最短构建估价函数，采用节点之间的实际距离除以路网平均车速来确定启发式函数。假设g(n)是开始节点s至当前节点n的总行程时间，可通过计算起始节点s至当前节点n的行程时间总和得到，h(n)是当前节点n至目标节点e的行程时间估计，可通过以下函数计算得到：

(2)

d(n,e)=

(3)

(4)

3 实例分析

本文以2030年重庆高速公路网络shape格式数据作为基础数据，通过高德地图API创建高速公路互联网地图，创建结果如图2所示，其中灰色线为未来年规划路网，灰色圆圈代表收费站。该高速公路网包含17 772个路段，16 071个节点。

图2 2030年重庆高速公路互联网地图

本文随机选取5个测试样本，分别用传统A*算法、改进A*算法搜索网络中两节点之间的最短路径。经测试，改进A*算法能够搜索到节点之间的最短路径，且与传统A*算法相比，搜索结果完全一致，如图3～图7所示，说明改进A*算法在最短路径搜索上可行。图3～图7中，黑色带方向箭头线代表两节点间的最短路径，标签框显示了最短路径的长度和行程耗时。

图3 样本1最短路径搜索结果

图4 样本2最短路径搜索结果

图5 样本3最短路径搜索结果

图6 样本4最短路径搜索结果

图7 样本5最短路径搜索结果

此外，本文对2种算法的最短路径搜索时间进行了测试，结果见表1。由表1可知，改进A*算法的最短路径搜索时间基本控制在毫秒级，而传统 A*算法的最短路径搜索时间则在毫秒级至秒级之间，改进A*算法相比传统A*算法在算法性能上有了很大提升，搜索效率更高。

表1 传统A*算法与改进A*算法下节点之间最短路径搜索测试结果

4 结束语

本文在传统A*算法的基础上，对A*算法中网络节点、数据库、启发式函数进行了改进，提出了改进A*算法并进行了应用，认识如下：

1) 改进A*算法能够搜索到互联网地图中的最短路径，且搜索时间基本控制在毫秒级，相比传统A*算法，搜索效率更高。

2) 改进A*算法主要适用于省级(直辖市)高速公路网，对于全国高速公路网，由于其网络规模增大几十倍，搜索最短路径的时间会大大增加，因此对其适用性不强。

3) 随着2020年全国高速公路取消省界收费站，全国高速公路已形成一张网，分析跨省节点之间的最短路径将会变得十分普遍，如何对A*算法做进一步优化，未来需进行更深入的研究。