城市交通流量預測與信號控制優(yōu)化

趙文天,萬夕里,白光偉

(南京工業(yè)大學 計算機科學與技術學院,南京 211816)

1 引 言

隨著國民經濟的快速發(fā)展以及城市規(guī)模不斷擴大,城市中的車輛變得越來越多,導致交通堵塞頻繁發(fā)生.目前,緩解城市交通壓力主要有兩類方法:一是降低交通需求;二是提高交通運輸效能[2].通過限牌等方法來降低交通需求雖然可以緩解城市交通壓力,但是該方法與城市出行需求之間構成沖突,不適合長期采用.目前第二種方法已經成為提高交通系統(tǒng)運輸效率的最主要手段.通過提前預測各個路口的車輛數(shù)量來實時變更信號燈時長,使得在一段時間內到達路口的所有車輛全部通過該路口的時間最短.

車載自組織網(wǎng)絡(Vehicular Ad-Hoc Network,VANET)是智能交通系統(tǒng)(Intelligent Traffic System,ITS)在過去十幾年中飛速發(fā)展的產物,把行駛的車輛看作移動節(jié)點,利用無線通信技術形成無線移動網(wǎng)絡[2].車與車/車與基礎設施(Vehicle-to-Vehicle/Vehicle-to-Infrastructure,V2V/V2I)之間可以通過無線信號進行實時的網(wǎng)絡通信.隨著通信技術的發(fā)展,車與外界信息交換(vehicle to everything,V2X)技術在車輛上的應用已成為必然趨勢,被認為在改善行車安全和減少事故中具有巨大的潛力.此外,它為改善交通和駕駛環(huán)境提供了技術支持[3].文獻[4]基于VANET的V2I通信,提出了一種在線交通信號燈控制算法OJF(Old Job First),并證明其在同類算法中是最優(yōu)的.但該在線算法在實際生活中很難應用,因為每當一輛車輛到達路口,信號控制系統(tǒng)就要根據(jù)在線算法變換信號燈,所以信號燈切換的次數(shù)會過于頻繁,這使得該算法不適合應用于道路擁堵場景下的信號燈控制.

文獻[5]提出了一個十字交叉路口附近車輛的協(xié)作優(yōu)化算法.該算法將相鄰交叉口區(qū)域的車輛劃分為若干排,并為同一排的第一輛車和其他車輛指定不同的駕駛策略,以提高交通系統(tǒng)的效率.該優(yōu)化算法是基于粒子群優(yōu)化(Particle Swarm Optimization,PSO)算法.由于PSO算法的時間復雜度較高,當系統(tǒng)中存在更多車輛時,需要花費較長的時間來解決問題,并且該算法對系統(tǒng)運行的硬件要求很高.

文獻[6,7]提出了兩個協(xié)調推動交叉路口附近車輛的優(yōu)化策略.文獻[6]提出了一種算法,該算法可以協(xié)調沒有交通信號的交叉路口區(qū)域的交通流沖突,但該算法假定車輛加速度從進入交通信號附近的點開始保持不變直至車輛離開沖突地區(qū).此外,文獻[7]假定車輛的加速度可以保持恒定且均勻的變化.但是由于城市道路條件復雜,交叉口附近的交通流量密度可能會發(fā)生較大變化.因此,這兩種模式的適用性是有限的.另外,車輛可能會在交叉路口轉彎,并在交通信號附近進行強制車道改變,然而這些研究并沒有考慮到車輛的車道變化.

在車道變化方面,許多學者進行了相關研究[8,9].這些研究大多集中在可選車道變換上,而且很少有人提出在交通信號附近強制變換車道.在車輛調度算法方面,文獻[4]提出了OJF算法,雖然證明了OJF算法在在線算法中是最優(yōu)的,但在線算法會導致信號燈切換頻繁,很難在實際中應用.文獻[16]提出了FTC(fixed-time signal control)算法,但是該算法被證明只能在車流量較低時具有較好的表現(xiàn).

針對上述問題,本文提出了一種基于V2X的聯(lián)合駕駛和變換車道模型,預測出一個時間段內各車道車輛的數(shù)目,充分利用V2X通信來提高區(qū)域交通系統(tǒng)的安全性和效率.在此模型的基礎上設計了一種基于圖的信號燈控制算法,有效減少了交通信號燈切換的次數(shù),并且能夠大幅提升交通運輸?shù)男?

本文第2節(jié)詳細介紹了基于V2X的交通流量預測模型;第3節(jié)詳細介紹了圖模型和基于本文交通模型提出的高效調度算法;第4節(jié)通過理論證明了我們提出算法的高效性;第5節(jié)通過實驗驗證并分析了我們提出算法的性能;第6節(jié)是本文的總結和對未來工作的展望.

2 基于V2X的交通流量預測模型設計

在交通信號燈附近,當一輛汽車跟隨另一輛汽車時,駕駛員必須注意前方汽車和交通信號燈的狀態(tài)來調整駕駛行為.假設當前信號燈為綠燈,如果車輛能夠在綠燈持續(xù)時間內通過沖突區(qū)域,如圖1所示.駕駛員通常選擇通過沖突區(qū)域跟隨前方車輛,并且車輛的速度受到前方車輛速度的影響.如果前方沒有車輛,司機可以按照理想的速度穿過沖突區(qū).如果紅燈亮起或黃光閃爍,司機通常會選擇放慢車速或者停車.

圖1 沖突域說明圖Fig.1 Illustration of conflict domain

在上述過程中,缺乏信息可能會導致很多問題.例如,由于判斷不準確,當車輛在沖突區(qū)域中移動并且無法立即停止時,信號燈可能會變?yōu)榧t燈,導致車輛的碰撞,這就是所謂的沖突區(qū)域[10],如圖1中陰影區(qū)域所示.另外,司機需要頻繁關注交通信號,因此他們往往會頻繁減速,導致行駛時間延長,燃油消耗增加以及道路擁堵[11].

然而在V2X環(huán)境中,司機可以隨時隨地獲得前方車輛和交通信號燈的狀態(tài),這為聯(lián)合駕駛創(chuàng)造了條件.司機提前獲取了交通信號燈的狀態(tài)信息并調節(jié)車輛速度,以適當?shù)乃俣韧ㄟ^沖突區(qū)域,避免了長時間停止.因此,本部分規(guī)劃了交通信號燈附近車輛的聯(lián)合駕駛和車道變換過程,以便提前確定駕駛軌跡和減少停車延誤,并預測出下一個時間段檢測區(qū)域內車輛的數(shù)目.

假設交通信號燈的周期是TC,綠燈和紅燈的持續(xù)時間分別為TG和TR,TC,TG和TR的關系如公式(1)所示:

TC=TG+TR

(1)

在t時刻,交通信號的狀態(tài)可以定義為公式(2):

(2)

其中tlight代表當前時間的交通信號周期,假設t時刻的車輛Vi的位置,速度和加速度分別為xi(t),vi(t)和ai(t),并且車輛運動符合以下的運動學方程:

(3)

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

(4)

上述k代表著時刻t之后所經過的時間間隔,文獻[12-14]提出了一種智能駕駛模型,可以描述道路上車輛的流動.此外,該模型具有很強的通用性,可以描述從自由流(車流速度不受限制)到沖突流(車流速度被限制)的不同流量.在該模型中,后續(xù)車輛的加速度如公式(5)所示:

(5)

(6)

當車輛Vi接近交通信號附近時,我們首先考慮它是否是檢測區(qū)域中的第一輛車.如果是,則在獲取交通信號燈信息之前,讓其以自由流量速度(最大速度或道路限速)駕駛.相應地,此時的加速度為0(已達到自由流速)或舒適加速度(尚未達到自由流速).如果不是,它將跟隨前方車輛,并且加速度可以由公式(5)和公式(6)確定.

為了避免停車,駕駛員需要在獲取交通信號燈信息之前提前計劃路線.圖2描述了車輛Vi在t0時接近交通信號燈.在圖2中,水平軸表示時間,垂直軸表示車輛與交通信號之間的距離.當Vi接近交通信號附近并進入V2X通信范圍時,假設交通信號具有固定的周期,那么車輛軌跡就被限制在區(qū)域1和區(qū)域3(因為車輛只能在綠燈周期內通過路口).如果Vi的平均速度滿足以下條件:

(7)

圖2 交通信號附近的車輛狀態(tài)Fig.2 State of vehicle near the traffic signal

(8)

圖3 車輛變換車道Fig.3 Vehicle changing lane

dLD(t)≥dmin+h1vi(t)

(9)

其中h1代表變換車道的時間,研究表明,車道變換過程的持續(xù)時間與車道變換速度稍有關系[15].在換線時間固定的情況下,換道車輛的橫向加速度和運動軌跡可用公式(10)、公式(11)描述

(10)

(11)

其中alat表示橫向加速度,H表示車道寬度,tlat表示車道變換的持續(xù)時間,ylat表示側向空間.當Vi從L0移動到車道LD時,跟隨的第一輛車從VLO逐漸過渡到VLD.根據(jù)Vi的橫向位移,其縱向加速度可由公式(12)得出:

(12)

(13)

(14)

基于上述的分析,車輛的速度和加速度需要符合上述公式才能安全變道并通過沖突區(qū)域.根據(jù)上述車輛模型,可以預測出下一個時間段內檢測區(qū)域的車輛數(shù)目,如公式(15)所示.本節(jié)更加真實地模擬了現(xiàn)實生活中車輛的運動模型,這為下文提出的車輛調度算法提供了基礎.

(15)

3 基于圖的車輛調度算法設計

本文的算法模型是基于一個典型的十字交叉路口,其結構如圖4(a)所示.圖4(a)展示了八種交通動作,其序號為1-8,其中右轉與直行將作為一種交通動作考慮(右轉與其他交通動作不沖突),這種十字路口是我們平時最常見的,也是比較易于研究的一種交通模型.這些交通動作之間會有沖突即不能共同執(zhí)行比如動作1和動作2,如果同時執(zhí)行動作1和動作2,必會造成交通路口的堵塞.

圖4 交通動作轉換圖Fig.4 Transition diagram of traffic movements

本文可以通過圖4(a)的八種交通動作建立一個沖突圖G(V,E),其中V代表的是一系列頂點,E代表的的是兩點之間的連線.每有一種動作種類就需要設立一個頂點,如果兩個動作之間有沖突(兩個動作不能同時執(zhí)行),那么就需要在這兩個頂點之間連接一條線.如圖4(b)所示,將圖4(a)這八種交通動作構建成一個沖突圖,每個結點代表一個交通動作,結點之間的連線代表他們不能同時執(zhí)行.

在文獻[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′也可以同時調度.

傳統(tǒng)的車輛在線調度算法[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′中暫存的車輛數(shù)量是根據(jù)公式(15)計算得到的.圖4(a)中展示的每一個交通動作所在的車道都存在如圖5所示的陰影區(qū)域(圖5只覆蓋了交通動作6),意在監(jiān)測車輛的行駛信息并將信息傳送到中心服務器進行計算.

圖5 FTS算法的應用場景Fig.5 Application of FTS algorithm

當車輛進入檢測范圍時,向路測單元RSU1發(fā)送駛入消息(Entering Message,EM),EM內容包括車輛的標識符、行駛車道、當前車速以及進入?yún)^(qū)域的時刻.當車輛駛出檢測區(qū)域時,向路測單元RSU2發(fā)送駛離消息(Leaving Message,LM),LM內容僅僅包含車輛的標識符.本文不考慮車輛類型,只計算車輛數(shù)目.RSU1接收到EM后,將信息傳輸?shù)街行姆掌?由中心服務器分析一個時間段內收到的EM消息,并且根據(jù)上一節(jié)的模型計算出下一個時間段監(jiān)控區(qū)域內車輛的數(shù)目;RSU2收到LM后,將信息傳輸?shù)街行姆掌?由中心服務器分析LM消息,并且刪除相應區(qū)域內的車輛.中心服務器根據(jù)下一個時間段路口的車輛信息以及本文提出的高效調度算法計算出信號燈的配時方案,并通過RSU2將配時方案發(fā)送給交通信號控制系統(tǒng),用于控制十字路口的信號燈時間分配.

4 算法性能分析

本節(jié)對本文提出的FTS算法進行性能分析,不僅證明了算法的近似比為2,還對算法的時間復雜度進行了分析.近似算法的定義為公式(16):

(16)

對于任何規(guī)模的輸入值n來說,由近似算法產生的解的代價C與最優(yōu)解的代價C*都只差一個因子ρ(n)(近似比，approximation ratio),那么則稱該算法為ρ(n)近似算法.

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

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

(17)

調度策略SALG所需要花費的時間如公式(18)所示:

(18)

所以本文提出的車輛調度算法的近似比為2.

定理2.FTS算法的時間復雜度為O(1).

證明:若圖4(c)中四個頂點的權值都不為0,那么將全部車輛調度完成所花費的時間一定是最多.然而按照本文提出的調度算法,調度完一個時間段內路口積攢的所有車輛只需要四步,所以本文提出的FTS算法基本語句執(zhí)行次數(shù)為一個常數(shù),其時間復雜度為O(1).

5 實驗與分析

本文采用的實驗模擬環(huán)境為Matlab,假設每一秒鐘到達各個節(jié)點的車輛數(shù)目最多為1.那么就可以隨機模擬出100s內四個節(jié)點的車輛積攢情況,如表1所示.本節(jié)根據(jù)不同的路況,通過三種算法分別調度,比較三者將一個時間段內的全部車輛調度完的時間以及信號燈切換的次數(shù).其中車流量代表的是道路的飽和程度,即當前監(jiān)控區(qū)域內的所有車輛占該路口可容納車輛最大值的百分比.

表1 模擬100s內的路口車輛信息
Table 1 Simulation of traffic information in 100s

節(jié)點10s20s30s40s50s60s70s80s90s100s總計100s內車輛數(shù)(1,2)806471347545(3,4)175236754242(5,6)942125274440(7,8)756324443644

在Matlab中隨機生成一個4X10,元素為0-10中隨機整數(shù)的矩陣作為函數(shù)的輸入.通過圖6,可以觀察到在車流量較小時,本文提出的FTS算法耗時要比FTC算法少,并且只有OJF算法的一半. 隨著車流量的不斷增加,本文提出的FTS算法耗時逐漸向OJF算法以及FTC算法逼近.這是因為當路口積攢的車輛過于飽和時,無論用什么方式調度,將這些車輛全部調度完的時間都趨于一致.圖7表明本文提出的算法信號燈切換的次數(shù)一直保持一個較低的數(shù)值,而OJF以及FTC算法隨著車流量的增加,信號燈切換的次數(shù)迅速增加.

圖6 三種算法調度時間的比較Fig.6 Comparison of scheduling time between three algorithms

圖7 三種算法信號燈切換次數(shù)的比較Fig.7 Comparison of the switching times of traffic signal in three algorithms

5.1 較低車流量下FTS算法表現(xiàn)

圖8比較了車流量在30%的情況下,三種算法的耗時.圖8顯示當車流量較小時,本文提出的FTS算法耗時基本上接近于OJF算法的一半,并且要優(yōu)于在低車流量下表現(xiàn)良好的FTC算法.

5.2 較高車流量下FTS算法表現(xiàn)

圖9比較了車流量在80%情況下,三種算法的耗時.圖9顯示即使改變了多種路況,在調度車輛耗時方面,我們提出的FTS算法還是要優(yōu)于OJF算法以及FTC算法.雖然在車流量非常大時,三種算法調度車輛所花費的時間比較相近,但我們提出的FTS算法信號燈切換的次數(shù)要遠遠小于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 總結和展望

在日漸擁堵的城市環(huán)境中,高效的交通信號控制策略變得格外重要,不僅可以改善交通安全和提升運輸效率,還可以減少能源的消耗并降低對環(huán)境的污染.本文首先提出了一種基于V2X的聯(lián)合駕駛和變換車道模型,然后根據(jù)該模型預測出下一個時間段內檢測區(qū)域的車輛數(shù)目,其次設計了一種基于圖的高效的車輛調度算法,并證明其近似比為2.能夠有效地提高交通運輸效率,極大地減少了交通擁堵的時間.

實驗結果表明:本文提出的FTS算法在車流量較小的情況下,調度完一個時間段內路口積攢的全部車輛所花費的時間僅占另外OJF算法的50%;在車流量較大時,我們提出的FTS算法調度車輛所消耗的時間也比另外兩種算法更少.在信號燈的變化頻率方面,無論車流量大小,我們提出的FTS算法調度完全部車輛,信號燈切換的次數(shù)要遠遠小于另外兩種算法.

本文的研究是基于傳統(tǒng)的十字路口,下一步我們將會考慮更加復雜的道路狀況.對于多道直行路口的交通信號控制策略展開進一步的研究,并且會將深度強化學習應用到智能交通領域.