城市交通流量预测与信号控制优化

赵文天,万夕里,白光伟

(南京工业大学 计算机科学与技术学院,南京 211816)

1 引 言

随着国民经济的快速发展以及城市规模不断扩大,城市中的车辆变得越来越多,导致交通堵塞频繁发生.目前,缓解城市交通压力主要有两类方法:一是降低交通需求;二是提高交通运输效能[2].通过限牌等方法来降低交通需求虽然可以缓解城市交通压力,但是该方法与城市出行需求之间构成冲突,不适合长期采用.目前第二种方法已经成为提高交通系统运输效率的最主要手段.通过提前预测各个路口的车辆数量来实时变更信号灯时长,使得在一段时间内到达路口的所有车辆全部通过该路口的时间最短.

车载自组织网络(Vehicular Ad-Hoc Network,VANET)是智能交通系统(Intelligent Traffic System,ITS)在过去十几年中飞速发展的产物,把行驶的车辆看作移动节点,利用无线通信技术形成无线移动网络[2].车与车/车与基础设施(Vehicle-to-Vehicle/Vehicle-to-Infrastructure,V2V/V2I)之间可以通过无线信号进行实时的网络通信.随着通信技术的发展,车与外界信息交换(vehicle to everything,V2X)技术在车辆上的应用已成为必然趋势,被认为在改善行车安全和减少事故中具有巨大的潜力.此外,它为改善交通和驾驶环境提供了技术支持[3].文献[4]基于VANET的V2I通信,提出了一种在线交通信号灯控制算法OJF(Old Job First),并证明其在同类算法中是最优的.但该在线算法在实际生活中很难应用,因为每当一辆车辆到达路口,信号控制系统就要根据在线算法变换信号灯,所以信号灯切换的次数会过于频繁,这使得该算法不适合应用于道路拥堵场景下的信号灯控制.

文献[5]提出了一个十字交叉路口附近车辆的协作优化算法.该算法将相邻交叉口区域的车辆划分为若干排,并为同一排的第一辆车和其他车辆指定不同的驾驶策略,以提高交通系统的效率.该优化算法是基于粒子群优化(Particle Swarm Optimization,PSO)算法.由于PSO算法的时间复杂度较高,当系统中存在更多车辆时,需要花费较长的时间来解决问题,并且该算法对系统运行的硬件要求很高.

文献[6,7]提出了两个协调推动交叉路口附近车辆的优化策略.文献[6]提出了一种算法,该算法可以协调没有交通信号的交叉路口区域的交通流冲突,但该算法假定车辆加速度从进入交通信号附近的点开始保持不变直至车辆离开冲突地区.此外,文献[7]假定车辆的加速度可以保持恒定且均匀的变化.但是由于城市道路条件复杂,交叉口附近的交通流量密度可能会发生较大变化.因此,这两种模式的适用性是有限的.另外,车辆可能会在交叉路口转弯,并在交通信号附近进行强制车道改变,然而这些研究并没有考虑到车辆的车道变化.

在车道变化方面,许多学者进行了相关研究[8,9].这些研究大多集中在可选车道变换上,而且很少有人提出在交通信号附近强制变换车道.在车辆调度算法方面,文献[4]提出了OJF算法,虽然证明了OJF算法在在线算法中是最优的,但在线算法会导致信号灯切换频繁,很难在实际中应用.文献[16]提出了FTC(fixed-time signal control)算法,但是该算法被证明只能在车流量较低时具有较好的表现.

针对上述问题,本文提出了一种基于V2X的联合驾驶和变换车道模型,预测出一个时间段内各车道车辆的数目,充分利用V2X通信来提高区域交通系统的安全性和效率.在此模型的基础上设计了一种基于图的信号灯控制算法,有效减少了交通信号灯切换的次数,并且能够大幅提升交通运输的效率.

本文第2节详细介绍了基于V2X的交通流量预测模型;第3节详细介绍了图模型和基于本文交通模型提出的高效调度算法;第4节通过理论证明了我们提出算法的高效性;第5节通过实验验证并分析了我们提出算法的性能;第6节是本文的总结和对未来工作的展望.

2 基于V2X的交通流量预测模型设计

在交通信号灯附近,当一辆汽车跟随另一辆汽车时,驾驶员必须注意前方汽车和交通信号灯的状态来调整驾驶行为.假设当前信号灯为绿灯,如果车辆能够在绿灯持续时间内通过冲突区域,如图1所示.驾驶员通常选择通过冲突区域跟随前方车辆,并且车辆的速度受到前方车辆速度的影响.如果前方没有车辆,司机可以按照理想的速度穿过冲突区.如果红灯亮起或黄光闪烁,司机通常会选择放慢车速或者停车.

图1 冲突域说明图Fig.1 Illustration of conflict domain

在上述过程中,缺乏信息可能会导致很多问题.例如,由于判断不准确,当车辆在冲突区域中移动并且无法立即停止时,信号灯可能会变为红灯,导致车辆的碰撞,这就是所谓的冲突区域[10],如图1中阴影区域所示.另外,司机需要频繁关注交通信号,因此他们往往会频繁减速,导致行驶时间延长,燃油消耗增加以及道路拥堵[11].

然而在V2X环境中,司机可以随时随地获得前方车辆和交通信号灯的状态,这为联合驾驶创造了条件.司机提前获取了交通信号灯的状态信息并调节车辆速度,以适当的速度通过冲突区域,避免了长时间停止.因此,本部分规划了交通信号灯附近车辆的联合驾驶和车道变换过程,以便提前确定驾驶轨迹和减少停车延误,并预测出下一个时间段检测区域内车辆的数目.

假设交通信号灯的周期是TC,绿灯和红灯的持续时间分别为TG和TR,TC,TG和TR的关系如公式(1)所示:

TC=TG+TR

(1)

在t时刻,交通信号的状态可以定义为公式(2):

(2)

其中tlight代表当前时间的交通信号周期,假设t时刻的车辆Vi的位置,速度和加速度分别为xi(t),vi(t)和ai(t),并且车辆运动符合以下的运动学方程:

(3)

v(t+k)=vi(t)+kai(t)

(4)

上述k代表着时刻t之后所经过的时间间隔,文献[12-14]提出了一种智能驾驶模型,可以描述道路上车辆的流动.此外,该模型具有很强的通用性,可以描述从自由流(车流速度不受限制)到冲突流(车流速度被限制)的不同流量.在该模型中,后续车辆的加速度如公式(5)所示:

(5)

(6)

当车辆Vi接近交通信号附近时,我们首先考虑它是否是检测区域中的第一辆车.如果是,则在获取交通信号灯信息之前,让其以自由流量速度(最大速度或道路限速)驾驶.相应地,此时的加速度为0(已达到自由流速)或舒适加速度(尚未达到自由流速).如果不是,它将跟随前方车辆,并且加速度可以由公式(5)和公式(6)确定.

为了避免停车,驾驶员需要在获取交通信号灯信息之前提前计划路线.图2描述了车辆Vi在t0时接近交通信号灯.在图2中,水平轴表示时间,垂直轴表示车辆与交通信号之间的距离.当Vi接近交通信号附近并进入V2X通信范围时,假设交通信号具有固定的周期,那么车辆轨迹就被限制在区域1和区域3(因为车辆只能在绿灯周期内通过路口).如果Vi的平均速度满足以下条件:

(7)

图2 交通信号附近的车辆状态Fig.2 State of vehicle near the traffic signal

(8)

图3 车辆变换车道Fig.3 Vehicle changing lane

dLD(t)≥dmin+h1vi(t)

(9)

其中h1代表变换车道的时间,研究表明,车道变换过程的持续时间与车道变换速度稍有关系[15].在换线时间固定的情况下,换道车辆的横向加速度和运动轨迹可用公式(10)、公式(11)描述

(10)

(11)

其中alat表示横向加速度,H表示车道宽度,tlat表示车道变换的持续时间,ylat表示侧向空间.当Vi从L0移动到车道LD时,跟随的第一辆车从VLO逐渐过渡到VLD.根据Vi的横向位移,其纵向加速度可由公式(12)得出:

(12)

(13)

(14)

基于上述的分析,车辆的速度和加速度需要符合上述公式才能安全变道并通过冲突区域.根据上述车辆模型,可以预测出下一个时间段内检测区域的车辆数目,如公式(15)所示.本节更加真实地模拟了现实生活中车辆的运动模型,这为下文提出的车辆调度算法提供了基础.

(15)

3 基于图的车辆调度算法设计

本文的算法模型是基于一个典型的十字交叉路口,其结构如图4(a)所示.图4(a)展示了八种交通动作,其序号为1-8,其中右转与直行将作为一种交通动作考虑(右转与其他交通动作不冲突),这种十字路口是我们平时最常见的,也是比较易于研究的一种交通模型.这些交通动作之间会有冲突即不能共同执行比如动作1和动作2,如果同时执行动作1和动作2,必会造成交通路口的堵塞.

图4 交通动作转换图Fig.4 Transition diagram of traffic movements

本文可以通过图4(a)的八种交通动作建立一个冲突图G(V,E),其中V代表的是一系列顶点,E代表的的是两点之间的连线.每有一种动作种类就需要设立一个顶点,如果两个动作之间有冲突(两个动作不能同时执行),那么就需要在这两个顶点之间连接一条线.如图4(b)所示,将图4(a)这八种交通动作构建成一个冲突图,每个结点代表一个交通动作,结点之间的连线代表他们不能同时执行.

在文献[4]中,将图4(b)中的顶点1和2,3和4,5和6,以及7和8合并,将图4(b)中的G转换为图4(c)的G′.本文所提出的车辆调度算法是基于图4(c),将图4(c)右侧的两个顶点定义为r和r′,将左侧的两个顶点定义为l和l′.因为r和r′之间没有连线,所以r和r′可以同时调度,同理l和l′也可以同时调度.

传统的车辆在线调度算法[4]只是处理最先到达路口的车辆,我们提出的算法将一个时间段路口积攒的车辆一起处理,有效地减少了车辆的等待时间.具体算法如算法1所示.

算法1.Frame-based Trafic Scheduling(FTS)算法

1.BEGIN

2.INPUTr,r′,l,l′

3.SETtime= 0;

4.WHILEr,r′,l,l′havejobswaiting,do

5.SETminR=min(r,r′),minL=min(l,l′);

6.IFminR==0THEN

7. SETminR=max(r,r′);

8.SETtime+=minR;

9.ELSETHEN

10.SETtime+=minR;

11.SETr-=minR;

12.SETr′-=minR;

13.ENDIF

14. IFminL==0THEN

15.SETminL=max(l,l′);

16.SETtime+=minL;

17.ELSETHEN

18.SETtime+=minL;

19.SETl-=minL;

20.SETl′-=minL;

21.ENDIF

22. OUTPUTtime;

23.END

G′中的四个顶点r,r′,l和l′中暂存的车辆数量是根据公式(15)计算得到的.图4(a)中展示的每一个交通动作所在的车道都存在如图5所示的阴影区域(图5只覆盖了交通动作6),意在监测车辆的行驶信息并将信息传送到中心服务器进行计算.

图5 FTS算法的应用场景Fig.5 Application of FTS algorithm

当车辆进入检测范围时,向路测单元RSU1发送驶入消息(Entering Message,EM),EM内容包括车辆的标识符、行驶车道、当前车速以及进入区域的时刻.当车辆驶出检测区域时,向路测单元RSU2发送驶离消息(Leaving Message,LM),LM内容仅仅包含车辆的标识符.本文不考虑车辆类型,只计算车辆数目.RSU1接收到EM后,将信息传输到中心服务器,由中心服务器分析一个时间段内收到的EM消息,并且根据上一节的模型计算出下一个时间段监控区域内车辆的数目;RSU2收到LM后,将信息传输到中心服务器,由中心服务器分析LM消息,并且删除相应区域内的车辆.中心服务器根据下一个时间段路口的车辆信息以及本文提出的高效调度算法计算出信号灯的配时方案,并通过RSU2将配时方案发送给交通信号控制系统,用于控制十字路口的信号灯时间分配.

4 算法性能分析

本节对本文提出的FTS算法进行性能分析,不仅证明了算法的近似比为2,还对算法的时间复杂度进行了分析.近似算法的定义为公式(16):

(16)

对于任何规模的输入值n来说,由近似算法产生的解的代价C与最优解的代价C*都只差一个因子ρ(n)(近似比，approximation ratio),那么则称该算法为ρ(n)近似算法.

定理1.FTS算法的近似比为2.

所以对于任意的k,都能得到公式(17):

(17)

调度策略SALG所需要花费的时间如公式(18)所示:

(18)

所以本文提出的车辆调度算法的近似比为2.

定理2.FTS算法的时间复杂度为O(1).

证明:若图4(c)中四个顶点的权值都不为0,那么将全部车辆调度完成所花费的时间一定是最多.然而按照本文提出的调度算法,调度完一个时间段内路口积攒的所有车辆只需要四步,所以本文提出的FTS算法基本语句执行次数为一个常数,其时间复杂度为O(1).

5 实验与分析

本文采用的实验模拟环境为Matlab,假设每一秒钟到达各个节点的车辆数目最多为1.那么就可以随机模拟出100s内四个节点的车辆积攒情况,如表1所示.本节根据不同的路况,通过三种算法分别调度,比较三者将一个时间段内的全部车辆调度完的时间以及信号灯切换的次数.其中车流量代表的是道路的饱和程度,即当前监控区域内的所有车辆占该路口可容纳车辆最大值的百分比.

表1 模拟100s内的路口车辆信息
Table 1 Simulation of traffic information in 100s

节点10s20s30s40s50s60s70s80s90s100s总计100s内车辆数(1,2)806471347545(3,4)175236754242(5,6)942125274440(7,8)756324443644

在Matlab中随机生成一个4X10,元素为0-10中随机整数的矩阵作为函数的输入.通过图6,可以观察到在车流量较小时,本文提出的FTS算法耗时要比FTC算法少,并且只有OJF算法的一半. 随着车流量的不断增加,本文提出的FTS算法耗时逐渐向OJF算法以及FTC算法逼近.这是因为当路口积攒的车辆过于饱和时,无论用什么方式调度,将这些车辆全部调度完的时间都趋于一致.图7表明本文提出的算法信号灯切换的次数一直保持一个较低的数值,而OJF以及FTC算法随着车流量的增加,信号灯切换的次数迅速增加.

图6 三种算法调度时间的比较Fig.6 Comparison of scheduling time between three algorithms

图7 三种算法信号灯切换次数的比较Fig.7 Comparison of the switching times of traffic signal in three algorithms

5.1 较低车流量下FTS算法表现

图8比较了车流量在30%的情况下,三种算法的耗时.图8显示当车流量较小时,本文提出的FTS算法耗时基本上接近于OJF算法的一半,并且要优于在低车流量下表现良好的FTC算法.

5.2 较高车流量下FTS算法表现

图9比较了车流量在80%情况下,三种算法的耗时.图9显示即使改变了多种路况,在调度车辆耗时方面,我们提出的FTS算法还是要优于OJF算法以及FTC算法.虽然在车流量非常大时,三种算法调度车辆所花费的时间比较相近,但我们提出的FTS算法信号灯切换的次数要远远小于OJF以及FTC算法.

图8 车流量为30%时三种算法的比较Fig.8 Comparison of three algorithms when the traffic volume is 30%

图9 车流量为80%时三种算法的比较Fig.9 Comparison of three algorithms when the traffic volume is 80%

6 总结和展望

在日渐拥堵的城市环境中,高效的交通信号控制策略变得格外重要,不仅可以改善交通安全和提升运输效率,还可以减少能源的消耗并降低对环境的污染.本文首先提出了一种基于V2X的联合驾驶和变换车道模型,然后根据该模型预测出下一个时间段内检测区域的车辆数目,其次设计了一种基于图的高效的车辆调度算法,并证明其近似比为2.能够有效地提高交通运输效率,极大地减少了交通拥堵的时间.

实验结果表明:本文提出的FTS算法在车流量较小的情况下,调度完一个时间段内路口积攒的全部车辆所花费的时间仅占另外OJF算法的50%;在车流量较大时,我们提出的FTS算法调度车辆所消耗的时间也比另外两种算法更少.在信号灯的变化频率方面,无论车流量大小,我们提出的FTS算法调度完全部车辆,信号灯切换的次数要远远小于另外两种算法.

本文的研究是基于传统的十字路口,下一步我们将会考虑更加复杂的道路状况.对于多道直行路口的交通信号控制策略展开进一步的研究,并且会将深度强化学习应用到智能交通领域.