基于Ncut的城市路網(wǎng)交通子區(qū)劃分方法

(浙江工業(yè)大學 計算機科學與技術(shù)學院，浙江 杭州 310023)

隨著城市的發(fā)展，交通路網(wǎng)規(guī)模擴大，城市車輛不斷增加，區(qū)域性擁堵頻發(fā)，使得本就復雜的交通網(wǎng)更加難以管理。為應(yīng)對城市交通問題，城市交通協(xié)調(diào)控制策略被提出并不斷完善[1]。交通流的空間分布情況決定了協(xié)調(diào)控制策略必須有合理的目標區(qū)域，交通子區(qū)劃分在協(xié)調(diào)控制中扮演著重要角色，直接影響到交通協(xié)調(diào)控制策略的效率與性能。交通子區(qū)劃分是協(xié)調(diào)控制策略實施之前的必要步驟。交通子區(qū)劃分的作用主要有：1) 把龐大而復雜的交通路網(wǎng)分為相對較小、更易管理的交通子區(qū)，以分治的方法解決交通管理問題；2) 根據(jù)每個子區(qū)的特點實施靈活的交通控制策略，以提高每個子區(qū)交通控制的性能；3) 在各個子區(qū)內(nèi)部執(zhí)行獨立的交通控制策略，避免了大規(guī)模集中式控制方法帶來的問題，提高系統(tǒng)的可靠性。交通子區(qū)劃分的概念由Walinchus[2]在1971 年提出，以子區(qū)劃分是否依據(jù)動態(tài)交通狀態(tài)，可以分為靜態(tài)子區(qū)劃分與動態(tài)子區(qū)劃分。在1969 年開發(fā)的TRANSYT[3]與1979 年開發(fā)的SCOOT[4]交通控制系統(tǒng)中，以靜態(tài)路網(wǎng)特征與歷史交通流信息作為劃分依據(jù)，均采用了靜態(tài)子區(qū)劃分方法。靜態(tài)劃分方法在劃分后子區(qū)不再改變，不能根據(jù)交通流變化做出調(diào)整，會影響交通協(xié)調(diào)控制策略的效率。隨著實時交通流參數(shù)測量方法越來越成熟，動態(tài)子區(qū)劃分方法的研究成為主流。沈國江等[5]提出了一種路口過飽和狀態(tài)識別方法，基于路口擁堵等級與相鄰路口關(guān)聯(lián)度，提出過飽和交通狀態(tài)下的控制子區(qū)動態(tài)劃分方法。莫漢康等[6]提出在路線誘導條件下，可同時獲得實時與預測的交通流數(shù)據(jù)，并依據(jù)距離原則、流量原則和周期原則等分別建立交通控制子區(qū)自動劃分過程。Lin等[7]基于MFD設(shè)計了需求平衡模型，使得交通子區(qū)根據(jù)實際交通態(tài)勢調(diào)整，配合控制策略，對整個路網(wǎng)進行優(yōu)化。

子區(qū)劃分主要根據(jù)交叉口間的關(guān)聯(lián)度進行，關(guān)聯(lián)度是交叉口間靜態(tài)結(jié)構(gòu)特征和動態(tài)交通流參數(shù)的組合,關(guān)聯(lián)度大的交叉口需要劃分到同一子區(qū)中，以更好地配合協(xié)調(diào)控制策略。Hu等[8]提出了一種新的車輛檢測器布設(shè)方法來收集、存儲高精度交通數(shù)據(jù)，并建立基于交通狀態(tài)數(shù)據(jù)的干道相鄰交叉口關(guān)聯(lián)度模型。李瑞敏等[9]考慮路口間距、交通流離散性和交通流量等要素，應(yīng)用模糊推理確定路口間協(xié)調(diào)控制需求系數(shù)并用協(xié)調(diào)系數(shù)進行控制子區(qū)劃分。Zhao等[10]提出了基于Newman快速算法的交通子區(qū)劃分方法，應(yīng)用于大規(guī)模路網(wǎng)劃分上，但其方法會劃分出規(guī)模相差巨大的子區(qū)。盧凱等[11]提出相鄰交叉口關(guān)聯(lián)度與多交叉口組合關(guān)聯(lián)度的計算公式，并建立協(xié)調(diào)控制子區(qū)的劃分模型，但所提方法時間復雜度高，在實際大規(guī)模路網(wǎng)中很難應(yīng)用。交通子區(qū)劃分雖然已進行多年系統(tǒng)性研究，但還存在著一些問題。現(xiàn)有方法中大都以小規(guī)模路網(wǎng)中歷史數(shù)據(jù)或仿真數(shù)據(jù)進行研究，難以保證在實際大規(guī)模路網(wǎng)上應(yīng)用的可行性，同時對劃分的目標與原則缺少明確定義。歸一化分割[12](Normalized cut，簡寫為Ncut)是一種普聚類算法，首先應(yīng)用在圖的分割領(lǐng)域，在劃分時以整體效益為目標，均衡地劃分圖。通過簡化路網(wǎng)構(gòu)建成圖，可以應(yīng)用Ncut在大規(guī)模路網(wǎng)的劃分中，快速得到理想的劃分結(jié)果。實時交通狀態(tài)是交通控制的基礎(chǔ)數(shù)據(jù)[13]，對子區(qū)劃分有顯著影響，筆者依據(jù)主要交通流參數(shù)，給出路段與交叉口運行態(tài)勢計算方法，并考慮交叉口距離因素，給出動靜態(tài)結(jié)合的關(guān)聯(lián)度計算方法，并應(yīng)用Ncut對大規(guī)模交通路網(wǎng)進行劃分。

1 交通運行態(tài)勢

1.1 路段態(tài)勢

速度可以直觀地反映出路段的運行水平，我國制定了城市道路交通運行等級標準，規(guī)定了每個等級的道路速度與所處擁堵等級，如表1所示。擁堵等級表以粗略的方式把速度劃分為5 個運行等級，但這種表示方法太過離散，不利于在研究中精確表示路段運行水平。以Lj→i代表交叉口j到交叉口i的路段，為更精細化表示路段的擁堵水平，定義SLj→i為路段Lj→i的運行態(tài)勢，SLj→i是屬于[0,1]區(qū)間的浮點數(shù)據(jù)，由0到1代表交通運行態(tài)勢從暢通到嚴重擁堵，定義為

(1)

式中：vj→i為路段Lj→i的速度；vu為交通暢通和輕度擁堵的速度分解線；vd為中度擁堵與嚴重擁堵的分界線。如果速度vj→i高于vu，設(shè)置SLj→i=0，表示交通態(tài)勢處于最好的狀態(tài)。當路段速度vj→i低于vd，設(shè)置SLj→i=1，表示交通處于嚴重擁堵。

表1 路段交通運行等級劃分Table 1 Running level of link in different speed km/h

1.2 交叉口態(tài)勢

交叉口流量能一定程度上反映交叉口運行態(tài)勢。交叉口態(tài)勢可以表示為交叉口流量與通行能力的比值，當比值較小時表示處于暢通狀態(tài)，較大時表示處于擁堵狀態(tài)。交叉口不同的方向交通流量一般不同，所以擁堵水平有所差別，這里設(shè)置RFi,j表示交叉口i在j方向上的流量與這個方向的通行能力的比值，用來表示交叉口在這個方向的交通態(tài)勢，其計算式為

(2)

式中：qi,j為交叉口i在j方向上的交通流量；ni,j為交叉口i在j方向上進口車道數(shù)；c為單車道通行能力。

圖1為15 min內(nèi)3 車道和2 車道道路交通車輛數(shù)與速度關(guān)系，可以看出速度受交通流量影響很大。流量的增加讓道路上車流密度變大，使速度降低，進而影響到流量，使流量被限制在道路的通行能力之內(nèi)?？梢钥闯觯涸?5 min內(nèi)3 車道車輛數(shù)最大值在420左右，2 車道最大值在280左右，所以單車道通行能力c取560 pcu/h。

圖1 15 min交通車輛數(shù)與速度關(guān)系圖Fig.1 Diagram of vehicle number and speed in 15 minutes

1.3 擬合態(tài)勢

由于交通流時空連續(xù)的特點，路段擁堵水平與其下游交叉口有很強關(guān)聯(lián)性。交叉口過飽和會顯著影響上游路段車輛匯入交叉口的速率，造成路段的擁堵。因此，可以使用路段擁堵水平反映其下游交叉口的擁堵水平。一般的，每個交叉口有4 條與其相連的路段，最為擁堵的路段對交叉口的影響最大。所以，定義SNi來表示交叉口i的擬合交通態(tài)勢，其計算式為

(3)

用以擬合擁堵態(tài)勢整合交叉口方向流量信息與相連路段速度信息，取(0,1)之間的浮點數(shù)，值越高表示交叉口越擁堵。

2 基于Ncut的交通子區(qū)劃分

交通子區(qū)的動態(tài)劃分要考慮路網(wǎng)結(jié)構(gòu)特點和交通狀態(tài)，劃分出的子區(qū)應(yīng)有利于交通管理和協(xié)調(diào)控制策略的實施?；趯討B(tài)子區(qū)劃分的理解和前人工作的總結(jié)，筆者提出4 點劃分原則：1) 子區(qū)內(nèi)部交叉口的交通態(tài)勢度盡可能相似，以利于使用同一套配時方案；2) 距離是影響交叉口間關(guān)聯(lián)度的重要因素，距離越小關(guān)聯(lián)度越大；3) 同一子區(qū)的交叉口必須是空間上連通的，否則不利于交通管理；4) 子區(qū)的規(guī)模應(yīng)限制在合適的范圍內(nèi)，因為規(guī)模過大的子區(qū)其內(nèi)部交叉口的態(tài)勢差異勢必過大，同時也會更加復雜，不利于交通控制的實施，子區(qū)的最大交叉口數(shù)目設(shè)置為15比較合適[14]。

2.1 關(guān)聯(lián)度計算

相鄰交叉口之間靜態(tài)關(guān)聯(lián)度主要由交叉口間距離(或者說路段長度)構(gòu)成。距離越短，關(guān)聯(lián)度越大，當距離小于等于200 m，關(guān)聯(lián)度達到最大值。設(shè)置FS(i,j)表示交叉口i與交叉口j之間的關(guān)聯(lián)度，定義式為

(4)

式中：a(i,j)為交叉口之間的鄰接關(guān)系，設(shè)置a(i,j)=1表示交叉口i與交叉口j直接相連，反之a(chǎn)(i,j)=0；li,j為交叉口i與j之間路段的長度；σX為配置參數(shù)，取值為160；FS(i,j)反映了路網(wǎng)靜態(tài)部分中交叉口之間鄰接關(guān)系與距離關(guān)系，相鄰交叉口隨著距離增大，關(guān)聯(lián)度逐漸變小。

整合交叉口的交通態(tài)勢，定義交叉口i與j的關(guān)聯(lián)度w(i,j)為

(5)

式中配置參數(shù)σI取值為0.2。此關(guān)聯(lián)度整合了動靜態(tài)要素，動態(tài)要素中，2 個交叉口之間擁堵態(tài)勢差異越大，關(guān)聯(lián)度越小。直接相連的2 個交叉口，距離越近、交通態(tài)勢越相近關(guān)聯(lián)度越大，反之越小。

2.2 路網(wǎng)初步劃分

Ncut在分割圖時，把圖G=(V,E)(V是圖中節(jié)點的集合，E是圖中邊的集合)劃分為A和B兩部分時，其中A∪B=V，A∩B=?，即移走所有連接A，B兩部分的邊，被移走的邊的權(quán)值之和定義為cut(A,B)，表示子圖A，B之間的割值，即

(6)

式中w(u,v)為節(jié)點u和v之間邊的權(quán)重。Ncut使用了子圖之間歸一化割值(Ncut)和子圖內(nèi)部歸一化關(guān)聯(lián)度(Nassoc)來衡量劃分的優(yōu)劣，并定義為

(7)

(8)

Ncut(A,B)=2-Nassoc(A,B)

(9)

尋找最小的Ncut值問題可以通過解特征方程高效計算出來，其計算式為

(D-W)x=λDx

(10)

式中：W為圖G的邊權(quán)矩陣；D為W的度矩陣。求解特征方程式(10)，可以利用第二小的特征解對應(yīng)的特征向量二分圖G。

把Ncut算法應(yīng)用到交通子區(qū)的劃分問題上，對路網(wǎng)進行初步劃分，步驟如下：

1) 基于交通路網(wǎng)構(gòu)建帶權(quán)圖G=(V,E)，圖G中節(jié)點為路網(wǎng)中交叉口，邊為路段，權(quán)重為交叉口之間的關(guān)聯(lián)度，構(gòu)建邊權(quán)矩陣W。

2) 解特征方程(D-W)x=λDx。

3) 利用解得的第二小的特征值對應(yīng)的特征向量，劃分圖G。

4) 如果子圖中節(jié)點數(shù)多于15 個，則遞歸地調(diào)用此過程對子圖劃分，直到子圖中節(jié)點數(shù)小于或等于15 個。

2.3 邊界調(diào)整

Ncut每次對圖的劃分以當前最優(yōu)的歸一化割值為目標進行二分，而當前劃分在其子圖的劃分結(jié)果中不一定是最優(yōu)的，隨著劃分次數(shù)的增加，使得劃分結(jié)果偏離最優(yōu)劃分目標。在經(jīng)過多次劃分后，可能有子區(qū)邊界上個別節(jié)點在劃分結(jié)果里并非最優(yōu)，需要做調(diào)整。調(diào)整以子區(qū)總關(guān)聯(lián)度最大為目標，每次移動子區(qū)邊界上的交叉口到相鄰子區(qū)，最終形成更加緊密的子區(qū)。子區(qū)總關(guān)聯(lián)度的計算為

(11)

式中：cor(G)為路網(wǎng)G的總關(guān)聯(lián)度；N為子區(qū)總數(shù)。通過對子區(qū)邊界節(jié)點調(diào)整，讓處于子區(qū)邊界上的節(jié)點回到能使得總關(guān)聯(lián)度最大的子區(qū)中，使劃分趨于最優(yōu)。具體步驟如下：

1) 計算當前劃分的總關(guān)聯(lián)度，并記為cor(G)pre。

2) 對所有子區(qū)邊緣的交叉口i(i∈A)，如果在i并入其相鄰的子區(qū)B后，B中交叉口數(shù)目沒達到子區(qū)規(guī)模上限，計算當節(jié)點i加入子區(qū)B之后總的cor(G)值。

3) 選擇步驟2)中所算出來的最大的cor(G)，判斷其是否大于cor(G)pre，如果大于，則讓其對應(yīng)節(jié)點加入對應(yīng)子區(qū)，返回步驟1)并繼續(xù)。否則，調(diào)整結(jié)束。

3 實 驗

3.1 路網(wǎng)描述

為檢驗上述討論方法，設(shè)計實驗使用真實的路網(wǎng)數(shù)據(jù)來加以驗證。實驗路網(wǎng)是紹興市柯橋區(qū)，共有23條路，223 個路段和69 個交叉口，從主城區(qū)到郊區(qū)，交叉口和路段上全都覆蓋了交通檢測器。實驗以2017 年6 月6 日17：00—17：15晚高峰的數(shù)據(jù)來作研究，路網(wǎng)交通態(tài)勢如圖2所示。同時在交通圖2中圈出了路網(wǎng)的一部分，其中交叉口已做編號，交通流量和運行態(tài)勢在如表2所示。交通運行態(tài)勢由交叉口的方向飽和度和相連路段的擁堵態(tài)勢組成，數(shù)值越大表示擁堵程度越高。

圖2 路段交通態(tài)勢圖Fig.2 Map of link traffic state

表2 路網(wǎng)部分交叉口流量及態(tài)勢Table 2 Traffic flow and traffic state of part road network

3.2 交通子區(qū)劃分

應(yīng)用基于歸一化分割的子區(qū)劃分方法在柯橋區(qū)路網(wǎng)上進行子區(qū)劃分，圖3為劃分過程。圖3(a)為劃分的路網(wǎng)范圍。圖3(b)中，經(jīng)過第1 次分割路網(wǎng)被劃分為地圖最下部的6 個交叉口與路網(wǎng)其他部分。可以看出地圖最下面的6 個路口通過1 條干道組成1 個子區(qū)，它們與路網(wǎng)的其他部分只有1 條道路相連,因此容易形成獨立子區(qū)。圖3(c～g)中，每次劃分都近似為對目標網(wǎng)絡(luò)的均衡劃分，并且產(chǎn)生2 個形狀良好且空間上緊密相連的子區(qū)。Ncut劃分從原則上要求子區(qū)內(nèi)部交叉口間有較強的關(guān)聯(lián)度，而較強的關(guān)聯(lián)度傾向于讓子區(qū)形成較規(guī)則的形狀。在圖3(g)中，最后把16 個交叉口劃分形成了子區(qū)C和D，根據(jù)圖2與表2中路網(wǎng)的交通狀態(tài)數(shù)據(jù)，子區(qū)C同D相比，交叉口流量更大，更為擁堵，而C和D在子區(qū)內(nèi)部各自擁有較短路段距離，分別形成較高關(guān)聯(lián)度，Ncut均衡分割的特點最后形成2 個交叉口數(shù)目相近的穩(wěn)定子區(qū)。可以看出：基于Ncut劃分方法能有效把擁堵相近、距離緊密的交叉口劃分到同一子區(qū)內(nèi)。路網(wǎng)最后被劃分為7 個子區(qū)，各子區(qū)交叉口數(shù)目及關(guān)聯(lián)度值如表3所示，總關(guān)聯(lián)度為22.36。

經(jīng)過邊界調(diào)整，共有3 個節(jié)點從原來的子區(qū)移動到臨近子區(qū)中。最終的劃分如圖3(h)所示，對應(yīng)的總關(guān)聯(lián)度值為22.43，其中每個子區(qū)的交叉口數(shù)目和關(guān)聯(lián)度對應(yīng)如表4所示。

圖3 路網(wǎng)子區(qū)劃分過程Fig.3 Partition process of road network

表3 初步劃分結(jié)果Table 3 Preliminary partition result

表4 邊界調(diào)整后劃分結(jié)果Table 4 Partition result after boundary adjustment

3.3 對比實驗

為了驗證Ncut在子區(qū)劃分中的優(yōu)越性，用層次聚類的方法在相同條件下作為對照，對交通路網(wǎng)進行劃分。凝聚的層次聚類在子區(qū)劃分中是一種較常用的基礎(chǔ)算法，其貪心的思想能在劃分中取得不錯的效果。在劃分時，層次聚類算法每次尋找兩個關(guān)聯(lián)度最為密切的交叉口并合并到同一子區(qū)，保證了劃分結(jié)果總關(guān)聯(lián)度值接近最大。作為對照，實驗采用上面的路網(wǎng)與關(guān)聯(lián)度矩陣，同樣要求劃分的子區(qū)規(guī)模不能超過15 個交叉口，不限制最后生成幾個子區(qū)。劃分結(jié)果如表5所示。層次聚類劃分結(jié)果所得到的總關(guān)聯(lián)值為22.03，較小于基于Ncut子區(qū)劃結(jié)果。但是層次聚類的劃分結(jié)果里常會出現(xiàn)單交叉口作為子區(qū)的情況，在上面的劃分中有2 個子區(qū)包含1 個交叉口，1 個子區(qū)包含2 個交叉口，這些少量交叉口形成的子區(qū)大都分布在路網(wǎng)的邊緣地帶。究其原因，層次聚類在劃分時讓關(guān)聯(lián)度最大的優(yōu)先合并，在路網(wǎng)內(nèi)部關(guān)聯(lián)度較大的合并達到子區(qū)最大規(guī)模時，路網(wǎng)邊緣交叉口則無法再并入子區(qū)，因而成為獨立子區(qū)。單交叉口形成子區(qū)往往給管理增加負擔，在子區(qū)劃分中應(yīng)盡量避免?；贜cut的子區(qū)劃分方法能均衡劃分，因此可以避免少數(shù)交叉口形成獨立子區(qū)的情況。

表5 基于層次聚類的子區(qū)劃分結(jié)果Table 5 Partition result based on hierarchical clustering

4 結(jié) 論

在交通子區(qū)動態(tài)劃分中，交通態(tài)勢對劃分結(jié)果產(chǎn)生重要影響。應(yīng)用重要交通流參數(shù)計算交通運行狀態(tài)，得到路段、交叉口擁堵態(tài)勢，結(jié)合路網(wǎng)靜態(tài)參數(shù)計算路網(wǎng)關(guān)聯(lián)度矩陣?；贜cut的交通子區(qū)劃分方法讓交通態(tài)勢相似，空間上臨近的交叉口劃分到同一子區(qū)，Ncut的每次分割是對目標網(wǎng)絡(luò)進行均衡分割，形成兩個互相關(guān)聯(lián)較小而內(nèi)部緊密的子區(qū)，并且避免少數(shù)交叉口形成獨立子區(qū)的情況。通過邊界調(diào)整，讓子區(qū)總關(guān)聯(lián)度達到最大，同時劃分結(jié)果趨于最優(yōu)。經(jīng)過真實路網(wǎng)數(shù)據(jù)驗證與對比實驗分析，該方法在滿足子區(qū)劃分要求的同時能出色完成子區(qū)劃分任務(wù)。