基于圖論的道路偶發性局部擁堵區域動態演化

吳義虎，謝 芝，喻 偉，喻 丹，屈曉光

（長沙理工大學交通運輸工程學院，湖南長沙 410004）

隨著城市人口和機動車保有量持續、大幅增加，城市交通設施的規劃和建設已不能滿足交通需求的變化，城市交通供需矛盾日益尖銳，交通擁堵已成為城市的主要問題之一。除了人們常見的高峰期擁堵外，城市道路網中一些交通事件易造成偶發性交通擁堵。由于偶發性交通擁堵的隨機性和衍生性，若處理不及時或控制策略不佳，容易導致城市路網大面積的交通擁堵。

對于高峰期擁堵，對應的交通控制策略是提高通行能力與各交叉口、路段的相互協調。而偶發性交通擁堵發生的地點和時間具有隨機性，其疏散控制比較復雜：①由于交通擁堵控制發生的地點具有隨機性，其相鄰交叉口和路段的通行能力、交通流特性是不同的；②由于發生擁堵的時間具有隨機性，不同時段交通流也具有不同的特性。相對常態交通流的優化控制方案，偶發性交通擁堵疏散控制區域的動態劃分是將關聯程度較大的相鄰交叉口合并成一個控制區域，不同的控制區域采用不同的控制策略，由控制系統實施實時控制，達到擁堵快速疏散的控制目標。

學者們針對交通擁堵的疏散控制進行了大量的研究工作。一旦某路段或交叉口發生擁堵，道路通行能力下降，擁堵將向與之相鄰的路段和交叉口傳播，形成擁堵區域。因此，疏散控制的關鍵是控制區域的動態劃分。Walinchus［1］最先提出了交通控制子區的概念，并將控制子區分界線劃在流量特性或道路特性發生顯著變化的地段以及行政邊界之上；Wilson［2］等人將控制區域劃分為若干個獨立的小區；莫漢康［3］等人給出了誘導條件下的交通子區動態劃分方法，給出了子區劃分的周期原則、流量原則和距離原則等；楊曉光［4－6］等人提出了動態交叉口群協調控制理論與方法，并考慮物理關聯性和路徑關聯性，將整個擁堵區域劃分為阻塞區、過渡區及常態區。這些研究從擁堵發生時交通流的特性出發，探討了相鄰交叉口關聯程度的確定方法。

圖論是離散數學的重要分支。隨著離散數學和計算機科學的發展，圖論在網絡分析方面發揮了重要的作用［7］。同樣，圖論也可應用于道路交通網絡中，道路中的交叉口（或節點）通過路段（或線條）連接起來所形成的點和線的關系圖即為路網（如圖1所示），其實際是描述了物理關聯性和路徑關聯性。圖論在處理分類問題上，以其直接明了和簡單實用等特點具有相當大的優勢［8］。作者擬采用圖論的方法，分析擁堵發生時道路交通流動態演化的情況。利用圖論中相似度矩陣，對擁堵區域各交叉口交通流狀態進行聚類分析，以判斷路段或交叉口屬于阻塞區、過渡區或常態區。根據不同時刻擁堵區域內交通流的實時狀態參數進行聚類分析，動態描述擁堵區域阻塞區、過渡區及常態區的演化過程，將其結果用于控制區域動態劃分或城市路網易堵區域的分析，以期對路網規劃和擁堵控制提供有用的參考數據。

1 圖論的基本概念

圖論中的“圖”，并非通常意義下的幾何圖或設計圖等，而是以一種抽象的形式來表達一些具體的對象，以及各對象間具有或不具有的某種特定關系的數學模型。直觀地說，給出n個點集合V，用直線或曲線集合E將其中的一些點連接起來，這樣所形成的點與線的關系結構（V，E）就是一個圖G。某路網結構如圖2所示，用節點集V＝｛V1，V2，…，V6｝表示交叉路口，用邊集合E＝｛e1，e2，…，e9｝表示各交叉路口間的道路。

圖1 某交通路網Fig.1 A road network

圖2 某交通路網結構Fig.2 The structure of a road network map

圖G的結構也可用一個n×m階的矩陣X＝（xij）n×m表示。圖2中交叉口集合V＝｛V1，V2，…，V6｝中各交叉口分別具有權值系數，其物理意義為該交叉口擁有的車道數N、t時刻駛向該交叉口的交通流密度P和t時刻該交叉口通行能力C，則圖2可表示為：

2 基于圖論的擁堵區域交通流動態聚類方法

2.1 動態聚類時間間隔

偶發性事件易造成道路擁堵。由于擁堵漂移，擁堵規模也隨之變大。然后，隨著交通事件的處理與交通控制措施的實施，擁堵逐漸消散。因此，擁堵區域交通流狀態變化是一個動態過程。如果為了實現快速疏散控制，需要每隔一段時間對路網交通流參數進行采集并對其狀態分別屬于阻塞區、過渡區及常態區進行聚類分析。因為擁堵區域是以某個交叉口與其相鄰交叉口之間的路段為最小單位，故動態界定擁堵區時間間隔為：

2.2 擁堵區域交通流參數選擇和原始矩陣構建

式中：xnm為第n個分類交叉口中第m個參數的原始數據。

對于偶發性局部擁堵區域，交叉口擁堵狀態劃分是最重要和最基礎的。選取能夠代表該擁堵程度的參數，反映擁堵狀態和發展趨勢，用于疏散控制策略的選取。選取3個參數作為擁堵區域動態聚類分析：①連接該交叉口的車道數N；②交叉口通行能力C；③t時刻該交叉口的交通流密度P，其中密度參數為：

2.3 擁堵區域內各交叉口相似度矩陣構造

反映交叉口的交通狀態參數類型繁多，且不同參數間的差異較大，因此用相似性法的歸一化處理參數間的差異。為了避免對同一聚類問題用不同方法構造相似矩陣時產生較大的聚類差異，本研究采用絕對值指數法構造相似矩陣。在原始矩陣X的基礎上，造出n行n列的相似度矩陣R，xk與xl的相似程度為：

式中：rkl為2個樣本xk與xt相似程度的變量（rkl越小，表示2個樣本越接近）。

2.4 采用Kruskal算法生成最小樹

交通路網中道路錯綜復雜，交叉口之間通過不同的道路相連接。若依次對每個通過道路相連的交叉口進行聚類分析，其計算工作量太大。因此，去除相似度較大的交叉口間的道路連接，從而排除兩交叉口間的關聯較少而沒必要進行的聚類分析。克魯斯卡爾（kruskal）算法用于生成最小樹可以解決這一問題。它是在原有n個交叉路口（或頂點）的連通交通網絡G＝（V，R）中，最初先構造一個只有n個交叉口（或頂點），沒有道路（或邊）相連的非連通圖M＝｛V，Φ｝，圖中每個交叉口自成一個連通分量。然后，在待選道路R中選取一條rkl最小的道路。若該道路的兩個頂點落在不同的連通分量上，則將此邊加入到最小樹道路集合J0中；否則，將此邊舍去，重新選擇另一條rkl較小的邊。如此重復下去，直到所有頂點在同一個連通分量上為止。此時得到的最小樹集合圖則為最終聚類結果。雖然用Kruskal法得出的最小樹不唯一，但聚類結果是唯一的。給定賦權連通圖G＝（V，R），Kruskal算法步驟為：

1）開始原頂點集合V＝（v1，v2，...，vn），且頂點集合對應的邊的權值矩陣

生成的最小樹頂點集合T0＝｛｝，生成的最小樹邊集合J0＝｛｝。

4）重復3），直至J＝V，則結束運算，所得最小樹集合為J。

2.5 交通流狀態聚類

求出最小樹J后，根據rkl的大小確定各區域間的相互關系。本研究選定的3個參數中，交通流密度P可直觀地反映擁堵狀態；交叉口通行能力C和道路車道數N為道路物理參數，二者的大小對擁堵傳播速度產生的影響是：通行能力和車道數越大，擁堵傳播速度越快。其原因是：車道數越多的道路和通行能力越大的交叉口，其車流量也越大，偶發性擁堵傳播的速度也越大。因此rkl的大小既綜合描述了擁堵狀態，又反映了交通流狀態變化趨勢。距事故發生地點較近的路段和交叉口，其擁堵程度越大。以事故發生點為中心由內而外的區域，交通流狀態依次是阻塞區、過渡區及常態區，而且3個區域的空間形狀不一定規則。

相似程度的變量rkl閾值的確定應參考實際交通情況而定。rkl越小，說明2交叉口間的相似度越大，交通擁堵狀況越嚴重。根據實際交通情況，假設：當rkl≤0.65時，兩相鄰交叉口可合并為交通阻塞區；當0.65＜rkl≤1時，兩相鄰交叉口可并為交通過渡區；當rkl＞1時為交通常態區。

3 仿真結果與分析

為了檢驗基于圖論的城市道路偶發性交通擁堵區域交通流狀態聚類分析方法的有效性和穩定性，以某城市道路網絡突發交通事件為例，利用Matlab進行仿真實驗。設定偶發性事故發生地點處于某條雙向6車道，在由南往北方向上，事故占用兩個車道，且該路段中間隔離設施優良，事故發生后不會對對向道路通行能力產生影響。依次設定該路段區域路網參數，偶發性交通發生10min后，該事故區域交叉口的原始參數見表1。

表1 相關系數及劃分結果Table 1 The correlation coefficient and the divided the result

在Matlab中，將基于圖論的Kruskal方法與FCM算法分別進行聚類分析，并比較計算結果。因為FCM方法是被驗證過的有效的聚類分析方法，若二者差別不大，則證明圖論Kruskal算法是有效可行的。表1是由圖論Kruskal方法和FCM聚類方法計算得到的各交叉路口相似程度的變量及各子區交通流狀態結果。

表1中，由圖論Kruskal方法與FCM聚類方法計算得到的輸出交叉路口相似程度值和交通流狀態結果相似，故基于圖論的Kruskal方法用于擁堵區域交通流狀態演化分析是可行的。偶發性事件發生10min后，擁堵區域交通流狀態如圖3所示。

圖3 偶發性事件區域交通劃分結果Fig.3 The division scheme of the region with accidental incidents

該偶發性事件發生15min后，若不采用任何的控制措施下，再次用圖論Kruskal方法得到的該擁堵區域交通流狀態如圖4所示。

圖4 不采取控制措施下擁堵區域范圍變化Fig.4 The change of average queue length without any strategies for the heavy traffic region

從圖3和圖4中可以看出，偶發性事件發生后，該路段通行能力下降，造成了交通擁堵。出行者根據其出行目的地，由擁堵區域上游駛入擁堵區域，進入了該區域相應的排隊區域。由于下游路段通行能力下降，擁堵區域將通過交叉口由下游路段后溢至上游相鄰的交叉口。故交通擁堵區域在空間上呈菱形，距事件點交通流密度較大的交叉口和路段為菱形的長軸，距事件點交通流密度較小的交叉口和路段為菱形的短軸。隨著時間的增加，擁堵區菱形面積增大。

4 結論

1）提出了一種利用圖論的相似度矩陣，對擁堵區域各交叉口交通流狀態采用聚類分析方法，以判斷路段或交叉口屬于阻塞區、過渡區或常態區。根據不同時刻擁堵區域內交通流的實時狀態參數進行了聚類分析，動態描述了擁堵區域阻塞區、過渡區及常態區的演化過程，數值仿真結果表明：該方法可行，與實際交通擁堵發生造成交通流變化情形吻合，該方法具有交通流狀態演化結果直接明了和簡單實用等特點。

2）初步仿真結果表明，偶發性事件發生后，事發路段通行能力下降，出行者根據其出行目的地，由事發路段上游駛入擁堵區域，進入了該區域相應的排隊區域。交通擁堵區域在空間上呈菱形，距事件點交通流密度較大的交叉口和路段為菱形的長軸，距事件點交通流密度較小的交叉口和路段為菱形的短軸。隨著時間的增加，擁堵區將沿菱形長、短軸蔓延。

3）采用圖論方法分析擁堵發生時道路交通流狀態演化情況，其結果可以用于城市交通擁堵控制區域動態劃分，也可以用于城市路網易堵區域的分析，為路網規劃和擁堵控制策略的選擇提供依據。

（References）：

［1］Walinchus R J.Real－time network decomposition and sub－network interfacing［J］.Highway Research Record，1971（366）：20－28.

［2］Wilson D R，Martinez T R.Improved heterogeneous distance functions［J］.Journal of Artificial Intelligence Research，1997，6：1－34.

［3］莫漢康，彭國雄，云美萍.誘導條件下的交通控制子區自動劃分［J］.交通運輸工程學報，2002，2（2）：67－72.（MO Han－kang，PENG Guo－xiong，YUN Meiping.Automatic division of traffic control sub－area under condition of route guidance［J］.Journal of Traf－fic and Transportation Engineering，2002，2（2）：67－72.（in Chinese））

［4］段后利，李志恒，張毅，等.交通控制子區動態劃分模型［J］.吉林大學學報：工學版，2009，39（S2）：13－18.（DUAN Hou－li，LI Zhi－heng，ZHANG Yi，et al.Dynamic subdivision of road network into coordinated control regions［J］.Journal of Jilin University：Engineering and Technology Edition，2009，39（S2）：13－18.（in Chinese））

［5］楊曉光，黃瑋，馬萬經.過飽和狀態下交通控制小區動態劃分方法［J］.同濟大學學報：自然科學版，2010，38（10）：1450－1457.（YANG Xiao－guang，HUANG Wei，MA Wan－Jing.Method of delimiting urban traffic signal coordinated control subarea under oversaturated condition［J］.Journal of Tongji University：Natural Science Edition，2010，38（10）：1450－1457.（in Chinese））

［6］盧凱，徐建閩，李軼舜.基于關聯度分析的協調控制子區劃分方法［J］.華南理工大學學報：自然科學版，2009，37（7）：6－9.（LU Kai，XU Jian－min，LI Yishun.Division method of coordinated control subareas based on correlation degree analysis［J］.Journal of South China University of Technology：Natural Science Edition，2009，37（7）：6－9.（in Chinese））

［7］楊慶芳，陳林.交通控制子區動態劃分方法［J］.吉林大學學報：工學版，2006，36（增刊2）：139－142.（YANG Qing－fang，CHEN Lin.Division approach of traffic control work zone［J］.Journal of Jilin University：Engineering and Technology Edition，2006，36（Supple2）：139－142.（in Chinese））

［8］邱關源.網絡圖論簡介［M］.北京：人民教育出版社，2002.（QIU Guan－yuan.The introduction of network graph theory［M］.Beijing：People’s Education Press，2002.（in Chinese））

［9］耿素云.集合論與圖論［M］.北京：北京大學出版社，1998.（GENG Su－yun.Set theory and graph theory［M］.Beijing：Beijing University Press，1998.（in Chinese））

［10］肖位樞.圖論及其算法［M］.北京：航空工業出版社，1993.（XIAO Wei－shu.Graph theory and algorithms［M］.Beijing：Aviation Industry Press，1993.（in Chinese））

［11］曹建農，方丹霞.基于圖論的圖像分割方法及其局限性研究［J］.測繪技術裝備，2006（2）：12－15.（CAO Jian－nong，FANG Dan－xia.The image segmentation method based on graph theory and its limitations［J］.Geomatics Technology and Equipment，2006（2）：12－15.（in Chinese））

［12］張敖木翰，高自友，任華玲.突發事故下交通擁堵控制策略［J］.中國科學：技術科學，2011，41（7）：955－961.（ZHANG Ao－mu－han，GAO Zi－you，REN Hualing.Incident－based traffic congestion control strategy［J］.Science China：Technology Science，2011，41（7）：955－961.（in Chinese））

［13］張敖木翰.突發事件下非重復性交通擁堵傳播規律與控制策略研究［D］.北京：北京交通大學，2012.（ZHANG Ao－mu－han.Studies on properties and control strategies of incident－based non－recurrent traffic congestion propagation［D］.Beijing：Beijing Jiaotong University，2012.（in Chinese））

［14］王煒，過秀成.交通工程學［M］.南京：東南大學出版社，2011.（WANG Wei，GUO Xiu－cheng.Traffic engineering［M］.Nanjing：Southeast University Press，2011.（in Chinese））