基于DA* 算法的路径诱导优化研究

赵 冲 贺春林

(西华师范大学 计算机学院，四川 南充437000)

近年来，随着我国经济的飞速发展，车辆的人均占有率呈现几何级增长，随之而来的交通拥堵及交通事故也频繁发生。为了改善该状况，有以下两种可行方法：①拓宽道路，合理建设和布局城市规划，但道路的扩充和增加受各种情况制约，发展水平远不如车辆增加的速度;②对行驶中的车辆进行动态路径诱导，将车辆合理分布在不同的道路上，以提高空闲路段的道路利用率，分散车流，防止拥堵。

基于GIS 的智能交通系统(intelligent transportation system，ITS)越来越受到学者的关注，各种路径选择算法和策略的研究为改善交通状况提供了方向。1973 年，日本CACS(comprehensive automobile traffic control system)实现了基于RF 射频通信的车载动态路径诱导系统;1986 年，欧洲智能交通发起名为“EUREKA”的联合研发计划，包含以车辆定位信息为主的“PROMETHEUS”部分和道路基础设计为主的“DRIVE”部分;1992年，美国的TravTek(travel technology)开始运行，这是一种典型的自治型路径诱导系统;我国的路径诱导系统研究起步较晚，1995 年，由上海交警总队和同济大学研发出多段接力式动态标志路线引导系统，其基本方法是通过道路两旁的可变交通牌及广播来实现交通分流的目的［1］。

路径诱导系统可视为基于图论的寻找最短路径问题。路径的起点为图的初始节点，路径的终点为图的目标节点。但两点间的最短问题，并不仅仅是“空间距离最短”，有时要根据现实情况，改变为所需“时间最短”或“费用最少”［2-3］。解决最短路径常用的算法有基于盲目式搜索的Dijkstra 算法和Floyd 算法、基于启发式搜索的A*算法、基于生物习性的蚁群算法和遗传算法，以及神经网络算法。笔者主要介绍经典的Dijkstra 算法和A* 算法，并提出了带动态权值的DA* 算法，通过仿真实验来验证其有效性和可行性。

1 交通流的表示

路径诱导系统依赖于交通信息的准确性和实时性，一般需要道路状况信息、交通状况信息、气象信息及交通法规信息等。其中交通状况信息包括流量、道路占有率、行程时间和行车速度等信息。收集交通信息的方法主要有自动采集法和非自动采集法两种。自动采集法主要利用检测线圈、超声波检测器、红外检测器及微波检测器采集信息;非自动检测法则利用人工、试验车及摄影视频装置来采集信息［4］。

1.1 交通流数学模型

车辆匀速运动时，路程= 速度× 时间(s=ut)，但在实际生活中，车辆并不可能始终保持匀速运动，因此，用u=s/t来计算实际的车流速度是不可取的。有关如何计算道路上行驶车辆的速度，有下面几种方法：

1935 年，格林希尔兹提出了速度-密度线性模型［5］，可知：

式中：uf为畅行速度;ρx为阻塞密度。当车流密度较大时，车速降低;当车流密度较小时，车速升高;当车流密度为0，即路段没有车流时，实际车速等于车辆自由行驶的速度uf;当车流密度最大，即ρ=s/l时，实际车速u=0，其中l为车辆平均长度。

根据格林希尔兹提出的速度-密度模型，可以推导出速度-流量模型。

由式(1)可得：

将式(2)代入q=ρu可得：

式中，qx为交通流量。当交通密度为0 时，流量为0;当交通流量增大时，直至达到道路的通行能力上限，交通密度为最佳密度ρm，即道路通行情况达到最佳状态;交通密度继续增大，此时车流速度降低，流量减少，直至交通密度达到ρx，即阻塞密度时，速度与流量均接近于零。

1975 年，DANIEL 与MARTHOW 在《交通流理论》中提出时间-流量模型：

式中：cx为当前路段的容量;α，β 为参数，大量实验表明，当α=2.62，β=5 时，模型最优［6］。

将式(3)代入式(4)可得时间t与速度u的函数关系为：

在式(2)～式(5)中，仅车辆速度ux是未知量，速度可通过车辆行驶过程中接收到的广播信息来获取。目前我国的交通诱导系统(traffic guidance system，TGS)主要通过无线电信号向行驶中的车辆进行广播，播发的实时交通信息包括主要路段的行程时间、交通拥挤情况、交通法规、交通事故信息、广域的最优路径选择信息、道路施工信息、天气情况及停车场信息等。

1.2 路段权值计算

路段的权值与距离s、时间t及速度u有关。当距离s增大时，权值也增大，即权值w与距离s成正比;当时间t增加时，权值w也增大，因为距离与时间成正比，所以权值w与时间t的函数为单调递增的曲线;当速度u增大时，权值w减小，因为速度与时间成反比，所以权值w与速度u的函数为单调递减的曲线。

根据以上描述，可得出权值w与距离s、时间t、速度u的函数表达式为：

其中，λ 为距离与时间的比例，其取值受车型和车主主观意识影响。例如，载重货车在拥堵路段，频繁起步与刹车所消耗的燃油费用比小型汽车消耗的燃油费用高得多，因此，载重货车的λ值要低于小型汽车，即在路径选择上，载重货车会优先选择路程较长但道路畅通的路段。对于小型汽车司机而言，过长的距离费用可能带来大量的时间消耗与燃油费用，因此，小型汽车司机在路径选择时会倾向于略为拥堵但路程较短的道路;而对于初学车者而言，拥堵路段的路况较复杂，根据交通流理论跟驰原理，在拥堵路段上对司机的反应速度及精神集中度要求较高［7-8］，因此，在距离代价可以接受的情况下，初学者会优先选择道路畅通的路段。

对于任一条路段，s是固定值，且s=ut;λ 由自主设置且固定不变。将s=ut代入式(5)可得：

其中仅ux为变量，即对于该路段，权值仅受车流速度的影响。对于城市道路而言，每个时刻的车流量可能并不相同，车流速度在不同的时间段取不同的值，因此路段权值随着车流速度的变化而变化，即道路拥有动态权值。

2 路径搜索算法描述

2.1 Dijkstra 算法

Dijkstra 算法是基于广度优先算法，其优点是必定能找到一条路径使得初始节点到目标节点间的距离最短［9］。但因为广度优先算法搜索的节点数量多，时间复杂度高，因此在中间节点较多的情况下，算法的实用性不高。

Dijkstra 算法是盲目的搜索方法，即没有利用问题本身的特性信息，在决定被扩展的节点时，既没有考虑该节点在解的路径上的可能性有多大，又没有考虑是否有利于问题求解及求出的解是否为最优。Dijkstra 算法需要遍历图中所有的节点，在城市交通网络中，每一个路口都是一个节点，因此Dijkstra 算法的时间复杂度和空间复杂度都较高，不太适用于要求实时性的路径诱导。

2.2 A* 算法

A* 算法是一种静态路网中求解最短路径最有效的方法，利用估价函数和实际值的对比来选择最佳路径，属于启发式搜索的优化，在搜索中加入了与问题有关的启发性信息，用于指导搜索朝着最有希望的方向进行，加速问题的求解过程并找到最优解，其核心公式为f(n) =g(n) +h(n) 。其中：f(n) 为初始节点经节点n到目标节点的估价函数;g(n) 为初始节点到节点n的实际代价;h(n)为从节点n到目标节点的最佳路径的估计代价，可以取两节点间欧几理德距离作为估价值，即

这样估价函数f在g值一定的情况下，受估价值h的制约，节点距目标点越近，h值越小，f值也相对越小，这样就能保证最短路的搜索向终点的方向进行。故A* 算法优于毫无方向地向四周搜索的Dijkstra 算法。

A* 算法的搜索效率在很大程度上取决于h(n)，h(n)所携带的启发性信息越多，搜索时所扩展的节点数越少，搜索效率就越高。在实际应用中，A* 算法能用较短的时间寻找到一条最优路径，尽管这条最优路径也许不是最短路径。在城市交通路网中，A* 算法并不能有效地预防车流堵塞问题，因此提出动态赋权的改进A* 算法，笔者将其命名为DA* 算法，实质上就是为h(n)函数增加一条动态的启发性信息，以根据路段上的实时车流速度来改变h(n) 的函数值，在路径选择上优先考虑畅通无阻的路线。

2.3 DA* 算法

由A* 算法的步骤可知，在选择节点N的后继节点时，f值最小的节点会优先考虑。基于该原则，笔者将算法的启发式函数f(n) =g(n) +h(n)改进为f(n)=g(n)+h(n)+w(n)。其中，令w(n)=σ(w(x，t))，即w(n)为t时刻x路段的权值。DA* 算法流程如图1 所示。

从图1 可知，当路段中的车速信息变化时，路段的权值也随之变化，因此路径的选择也会相应改变。例如，从起点S出发，有S→A、S→B两条路径可以选择，且A、B两点到目标节点的直线距离满足：g(A) ＞g(B) ，且h(A) =h(B) 。

图1 DA* 算法流程图

(1)当S→A和S→B路段上车速相等，即σ(w(A，t))= σ(w(B，t))时，f(A)＞f(B)，DA*算法会转变成传统的A* 算法，路径选择与传统算法保持一致，即可以保证寻找到最优路径。

(2)当S→A和S→B路段上车速不等时，假设S→A路段堵塞，即σ(w(A，t))＜σ(w(B，t))时，不能直接比较f(A) 与f(B) 的大小，而需要根据权值计算公式中的λ 取值来决定路径的选择，即在付出一定行驶距离代价的情况下，DA* 算法能寻找到一条行驶速度快、时间短，且距离可接受的优化路径。

3 实证分析

DA* 算法主要解决的是城市交通中的道路拥堵问题，而城市路段的交通状况主要受时间及周围建筑情况的影响。从时间段来考虑，上下班高峰期与非高峰期的车流量有明显区别，节假日与工作日的车流相比，在时段上呈现均匀分布，对路段交通情况的分析要结合道路各个时段的特点;从周边建筑情况来看，车站、学校、政府机关、商业写字楼、大型商场及旅游景点等路段的路况各有其分布规律。因此笔者在实验中将引入一条路况比较复杂的城市交通路网，以四川省南充市西华师范大学华凤校区至西华师范大学北湖校区的路网为实验对象，该路网模拟图如图2 所示。

图2 中A点表示西华师范大学华凤校区，为路网的起点;S点表示西华师范大学北湖校区，为路网的终点，途径各路段长度及各路口与终点的直线距离如表1 所示。

图2 西华师范大学华凤校区—北湖校区路网模拟图

表1 路网中各路段的距离值

表1 中数据由百度地图测距工具测得。根据实际情况作出如下假设：城市道路按等级可以分为4 类，快速路、主干道、次干道和支路，其中A→C、C→G、G→F为快速路，车流速度限制值为60 km/h;H→R、Q→R、R→S为支路，以服务功能为主，连接次干道与小区路，除了考虑车流量外，还必须考虑道路间行人数量，全天限速为20 km/h;其余路段为市区主、次干道，根据时段不同呈现图3 所示曲线分布［10-11］。

图3 市区路段不同时段车速曲线图

从图3 可以看出，车流速度在上下班高峰期呈现明显的下降趋势，而在其他时段则保持平稳态势。笔者以工作日的路况为基础，忽略路段与路段之间的差异，按照图3 所示的速度曲线对车辆行驶过程进行模拟诱导。

对路网中的各个路段取不同的λ 值(当λ=0时为传统A* 算法)来计算权值，然后进行DA*算法路径搜索，得到不同路径所花费的时间和距离耗费，如表2 所示。

表2 A* 算法(λ=0 时)与DA* 算法耗费的时间和距离费用表

从表2 可知，λ 的取值与路径选择关系为：当λ=0 时，DA* 算法与传统A* 算法相等。当0 ＜λ ＜1 时，λ 取值越趋近于0，时间耗费越少，距离耗费越多;而λ 取值越趋近于1，时间和距离耗费越趋近于传统A* 算法。因此，车辆可以根据自身需要来确定λ 的取值。

在车流量比较密集时，即平均车速为20 km/h时，传统A* 算法所耗费的时间为638 s，而DA* 算法耗费的时间为511 s，节省了约20%的时间;传统A* 算法耗费的距离为3 553 m，而DA* 算法耗费的距离为4 466 m，比传统A* 算法多耗费约20%的距离费用。

在车流量发生拥堵，即平均车速为10 km/h时，传统A* 算法耗费的时间为1 125 s，耗费的距离为3 553 m，而DA* 算法耗费的时间为605 s，耗费的距离为3 963 m，即DA* 算法在付出多走约10% 距离代价的情况下，节省了约46% 的时间。

当车流畅通时，DA* 算法与传统A* 算法可选择相同的路径，因为A* 算法可优点是保证可以找到一条最优路径，因此，DA* 算法也能保证找到一条最优路径;当车流开始拥堵时，传统A*算法无法有效地避开拥堵路段，只能依靠路段的距离耗费值来选择路径，而DA* 算法则可以通过接收到的数据信息了解将要到达下一路段的拥堵情况，从而动态变更路段权值，实现实时的寻路策略。

4 结论

针对近年来我国的车辆拥有量越来越大、道路拥堵越来越严重的情况，通过对交通流的分析和对现有路径诱导系统的运用，设计出对道路进行变换权值计算的方法，并将道路权值运用于A* 算法搜索路径的启发式函数中，对实时交通信息做出动态的响应，以实现A* 算法的拥堵控制策略。仿真实验表明，DA* 算法在道路拥堵时具有节省20% ～46%的行车时间的优越性能。

［1］ 景玲.城市动态路径诱导系统框架及最优路径选择算法研究［D］.重庆：重庆大学，2002.

［2］ 夏立民. 交通系统中最优路径选择算法的研究［D］.北京：首都师范大学，2007.

［3］ 王行风，贾凌.GIS 支持下的城市交通网络最短路径研究［J］.计算机与现代化，2005(3)：9 -13.

［4］ 章先阵，吴超仲，初秀民，等.基于机器视觉的公路交通设施信息采集系统设计［J］. 武汉理工大学学报(信息与管理工程版)，2004，26(5)：62 -66.

［5］ 曹亚康，刘立英，王卫卫.城市快速路交通流速度-密度模型研究［J］.物流技术，2013，32(7)：166-169.

［6］ 丁锐.基于VANET 的车辆动态路径选择研究［D］.长春：吉林大学，2013.

［7］ 贺春林.一种基于视频的车辆检测算法［J］.计算机科学，2005，32(5)：243 -245.

［8］ 刘建.基于CAPS_WebGIS 的车辆监控系统的研究［J］. 武汉理工大学学报(信息与管理工程版)，2012，34(3)：297 -300.

［9］ 田哲文，刘峰宇，邓亚东，等. 汽车防追尾预警系统安全距离数学模型［J］.武汉理工大学学报(信息与管理工程版)，2012，31(4)：590 -593.

［10］ 严蔚敏，吴伟明.数据结构［M］.北京：清华大学出版社，1997：186 -190.

［11］ 南充市顺庆区人民政府网.顺庆缓堵保畅：关键要发挥每条道路的作用［EB/OL］.［2015 -01 -05］. http：//www.shunqing.gov.cn/Detail.php?id=35064.