路 婷,貝曉旭,劉桂云*
(1.寧波大學(xué)海運學(xué)院,浙江寧波315200;2.德國宇航中心(DLR)交通系統(tǒng)研究所,柏林12489,德國)
隨著經(jīng)濟(jì)的增長及城市規(guī)模的不斷擴大,中國及其他發(fā)展中國家的機動車擁有量大幅增加,給城市交通控制系統(tǒng)帶來嚴(yán)峻的挑戰(zhàn).據(jù)公安部道路交管局發(fā)布的消息,截止2017年6月,中國機動車保有量已經(jīng)達(dá)到3.04億,年增長率超過10%,超過百萬汽車保有量的城市有52個,其中6個城市超過300萬.這要求交通管理者不僅要關(guān)注點的效率的提升,提升路口的通行效率;同時也要從路網(wǎng)的角度來做均衡的調(diào)控,對整個路網(wǎng)的交通進(jìn)行均衡疏導(dǎo).因此,從整個路網(wǎng)的角度出發(fā),研究路網(wǎng)內(nèi)的交通運行規(guī)律,協(xié)調(diào)交通信號控制,提升交通控制的效率,是一個重要且亟待解決的問題.
對于路網(wǎng)交通信號協(xié)調(diào)優(yōu)化和均衡疏導(dǎo),研究人員多采用雙層規(guī)劃的方法,將信號控制參數(shù)優(yōu)化和出行者路徑選擇結(jié)合,迭代優(yōu)化,如Chiou的雙層規(guī)劃模型[1-2].考慮到路網(wǎng)中不同區(qū)域間的交通流可能存在較強的關(guān)聯(lián)性,當(dāng)采取某種控制策略后,擁堵有可能轉(zhuǎn)移至相鄰區(qū)域,Dahal設(shè)計了控制策略表和預(yù)測的相鄰區(qū)域交通狀況變化情況,提出了基于智能體協(xié)作的智能交通控制決策支持系統(tǒng)[3].Abu等考慮了交叉口信號控制與路段交通流的相互影響,建立了輕度擁堵情況下的路網(wǎng)輸出量約束[4].Daganzo等研究了均質(zhì)路網(wǎng)內(nèi)宏觀基本圖與信號控制的關(guān)系,發(fā)現(xiàn)信號控制能夠均衡路網(wǎng)內(nèi)交通負(fù)荷,使得宏觀基本圖中平均流量臨界值最大[5].Keyvan等根據(jù)宏觀基本圖所展示的交通流演化模型設(shè)計了邊界門控制算法,當(dāng)預(yù)計區(qū)域交通流密度超過臨界密度閾值時啟動門控制,限制從邊界駛?cè)霌頂D區(qū)域的車輛數(shù)[6].Yan等提出異質(zhì)路網(wǎng)內(nèi)車輛密度的分布越均勻路網(wǎng)通行能力越大,設(shè)計了自適應(yīng)信號控制規(guī)則來均衡交叉口4個交口方向的排隊長度,并用迭代學(xué)習(xí)控制理論來實現(xiàn)控制方案與交通環(huán)境的交互[7].
由于路網(wǎng)信號控制涉及大規(guī)模路網(wǎng)單元上的交通流的動態(tài)傳播和控制,這些優(yōu)化控制方法都在一定程度上被證實可以改進(jìn)交通控制效益,但也存在一些缺陷,例如信號控制方案無法主動引導(dǎo)交通狀態(tài)的演變,無法避免交通流陷入擁堵狀態(tài).另外,優(yōu)化結(jié)果的可靠性和魯棒性與優(yōu)化時間有很大的正相關(guān)性,尤其是在處理大型路網(wǎng)時,優(yōu)化結(jié)果常常限于局部最優(yōu)解,優(yōu)化時間過慢而無法用于實時信號優(yōu)化控制策略.鑒于此,本文的研究試圖從路網(wǎng)拓?fù)浣Y(jié)構(gòu)入手,分析交叉口(節(jié)點)之間的相互影響關(guān)系,確定能夠表征交叉口節(jié)點相互影響的交通流參數(shù),建立以拓?fù)浣Y(jié)構(gòu)為基礎(chǔ)的交叉口重要度估計模型,進(jìn)而以交叉口重要度排序得到的信號協(xié)調(diào)優(yōu)先順序為依據(jù),從全局的角度建立一種均衡疏導(dǎo)路網(wǎng)交通流的信號協(xié)調(diào)控制方法.
路網(wǎng)拓?fù)浣Y(jié)構(gòu)是指交叉口在路網(wǎng)中的位置及交叉口內(nèi)在組成方式所決定的結(jié)構(gòu)特征屬性.國內(nèi)外研究者主要通過建立交叉口關(guān)聯(lián)度模型分析交叉口之前的相互作用關(guān)系.交叉口關(guān)聯(lián)首先是指物理關(guān)聯(lián)特征,即道路交叉口的網(wǎng)絡(luò)拓?fù)湫问?,如交叉口間的距離是否相鄰等;其次是指交通關(guān)聯(lián)特征,即連線或節(jié)點間的交通流參數(shù)的關(guān)聯(lián)程度.
對于單個交叉口,飽和度最高,亦或是流量最大,亦或是車道數(shù)最多的交叉口往往被認(rèn)為是最關(guān)鍵的交叉口.然而,這種簡單的貪婪算法只能反映交叉口本身的交通狀況,而不能反映它和其他交叉口之間的相互影響及它在整個路網(wǎng)內(nèi)重要程度.由交通擁堵的時空傳遞現(xiàn)象可知,交叉口的重要度不僅與其本身重要度有關(guān),還應(yīng)該與其相鄰交叉口的數(shù)量及重要度有關(guān),此特征的研究在Saeedmanesh[8]的文章中也被證實.因此,首先要定義1個交叉口重要度指數(shù),該指數(shù)將沿道路隨交通流傳遞.
基于此思想,令r表示交叉口的重要度指數(shù);b表示相鄰交叉口重要度之間的關(guān)聯(lián)性;ri和rj表示交叉口i和j的重要度指數(shù);Ui表示交叉口i的上游交叉口的集合;bij表示交叉口j的重要度對交叉口i的重要度的關(guān)聯(lián)性.由分析可知,交叉口i的重要度可以表示為其所有的相鄰上游交叉口的重要度(rj,j∈Ui)與其作用于交叉口i的重要度的關(guān)聯(lián)性的乘積之和,即
若路網(wǎng)中有n個交叉口,則構(gòu)成1個n維方程組,該方程組的解就是交叉口的重要度值.ri也可以理解為某個交叉口具有某優(yōu)先順序的概率.寫成矩陣乘積的形式為
這里交叉口重要度關(guān)聯(lián)性構(gòu)成1個n×n的矩陣B,交叉口重要度指數(shù)構(gòu)成1個的非零列向量R.若交叉口i和交叉口j是相鄰交叉口且有交通流從j運動到i,那么矩陣的第i行第j列的元素是bij>0;若交叉口i和交叉口j不是相鄰交叉口或者沒有交通流從j運動到i,那么bij=0.此外,應(yīng)該注意到相鄰交叉口的重要度的關(guān)聯(lián)性與交叉口之間的距離有關(guān),若交叉口之間的距離過大,那么它們被認(rèn)為不具有連通性.因此,設(shè)置1個距離臨界值,若交叉口i和交叉口j之間的距離大于該臨界值,其對應(yīng)的關(guān)聯(lián)性矩陣元素值為0,即bij=0,bji=0.矩陣B的主對角線的元素是0,且矩陣B是奇異矩陣.
道路飽和度,即交通量和道路通行能力之比,是反映道路擁堵狀況的重要參數(shù)之一,越是擁堵的路段應(yīng)該越早被疏散,以免造成大面積交通癱瘓.因此,我們用道路飽和度作為矩陣B的元素值,反映交叉口之間的關(guān)聯(lián)性.雖然交通流量也可反映交叉口和交叉口之間交通流的運動狀況,但是,經(jīng)過試驗發(fā)現(xiàn)以交通流量作為關(guān)聯(lián)度矩陣的元素而求得的重要度排序結(jié)果并不能產(chǎn)生最優(yōu)的控制效益指標(biāo).如果路段有多條車道且不同的車道由不同的信號相位控制,以各車道的飽和度之和作為該路段的飽和度,即
式中:Lij表示從交叉口j到交叉口i的車道集合;xij,l表示車道l的飽和度,其中l(wèi)∈Lij;xij表示從交叉口j到交叉口i的路段的飽和度.
由于關(guān)聯(lián)性矩陣B是1個奇異矩陣,所以,用其主特征向量作為R的求解結(jié)果.主特征向量可用乘冪法(Power Method)得到,乘冪法的求解過程如下:
(1)選擇1個初始向量R()0,設(shè)k=0;
(3)設(shè)置一個最小值ε,并重復(fù)運算第(2)步求解R()k+1和R()k,直到兩者之差的絕對值小于該最小值,即,在本文的算例中,ε被設(shè)為10-7;
(4)第(3)步中求得的向量R()k即是主特征向量的近似值,R*=R()k.
乘冪法在只有一個主特征值的情況下是有效的.主特征向量R*的元素值即是交叉口的重要度指數(shù)值,對其進(jìn)行降序排序,便得到了交叉口信號優(yōu)化順序.若主特征向量的所有元素都為負(fù)值,先進(jìn)行歸一化運算再排序.初始向量R(0)對于收斂結(jié)果無影響,因此,可以假定所有交叉口具有相同重要度指數(shù),即
經(jīng)過1.1節(jié)的計算,整個路網(wǎng)可以用一個節(jié)點具有優(yōu)先屬性的有向圖表示,即路網(wǎng)拓?fù)浣Y(jié)構(gòu)圖,如圖1所示.圖1(a)是路網(wǎng)構(gòu)成,其中交叉口3、5、8是無信號交叉口,其他交叉口是信號交叉口.交叉口之間的路段長0.4 km,假設(shè)相鄰交叉口連通性的臨界距離是0.8 km,則該路網(wǎng)的拓?fù)浣Y(jié)構(gòu)圖如圖1(b)所示.圖1(b)中,節(jié)點數(shù)字代表對應(yīng)信號交叉口按重要度的排序值,1表示該交叉口的重要度最高,優(yōu)先順序為1,以此類推.
圖1 示例路網(wǎng)及其有向圖Fig.1 Example road network configuration and its topological graph
深度優(yōu)先搜索算法(Depth-First-Search,DFS)是圖論中的經(jīng)典算法,是一種用于遍歷或搜索樹或圖的算法.沿著樹的深度遍歷樹的節(jié)點,當(dāng)節(jié)點所在邊都已被探尋過,搜索將回溯到發(fā)現(xiàn)節(jié)點的那條邊的起始節(jié)點,這一過程一直進(jìn)行到已發(fā)現(xiàn)從源節(jié)點可達(dá)的所有節(jié)點為止,如果還存在未被發(fā)現(xiàn)的節(jié)點,則選擇其中一個作為源節(jié)點并重復(fù)以上過程,整個進(jìn)程反復(fù)進(jìn)行直到所有節(jié)點都被訪問為止.本文中的信號協(xié)調(diào)方法利用深度優(yōu)先搜索算法的思想,從最重要的交叉口開始,對當(dāng)前交叉口和其相鄰交叉口進(jìn)行協(xié)調(diào)優(yōu)化,直至所有的交叉口都被優(yōu)化完畢.若有多個控制區(qū)域,則先對區(qū)域內(nèi)的交叉口進(jìn)行協(xié)調(diào)優(yōu)化,再優(yōu)化相鄰區(qū)域的邊界交叉口的信號.在信號優(yōu)化時,首先,要確定控制區(qū)域的公共周期;其次,利用等飽和度模型等計算信號交叉口各相位的綠燈時長;最后,協(xié)調(diào)相鄰交叉口確定最佳相位差,具體步驟如下:
Step 1搜索優(yōu)先順序為k()1≤k≤n的節(jié)點,n是有向圖中節(jié)點的總數(shù),此時的目標(biāo)搜索節(jié)點,用Ik表示,在有向圖找到該節(jié)點的相鄰節(jié)點中未被協(xié)調(diào)的節(jié)點,按照未被協(xié)調(diào)的相鄰節(jié)點的重要度排序依序協(xié)調(diào)這些相鄰節(jié)點與目標(biāo)搜索節(jié)點,求解每一對協(xié)調(diào)交叉口的最佳相對相位差,并轉(zhuǎn)換為最佳絕對相位差.在這個過程中可能出現(xiàn)的情況有:
(1)目標(biāo)搜索節(jié)點的相位差未被優(yōu)化確定,也就是說目標(biāo)搜索節(jié)點之前未與任何節(jié)點進(jìn)行協(xié)調(diào)控制.這種條件下,有3種可能的情況:
①該目標(biāo)搜索節(jié)點的所有相鄰節(jié)點Uk,它們的相位差都未被優(yōu)化確定,那么,令目標(biāo)搜索節(jié)點的相位差為0,即φk=0,按照相鄰節(jié)點的優(yōu)先順序依次協(xié)調(diào)交叉口對,求得它們的最佳相對相位差φk,j,j∈Uk,再求得所有相鄰節(jié)點的最佳絕對相位差φj,φj=φk,j+φk.
②該目標(biāo)搜索節(jié)點的所有相鄰節(jié)點的相位差已被優(yōu)化確定,那么,找到這些已被協(xié)調(diào)的相鄰節(jié)點中優(yōu)先順序最高的節(jié)點(假設(shè)節(jié)點m),協(xié)調(diào)該節(jié)點Im與目標(biāo)搜索節(jié)點Ik,求得它們的最佳相對相位差是φk,m,再求得目標(biāo)搜索節(jié)點的絕對最佳相位差φk,φk=φm-φk,m.
③該搜索節(jié)點的部分相鄰節(jié)點的相位差已被優(yōu)化確定,部分相鄰節(jié)點的相位差未被優(yōu)化確定,那么,先根據(jù)步驟②的方法求出目標(biāo)搜索節(jié)點的最佳相位差,再根據(jù)步驟①的方法協(xié)調(diào)目標(biāo)搜索節(jié)點和其未被協(xié)調(diào)的相鄰節(jié)點,求得相鄰節(jié)點的最佳相位差.
(2)目標(biāo)搜索節(jié)點的相位差已被優(yōu)化確定,也就是說目標(biāo)搜索節(jié)點之前已經(jīng)與某一節(jié)點進(jìn)行協(xié)調(diào)控制.這種條件下,也有3種情況:
①該目標(biāo)搜索節(jié)點的所有相鄰節(jié)點的相位差都未被優(yōu)化確定,那么,協(xié)調(diào)該目標(biāo)搜索節(jié)點Ik與其相鄰節(jié)點j(j∈Uk),求得它們的最佳相對相位差是φk,j,根據(jù)φj=φk,j+φk,求得相鄰節(jié)點的最佳絕對相位是φj.
②該搜索節(jié)點的所有相鄰節(jié)點的相位差已被優(yōu)化確定,說明該目標(biāo)節(jié)點無需再被協(xié)調(diào),那么,將優(yōu)先順序加1,更新目標(biāo)節(jié)點到下一優(yōu)先順序k+1,重復(fù)Step1.
③該搜索節(jié)點的部分相鄰節(jié)點的相位差已被優(yōu)化確定,部分相鄰節(jié)點的相位差未被優(yōu)化確定,那么,根據(jù)步驟(2)中①的方法協(xié)調(diào)目標(biāo)搜索節(jié)點和其未被協(xié)調(diào)的相鄰節(jié)點,求得相鄰節(jié)點的最佳相位差.
Step 2重復(fù)Step1的搜索與計算直至所有交叉口都被協(xié)調(diào)并求得最佳相位差.整個信號協(xié)調(diào)過程如流程圖2所示.
以圖1路網(wǎng)為例,交叉口4的優(yōu)先順序是1,則它的相位差為0,與其相鄰交叉口的優(yōu)先順序分別是2、3、4和6.那么,協(xié)調(diào)優(yōu)先順序為1的交叉口I1和優(yōu)先順序為2的交叉口I2,得到I2的最佳相位差φ2,如圖3(a)所示;協(xié)調(diào)I1和優(yōu)先順序為3的交叉口I3,得到I3的最佳相位差φ3,如圖3(b)所示;協(xié)調(diào)I1和優(yōu)先順序為4的交叉口I4,得到I4的最佳相位差φ4,如圖3(c)所示;協(xié)調(diào)I1和優(yōu)先順序為6的交叉口I6,得到I6的最佳相位差φ6,如圖3(d).此時,I1的所有相鄰交叉口都已求得了最佳相位差.找到優(yōu)先順序為2的交叉口I2,此時I2是目標(biāo)搜索節(jié)點.由于I2及其相鄰節(jié)點都已經(jīng)有最佳相位差,因此,優(yōu)先順序加1,更新目標(biāo)搜索節(jié)點為優(yōu)先順序為3的交叉口I3.此節(jié)點已有最佳相位差,判斷其相鄰節(jié)點I1、I2、I5,其中I1和I2最佳相位差已確定,I5的最佳相位差未確定,那么,協(xié)調(diào)I3和I5,求得I5的最佳相位差φ5,如圖3(e)所示.圖中粗虛線代表即將要協(xié)調(diào)的路段,粗實線代表已經(jīng)協(xié)調(diào)的路段.
圖2 信號協(xié)調(diào)控制流程圖Fig.2 Signal coordination control flow chart
圖3 示例路網(wǎng)的信號協(xié)調(diào)過程Fig.3 Traffic signal coordination process of example road network
基于上述研究成果,本文以德國Braunschweig市的部分交叉口為實驗對象,在Matlab中編程重要度估計模型和信號協(xié)調(diào)控制算法,在仿真軟件Simulation of Urban MObility(SUMO)中搭建路網(wǎng)并仿真,對比分析本文方法的有效性.
實驗路網(wǎng)由沿Sackring到Frankfurter Strasse的9個信號交叉口組成,如圖4所示.
圖4 實驗路網(wǎng)Fig.4 Test road network
圖4路網(wǎng)中交叉口的信號相位相序來自于信號機公司西門子的報告,如圖5所示.每個相位的最小綠燈時間是6 s,損失時間是4 s.
我們仿真了1天中6:00-20:00的交通流運行情況,信號配時方案每30 min優(yōu)化1次.首先,根據(jù)交叉口重要度估計模型求解出交叉口的重要度,并對其排序得到交叉口的優(yōu)先順序.由結(jié)果可知,優(yōu)先順序在不同的日期大體相似,第1位優(yōu)先順序幾乎總是出現(xiàn)在交叉口4,第2位和第3位優(yōu)先順序總是出現(xiàn)在交叉口5和交叉口6,第4位優(yōu)先順序總是出現(xiàn)在交叉口3,第5、6位優(yōu)先順序大部分時間出現(xiàn)在交叉口7和交叉口2,最后兩位優(yōu)先順序總是出現(xiàn)在交叉口8和9.根據(jù)信號協(xié)調(diào)控制方法,優(yōu)先順序越前的交叉口在協(xié)調(diào)時越具有優(yōu)勢,也就是說交叉口4、5、6具有更加重要的決定作用,尤其是交叉口4.由以上結(jié)果也可看出,越是處在中心位置的交叉口具有越高的優(yōu)先順序.
圖5 實驗路網(wǎng)內(nèi)交叉口的信號相位Fig.5 Phase configuration of intersections in test network
其次,在SUMO中仿真本文的協(xié)調(diào)控制方法優(yōu)化出的信號配時方案和Synchro 7優(yōu)化后的信號配時方案,并以車均延誤作為效益評價指標(biāo),其結(jié)果如圖6所示.由圖6可知,在2種方法下,車均延誤的趨勢具有相似性,且本文方法優(yōu)化的信號配時方案下的車均延誤在所有時間都是最小的.與Synchro7優(yōu)化的信號配時方案相比,車均延誤最少減少2.1%,最多減少達(dá)20.8%,平均減少11.9%.
圖6 不同方法下的車均延誤Fig.6 Mean delay per vehicle by different methods
隨著城市路網(wǎng)規(guī)模的不斷擴大,從路網(wǎng)的角度研究交通運行規(guī)律特征,對整個路網(wǎng)的交通流均衡疏導(dǎo)是一個趨勢.本文分析了交叉口之間的交通關(guān)聯(lián)性和路網(wǎng)拓?fù)浣Y(jié)構(gòu),建立了交叉口重要度估計模型,并基于有向深度搜索算法設(shè)計了區(qū)域信號協(xié)調(diào)優(yōu)化方法.最后,以Braunschweig的交叉口作為實驗路網(wǎng),通過微觀仿真對所提出的信號協(xié)調(diào)控制方法進(jìn)行效益評價,仿真結(jié)果證明本文提出的方法有效地改進(jìn)了交通控制效益.
參考文獻(xiàn):
[1]CHIOU S W.An efficient algorithm for optimal design of area traffic control with network flows[J].Applied Mathematical Modelling,2009,33(6):2710-2722.
[2]CHIOU S W.Joint optimization for area traffic control and network flow[J].Computers&Operations Research,2005,32(11):2821-2841.
[3]KESHAV DAHAL,KHALED ALMEJALLI,ALAMGIR HOSSAIN M.Decision support for coordinated road traffic control actions[J].Decision Support Systems,2013,54(2):962-975.
[4]ABU-LEBDEH G,CHEN H,BENEKOHAL R F.Modeling traffic output for design of dynamic multicycle control in congested conditions[J].Journal of Intelligent Transportation Systems,2007,11(1):25-40.
[5]DAGANZO C F,GEROLIMINIS N.An analytical approximation for the macroscopic fundamental diagram of urban traffic[J].Transportation Research Part B:Methodological,2008,42(9):771-781.
[6]KEYVANEKBATANI M,PAPAGEORGIOUM,PAPAMICHAIL I.Urban congestion gating control based on reduced operational network fundamental diagrams[J].Transportation Research Part C:Emerging Technologies,2013(33):74-87.
[7]YAN F,TIAN F,SHI Z.An extended signal control strategy for urban network traffic flow[J].Physica A:Statistical Mechanics and its Applications,2016(445):117-127.
[8]MOHAMMADREZA SAEEDMANESH,NIKOLAS GEROLIMINIS.Clustering of heterogeneous networks with directional flows based on“Snake”similarities[J].Transportation Research Part B:Methodological,2016(91):250-269.