(浙江工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,浙江 杭州 310023)
隨著城市的發(fā)展,交通路網(wǎng)規(guī)模擴(kuò)大,城市車(chē)輛不斷增加,區(qū)域性擁堵頻發(fā),使得本就復(fù)雜的交通網(wǎng)更加難以管理。為應(yīng)對(duì)城市交通問(wèn)題,城市交通協(xié)調(diào)控制策略被提出并不斷完善[1]。交通流的空間分布情況決定了協(xié)調(diào)控制策略必須有合理的目標(biāo)區(qū)域,交通子區(qū)劃分在協(xié)調(diào)控制中扮演著重要角色,直接影響到交通協(xié)調(diào)控制策略的效率與性能。交通子區(qū)劃分是協(xié)調(diào)控制策略實(shí)施之前的必要步驟。交通子區(qū)劃分的作用主要有:1) 把龐大而復(fù)雜的交通路網(wǎng)分為相對(duì)較小、更易管理的交通子區(qū),以分治的方法解決交通管理問(wèn)題;2) 根據(jù)每個(gè)子區(qū)的特點(diǎn)實(shí)施靈活的交通控制策略,以提高每個(gè)子區(qū)交通控制的性能;3) 在各個(gè)子區(qū)內(nèi)部執(zhí)行獨(dú)立的交通控制策略,避免了大規(guī)模集中式控制方法帶來(lái)的問(wèn)題,提高系統(tǒng)的可靠性。交通子區(qū)劃分的概念由Walinchus[2]在1971 年提出,以子區(qū)劃分是否依據(jù)動(dòng)態(tài)交通狀態(tài),可以分為靜態(tài)子區(qū)劃分與動(dòng)態(tài)子區(qū)劃分。在1969 年開(kāi)發(fā)的TRANSYT[3]與1979 年開(kāi)發(fā)的SCOOT[4]交通控制系統(tǒng)中,以靜態(tài)路網(wǎng)特征與歷史交通流信息作為劃分依據(jù),均采用了靜態(tài)子區(qū)劃分方法。靜態(tài)劃分方法在劃分后子區(qū)不再改變,不能根據(jù)交通流變化做出調(diào)整,會(huì)影響交通協(xié)調(diào)控制策略的效率。隨著實(shí)時(shí)交通流參數(shù)測(cè)量方法越來(lái)越成熟,動(dòng)態(tài)子區(qū)劃分方法的研究成為主流。沈國(guó)江等[5]提出了一種路口過(guò)飽和狀態(tài)識(shí)別方法,基于路口擁堵等級(jí)與相鄰路口關(guān)聯(lián)度,提出過(guò)飽和交通狀態(tài)下的控制子區(qū)動(dòng)態(tài)劃分方法。莫漢康等[6]提出在路線誘導(dǎo)條件下,可同時(shí)獲得實(shí)時(shí)與預(yù)測(cè)的交通流數(shù)據(jù),并依據(jù)距離原則、流量原則和周期原則等分別建立交通控制子區(qū)自動(dòng)劃分過(guò)程。Lin等[7]基于MFD設(shè)計(jì)了需求平衡模型,使得交通子區(qū)根據(jù)實(shí)際交通態(tài)勢(shì)調(diào)整,配合控制策略,對(duì)整個(gè)路網(wǎng)進(jìn)行優(yōu)化。
子區(qū)劃分主要根據(jù)交叉口間的關(guān)聯(lián)度進(jìn)行,關(guān)聯(lián)度是交叉口間靜態(tài)結(jié)構(gòu)特征和動(dòng)態(tài)交通流參數(shù)的組合,關(guān)聯(lián)度大的交叉口需要?jiǎng)澐值酵蛔訁^(qū)中,以更好地配合協(xié)調(diào)控制策略。Hu等[8]提出了一種新的車(chē)輛檢測(cè)器布設(shè)方法來(lái)收集、存儲(chǔ)高精度交通數(shù)據(jù),并建立基于交通狀態(tài)數(shù)據(jù)的干道相鄰交叉口關(guān)聯(lián)度模型。李瑞敏等[9]考慮路口間距、交通流離散性和交通流量等要素,應(yīng)用模糊推理確定路口間協(xié)調(diào)控制需求系數(shù)并用協(xié)調(diào)系數(shù)進(jìn)行控制子區(qū)劃分。Zhao等[10]提出了基于Newman快速算法的交通子區(qū)劃分方法,應(yīng)用于大規(guī)模路網(wǎng)劃分上,但其方法會(huì)劃分出規(guī)模相差巨大的子區(qū)。盧凱等[11]提出相鄰交叉口關(guān)聯(lián)度與多交叉口組合關(guān)聯(lián)度的計(jì)算公式,并建立協(xié)調(diào)控制子區(qū)的劃分模型,但所提方法時(shí)間復(fù)雜度高,在實(shí)際大規(guī)模路網(wǎng)中很難應(yīng)用。交通子區(qū)劃分雖然已進(jìn)行多年系統(tǒng)性研究,但還存在著一些問(wèn)題?,F(xiàn)有方法中大都以小規(guī)模路網(wǎng)中歷史數(shù)據(jù)或仿真數(shù)據(jù)進(jìn)行研究,難以保證在實(shí)際大規(guī)模路網(wǎng)上應(yīng)用的可行性,同時(shí)對(duì)劃分的目標(biāo)與原則缺少明確定義。歸一化分割[12](Normalized cut,簡(jiǎn)寫(xiě)為Ncut)是一種普聚類(lèi)算法,首先應(yīng)用在圖的分割領(lǐng)域,在劃分時(shí)以整體效益為目標(biāo),均衡地劃分圖。通過(guò)簡(jiǎn)化路網(wǎng)構(gòu)建成圖,可以應(yīng)用Ncut在大規(guī)模路網(wǎng)的劃分中,快速得到理想的劃分結(jié)果。實(shí)時(shí)交通狀態(tài)是交通控制的基礎(chǔ)數(shù)據(jù)[13],對(duì)子區(qū)劃分有顯著影響,筆者依據(jù)主要交通流參數(shù),給出路段與交叉口運(yùn)行態(tài)勢(shì)計(jì)算方法,并考慮交叉口距離因素,給出動(dòng)靜態(tài)結(jié)合的關(guān)聯(lián)度計(jì)算方法,并應(yīng)用Ncut對(duì)大規(guī)模交通路網(wǎng)進(jìn)行劃分。
速度可以直觀地反映出路段的運(yùn)行水平,我國(guó)制定了城市道路交通運(yùn)行等級(jí)標(biāo)準(zhǔn),規(guī)定了每個(gè)等級(jí)的道路速度與所處擁堵等級(jí),如表1所示。擁堵等級(jí)表以粗略的方式把速度劃分為5 個(gè)運(yùn)行等級(jí),但這種表示方法太過(guò)離散,不利于在研究中精確表示路段運(yùn)行水平。以Lj→i代表交叉口j到交叉口i的路段,為更精細(xì)化表示路段的擁堵水平,定義SLj→i為路段Lj→i的運(yùn)行態(tài)勢(shì),SLj→i是屬于[0,1]區(qū)間的浮點(diǎn)數(shù)據(jù),由0到1代表交通運(yùn)行態(tài)勢(shì)從暢通到嚴(yán)重?fù)矶拢x為
(1)
式中:vj→i為路段Lj→i的速度;vu為交通暢通和輕度擁堵的速度分解線;vd為中度擁堵與嚴(yán)重?fù)矶碌姆纸缇€。如果速度vj→i高于vu,設(shè)置SLj→i=0,表示交通態(tài)勢(shì)處于最好的狀態(tài)。當(dāng)路段速度vj→i低于vd,設(shè)置SLj→i=1,表示交通處于嚴(yán)重?fù)矶隆?/p>
表1 路段交通運(yùn)行等級(jí)劃分Table 1 Running level of link in different speed km/h
交叉口流量能一定程度上反映交叉口運(yùn)行態(tài)勢(shì)。交叉口態(tài)勢(shì)可以表示為交叉口流量與通行能力的比值,當(dāng)比值較小時(shí)表示處于暢通狀態(tài),較大時(shí)表示處于擁堵?tīng)顟B(tài)。交叉口不同的方向交通流量一般不同,所以擁堵水平有所差別,這里設(shè)置RFi,j表示交叉口i在j方向上的流量與這個(gè)方向的通行能力的比值,用來(lái)表示交叉口在這個(gè)方向的交通態(tài)勢(shì),其計(jì)算式為
(2)
式中:qi,j為交叉口i在j方向上的交通流量;ni,j為交叉口i在j方向上進(jìn)口車(chē)道數(shù);c為單車(chē)道通行能力。
圖1為15 min內(nèi)3 車(chē)道和2 車(chē)道道路交通車(chē)輛數(shù)與速度關(guān)系,可以看出速度受交通流量影響很大。流量的增加讓道路上車(chē)流密度變大,使速度降低,進(jìn)而影響到流量,使流量被限制在道路的通行能力之內(nèi)??梢钥闯觯涸?5 min內(nèi)3 車(chē)道車(chē)輛數(shù)最大值在420左右,2 車(chē)道最大值在280左右,所以單車(chē)道通行能力c取560 pcu/h。
圖1 15 min交通車(chē)輛數(shù)與速度關(guān)系圖Fig.1 Diagram of vehicle number and speed in 15 minutes
由于交通流時(shí)空連續(xù)的特點(diǎn),路段擁堵水平與其下游交叉口有很強(qiáng)關(guān)聯(lián)性。交叉口過(guò)飽和會(huì)顯著影響上游路段車(chē)輛匯入交叉口的速率,造成路段的擁堵。因此,可以使用路段擁堵水平反映其下游交叉口的擁堵水平。一般的,每個(gè)交叉口有4 條與其相連的路段,最為擁堵的路段對(duì)交叉口的影響最大。所以,定義SNi來(lái)表示交叉口i的擬合交通態(tài)勢(shì),其計(jì)算式為
(3)
用以擬合擁堵態(tài)勢(shì)整合交叉口方向流量信息與相連路段速度信息,取(0,1)之間的浮點(diǎn)數(shù),值越高表示交叉口越擁堵。
交通子區(qū)的動(dòng)態(tài)劃分要考慮路網(wǎng)結(jié)構(gòu)特點(diǎn)和交通狀態(tài),劃分出的子區(qū)應(yīng)有利于交通管理和協(xié)調(diào)控制策略的實(shí)施?;趯?duì)動(dòng)態(tài)子區(qū)劃分的理解和前人工作的總結(jié),筆者提出4 點(diǎn)劃分原則:1) 子區(qū)內(nèi)部交叉口的交通態(tài)勢(shì)度盡可能相似,以利于使用同一套配時(shí)方案;2) 距離是影響交叉口間關(guān)聯(lián)度的重要因素,距離越小關(guān)聯(lián)度越大;3) 同一子區(qū)的交叉口必須是空間上連通的,否則不利于交通管理;4) 子區(qū)的規(guī)模應(yīng)限制在合適的范圍內(nèi),因?yàn)橐?guī)模過(guò)大的子區(qū)其內(nèi)部交叉口的態(tài)勢(shì)差異勢(shì)必過(guò)大,同時(shí)也會(huì)更加復(fù)雜,不利于交通控制的實(shí)施,子區(qū)的最大交叉口數(shù)目設(shè)置為15比較合適[14]。
相鄰交叉口之間靜態(tài)關(guān)聯(lián)度主要由交叉口間距離(或者說(shuō)路段長(zhǎng)度)構(gòu)成。距離越短,關(guān)聯(lián)度越大,當(dāng)距離小于等于200 m,關(guān)聯(lián)度達(dá)到最大值。設(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之間路段的長(zhǎng)度;σX為配置參數(shù),取值為160;FS(i,j)反映了路網(wǎng)靜態(tài)部分中交叉口之間鄰接關(guān)系與距離關(guān)系,相鄰交叉口隨著距離增大,關(guān)聯(lián)度逐漸變小。
整合交叉口的交通態(tài)勢(shì),定義交叉口i與j的關(guān)聯(lián)度w(i,j)為
(5)
式中配置參數(shù)σI取值為0.2。此關(guān)聯(lián)度整合了動(dòng)靜態(tài)要素,動(dòng)態(tài)要素中,2 個(gè)交叉口之間擁堵態(tài)勢(shì)差異越大,關(guān)聯(lián)度越小。直接相連的2 個(gè)交叉口,距離越近、交通態(tài)勢(shì)越相近關(guān)聯(lián)度越大,反之越小。
Ncut在分割圖時(shí),把圖G=(V,E)(V是圖中節(jié)點(diǎn)的集合,E是圖中邊的集合)劃分為A和B兩部分時(shí),其中A∪B=V,A∩B=?,即移走所有連接A,B兩部分的邊,被移走的邊的權(quán)值之和定義為cut(A,B),表示子圖A,B之間的割值,即
(6)
式中w(u,v)為節(jié)點(diǎn)u和v之間邊的權(quán)重。Ncut使用了子圖之間歸一化割值(Ncut)和子圖內(nèi)部歸一化關(guān)聯(lián)度(Nassoc)來(lái)衡量劃分的優(yōu)劣,并定義為
(7)
(8)
Ncut(A,B)=2-Nassoc(A,B)
(9)
尋找最小的Ncut值問(wèn)題可以通過(guò)解特征方程高效計(jì)算出來(lái),其計(jì)算式為
(D-W)x=λDx
(10)
式中:W為圖G的邊權(quán)矩陣;D為W的度矩陣。求解特征方程式(10),可以利用第二小的特征解對(duì)應(yīng)的特征向量二分圖G。
把Ncut算法應(yīng)用到交通子區(qū)的劃分問(wèn)題上,對(duì)路網(wǎng)進(jìn)行初步劃分,步驟如下:
1) 基于交通路網(wǎng)構(gòu)建帶權(quán)圖G=(V,E),圖G中節(jié)點(diǎn)為路網(wǎng)中交叉口,邊為路段,權(quán)重為交叉口之間的關(guān)聯(lián)度,構(gòu)建邊權(quán)矩陣W。
2) 解特征方程(D-W)x=λDx。
3) 利用解得的第二小的特征值對(duì)應(yīng)的特征向量,劃分圖G。
4) 如果子圖中節(jié)點(diǎn)數(shù)多于15 個(gè),則遞歸地調(diào)用此過(guò)程對(duì)子圖劃分,直到子圖中節(jié)點(diǎn)數(shù)小于或等于15 個(gè)。
Ncut每次對(duì)圖的劃分以當(dāng)前最優(yōu)的歸一化割值為目標(biāo)進(jìn)行二分,而當(dāng)前劃分在其子圖的劃分結(jié)果中不一定是最優(yōu)的,隨著劃分次數(shù)的增加,使得劃分結(jié)果偏離最優(yōu)劃分目標(biāo)。在經(jīng)過(guò)多次劃分后,可能有子區(qū)邊界上個(gè)別節(jié)點(diǎn)在劃分結(jié)果里并非最優(yōu),需要做調(diào)整。調(diào)整以子區(qū)總關(guān)聯(lián)度最大為目標(biāo),每次移動(dòng)子區(qū)邊界上的交叉口到相鄰子區(qū),最終形成更加緊密的子區(qū)。子區(qū)總關(guān)聯(lián)度的計(jì)算為
(11)
式中:cor(G)為路網(wǎng)G的總關(guān)聯(lián)度;N為子區(qū)總數(shù)。通過(guò)對(duì)子區(qū)邊界節(jié)點(diǎn)調(diào)整,讓處于子區(qū)邊界上的節(jié)點(diǎn)回到能使得總關(guān)聯(lián)度最大的子區(qū)中,使劃分趨于最優(yōu)。具體步驟如下:
1) 計(jì)算當(dāng)前劃分的總關(guān)聯(lián)度,并記為cor(G)pre。
2) 對(duì)所有子區(qū)邊緣的交叉口i(i∈A),如果在i并入其相鄰的子區(qū)B后,B中交叉口數(shù)目沒(méi)達(dá)到子區(qū)規(guī)模上限,計(jì)算當(dāng)節(jié)點(diǎn)i加入子區(qū)B之后總的cor(G)值。
3) 選擇步驟2)中所算出來(lái)的最大的cor(G),判斷其是否大于cor(G)pre,如果大于,則讓其對(duì)應(yīng)節(jié)點(diǎn)加入對(duì)應(yīng)子區(qū),返回步驟1)并繼續(xù)。否則,調(diào)整結(jié)束。
為檢驗(yàn)上述討論方法,設(shè)計(jì)實(shí)驗(yàn)使用真實(shí)的路網(wǎng)數(shù)據(jù)來(lái)加以驗(yàn)證。實(shí)驗(yàn)路網(wǎng)是紹興市柯橋區(qū),共有23條路,223 個(gè)路段和69 個(gè)交叉口,從主城區(qū)到郊區(qū),交叉口和路段上全都覆蓋了交通檢測(cè)器。實(shí)驗(yàn)以2017 年6 月6 日17:00—17:15晚高峰的數(shù)據(jù)來(lái)作研究,路網(wǎng)交通態(tài)勢(shì)如圖2所示。同時(shí)在交通圖2中圈出了路網(wǎng)的一部分,其中交叉口已做編號(hào),交通流量和運(yùn)行態(tài)勢(shì)在如表2所示。交通運(yùn)行態(tài)勢(shì)由交叉口的方向飽和度和相連路段的擁堵態(tài)勢(shì)組成,數(shù)值越大表示擁堵程度越高。
圖2 路段交通態(tài)勢(shì)圖Fig.2 Map of link traffic state
表2 路網(wǎng)部分交叉口流量及態(tài)勢(shì)Table 2 Traffic flow and traffic state of part road network
應(yīng)用基于歸一化分割的子區(qū)劃分方法在柯橋區(qū)路網(wǎng)上進(jìn)行子區(qū)劃分,圖3為劃分過(guò)程。圖3(a)為劃分的路網(wǎng)范圍。圖3(b)中,經(jīng)過(guò)第1 次分割路網(wǎng)被劃分為地圖最下部的6 個(gè)交叉口與路網(wǎng)其他部分??梢钥闯龅貓D最下面的6 個(gè)路口通過(guò)1 條干道組成1 個(gè)子區(qū),它們與路網(wǎng)的其他部分只有1 條道路相連,因此容易形成獨(dú)立子區(qū)。圖3(c~g)中,每次劃分都近似為對(duì)目標(biāo)網(wǎng)絡(luò)的均衡劃分,并且產(chǎn)生2 個(gè)形狀良好且空間上緊密相連的子區(qū)。Ncut劃分從原則上要求子區(qū)內(nèi)部交叉口間有較強(qiáng)的關(guān)聯(lián)度,而較強(qiáng)的關(guān)聯(lián)度傾向于讓子區(qū)形成較規(guī)則的形狀。在圖3(g)中,最后把16 個(gè)交叉口劃分形成了子區(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均衡分割的特點(diǎn)最后形成2 個(gè)交叉口數(shù)目相近的穩(wěn)定子區(qū)??梢钥闯觯夯贜cut劃分方法能有效把擁堵相近、距離緊密的交叉口劃分到同一子區(qū)內(nèi)。路網(wǎng)最后被劃分為7 個(gè)子區(qū),各子區(qū)交叉口數(shù)目及關(guān)聯(lián)度值如表3所示,總關(guān)聯(lián)度為22.36。
經(jīng)過(guò)邊界調(diào)整,共有3 個(gè)節(jié)點(diǎn)從原來(lái)的子區(qū)移動(dòng)到臨近子區(qū)中。最終的劃分如圖3(h)所示,對(duì)應(yīng)的總關(guān)聯(lián)度值為22.43,其中每個(gè)子區(qū)的交叉口數(shù)目和關(guān)聯(lián)度對(duì)應(yīng)如表4所示。
圖3 路網(wǎng)子區(qū)劃分過(guò)程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
為了驗(yàn)證Ncut在子區(qū)劃分中的優(yōu)越性,用層次聚類(lèi)的方法在相同條件下作為對(duì)照,對(duì)交通路網(wǎng)進(jìn)行劃分。凝聚的層次聚類(lèi)在子區(qū)劃分中是一種較常用的基礎(chǔ)算法,其貪心的思想能在劃分中取得不錯(cuò)的效果。在劃分時(shí),層次聚類(lèi)算法每次尋找兩個(gè)關(guān)聯(lián)度最為密切的交叉口并合并到同一子區(qū),保證了劃分結(jié)果總關(guān)聯(lián)度值接近最大。作為對(duì)照,實(shí)驗(yàn)采用上面的路網(wǎng)與關(guān)聯(lián)度矩陣,同樣要求劃分的子區(qū)規(guī)模不能超過(guò)15 個(gè)交叉口,不限制最后生成幾個(gè)子區(qū)。劃分結(jié)果如表5所示。層次聚類(lèi)劃分結(jié)果所得到的總關(guān)聯(lián)值為22.03,較小于基于Ncut子區(qū)劃結(jié)果。但是層次聚類(lèi)的劃分結(jié)果里常會(huì)出現(xiàn)單交叉口作為子區(qū)的情況,在上面的劃分中有2 個(gè)子區(qū)包含1 個(gè)交叉口,1 個(gè)子區(qū)包含2 個(gè)交叉口,這些少量交叉口形成的子區(qū)大都分布在路網(wǎng)的邊緣地帶。究其原因,層次聚類(lèi)在劃分時(shí)讓關(guān)聯(lián)度最大的優(yōu)先合并,在路網(wǎng)內(nèi)部關(guān)聯(lián)度較大的合并達(dá)到子區(qū)最大規(guī)模時(shí),路網(wǎng)邊緣交叉口則無(wú)法再并入子區(qū),因而成為獨(dú)立子區(qū)。單交叉口形成子區(qū)往往給管理增加負(fù)擔(dān),在子區(qū)劃分中應(yīng)盡量避免?;贜cut的子區(qū)劃分方法能均衡劃分,因此可以避免少數(shù)交叉口形成獨(dú)立子區(qū)的情況。
表5 基于層次聚類(lèi)的子區(qū)劃分結(jié)果Table 5 Partition result based on hierarchical clustering
在交通子區(qū)動(dòng)態(tài)劃分中,交通態(tài)勢(shì)對(duì)劃分結(jié)果產(chǎn)生重要影響。應(yīng)用重要交通流參數(shù)計(jì)算交通運(yùn)行狀態(tài),得到路段、交叉口擁堵態(tài)勢(shì),結(jié)合路網(wǎng)靜態(tài)參數(shù)計(jì)算路網(wǎng)關(guān)聯(lián)度矩陣?;贜cut的交通子區(qū)劃分方法讓交通態(tài)勢(shì)相似,空間上臨近的交叉口劃分到同一子區(qū),Ncut的每次分割是對(duì)目標(biāo)網(wǎng)絡(luò)進(jìn)行均衡分割,形成兩個(gè)互相關(guān)聯(lián)較小而內(nèi)部緊密的子區(qū),并且避免少數(shù)交叉口形成獨(dú)立子區(qū)的情況。通過(guò)邊界調(diào)整,讓子區(qū)總關(guān)聯(lián)度達(dá)到最大,同時(shí)劃分結(jié)果趨于最優(yōu)。經(jīng)過(guò)真實(shí)路網(wǎng)數(shù)據(jù)驗(yàn)證與對(duì)比實(shí)驗(yàn)分析,該方法在滿(mǎn)足子區(qū)劃分要求的同時(shí)能出色完成子區(qū)劃分任務(wù)。