基于改進(jìn)社區(qū)發(fā)現(xiàn)算法的交通控制子區(qū)動(dòng)態(tài)劃分

張正華, 錢 錦, 房崇鑫, 張嘉烽, 顧逸楓

(揚(yáng)州大學(xué)信息工程學(xué)院, 江蘇 揚(yáng)州 225127)

對(duì)區(qū)域交通網(wǎng)絡(luò)的合理劃分可降低區(qū)域交通網(wǎng)絡(luò)整體控制與管理的復(fù)雜性[1-2]．針對(duì)復(fù)雜交通網(wǎng)絡(luò)下的子區(qū)域動(dòng)態(tài)劃分, 國(guó)內(nèi)外學(xué)者開展了大量研究．Etemadnia等[3]結(jié)合網(wǎng)絡(luò)出口函數(shù)(network exit function, NEF)對(duì)不同道路結(jié)構(gòu)的交通性能實(shí)現(xiàn)分區(qū), 但是此方法無法適用于大型交通網(wǎng)絡(luò); Ramezani等[4]引入基于整個(gè)交通網(wǎng)絡(luò)的聚合模型, 結(jié)合動(dòng)力學(xué)原理實(shí)現(xiàn)分區(qū),但因僅考慮了路段交通流量這一因素的影響,導(dǎo)致劃分結(jié)果不夠全面; Johnson等[5]采用雙層規(guī)劃模型預(yù)先定義若干互連子區(qū)域, 但該方法提前假設(shè)的子區(qū)域數(shù)目較為武斷; Lin等[6]考慮交通網(wǎng)絡(luò)流量的移動(dòng)性和吞吐量, 基于宏觀基本圖論(macroscopic fundamental diagram, MFD)提出一種需求平衡子區(qū)域劃分模型; Kouvelas等[7]運(yùn)用非線性模型描述劃分的子區(qū)隨時(shí)間變化的關(guān)系, 由于子區(qū)域劃分策略頻繁切換, 從而導(dǎo)致區(qū)域內(nèi)部不穩(wěn)定; An等[8]提出交通網(wǎng)絡(luò)四步劃分方法, 因增加了交通擁堵的劃分, 導(dǎo)致算法復(fù)雜度太大,而無法適用于大型網(wǎng)絡(luò); Dong等[9]基于文獻(xiàn)[6]方法通過回歸分析計(jì)算各個(gè)子區(qū)域的交通狀態(tài)值并合并若干小的子區(qū)域, 驗(yàn)證了小規(guī)模交通網(wǎng)絡(luò)的MFD存在, 但該算法限制了交通網(wǎng)絡(luò)外部邊界的車流流入; 徐建閩等[10]采用Mcut算法, 以路口飽和度表示交叉口的擁堵程度,從而建立路段權(quán)值模型進(jìn)行子區(qū)域劃分,該方法因須已知網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目, 故無法適用于未知網(wǎng)絡(luò); Li等[11]利用交通多源數(shù)據(jù)采集系統(tǒng)進(jìn)行交通信息預(yù)測(cè), 采用k-means算法對(duì)交通網(wǎng)絡(luò)進(jìn)行劃分,其聚類中心節(jié)點(diǎn)的選取存在主觀性．上述算法大部分針對(duì)無權(quán)網(wǎng)絡(luò)且劃分的結(jié)果具有不確定性,難以保證劃分的客觀性和有效性．社區(qū)發(fā)現(xiàn)算法[12-13]可以向著最優(yōu)模塊度的方向不斷合并網(wǎng)絡(luò)節(jié)點(diǎn)得到劃分結(jié)果,能夠保持較高的準(zhǔn)確性且適應(yīng)交通網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu);因此,本文擬改進(jìn)社區(qū)發(fā)現(xiàn)算法,以網(wǎng)絡(luò)模塊度作為劃分的評(píng)價(jià)指標(biāo), 綜合考慮相鄰交叉口之間的距離、路段交通流量時(shí)空特性、交通信號(hào)配時(shí)參數(shù)和車輛排隊(duì)長(zhǎng)度等因素,建立動(dòng)態(tài)子區(qū)域劃分模型, 并以江蘇省揚(yáng)州市部分區(qū)域的交通為案例進(jìn)行對(duì)比實(shí)驗(yàn), 驗(yàn)證方案的可行性和合理性．

1 相鄰交叉口的關(guān)聯(lián)度分析

1.1 路段長(zhǎng)度關(guān)聯(lián)度

當(dāng)兩交叉口間的距離較小時(shí), 二者表現(xiàn)出強(qiáng)相關(guān)性; 反之, 距離較大時(shí), 則表現(xiàn)出弱相關(guān)性．交叉口i、j之間的路段長(zhǎng)度關(guān)聯(lián)度

(1)

其中l(wèi)ij為交叉口i、j之間的距離,σ為縮小函數(shù)值域的配置參數(shù),lmin為兩交叉口間允許的最小距離．

1.2 車輛排隊(duì)長(zhǎng)度關(guān)聯(lián)度

車輛排隊(duì)長(zhǎng)度主要由前一個(gè)周期未通行車輛和上游路口駛?cè)氲能囕v組成．假設(shè)交叉口i處由北駛?cè)胂蜃筠D(zhuǎn)彎的車流量為qNLi, 由南駛?cè)胂蛴肄D(zhuǎn)彎的車流量為qSNi, 交叉口j處前一個(gè)周期未通行的車流量為qoddj, 平均車身長(zhǎng)度為Δl．故交叉口i、j的車輛排隊(duì)長(zhǎng)度關(guān)聯(lián)度

(2)

1.3 信號(hào)周期關(guān)聯(lián)度

當(dāng)兩交叉口的信號(hào)周期相同或呈倍數(shù)關(guān)系且相位差保持穩(wěn)定時(shí),兩交叉口間表現(xiàn)出強(qiáng)相關(guān)性;反之,若兩者信號(hào)周期相差較大且相位差參差不齊,兩交叉口間表現(xiàn)出弱相關(guān)性．交叉口i、j間的信號(hào)周期關(guān)聯(lián)度

(3)

其中cmax、cmin分別為交叉口i、j信號(hào)周期的最大值和最小值;R為相鄰交叉口周期的關(guān)聯(lián)度,一般取值為2;λ為信號(hào)周期關(guān)聯(lián)權(quán)重系數(shù),λ=ent(R+1).

綜合考慮上述相鄰交叉口的路段長(zhǎng)度、車輛排隊(duì)長(zhǎng)度及信號(hào)周期關(guān)聯(lián)度,建立總關(guān)聯(lián)度模型:

Dij=Dlij·Dqij·Dcij.

(4)

2 改進(jìn)的社區(qū)發(fā)現(xiàn)算法

2.1 社區(qū)模塊度

社區(qū)模塊度[14]被專用于社區(qū)劃分的性能評(píng)價(jià)．假設(shè)有x個(gè)節(jié)點(diǎn), 每個(gè)節(jié)點(diǎn)都代表一個(gè)輸出,現(xiàn)將其劃分成N個(gè)社區(qū), 其中一共有m個(gè)節(jié)點(diǎn)相連接．i和j為x中的任意兩個(gè)節(jié)點(diǎn), 當(dāng)兩個(gè)節(jié)點(diǎn)相連時(shí)Aij等于1, 反之則等于0．ki為節(jié)點(diǎn)i的度, 2m則為整個(gè)社區(qū)節(jié)點(diǎn)的度,si用來判斷i是否屬于同一社區(qū), 屬于則為1不屬于則為-1．定義模塊度

(5)

(6)

模塊度Q值越大代表社區(qū)網(wǎng)絡(luò)劃分的效果越好, 當(dāng)Q值為[0.3,0.7]時(shí)劃分結(jié)果較優(yōu)．

將式(5)改寫為

(7)

式中

(8)

(9)

其中evw表示一個(gè)節(jié)點(diǎn)在社區(qū)v內(nèi)、另一個(gè)節(jié)點(diǎn)在社區(qū)w內(nèi)的邊;hvv則代表在社區(qū)v內(nèi)所有的邊與整個(gè)社區(qū)網(wǎng)絡(luò)所有邊的比值;av為v社區(qū)節(jié)點(diǎn)的度占整個(gè)社區(qū)網(wǎng)絡(luò)度的比值．

2.2 改進(jìn)算法

參照文獻(xiàn)[15], 改進(jìn)文獻(xiàn)[13]中點(diǎn)權(quán)與邊權(quán)的表達(dá)式, 使得其更適用于有權(quán)網(wǎng)絡(luò)．將模塊度Q改寫為

(10)

式中對(duì)稱矩陣C表示網(wǎng)絡(luò)被劃分為k個(gè)社區(qū)的集合, 每個(gè)社區(qū)為一個(gè)矩陣c,c中元素cij為社區(qū)內(nèi)部邊權(quán)在整個(gè)網(wǎng)絡(luò)邊權(quán)中的占比,vi=∑jcij代表社區(qū)i內(nèi)部節(jié)點(diǎn)與外部相連節(jié)點(diǎn)的邊權(quán)和整個(gè)網(wǎng)絡(luò)邊權(quán)的比值．sum(C2)為C2中所有元素之和．

為了表示節(jié)點(diǎn)間關(guān)聯(lián)性的大小,現(xiàn)將式(8)(9)改寫為權(quán)值形式:

(11)

(12)

式中g(shù)ij為節(jié)點(diǎn)i和j之間邊的權(quán)值．

本文算法流程如下:

步驟1: 初始化社區(qū)網(wǎng)絡(luò), 將Y個(gè)節(jié)點(diǎn)劃分成各自獨(dú)立的社區(qū)．初始的evw滿足:

(13)

式中t為社區(qū)網(wǎng)絡(luò)的總邊數(shù);

步驟2: 合并有邊相連的節(jié)點(diǎn)形成新的社區(qū), 記錄每次合并后的模塊度增量ΔQ:

ΔQ=evw+ewv-2avaw=2(evw-avaw).

(14)

整個(gè)算法的運(yùn)行沿著模塊度Q增大最多或減少最小的方向進(jìn)行,每一次合并后更新相應(yīng)的元素evw,并將v,w社區(qū)有邊相連的節(jié)點(diǎn)進(jìn)行合并;

步驟3: 重復(fù)執(zhí)行步驟2,直至整個(gè)網(wǎng)絡(luò)成為一個(gè)整體, 共執(zhí)行n-1次合并, 由此可得社區(qū)網(wǎng)絡(luò)的劃分結(jié)構(gòu), 進(jìn)一步選擇對(duì)應(yīng)模塊度最大的Q值, 即可得到最優(yōu)的社區(qū)網(wǎng)絡(luò)劃分．

3 實(shí)例分析

3.1 交通網(wǎng)絡(luò)選取

本文以揚(yáng)州市部分交通網(wǎng)絡(luò)為實(shí)驗(yàn)對(duì)象,對(duì)改進(jìn)的算法進(jìn)行論證．選取以文昌閣為中心的全部安裝有交通信息檢測(cè)器的區(qū)域路網(wǎng)(如圖1所示), 其中包含23個(gè)路段和21個(gè)交叉口．為了直觀地說明, 現(xiàn)將圖1等效為如圖2所示的網(wǎng)絡(luò)節(jié)點(diǎn)圖, 交叉口等效為網(wǎng)絡(luò)節(jié)點(diǎn), 路段等效成網(wǎng)絡(luò)的邊,并對(duì)各節(jié)點(diǎn)進(jìn)行相應(yīng)的編號(hào)．

3.2 子區(qū)域劃分結(jié)果分析

采集2020年5月19日21個(gè)交叉口的交通數(shù)據(jù)信息,經(jīng)誤差分析剔除誤差較大的數(shù)據(jù)．選取14:00-15:00交通數(shù)據(jù)通過關(guān)聯(lián)度模型計(jì)算23個(gè)路段的關(guān)聯(lián)度,計(jì)算結(jié)果如表1所示．

分別采用傳統(tǒng)的社區(qū)發(fā)現(xiàn)算法和本文算法對(duì)選取的區(qū)域交通網(wǎng)絡(luò)進(jìn)行子區(qū)域劃分, 兩種最優(yōu)劃分結(jié)果如圖3所示．由圖3可見: 1) 傳統(tǒng)的社區(qū)發(fā)現(xiàn)算法的Q最大值為0.564 0, 整個(gè)網(wǎng)絡(luò)被劃分為4個(gè)社區(qū): 交叉口1、5、6、21為子區(qū)域Ⅰ; 交叉口2、4、10、11、12為子區(qū)域Ⅱ;交叉口7、8、9為子區(qū)域Ⅲ; 交叉口3、13、14、15、16、17、18、19、20為子區(qū)域Ⅳ．圖3(a)中交叉口1與交叉口5被劃分在同一區(qū)域內(nèi),而交叉口1與交叉口5在實(shí)際交通網(wǎng)絡(luò)中的距離遠(yuǎn)大于交叉口1與交叉口2、4的距離, 所以此類劃分方法存在不合理性,無法準(zhǔn)確顯示出交叉口之間的關(guān)聯(lián)性．

2) 改進(jìn)后算法的Q最大值為0.604 1, 整個(gè)網(wǎng)絡(luò)被劃分為5個(gè)社區(qū): 交叉口1、2、3、4、10、11、12、13、14為子區(qū)域Ⅰ; 交叉口5、6、21為子區(qū)域Ⅱ; 交叉口7、8、9為子區(qū)域Ⅲ; 交叉口15、16、19、20為子區(qū)域Ⅳ; 交叉口17、18為子區(qū)域Ⅴ．

結(jié)果表明: 本文算法在進(jìn)行子區(qū)域劃分時(shí)兼顧了相連交叉口路段長(zhǎng)度的固有屬性和交通環(huán)境的動(dòng)態(tài)特性, 并且Q值比傳統(tǒng)算法的高7.2%,本文算法劃分效果更優(yōu)．

表1 交叉口的關(guān)聯(lián)度計(jì)算結(jié)果

3.3 動(dòng)態(tài)劃分結(jié)果分析

選取當(dāng)日16:00-17:00數(shù)據(jù)驗(yàn)證本文算法的動(dòng)態(tài)劃分效果, 此時(shí)Q值為0.602 7, 劃分結(jié)果如圖4所示．整個(gè)網(wǎng)絡(luò)被劃分為5個(gè)社區(qū): 交叉口1、2、3、4、7、10、11、12、13、14為子區(qū)域Ⅰ; 交叉口5、6、21為子區(qū)域Ⅱ; 交叉口8、9為子區(qū)域Ⅲ; 交叉口15、16、19、20為子區(qū)域Ⅳ; 交叉口17、18為子區(qū)域Ⅴ．與圖3(b)劃分結(jié)果相比, 交叉口7劃分到區(qū)域Ⅰ中．結(jié)果表明本文算法可以實(shí)現(xiàn)不同時(shí)段的動(dòng)態(tài)劃分, 并且劃分的區(qū)域結(jié)果差異小,能夠保持整個(gè)交通網(wǎng)絡(luò)控制的穩(wěn)定性．

4 結(jié)論

本文綜合考慮交叉口之間的靜態(tài)和動(dòng)態(tài)特性建立交叉口關(guān)聯(lián)度模型,改進(jìn)社區(qū)網(wǎng)絡(luò)節(jié)點(diǎn)和邊的權(quán)值,進(jìn)而改進(jìn)社區(qū)發(fā)現(xiàn)算法．結(jié)果表明: 本文算法可以達(dá)到動(dòng)態(tài)劃分的目的,能促進(jìn)子區(qū)域內(nèi)信號(hào)協(xié)調(diào)控制決策的生成;有利于降低城市交通信號(hào)的聯(lián)合控制的復(fù)雜度,保證在同一個(gè)子區(qū)域內(nèi)的路口具有較強(qiáng)的內(nèi)聚性,而在不同子區(qū)域內(nèi)的路口具有較低的耦合性．