路网分层的改进A*算法在智能交通系统中的应用

　　车辆最短路径规划是智慧交通的重要体现，而高效的算法是路径规划的核心。本文在经典A*算法的基础上，将当前节点、

　　预选节点、目标节点之间的夹角做为估价函数的参数，这样规划出来的路径不会出现比较大的道路转向；同时整个道路网络分为两层，快速路和主干路做为高层，次干路和支路做为低层。

　　1路网分层的改进A*算法及实现1.1经典A*算法

　　般的A1*算法公式为f(n)=g(n)+h(n) ⑴

　　n为预选节点，其中f(n)是起点经过n节点到终点的估价函数，g(n)为从起点到n节的实际代价函数，h(n)为从n节点到终点的估算代价函数。h(n)的估算方式有多种，可以为欧氏距离，曼哈顿距离，切比雪夫距离等来估算，此次实验中我们采用的是欧式距离除以路网平均车速（按各等级道路所占路网权重计算）。

　　1.2改进A*算法

　　改进A*算法⑴主要考虑经过节点数较少的方式，来找到通行时间最短的路径，此时采用路径行驶中的角度偏转值做为h(n)的参数⑵。算法公式为：

　　f(n)=g(n)+arg(n)'h(n) (2)

　　其中f(n)是起点经过n节点到终点的估价函数；g(n)为从起点到n节点的实际代价函数，计算方法为在路段的行驶时间(行驶时间与路段等级、道路长度有关）与车辆在路口的红绿灯等待时间（等待时间可设置为红灯总时长的一半）之和；h(n)为从n节点到终点的估价函数，计算方法为n节点到终点的欧氏距离除以路网平均车速；arg(n)为从当前节点到预选节点的直线与预选节点到终点所形成的直线的夹角，夹角范围为（0，7)。为了防止各预选节点间的夹角差值太大，如预选节点与终点为相反方向时a「g(n)为n，相同方向为0，为a「g(n)设置一个上下阈值（7^6，5n/6)。

　　1.3路网分层的改进A*算法

　　路网分层B-5]是将整个路网按照行车速度分为两层：次干路和支路为低层路网，快速路和主干路分为高层路网?"7]。在高层路网中，一般交叉口密度较少，采用经典A*算法规划路径；而在低层路网中，交叉口密度较大，且车流量较大[|?]，采用改进A*算法。路网分层的改进A*算法的步骤如下：

　　1) 初始化道路数据，获得起点O和终点D所在节点层次；

　　2) 若O和D同在高层路网，则忽略低层路网，按经典A1*算法选择下一节点，直到达到D为止；否则转到3);

　　3) 0和D在低层网络，按欧式距离找出距离O和D最近的高层节点0*和D*，采用改进A*算法规划出0到0*路径R1，D到D*路径R2(若0与D有一节点在高层，算法类似）；

　　4) 按经典A*算法得到的方式得到0*到D*的路径R3;

　　5) 组合三条路径：R=R1+R3+R2，即为所求最优路径，算法结束。

　　2算法仿真

　　本文使用的绘图软件为MaplnfoProfessional10，以杭州江干区下沙经济技术开发区的重要路段进行提取绘制成电子地

　　193各种算法路径搜索结果图，其中截取了共215个节点，690条路段。采用的仿真平合为Linux平合下的GDB编译框架，用C语言编程。主要存储的数据有各节点坐标和等级、节点之间路段信息、各路口的红灯时长，所有信息由杭州下沙交通控制中心提供。将道路分为四个等级、两个网层，对应速度40、60、80、100km/h。行车平均速度由各等级道路所占路网权重确定，经计算得该路网平均速度v为58.6km/h。

　　为了体现出规划效果，每次规划中随机选取4个节点，两个为起点和终点，另外两为个中间节点，即实现3次路径规划，路径颜色依次为红、棕、绿。

　　从以上图与表的搜索节点数和经过节点数可知，由于改进算法的路径轨迹相对比较平滑，不会出现大的转弯，采用改进A*算法经过的节点数总体要少于经典A*算法，如图1中节点104到38减少了2个，节点38到15节点数相同，节点15到b改进A*算法路径93减少了5个，总节点数减少了7个，减少10%，表2中总节点数减少4个，减少8%。经过节点数减少后，搜索次数则变小，搜索节点数相应减少。对于分层改进A*算法，将路径分成了三段处理，使得经过节点数增加；在低层节点搜索高层节点时，屏蔽了高层节点，高层节点之间搜索时屏蔽了底层节点，因而搜索节点数减少，表2中搜索节点数较改进A*算法减少了有14%,经过节点数增加了25%。

　　由运算时间可以看出，改进A*算法的估价函数前有系数运算，增加了每次运算时长，又算法经过节点数少，减少了运算次数，所以总运算时间较经典算法差别不大。分层改进算法将路径划归为三段处理，规划时三段运算并发执行，当最后一条路径规划完搜索结束，相对于改进A*算法表1中运算时间减少了44%，表2中减少了60%，算法效率得到很大提高。

　　由路径长度和实际行驶时间可以看出，改进A*算法与A*c路网分层改进A*算法路径图2节点3-181-210-127各种算法路径搜索结果表1节点104-38-15-193的相关参数表2节点3-181-210-127的相关参数算法路径长度相差不大，甚至改进后路径变长，如表1中由22660m变为23140m，但考虑到经过节点时的路口延误时间，总行驶时间减少了7%。分层改进A*算法的路径长度有明显增加,如表2中路径长度为26860m，相比改进算法增加了53%，但整个路径中高层路段所占比例较大，反而行驶时间降低了31%。

　　从总体上来看，路网分层的改进A*算法较经典A*算法而言，虽然加大了路径长度，但能够从减少经过节点数和增加高层路段比例两个方面缩短最短行驶时间，且运算速度也有所降低,符合实际交通情况，总体效果优于经典A*算法。

　　3结束语

　　结合实例进行仿真，实验有效的证明该算法不仅可以保证经典A*算法的精度和效率，而且缩短了行程时间。此算法可以做为动态路径规划时的底层算法来运用，若在车辆导航系统中采用此算法，将给人们的出行带来方便。