智能交通燈的調度算法研究

高巍巍

(黑龍江外國語學院 信息科學系, 哈爾濱 150025)

智能交通燈的調度算法研究

高巍巍

(黑龍江外國語學院 信息科學系, 哈爾濱 150025)

由于交通信號是保證道路十字路口安全駕駛的重要交通工具。各個交通流存在隊列延遲破壞并降低了交通順暢性，提出了一種智能的交通燈調度算法。該算法分析通行十字路口的各交通流的實時交通特征，同時又對各個交通燈的時相進行調度。通過減少信號十字路口的通行車輛的等待時間改善了交通順暢，并且提升每秒穿過十字路口的車輛數。該算法的性能并與其它算法進行不同模擬場景的對比實驗。實驗表明，該算法可縮短隊列延時，明顯提高了交通燈信號調度方案的交通流暢性，而且提高了每個信號十字路口的通行量。

交通燈； 調度算法； 城市交通仿真平臺； 車載自組網

0 引言

自80年代交通燈使用到現在，它一直負責調度、控制各個配置有信號燈周期調度系統的十字路口的交通流[1-3]。它們提供便于所有交通流共享道路十字路口的安全調度[4-7]。各十字路口的隊列延遲使交通流順暢性下降，降低了所有道路網絡范圍內的交通效率[8]。為能夠改善交通效率，已有多名學者提出能對交通燈進行時間設定的調度智能算法[9-10]。每個交通燈的最佳調度使得信號十字路口的通行車輛的延遲達到最小。

眾多學者已經對獨立的交通燈路口進行過研究，他們對交通燈時相的設定都是根據周邊車流的實時交通來進行[11]。各個交通燈的交通控制為不定序列時相周期，這個周期代表了將要穿過某個道路十字路口的各個交通流時間調度情況。對各個十字路口的序列時相周期進行調度時需要利用到這幾個參數如：車輛數、交通速度以及各交通流的交通量[12]。各十字路口的平均延遲越短通過量就越大，算法的調度效率就越高。

智能交通信號燈考慮了周邊的交通流量和道路十字路口的交通特性[13]，利用車輛的 Ad hoc 網絡技術開發智能化的交通信號燈控制算法有幾種，在過去的幾年里，提出的自適應的智能交通燈的機制一直采用車載自組織網絡(VANET)。krajzewicz等[14]基于車-車通訊開發了自適應交通信號控制系統。提出嵌入SUMO[15]仿真器中交通信號燈控制算法。該算法的目的是利用在交通燈前的堵塞長度作為輸入，并且在每個交叉路口減少排隊延遲。每個交通燈的嘗試采用調度算法解決檢測堵塞。此外，韋伯斯特[16]提出的一個交通信號燈實時控制算法。它利用網絡收集和匯總的車輛實時位置和速度信息，并且在每個交叉路口優化交通燈控制。

自適應交通信號控制算法(OAF)通過對每個交通燈調度不同的時相最優序列，以最大限度地降低交叉路口的延遲。在每個交通流中調度采用先來先服務的原則，數學分析和仿真實現已經證明算法的正確性。本文把交通信號作為一個作業調度問題，其中每個任務對應一個車輛。本文提出智能的交通燈調度。該算法的目的在于通過縮短在各個十字路口的等待延遲時間而擴大通過量。首先對交通密度最大的交通流進行調度，不得超過該路口時相允許的最大綠燈時間。然后將車流準備通行的那個信號十字路口區域定義為“等候區”。這個概念的提出是為了確保在不超出最大允許的綠燈時間范圍內平等共用十字路口。從實驗結果可知，本文算法與其它的調度算法相比縮短了每個交通燈位置的隊列延遲。而且，采用該算法后，每秒穿過信號十字路口的車流更多，通行量也更大。

1 交通燈路口

在分析本文算法及研究成果之前，首先說明獨立交通燈的定義及特征。獨立交通燈各自控制著各個路口的交通，不需要兼顧附近信號路口的情況。例如圖1，是一個典型的十字路口，它由八個交通流共享，每兩個交通流同時進行。十字路口的交通燈對不同時相序列進行控制和調度，同時顯示不同交通流之間的沖突情況。每個交通燈的時間變量如周期長度、時相、間隔分割和補償參數的設置都根據實時交通流特征來設定。表1提供了各信號十字路口的時間變量定義。

對不定順序時相或跳躍時相可適用的十字路口時相進行設置的所有選擇，如圖1所示。

圖1 十字路口相態的選擇

在一個典型的控制機制里，安裝工作一旦結束，就需要對每個交通燈的周期長度、時相長度以及時相的個數和順序長期進行設置。工程人員利用交通特征的所有相關統計數據來設置這些參數。

另一方面，引進交通感應控制系統來根據當前交通特征對各個時相的定時值進行控制。需要配置實時探測器對每個獨立的交通燈針對性開發出半感應以及全感應控制系統。一般情況下，應根據數學模型來對綠燈及同行間隔設定時間。這些操作要考慮的因素有交通速度、十字路口的容納能力和有序的交通流動情況，如表1所示。

表1 交通信號燈時間變量定義

車輛自組織技術能對各個信號十字路口的各種交通流的交通特征進行評估和報道,它是一種實時探測器。許多自適應智能交通調度算法被用來提升十字路口的通行量以及所有相關交通的順暢性。

2 智能交通燈調度算法

本節說明一種交通燈智能調度算法。此算法分析各信號十字路口周邊各段道路的實時交通特征。本文以一個典型的十字路口進行距離分析，如圖1所示。在本文算法中，十字路口被看作是一個由8個交通流共享的一個處理器。車輛在不同預測時間抵達十字路口，所以每個交通流就是一組連續的進程。每個進程包含綠燈時相范圍內穿過十字路口的一臺或多臺車輛。根據數據采集階段等候區車輛的數量(即各個交通流的交通密度)來確定各個進程的大小。

等候區是針對各個十字路口而設定的一個虛擬區域，如圖2所示。

圖2 交通燈等候區

各等候區的界限根據允許的最長綠燈時間來設定。等候區保證了相互競爭的交通流能平等共用十字路口。目的是將連續的進程分散到各個交通流。每臺通行的車輛和每個位置的交通燈均配備一臺無線收發器和GPS裝置。各獨立十字路口的智能交通燈定期發布等候區的界限數據。于是，通行的車輛就會注意到自己是否已進入等候區，而且根據當前位置判斷出自己處在哪個交通流。等候區界限內的通行車輛需將各交通流的實時交通特征傳達給對應位置的智能交通燈。

每個車輛在道路行駛周期性地廣播的基本數據(如位置、速度、方向、目的地等)。車輛會接收到來自周邊車輛的交通數據。根據每臺發送車輛的位置，接收車輛會做出判斷它們是否同時處在同一個交通流(同一個進程)。等候區內各交通流的交通密度di、交通速度si以及預計通行時間ti,可根據[17]求得。對于每個交通流，靠近交通燈最近的車輛負責將對應交通流的交通特征傳達給智能交通燈。任何進程里所有車輛通過交通燈所需要的時間(T)由公式1計算，得到式(1)。

(1)

其中，α是一個常數，指一個進程里聚集的各組車輛里速度第一的車輛的啟動延時；它的最佳值根據實際經驗來設定；Fd是進程離十字路口交通燈最遠的車輛與該交通燈之間的距離；位于交通燈與等候區(Lra)界限之間的這個距離要根據各交通流(Stf)的交通速度來設定。時間T的值應不超出允許的最長綠燈時間。數據采集過程中所有聚集在等候區的車輛應在綠燈切換之前能夠通行完畢。

對于含八個交通流的十字路口，對各個時相的定時周期都采取八種雙線程執行的做法是不可取的。這些時相包括：P15(1+5),P25(2+5),P16(1+6),P26(2+6),P37(3+7),P47(4+7),P38(3+8)和P48(4+8)，如圖1所示。

本文提出算法中，所有交通流的調度都是從最大密度(Max(di))開始的。根據十字路口與各個進程中距離最遠車輛之間的距離設定各時相時間。算法1統計出調度算法的所有序列時相。一個交通流經過十字路口，將交通密度及其對應的預計通行時間均設為0。智能交通燈從最大的密度開始循環對競爭的交通流進行調度直至所有交通流密度為0。然后，交通燈再對等候區所有交通的最新交通特征執行算法操作。

算法1：智能交通燈的調度算法(TLSA)

輸入：交通燈(TL), 等候區(RA),RA交通流i的交通密度(di)，RA所有車輛所需時間(ti)

輸出：計算RA中所有交通流di和ti

1 While TL中任意交通流di>0do

2 設j為交通流，最大交通密度dj

3 設i1和i2為模擬穿過交通十字路口的交流流量

4 Ifdi1>di2then

Pji1=schedule (j,i1);dj=0.0;di1=0.0;tj=0.0;ti1=0.0;

5 Else

Pji2=schedule (j,i2);dj=0.0;di2=0.0;tj=0.0;ti2=0.0;

6 IF結束

7 調整等候區內所有其它交通流tk；

8 While結束

在每個交通燈周期，從八個候選時相中選出四個來對所有交通流進行處理。TLSA提升了十字路口的通行量并縮短通行車輛的隊列延時。主要是第一個時相期間在各個交通流等候的車輛數減少的緣故。而且，每個綠燈時相過去后要對各個交通流的調度時間及時進行調整，從而后續時相通行車輛所等候的時間就會更少。根據各交通流距離最遠車輛的當前預計位置設置調整時間。該車輛的當前位置根據最近傳送數據以及交通流的交通速度進行估算。但是，如果該車輛的預計位置靠近十字路口，說明該個交通流等候區的所有探測車輛均在十字路口等候。這時，交通流的綠燈時間就主要根據排在最遠車輛之前的通行車輛數進行設定。

前面提到在各個調度時相，可設兩個交通流同時穿過十字路口。這時綠燈時間的設定要根據兩個進程交通流之間的最大預計設定通行時間來。算法2統計了各時相的時間調度函數。

算法2：各時相的時間調度函數

輸入：交通流量i和j

1 Ifti>tjthen

返回ti

2 Else

返回tj

3IF結束；

3 實驗分析和結果

本文算法采用城市交通仿真平臺(SUMO)制作幾個實驗場景。SUMO是由德國宇航中心開發的，微觀、連續的道路交通仿真架構和模型基礎.通過道路交通微觀仿真軟件包，可以處理大量的道路網絡。在這些場景中，通行車輛試圖穿過由獨立的智能交通信號燈控制一個十字路口。對各個場景使用不同的通行車輛數來研究交通密度的效果。

本文主要將TLSA與自適應交通信號控制機制(OAF)進行比較，得出本文算法在車載自組網(VANET)啟用的車輛感應控制、VANET啟用的Webster’s以及最優定時信號控制方面有很好的性能，能夠縮短每臺車輛的平均延時。

在實驗中，首先比較由于交通燈隊列延遲導致的車輛延時；然后對一定時間內在等候區準備通行十字路口的所有待檢測車輛的總延時進行比較；最后，計算十字路口每秒通行的車輛數來評估各個機制的通行量。表2給出了實驗的主要參數，如表2所示。

表2 仿真參數

TLSA與OAF方法的性能比較結果，如圖3所示。

(a) 交通燈上每輛車的延時

(b) 等待區通過交通燈的車輛的總延時

(c) 交通燈的吞吐量 圖3 OAF和TLSA的性能評估

對30個不同場景分別進行了實驗。每個實驗的置信區間是95%。圖3(a)是每臺車輛的平均延時對比結果，其中TLSA較之于OAF將每臺通行車輛的平均延時降低30%。說明采用TLSA后每臺車輛在十字路口的等候時間平均要減少30%。

對某一時間點要經過十字路口的所有待檢測車輛的總延時進行分析。TLSA得到的總延時要比OAF的減少25%，如圖3(b)所示。由圖3(a)和3(b)可知，在所有交通密度場景下，TLSA要比OAF使通行車輛的隊列延時減少25%。另一方面，圖3(c)比較了TLSA與OAF對交通燈信號時相進行調度后，交通十字路口的通行量情況。顯然，采用TLSA后每秒通過十字路口的車輛數比OAF的要多出30%，由于TLSA最大密度優先調度原理，將最長綠燈時相分配給在交通流密度最小的交通流，這樣能探測到密度最大而數量較少的車輛。

4 總結

本文提出了一種智能交通燈調度算法(TLSA)。該算法利用到車輛自組技術來收集周邊各交通流的實時交通特征。利用最大密度優先調度原理來對各交通燈周期的時相進行設置。將等候區定義在信號十字路口的附近區域，根據它可以判斷各個時相的最大許可時間，但這個時間不得超出最長綠燈時間。各個時相的實際時間要根據各個交通流進程位置最遠的車輛距離進行確定。通過實驗得出TLSA算法要優于OAF算法。采用該算法后，各個車輛通行信號十字路口的延時平均減少20%；同時它還將各十字路口的通行量提高了30%。

[1] 文孟飛. 城市智能交通系統交通流協同優化與誘導關鍵技術研究[D].長沙：中南大學,2013:23-34.

[2] 王彬. 基于車路協同技術的交叉口協調方法研究[D].北京：北京工業大學,2013:56-70.

[3] 折志偉. 城市交通系統路口車流量的最優化控制[D].河北科技大學,2010:12-34.

[4] 張永燦,黃海平,曹雍,王汝傳. 基于無線傳感網的智能交通燈自適應算法[J]. 計算機技術與發展,2015(2):199-203.

[5] 孫衛真,王秀錦,徐遠超. 交通信息分布式處理中的Hadoop調度算法優化[J]. 計算機工程與設計,2014(4):1269-1273.

[6] 許其清,朱煉,孫方南,朱袁峰. 多路口聯控智能交通燈的設計與實現[J]. 控制工程,2009(4):34-38.

[7] 馬駿,蔡延光,湯雅連,梁秉毅. 智能交通系統中車輛調度問題的自適應蟻群算法[J]. 北京聯合大學學報(自然科學版),2015(1):75-80.

[8] 李慧,郭愛煌. 交通信號的實時公平調度及其仿真[J]. 計算機應用,2012(4):1161-1164.

[9] Priemer C, Friedrich B. A Decentralized Adaptive Traffic Signal Control Using V2I Communication Datas, Intelligent Transportation Systems[C].the 12th International IEEE Conference,2009: 1-7.

[10] Barba C T, Mateos M A, Soto P R, et al. Smart City for VANETs Using Warning Messages, Traffic Statistics and Intelligent Traffic Lights[J]. IEEE Intelligent Vehicles Symposium, 2012, 6(20):902-907.

[11] Mirchandani P, Head L. A Real-time Traffic Signal Control System:Architecture, Algorithms, and Analysis, Transportation Research [J].Emerging Technologies.2001,6(9):415-432,

[12] Baskar L D, De Schutter B, Hellendoorn J, et al. Traffic Control and Intelligent Vehicle Highway Systems: A Survey[J].Intelligent Transport Systems,2011,5(1):38-52.

[13] Krajzewicz D, Erdmann J, Behrisch M, et al. Recent De-velopment and Applications of SUMO Simulation of Urban Mobility[J].International Journal on Advances in Systems and Measurements, 2012, 5(4):128-138.

[14] Gradinescu V, Gorgorin C, Diaconescu R, et al. Adaptive Traffic Lights Using Car-to-Car Communication[J].Vehicular Technology:2007,65(2):21-25.

[15] Behrisch M, Bieker L, Erdmann J, et al. SUMO Simulation of Urban Mobility[C]. The Third International Conference on Advances in System Simulation, Barcelona, Spain,2011:63-68.

[16] Pandit K, Ghosal D, Zhang H M, et al. Adaptive Traffic Signal Control With Vehicular Ad hoc Networks, Vehicular Technology[J].IEEE Transactions, 2013,42(4): 1459-1471.

[17] Bani Younes M, Boukerche A. Efficient Traffic Congestion Detection Protocol for Next Generation VANETs[C]. 2013 IEEE International Conference on Communications (ICC), 2013, 9(13): 3764-3768.

Research on Scheduling Algorithm of Intelligent Traffic Light

Gao Weiwei

(The Department of Information Science, Heilongjiang International University, Harbin 150025, China)

The traffic signal is essential to guarantee safe driving at road intersection. Queuing delay of traffic flow damages and reduces the smooth smoothness ness of traffic flow. This paper proposed a scheduling algorithm of intelligent traffic light control (TLSA). First, it analyzed the real-time traffic characteristics of the traffic flow in an intersection, and the each traffic light time was scheduled. Secondly, in the intersection the traffic flow becomes easy and smooth by reducing waiting time of vehicles, hence, the crossing number of vehicles increases in every second. Finally, we compare TLSA to previous algorithms in this field by simulating different scenarios. Experiments show that this algorithm can not only shorten the queuing delay and improve the traffic flow signal scheduling, but also improve the traffic capacity of each signal intersection.

Traffic lights； Scheduling algorithm； Simulation platform of city traffic； Vehicular ad hoc network

黑龍江省教育廳科學技術研究項目(12543076)

高巍巍(1976-)，女,漢,副教授,碩士, CCF會員，研究方向：人工智能應用.

1007-757X(2017)04-0020-04

TP301.6

A

2016.05.12)