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

（長沙理工大學(xué)交通運(yùn)輸工程學(xué)院，湖南長沙 410004）

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

對(duì)于高峰期擁堵，對(duì)應(yīng)的交通控制策略是提高通行能力與各交叉口、路段的相互協(xié)調(diào)。而偶發(fā)性交通擁堵發(fā)生的地點(diǎn)和時(shí)間具有隨機(jī)性，其疏散控制比較復(fù)雜：①由于交通擁堵控制發(fā)生的地點(diǎn)具有隨機(jī)性，其相鄰交叉口和路段的通行能力、交通流特性是不同的；②由于發(fā)生擁堵的時(shí)間具有隨機(jī)性，不同時(shí)段交通流也具有不同的特性。相對(duì)常態(tài)交通流的優(yōu)化控制方案，偶發(fā)性交通擁堵疏散控制區(qū)域的動(dòng)態(tài)劃分是將關(guān)聯(lián)程度較大的相鄰交叉口合并成一個(gè)控制區(qū)域，不同的控制區(qū)域采用不同的控制策略，由控制系統(tǒng)實(shí)施實(shí)時(shí)控制，達(dá)到擁堵快速疏散的控制目標(biāo)。

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

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

1 圖論的基本概念

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

圖1 某交通路網(wǎng)Fig.1 A road network

圖2 某交通路網(wǎng)結(jié)構(gòu)Fig.2 The structure of a road network map

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

2 基于圖論的擁堵區(qū)域交通流動(dòng)態(tài)聚類方法

2.1 動(dòng)態(tài)聚類時(shí)間間隔

偶發(fā)性事件易造成道路擁堵。由于擁堵漂移，擁堵規(guī)模也隨之變大。然后，隨著交通事件的處理與交通控制措施的實(shí)施，擁堵逐漸消散。因此，擁堵區(qū)域交通流狀態(tài)變化是一個(gè)動(dòng)態(tài)過程。如果為了實(shí)現(xiàn)快速疏散控制，需要每隔一段時(shí)間對(duì)路網(wǎng)交通流參數(shù)進(jìn)行采集并對(duì)其狀態(tài)分別屬于阻塞區(qū)、過渡區(qū)及常態(tài)區(qū)進(jìn)行聚類分析。因?yàn)閾矶聟^(qū)域是以某個(gè)交叉口與其相鄰交叉口之間的路段為最小單位，故動(dòng)態(tài)界定擁堵區(qū)時(shí)間間隔為：

2.2 擁堵區(qū)域交通流參數(shù)選擇和原始矩陣構(gòu)建

式中：xnm為第n個(gè)分類交叉口中第m個(gè)參數(shù)的原始數(shù)據(jù)。

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

2.3 擁堵區(qū)域內(nèi)各交叉口相似度矩陣構(gòu)造

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

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

2.4 采用Kruskal算法生成最小樹

交通路網(wǎng)中道路錯(cuò)綜復(fù)雜，交叉口之間通過不同的道路相連接。若依次對(duì)每個(gè)通過道路相連的交叉口進(jìn)行聚類分析，其計(jì)算工作量太大。因此，去除相似度較大的交叉口間的道路連接，從而排除兩交叉口間的關(guān)聯(lián)較少而沒必要進(jìn)行的聚類分析?？唆斔箍枺╧ruskal）算法用于生成最小樹可以解決這一問題。它是在原有n個(gè)交叉路口（或頂點(diǎn)）的連通交通網(wǎng)絡(luò)G＝（V，R）中，最初先構(gòu)造一個(gè)只有n個(gè)交叉口（或頂點(diǎn)），沒有道路（或邊）相連的非連通圖M＝｛V，Φ｝，圖中每個(gè)交叉口自成一個(gè)連通分量。然后，在待選道路R中選取一條rkl最小的道路。若該道路的兩個(gè)頂點(diǎn)落在不同的連通分量上，則將此邊加入到最小樹道路集合J0中；否則，將此邊舍去，重新選擇另一條rkl較小的邊。如此重復(fù)下去，直到所有頂點(diǎn)在同一個(gè)連通分量上為止。此時(shí)得到的最小樹集合圖則為最終聚類結(jié)果。雖然用Kruskal法得出的最小樹不唯一，但聚類結(jié)果是唯一的。給定賦權(quán)連通圖G＝（V，R），Kruskal算法步驟為：

1）開始原頂點(diǎn)集合V＝（v1，v2，...，vn），且頂點(diǎn)集合對(duì)應(yīng)的邊的權(quán)值矩陣

生成的最小樹頂點(diǎn)集合T0＝｛｝，生成的最小樹邊集合J0＝｛｝。

4）重復(fù)3），直至J＝V，則結(jié)束運(yùn)算，所得最小樹集合為J。

2.5 交通流狀態(tài)聚類

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

相似程度的變量rkl閾值的確定應(yīng)參考實(shí)際交通情況而定。rkl越小，說明2交叉口間的相似度越大，交通擁堵狀況越嚴(yán)重。根據(jù)實(shí)際交通情況，假設(shè)：當(dāng)rkl≤0.65時(shí)，兩相鄰交叉口可合并為交通阻塞區(qū)；當(dāng)0.65＜rkl≤1時(shí)，兩相鄰交叉口可并為交通過渡區(qū)；當(dāng)rkl＞1時(shí)為交通常態(tài)區(qū)。

3 仿真結(jié)果與分析

為了檢驗(yàn)基于圖論的城市道路偶發(fā)性交通擁堵區(qū)域交通流狀態(tài)聚類分析方法的有效性和穩(wěn)定性，以某城市道路網(wǎng)絡(luò)突發(fā)交通事件為例，利用Matlab進(jìn)行仿真實(shí)驗(yàn)。設(shè)定偶發(fā)性事故發(fā)生地點(diǎn)處于某條雙向6車道，在由南往北方向上，事故占用兩個(gè)車道，且該路段中間隔離設(shè)施優(yōu)良，事故發(fā)生后不會(huì)對(duì)對(duì)向道路通行能力產(chǎn)生影響。依次設(shè)定該路段區(qū)域路網(wǎng)參數(shù)，偶發(fā)性交通發(fā)生10min后，該事故區(qū)域交叉口的原始參數(shù)見表1。

表1 相關(guān)系數(shù)及劃分結(jié)果Table 1 The correlation coefficient and the divided the result

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

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

圖3 偶發(fā)性事件區(qū)域交通劃分結(jié)果Fig.3 The division scheme of the region with accidental incidents

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

圖4 不采取控制措施下?lián)矶聟^(qū)域范圍變化Fig.4 The change of average queue length without any strategies for the heavy traffic region

從圖3和圖4中可以看出，偶發(fā)性事件發(fā)生后，該路段通行能力下降，造成了交通擁堵。出行者根據(jù)其出行目的地，由擁堵區(qū)域上游駛?cè)霌矶聟^(qū)域，進(jìn)入了該區(qū)域相應(yīng)的排隊(duì)區(qū)域。由于下游路段通行能力下降，擁堵區(qū)域?qū)⑼ㄟ^交叉口由下游路段后溢至上游相鄰的交叉口。故交通擁堵區(qū)域在空間上呈菱形，距事件點(diǎn)交通流密度較大的交叉口和路段為菱形的長軸，距事件點(diǎn)交通流密度較小的交叉口和路段為菱形的短軸。隨著時(shí)間的增加，擁堵區(qū)菱形面積增大。

4 結(jié)論

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

2）初步仿真結(jié)果表明，偶發(fā)性事件發(fā)生后，事發(fā)路段通行能力下降，出行者根據(jù)其出行目的地，由事發(fā)路段上游駛?cè)霌矶聟^(qū)域，進(jìn)入了該區(qū)域相應(yīng)的排隊(duì)區(qū)域。交通擁堵區(qū)域在空間上呈菱形，距事件點(diǎn)交通流密度較大的交叉口和路段為菱形的長軸，距事件點(diǎn)交通流密度較小的交叉口和路段為菱形的短軸。隨著時(shí)間的增加，擁堵區(qū)將沿菱形長、短軸蔓延。

3）采用圖論方法分析擁堵發(fā)生時(shí)道路交通流狀態(tài)演化情況，其結(jié)果可以用于城市交通擁堵控制區(qū)域動(dòng)態(tài)劃分，也可以用于城市路網(wǎng)易堵區(qū)域的分析，為路網(wǎng)規(guī)劃和擁堵控制策略的選擇提供依據(jù)。

（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］莫漢康，彭國雄，云美萍.誘導(dǎo)條件下的交通控制子區(qū)自動(dòng)劃分［J］.交通運(yùn)輸工程學(xué)報(bào)，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］段后利，李志恒，張毅，等.交通控制子區(qū)動(dòng)態(tài)劃分模型［J］.吉林大學(xué)學(xué)報(bào)：工學(xué)版，2009，39（S2）：13－18.（DUAN Hou－li，LI Zhi－h(huán)eng，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īng).過飽和狀態(tài)下交通控制小區(qū)動(dòng)態(tài)劃分方法［J］.同濟(jì)大學(xué)學(xué)報(bào)：自然科學(xué)版，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］盧凱，徐建閩，李軼舜.基于關(guān)聯(lián)度分析的協(xié)調(diào)控制子區(qū)劃分方法［J］.華南理工大學(xué)學(xué)報(bào)：自然科學(xué)版，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］楊慶芳，陳林.交通控制子區(qū)動(dòng)態(tài)劃分方法［J］.吉林大學(xué)學(xué)報(bào)：工學(xué)版，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］邱關(guān)源.網(wǎng)絡(luò)圖論簡介［M］.北京：人民教育出版社，2002.（QIU Guan－yuan.The introduction of network graph theory［M］.Beijing：People’s Education Press，2002.（in Chinese））

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

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

［11］曹建農(nóng)，方丹霞.基于圖論的圖像分割方法及其局限性研究［J］.測繪技術(shù)裝備，2006（2）：12－15.（CAO Jian－nong，F(xiàn)ANG 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］張敖木翰，高自友，任華玲.突發(fā)事故下交通擁堵控制策略［J］.中國科學(xué)：技術(shù)科學(xué)，2011，41（7）：955－961.（ZHANG Ao－mu－h(huán)an，GAO Zi－you，REN Hualing.Incident－based traffic congestion control strategy［J］.Science China：Technology Science，2011，41（7）：955－961.（in Chinese））

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

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