交通拥堵、汽车尾气问题一直都是智能交通的研究重点,怎样选择便捷路径行驶以减少汽车能耗已成为出行者日益关注的问题。生态智能交通[1]的提出为交通诱导与节能减排提供了一个新的发展方向,能够有效地降低汽车能耗。
国内外学者在有关交通诱导的路网建模、最优路径以及汽车排放等方面进行了很多的研究。在构建路网模型方面,曹政才等[2]建立了以道路为基本元素的RBM模型,但如果交通信息量大则会增加计算量。Demir 等[3]构建一种聚类超图模型,并通过把基于节点的数据存储方式转化为基于路段的数据存储方式,减少路网数据的存储量;宋青等人[4]建立了一个基于小区的大规模分层图论路网模型,提出新型分层路由算法提高了空间搜索精度。文献[5]将静态路网与动态信息结合起来建立了动静态广义路网模型。文献[6]提出了考虑用户均衡的新型动态模型,解决静态和动态交通分配问题。以上的路网模型,都把交叉口当作路段的一部分。但是实际上,交叉口处的信息是不可忽略的。在最优路径方面,文献[7]提出了基于智能优化搜索理论和人工免疫系统的最优搜索算法,实现路径诱导。文献[8]在博弈论基础上,建立了考虑广义出行费用的路径选择模型。文献[9, 10, 11]针对蚁群算法易陷入局部最优解的问题对蚁群算法进行了改进,实现有效的路径搜索。另外,李世武等[12]从排放角度确定了最佳的信号配时优化方案。文献[13]研究了道路等级以及行车速度对排放的不同影响。由以上研究可以看出,若从路网模型和能耗的角度进行交通诱导路径寻优,对实现交通节能减排具有重要的现实意义。
文中在传统图论的基础上,构建出动态路网模型,细化交叉口和路段的动态信息。对交叉口和路段的行驶能耗进行计算并得出能耗最优路径诱导模型,应用改进蚁群算法对模型进行求解,得出能耗最优路径。
1 动态路网模型的构建 1.1 动态交通路网模型城市交通路网复杂多变,从总体上看,都是由道路交叉口和路段相互连接而成的。可以用图论法对交通路网进行拓扑化抽象,图论中的节点及弧段分别与实际路网的交叉口及路段一一对应,并且对弧段进行赋权描述。
设交通路网由加权图G={V,E,T}表示。V为非空的交叉口集合V={1,2,…,n},i为节点;E表示路段的集合,E={rij丨i,j∈V};T代表每条路段的广义耗费。但是在实际路网中,不仅路段上会产生耗费(如路段交通拥堵等),在交叉口处也会产生不可忽略的耗费(如交叉口延误等)。并且路段和交叉口处的耗费并不是一成不变的,而是随着时间及路网的运行状态而变化的。因此可定义动态交通路网模型为G={V,E,Ti(t),Tij(t)},对交叉口和路段分别进行描述。其中V为非空的有限交叉口集合,E表示有限路段集合;Ti(t)表示t时段节点i上的耗费,t∈[t0,tn]在这个连续时间中取值;Tij(t)表示t时段在路段rij上的耗费。它们都是依赖于时间和交通状态的函数,当路段和交叉口处出现由于各种原因引起的严重拥堵时,Ti(t)、Tij(t)为无穷大;在路段和交叉口畅通或其他情况下,Ti(t)、Tij(t)为正值。
1.2 路网中动态交通信息实际路网中,影响交通网络通行能力的交通因素分别发生在交叉口和路段上。下面分别对交叉口和路段相关信息进行描述。
信号交叉口延误是由于交叉口处信号控制引起交通流间断而损失的车辆行驶时间,文中以十字交叉路口为例。根据质点排队模型,当交叉口驶出流量大于出口通行能力时,则在该处将出现点排队。此处,可以简化交叉口处的动态因素,排队时间的计算仅考虑路口排队车辆数,可以更直观、简便地反映实际路网,减少计算量。
交叉口排队延误时间与排队车辆数关系为
城市交通路段上的动态因素相对复杂,其中单位时间内的交通量表现为动态性和随机性;通行能力则为交通规定运行特征下的最大流量,表现为相对稳定性和规律性;行车速度、车流密度在交通状态上也表现出敏感性。下面将对主要的路段动态信息进行描述。
由交通流理论可知,交通量、速度和密度3个参数之间的关系为
设定某路段的长度为la,则有
路段流量与路段行驶所需时间的关系为
路段的行程时间是影响路径寻优的一个重要指标,而道路的拥堵的判定指标也备受关注。交通拥堵指数(traffic performance index,TPI)是北京市首创的综合反映道路网畅通或拥堵的概念性数值。TPI分成5个等级,取值用0~10之间的正整数来表示,数值越高,拥堵越严重
为了简化计算,文中在此基础上简化了TPI等级,如式(4)所示,路段拥挤程度值为
在进行交通状态分析时,可取TPI的不同值来判断路段的拥挤程度,对交通状态进行评价。此外,影响路段通行能力还有另外一个动态信息,如当遇到修路、雨雪天气导致的封路时,这个路段就为限行路段,这个路段的耗费可以设置为无穷大。
1.3 车辆行驶能耗城市道路上车辆行驶的能耗分为2部分,主要是在路段上以及交叉口红绿灯时的能耗。车辆行驶能耗的特点是,车辆从怠速到匀速行驶过程中能耗相对匀速行驶较大。在有信号控制的交叉口上,车辆一般有2种运动状态:一是车辆到达交叉口时遇到红灯和拥堵状态需要排队等待时,车辆必须怠速再启动通过交叉口。二是车辆到达交叉口时信号为绿灯,车辆匀速通过交叉口,其能耗量近似按路段能耗计算。
按照不同车型,能耗率也是不同的,见表 1 。
文中定义式(5)计算能耗:
交通网络中最短路径问题一直都是研究的热点。但是由于交通信息的不断变化,最短路径已经不能够作为最合理路径的标准。最优路径将从距离最短、时间最少和能耗最短等角度来诠释。
结合上述所建立的动态路网模型,建立了最优路径诱导模型,也可称作耗费最小模型。设Lmin为车辆最小耗费所经过的路径,rij、ri、rj为所经过的路段和交叉口。这是一个组合优化问题,可用式(6)的数学模型来表示:
根据车辆行驶的能耗公式,可得出能耗最优路径诱导模型:
蚁群算法作为一种启发式算法,常用在智能交通中的路径诱导方面。它是一种仿生学算法,通过模拟蚂蚁觅食的过程,将其应用到路径搜索过程中,并及时对外界的信息做出响应得到最优路径。影响蚁群算法的核心因素有2个,一个是节点间转移概率的计算策略,另一个是信息素更新规则。而传统蚁群算法在路径寻优过程中,搜索效率低并易陷入局部最优,搜索结果不稳定。
为了提高算法效率,使蚁群算法更加适应外界信息的变化,得到最优路径,文中分别在转移概率选择和信息素更新规则上进行改进。
在蚁群算法中,β为期望启发因子。外界的动态信息影响蚂蚁转移概率中的β,所以这里β不再是一个固定值,它与交通道路的拥堵指数有关,令β=TPI,当TPI越小时,道路越畅通,此时蚂蚁倾向于选择信息素浓度较高的地方。设m为蚁群中蚂蚁的数量,τij(t)相邻2个节点间的信息素量,为了提高算法的效率,直接去遍历和节点i相连接的节点,这里Vk={和i直接相连的节点},则转移概率为
在信息素更新规则上,蚂蚁每走一步后所经过的路径上的信息素要进行挥发,如式(7)所示。
而蚂蚁每经过一次循环后时,得到的最优解所经过的路径上的信息素要增强,而非最优解的路径上的信息素要减弱。将更新因子引入全局更新中,按照式(8)更新信息素:
算法的具体步骤如下。
1)初始化各路径上的信息素都为一常数;蚂蚁数目为m;并将m只蚂蚁放在起点处。
2)在t时刻每只蚂蚁按式(6)所示的转移概率选择下一节点。
3)到达下一节点后,用式(7)进行信息素的局部更新。
4)判断节点j是否为目的节点,若为目的节点则保存蚂蚁走过的路径。若不是目的节点,则返回步骤2)。
5)当m只蚂蚁全部迭代完后,则将各路径上的信息素按式(8)进行全局更新。并将每只蚂蚁搜索到的最优路径进行比较,得出全局最优路径。
3 仿真实验城市路网建设错综复杂,文中借助VS2010软件平台,对真实道路网应用改进的图论模型进行网格化抽象。图 1为仿真路网环境,其中黑色节点部分为交叉口,连接节点之间的连线为路段,每条路段间距离不同,示意图中标注了相应静态距离。下面将从能耗角度对最优路径进行模拟验证。首先进行初始化设置,设上路车辆均为小轿车,标准乘载,能耗率qv为0.23 mL·s-1,假设此时的路网正处于早高峰时段,局部车流相对缓慢,交通状况实时变化。此时在路口n5、n7处出现轻微拥堵;在n11、n22交叉口处排队车辆数较多,车行缓慢;其他路段相对较畅通。此时,车辆以n1为起点,终点为n19。
算法的参数设置为:车辆数量m=30;量子位数为2;概率参数q0=0.5;挥发系数ρ=0.7;α=0.5;β=0.5;最大迭代次数为400。在动态路网下应用改进后路径寻优算法得出的路径为n1-n2-n6-n10-n14-n18-n19,行车距离为19.5 km,能耗为0.49 L。而在静态路网下,车辆选择的是距离最短路径为n1-n5-n9-n10-n11-n15-n19,虽然走过路程为18.5 km,但是由于路口拥堵而造成等待时间延长,耗油量为0.55 L。路径仿真结果如图 2。
选择2组起点终点,在静态和动态路网下有不同路径,具体数据见表 2、表 3。
起点终点 | 静态路网 | 动态路网 |
n1-n19 | n1-n5-n9-n10-n11-n15-n19 | n1-n2-n6-n10- n14-n18-n19 |
n2-n16 | n2-n3-n7-n11- n15-n16 | n2-n6-n10-n14- n15-n16 |
分析上面的路径表可知,尽管在静态路网下能使行驶距离减少,但是却在行驶过程中增加了等待时间,增大了能耗,静态路网不能及时的对路网上的动态信息做出及时响应。而在动态路网中,距离不一定最短,但能够避开交叉口拥堵,减少了行程内怠速等待,根据表 3所示,在动态路网下的能耗相对减少,比较符合出行者的需求。图 3为改进蚁群算法下能耗最优解收敛图,在图中可以看出,未改进的蚁群算法在搜索过程中易出现早熟现象,收敛速度也较慢,未搜索到全局最优解。而改进蚁群算法可以有效避免局部最优现象的出现,提高了收敛速度。
4 结束语文中针对实时变化的交通路况,在图论基础上建立的动态路网模型综合考虑了交叉口和路段的动态信息,进而推导出能耗最优路径诱导模型;再针对蚂蚁状态转移概率和信息素更新规则方面对蚁群算法进行改进,改进后的蚁群算法可以有效地避免局部最优解,提高了算法的效率;由不同起终点得出的能耗最优路径可以有效地节省能耗,符合实际需求;也为今后研究交通诱导中的系统综合最优提供了基础,具有现实意义。
[1] | 朱昊,陶晨亮,赵方.发展生态型智能交通系统的建议[J]. 交通与运输,2013,29(3):21-22. |
[2] | 曹政才,韩丁富,乔非.基于新型路网模型的路径寻优方法研究[J].电子学报,2012,40(4):756-761. |
[3] | DEMIR E, AYKANAT C, CAMBAZOGLU B B. A link- based storage scheme for efficient aggregate query processing on clustered road networks[J]. Information Systems,2010,35(1):75- 93. |
[4] | SONG Qing, WANG Xiaofan. Efficient routing on large road networks using hierarchical communities[J]. IEEE Transactions on Intelligent Transportation Systems,2011(12):132-140. |
[5] | YANG Yuhong, HAN Xiaowei, YUAN Zhonghu. A model of dynamic traffic road network[J]. IERI Procedia,2012(13):46-51. |
[6] | JIN Wenlong. A dynamical system model of the traffic assignment problem[J]. Transportation Research Part B,2006,41 (1): 32-48. |
[7] | YANG Licai, LIN Jie,WANG Dewei, et al. Dynamic route guidance algorithm based on artificial immune system[J]. Journal Of Control Theory and Applications,2007, 5 (4):385-390. |
[8] | FENG Yuqin, LENG Junqiang, XIE Zhongyu, et al. Route choice model considering generalized travel cost based on game theory[J]. Mathematical Problems in Engineering,2013(1):1-5. |
[9] | LIU Zhishuo. SHEN Jinsheng, CHAI Yueting.Hybrid multiple ant colonies algorithm for capacitated vehicle routing problem[J]. Journal of System Simulation,2007,19(15):3513-3520. |
[10] | SONG Jinjuan, BAI Yanping. An improved ant colony algorithm and its application in optimal routing problem[J]. Journal of Measurement Science and Instrumentation,2013,4(1):23-29. |
[11] | GAN Rongwei, GUO Qingshun, CHANG Huiyou, et al. Improved ant colony optimization algorithm for the traveling salesman problems[J]. Journal of Systems Engineering and Electronics, 2010(2):329-333. |
[12] | 李世武,王云鹏,付建萍,等. 基于车辆排放的城市道路交叉口信号配时优化仿真[J]. 吉林大学学报:工学版,2007,37(6):1268-1272. |
[13] | 王云鹏,郭栋,隗海林,等. 城市分等级道路车辆运行速度对排放的影响[J]. 哈尔滨工业大学学报,2009,41(7):110-114. |