基于故障傳播有向圖的交通擁堵傳播研究?

梁坤,孫莉,羅建鋒,戴權

(1.淮陰工學院管理工程學院,江蘇淮安 223003;2.淮陰工學院研究生處,江蘇淮安 223003)

?

基于故障傳播有向圖的交通擁堵傳播研究?

梁坤1,孫莉2,羅建鋒1,戴權1

(1.淮陰工學院管理工程學院,江蘇淮安 223003;2.淮陰工學院研究生處,江蘇淮安 223003)

摘要:城市交通擁堵已成為亟需解的城市發展中的重大問題。文中將故障傳播有向圖方法應用于交通擁堵傳播研究,提出了交通擁堵傳播有向圖模型和基于該模型的擁堵傳播推理方法,并進行了基于K均值聚類的交叉口擁堵識別,為研究城市交通擁堵傳播規律提供參考。

關鍵詞:城市交通;交通擁堵;擁堵傳播;有向圖;交叉口;擁堵識別

近些年來,隨著經濟的快速發展和城市化、機動化的加快,交通需求增長和城市交通供給不足的矛盾不斷擴大,中國城市普遍出現了交通擁堵問題。交通擁堵造成出行者出行成本增加、交通事故、空氣和噪音污染等,嚴重影響城市的可持續發展,交通擁堵的緩解和預防成為城市迫切需要解決的難題之一。目前,人們對于城市道路交通擁堵傳播規律缺乏足夠、準確的認識,這導致交通擁堵的治理多采用事后疏導策略,實際緩解交通擁堵過程中存在一定的盲目性,缺乏有效的緩解與預防手段。物聯網、智能交通和信息技術的不斷發展為研究城市道路交通擁堵成因和傳播規律提供了必要的實時交通數據條件,這使交通擁堵主動治理成為可能。交通擁堵傳播規律的認識是主動交通擁堵治理的前提之一。

目前國內外對交通擁堵傳播進行了一些研究:李樹彬等運用改進的中觀交通流模型研究了網絡拓撲結構對交通擁堵的影響,分析了復雜網絡上的交通傳播動力學特征和傳播規律;潘捷、龍建成等利用元胞傳輸模型研究了由突發性事件引起的交通擁堵傳播特性;高自友應用微觀與宏觀相結合的方法建立了擁堵傳播模型;謝琛等利用雙隨機轉移矩陣提出了一個流量分配模型,并從級聯反應角度分析了擁堵現象的傳播過程;Shu-bin Li等利用雙向網格對交通擁堵傳播進行了分析;曾宇懷研究了基于有向圖的城市交通堵塞模型;袁紹欣利用傳染病模型分析了城市交通擁堵傳播機理及其控制策略。從國內外現有研究成果來看,交通擁擠傳播研究還處于起步階段,盡管相關研究已經積極開展,但理論方法還有待進一步豐富和深入。

故障傳播有向圖方法在機械復雜系統的故障診斷中已被成功使用,并取得了良好效果。交通擁堵傳播和機械復雜系統中部件故障影響傳播存在一定的類似,故將故障傳播有向圖方法應用于城市道路擁堵傳播研究,以準確認知城市交通擁堵傳播規律,為城市交通擁堵的疏散和治理提供參考依據。

1 交通擁堵傳播有向圖模型

將城市交通路網視為一個大規模的提供給交通參與者的服務生產系統,其中各交叉口之間、路段之間及路段和交叉口的交通流量之間相互關聯。在一個交叉口或路段的交通擁堵(即交叉口或路段故障)迅速傳播到其他交叉口或路段的過程中,相應的交叉口和路段將產生大量交通流特征參數(流量、密度和速度等)的異常信息。交通擁堵傳播推理系統必須利用這些信息產生一個精確的診斷結果,交通擁堵(故障)傳播模型是表達交通系統擁堵動態傳播的簡單和有效的方法。使用兩個交叉口之間的擁堵傳播概率和時間間隔表示交通系統的動態特性。當出現交通擁堵征兆時,通過從擁堵報警開始反向搜索確定擁堵傳播路徑,同時使用交通波理論從擁堵源開始用于預報將要發生的擁堵路段和交叉口。

擁堵(故障)傳播有向圖可用于表示擁堵(故障)傳播關系。交通擁堵傳播有向圖定義為TCPSDG ={V,E,D,Γ,Υ},其中:

(1)V節點集,且V≠0,表示路網中的交叉口。

(2)有向邊集合E=(V×V),表示交叉口間的關聯關系、反映路段上交通流信息,“關系對”分別表示每一路段的起始交叉口和終止交叉口,記為:

?+:E→V(路段的起始交叉口)

?-:E→V(路段的終止交叉口)

(3)D表示路網上的路段和交叉口采集的交通信息(流量、車速、檢測器占有率等)。

(4)函數Γ:E→{+,0},其中Γ(ei)(ei∈E)稱為路段的符號。用“+”表示擁堵在路段ei傳播、“0”表示擁堵在路段ei不傳播。

(5)函數Υ:v→{1,0,?}(?表示無采集交通信息交叉口),表示交叉口vj的交通狀態:

式中:X為交叉口vj對應檢測的交通特征值即流量、車速、檢測器占有率等;ε為交叉口vj交通運行正常狀態的閾值。

2 擁堵傳播的推理

基于TCPSDG模型的故障傳播推理是基于TCPSDG模型中的主要要素Υ(vj)的狀態估算實現的,步驟如下:

(1)針對初始Υ(vj)的狀態進行判斷,分析潛在交通擁堵傳播的路徑集合。交通擁堵在路網上通過相容通道才能進行傳播。在有向圖SDG模型中,如果Υ(?+ei)Γ(ei)Υ(?-ei)=+,則該支路ei稱為相容,由相容支路組成的路徑稱為相容通路。所以交通擁堵傳播路徑研究的是SDG圖的最大相容子圖,由有效節點和相容通路描述擁堵的傳遞關系。

(2)根據交叉口或路段當前檢測信息估計的交通狀態,分為交通運行暢通交叉口節點集合VN、擁堵交叉口節點集合VC。

(3)從檢測的擁堵節點出發,沿交通流方向回溯,對其經過的路段ei,若Υ(?+ei)Γ(ei)Υ(?-ei)=0,則該路徑不相容。將不相容路徑截斷,即構成最大相容子圖。該最大相容子圖即為交通擁堵傳播路徑。

3 交叉口擁堵識別

隨著智能交通的發展,城市路網上布置的交通檢測器越來越多,為城市道路交叉口交通狀態識別提供了大量交通數據。運用無監督的K均值自動聚類技術,將道路交叉口交通擁堵狀態看成一個特殊的分類問題,實現城市交叉口交通擁堵狀態判別,得出Υ(vj)值,然后根據擁堵傳播的推理即可得到擁堵傳播路徑。

3.1 聚類特征參數

國內外對于交通狀態的識別進行了一些研究。20世紀60年代美國加利福尼亞州運輸部開發的加州算法采用檢測截面占有率進行交通狀態識別;校準偏差算法采用交通量或占有率判別交通狀態;雙指數平滑算法采用速度、流量、占有率和密度三者之一進行交通擁堵判別;由加拿大Mc Master大學土木工程系開發的Mc Master算法采用速度和占有率識別交通狀態。這里根據數據采集的方便性和可行性,選用速度、流量和占有率(時間占有率)作為交叉口聚類參數。

3.2 數據的采集與處理

如圖1所示,采集各入口的速度、流量和占有率;vj表示第j個交叉口,vjn(n=1,2,…)表示第n個入口方向,vjns、vjnv、vjno分別表示j交叉口n入口的速度、流量和占有率;采集位置在離交叉口100 m處。對于信號控制交叉口,vjns、vjnv、vjno選用檢測時刻t的前5個信號周期長度T內檢測到的vjns、vjnv、vjno均值作為交叉口交通狀態相似度的特征參數;對于非信號控制交叉口,采用檢測時刻t的前5 min內檢測到的vjns、vjnv、vjno均值作為交叉口交通狀態相似度的特征參數。

圖1 交叉口數據采集示意圖(單位:m)

3.3 基于K均值聚類的交叉口擁堵識別

基于K均值聚類的交叉口擁堵識別的原理是聚類中的小樣本事件是異常事件。在城市路網中,一般同時擁堵的交叉口數量較少,應用交叉口入口交通運行狀態的相似度進行聚類,聚類簇中樣本數少的類識為擁堵交叉口,擁堵傳播方向為入口路段交通流反方向。輸入為t時刻采集的交叉口各入口數據Xvj,輸出為K個類C1,C2,…,CK。

算法流程如下:

(1)隨機選擇K個交叉口入口的數據作為初始聚類中心,令I=1,Cg(I),g=1,2,…,K。

(2)計算交叉口每個入口數據點與K個初始聚類中心的距離d[v-jn,Cg(I)](采用歐氏距離),其中j表示交叉口,n表示交叉口的入口,g表示初始聚類中心。如果滿足d[v-jn,Cg(I)]=min{d[v-jn,Cg(I)],g=1,2,…,K},則vjn∈Cg。

(3)計算K各新的聚類中心:

(4)若Cg(I+1)≠Cg(I),g=1,2,…,K,則I =I+1,返回第2步;否則算法結束。

(5)找出最少樣本的類Cg=min{Ng,g=1,2,…,K},vjn∈Cg。該類中的交叉口屬于擁堵交叉口,入口方向為擁堵方向。

采用S.Ray等提出的在迭代過程中類內距離與類間距離的比值最小時的K作為確定最優K值的判斷條件。

對識別出的擁堵交叉口vj的交通量特征值(流量、車速和檢測器占有率)與該交叉口交通運行正常狀態的閾值ε進行比較,確定vj的交通狀態Υ(vj)值。同時確定該交叉口擁堵方向路段Γ(ei)值為“+”,非擁堵傳播方向路段的Γ(ei)值為零,根據上文擁堵傳播推理即可得到交通擁堵在城市路網中的傳播路徑。

4 結語

傳統的擁堵事后疏導策略對緩解和預防交通擁堵的效果不佳,認知交通擁堵傳播規律是交通擁堵主動治理的前提之一,而目前智能交通和信息技術的快速發展使研究交通擁堵主動治理方法成為可能。該文引入故障傳播有向圖方法研究交通擁堵傳播規律,建立了城市路網交通擁堵傳播有向圖模型,提出了交叉口擁堵識別方法和擁堵傳播的推理方法。該文嘗試把復雜系統的故障診斷方法應用于交通擁堵傳播研究,希望能拋磚引玉,使更多其他領域的方法應用到交通擁堵研究中。

參考文獻:

[1]周堂.物聯網背景下城市交通擁堵事前疏導研究[D].長沙:湖南大學,2014.

[2]李樹彬,吳建軍,高自友,等.基于復雜網絡的交通擁堵與傳播動力學分析[J].物理學報,2011,60(5).

[3]潘捷.城市交通擁堵的傳播及處理[D].西安:長安大學,2014.

[4]龍建成.城市道路交通擁堵傳播規律及消散控制策略研究[D].北京:北京交通大學,2009.

[5]Long J C,Gao Z Y,Ren H L,et al.Urban traffic congestion propagation and bottleneck identification[J].Science in China Series F:Information Sciences,2008,51(7).

[6]田聰.基于元胞傳輸模型的城市交通擁堵機理研究[D].武漢:華中科技大學,2012.

[7]高自友.城市交通擁堵傳播規律與消散控制策略研究[J].上海理工大學學報,2011,33(6).

[8]謝琛,張曉東.城市交通擁堵產生與傳播及其分析[A].2007第三屆中國智能交通年會論文集[C].2007.

[9]Shu-bin Li,Bai-bai Fu,Jian-feng Zheng.Dynamic analysis of traffic state and congestion propagation on bidirectional grid network[J].Discrete Dynamics in Nature and Society,2013,2013.

[10]曾宇懷.基于有向圖的城市交通堵塞模型[A].第六屆全國網絡科學論壇暨第二屆全國混沌應用研討會論文集[C].2010.

[11]袁紹欣.城市交通擁堵傳播機理及其控制策略研究[D].西安:長安大學,2012.

[12]陳侃,李昌禧.故障傳播有向圖的故障定位研究[J].自動化儀表,2011,32(4).

[13]王偉,于達仁,趙輝,等.基于符號有向圖模型的故障診斷方法[J].動力工程,2007,27(5).

[14]姜桂艷.道路交通狀態判別技術與應用[M].北京:人民交通出版社,2004.

[15]毛保華,孫壯志,賈順平,等.區域交通組織優化方法及實踐研究[M].北京:人民交通出版社,2007.

[16]吳軍強,梁軍.基于圖論的故障診斷技術及其發展[J].機電工程,2003,20(5).

收稿日期:2015-11-06

基金項目:?國家青年科學基金項目(71403096);住房和城鄉建設部項目(2013-K5-25、2013-R2-36);江蘇省高校哲學社會科學研究指導項目(2012SJD630005)

中圖分類號:U491.2

文獻標志碼:A

文章編號:1671-2668(2016)02-0047-03