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

《路网分层的改进a-算法在智能交通系统中的应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、路网分层的改进A*算法在智能交通系统中的应用车辆最短路径规划是智慧交通的重要体现，而高效的算法是路径规划的核心。本文在经典A*算法的基础上，将当前节点、预选节点、目标节点之间的夹角做为估价函数的参数，这样规划出来的路径不会出现比较大的道路转向；同时整个道路X络分为两层，快速路和主干路做为高层，次干路和支路做为低层。1路X分层的改进A*算法及实现1.1经典A*算法般的A1*算法公式为f(n)=g(n)+h(n)⑴n为预选节点，其中f(n)是起点经过n节点到终点的估价函数，g(n)为从起点到n节的实际代价函数，h(n)为从n节点到终点的估算代价函数。h(n)的估算方式有多种，可以为欧

2、氏距离，曼哈顿距离，切比雪夫距离等来估算，此次实验中我们采用的是欧式距离除以路X平均车速（按各等级道路所占路X权重计算）。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

3、节点到终点的欧氏距离除以路X平均车速；arg(n)为从当前节点到预选节点的直线与预选节点到终点所形成的直线的夹角，夹角范围为（0，7)。为了防止各预选节点间的夹角差值太大，如预选节点与终点为相反方向时a「g(n)为n，相同方向为0，为a「g(n)设置一个上下阈值（7，5n/6)。1.3路X分层的改进A*算法路X分层B-5]是将整个路X按照行车速度分为两层：次干路和支路为低层路X，快速路和主干路分为高层路X?7]。在高层路X中，一般交叉口密度较少，采用经典A*算法规划路径；而在低层路X中，交叉口密度较大，且车流量较大[

4、?]，采用改进A*算法。路X分层的改进A*算法的步骤如下：1

5、)初始化道路数据，获得起点O和终点D所在节点层次；2)若O和D同在高层路X，则忽略低层路X，按经典A1*算法选择下一节点，直到达到D为止；否则转到3);3)0和D在低层X络，按欧式距离找出距离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各种算

6、法路径搜索结果图，其中截取了共215个节点，690条路段。采用的仿真平合为Linux平合下的GDB编译框架，用C语言编程。主要存储的数据有各节点坐标和等级、节点之间路段信息、各路口的红灯时长，所有信息由杭州下沙交通控制中心提供。将道路分为四个等级、两个X层，对应速度40、60、80、100km/h。行车平均速度由各等级道路所占路X权重确定，经计算得该路X平均速度v为58.6km/h。为了体现出规划效果，每次规划中随机选取4个节点，两个为起点和终点，另外两为个中间节点，即实现3次路径规划，路径颜色依次为红、棕、绿。从以上图与表的搜索节点数和经过节点数可知，由于改进算法的路径轨迹相对

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

8、运算，增加了每次运算时长，又算法经过节点数少，减少了运算次数，所以总运算时间较经典算法差别不大。分层改进算法将路径划归为三段处理，规划时三段运算并发执行，当最后一条路径规划完搜索结束，相对于改进A*算法表1中运算时间减少了44%，表2中减少了60%，算法效率得到很大提高。由路径长度和实际行驶时间可以看出，改进A*算法与A*c路X分层改进A*算法路径图2节点3-181-210-127各种算法路径搜索结果表1节点104-38-15-193的相关参数表2节点3-181-210-127的