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

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

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

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

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

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

(1)

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

1.2 車輛排隊長度關(guān)聯(lián)度

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

(2)

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

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

(3)

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

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

Dij=Dlij·Dqij·Dcij.

(4)

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

2.1 社區(qū)模塊度

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

(5)

(6)

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

將式(5)改寫為

(7)

式中

(8)

(9)

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

2.2 改進算法

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

(10)

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

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

(11)

(12)

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

本文算法流程如下:

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

(13)

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

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

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

(14)

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

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

3 實例分析

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

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

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

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

分別采用傳統(tǒng)的社區(qū)發(fā)現(xiàn)算法和本文算法對選取的區(qū)域交通網(wǎng)絡(luò)進行子區(qū)域劃分, 兩種最優(yōu)劃分結(jié)果如圖3所示．由圖3可見: 1) 傳統(tǒng)的社區(qū)發(fā)現(xiàn)算法的Q最大值為0.564 0, 整個網(wǎng)絡(luò)被劃分為4個社區(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在實際交通網(wǎng)絡(luò)中的距離遠大于交叉口1與交叉口2、4的距離, 所以此類劃分方法存在不合理性,無法準(zhǔn)確顯示出交叉口之間的關(guān)聯(lián)性．

2) 改進后算法的Q最大值為0.604 1, 整個網(wǎng)絡(luò)被劃分為5個社區(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é)果表明: 本文算法在進行子區(qū)域劃分時兼顧了相連交叉口路段長度的固有屬性和交通環(huán)境的動態(tài)特性, 并且Q值比傳統(tǒng)算法的高7.2%,本文算法劃分效果更優(yōu)．

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

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

選取當(dāng)日16:00-17:00數(shù)據(jù)驗證本文算法的動態(tài)劃分效果, 此時Q值為0.602 7, 劃分結(jié)果如圖4所示．整個網(wǎng)絡(luò)被劃分為5個社區(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é)果表明本文算法可以實現(xiàn)不同時段的動態(tài)劃分, 并且劃分的區(qū)域結(jié)果差異小,能夠保持整個交通網(wǎng)絡(luò)控制的穩(wěn)定性．

4 結(jié)論

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