張 曼,閆 飛,閻高偉,李 浦

(太原理工大學(xué) 電氣與動(dòng)力工程學(xué)院,太原 030024)

0 概述

城市規(guī)模的迅速擴(kuò)張使路網(wǎng)復(fù)雜性日益增加,針對(duì)交通擁堵的演化研究由此得到廣泛關(guān)注。然而對(duì)單路段擁堵狀況的研究難以適應(yīng)相鄰路段擁堵時(shí)的傳播和消散特性[1]。將路網(wǎng)劃分為不同擁堵程度的控制子區(qū),能夠可視化地顯示實(shí)時(shí)的擁堵場(chǎng)景,這體現(xiàn)了路網(wǎng)控制子區(qū)動(dòng)態(tài)劃分的重要性。

目前,對(duì)于路網(wǎng)控制子區(qū)的劃分方法已有一些相關(guān)研究[2-3]。研究者通常運(yùn)用譜圖理論[4]或歸一化分割(Normalized cut,Ncut)算法[5]求解矩陣特征系統(tǒng),從而將異構(gòu)路網(wǎng)劃分為密度均勻的控制子區(qū),但此類方法的劃分性能對(duì)參數(shù)值較為敏感。文獻(xiàn)[6]運(yùn)用遺傳算法與降維處理方法構(gòu)建一種控制子區(qū)快速劃分模型。文獻(xiàn)[7]考慮擁堵的傳播特性構(gòu)建一種相似性模型,將高相似性的路段聚類成簇。文獻(xiàn)[8]將大型路網(wǎng)轉(zhuǎn)化為密度峰值圖,并運(yùn)用圖切割算法實(shí)現(xiàn)控制子區(qū)劃分的快速尋優(yōu)。文獻(xiàn)[9]在Ncut算法的基礎(chǔ)上構(gòu)建具有最優(yōu)宏觀基本圖的控制子區(qū)劃分模型,但其獲取的子區(qū)邊界存在不平滑情形。文獻(xiàn)[10]基于λ-連通性的概念提出一種啟發(fā)式劃分算法,并執(zhí)行邊界調(diào)整程序得到具有光滑邊界的控制子區(qū)。文獻(xiàn)[11]將路段間的拓?fù)涮匦匀谌隟均值聚類算法中,彌補(bǔ)了必須對(duì)不平滑子區(qū)再根據(jù)連接性微調(diào)的不足。

上述方法實(shí)現(xiàn)了路網(wǎng)的靜態(tài)劃分,但未考慮子區(qū)在時(shí)間維度上的動(dòng)態(tài)演化。文獻(xiàn)[12]研究擁堵路段的時(shí)空關(guān)系,根據(jù)前一時(shí)刻的劃分結(jié)果,通過目標(biāo)函數(shù)最小化對(duì)后一時(shí)刻的高異質(zhì)性路段進(jìn)行合并或分割。文獻(xiàn)[13]采用一種兩層劃分方法,通過增量地更新控制子區(qū)來跟蹤擁堵的傳播,該方法與每一刻都重新執(zhí)行路網(wǎng)控制子區(qū)靜態(tài)劃分的方法相比具有更高的效率。

本文考慮路段的密度分布與交通流的時(shí)變特性,設(shè)計(jì)一種新的控制子區(qū)動(dòng)態(tài)劃分算法。利用路段與其鄰域內(nèi)其他路段的相似度重新定義局部密度概念,確定控制子區(qū)劃分方案,并對(duì)孤立路段進(jìn)行再處理,實(shí)現(xiàn)聚類與連通性的同步約束。在此基礎(chǔ)上,將狄利克雷問題求解模型融入算法中,迭代更新高異質(zhì)性路段的劃分結(jié)果,從而捕捉子區(qū)的演變趨勢(shì),實(shí)現(xiàn)控制子區(qū)的動(dòng)態(tài)劃分。

1 狄利克雷問題求解模型

構(gòu)建一個(gè)路網(wǎng)無向圖G=(V,E),其中,節(jié)點(diǎn)V={v1,v2,…,vi,vj,…,vm}表示m條路段,邊集合E={eij}表示所有路段間的n個(gè)交叉口。令si、sj表示路段vi、vj的飽和度,則路段vi、vj間的相似度w(i,j)定義如式(1)所示:

(1)

本文設(shè)置參數(shù)σ=0.1,并構(gòu)建相似度矩陣W={w(i,j)}m×m。度矩陣D的定義如式(2)和式(3)所示:

D=diag{di}

(2)

(3)

人為設(shè)置控制子區(qū)數(shù)k,以適應(yīng)交通量的時(shí)空分布。定義路網(wǎng)中控制子區(qū)的編號(hào)為G={G1,G2,…,Gk}。路網(wǎng)無向圖上狄利克雷問題的求解模型可看作是根據(jù)調(diào)和函數(shù)(定義如式(4)所示)求解路段對(duì)于各控制子區(qū)的概率矩陣r,其中,r(i,k)表示vi屬于子區(qū)Gk的概率。

(4)

由于拉普拉斯方程是狄利克雷積分的拉格朗日方程[14],因此拉普拉斯方程滿足邊界條件2r=0。定義(n×m)階的路段關(guān)聯(lián)矩陣,如式(5)所示:

(5)

定義(n×n)階的0-1對(duì)角矩陣C,則拉式矩陣可計(jì)算為L=ATCA,調(diào)和函數(shù)可分解為式(6):

(6)

由于L是半正定的,因此D[r]具有唯一的極小臨界點(diǎn)。將路網(wǎng)內(nèi)的路段分為2個(gè)部分,即劃分到控制子區(qū)的穩(wěn)定塊VS與未分配路段VU,VS∪VU=V,VS∩VU=?。求解調(diào)和函數(shù)的臨界值,即在確定穩(wěn)定塊的情況下求解未分配路段屬于不同子區(qū)的概率。假設(shè)L和r中控制子區(qū)的穩(wěn)定塊為第一部分,未分配路段依次排序在后,則調(diào)和函數(shù)可分解為式(7):

(7)

求D[rU]關(guān)于rU的倒數(shù),并找到臨界點(diǎn):

BTrS+LUrU

(8)

(9)

對(duì)未分配路段對(duì)應(yīng)的子矩陣rU進(jìn)行求解,任意vi屬于各子區(qū)的概率之和滿足式(10)。獲取第(i-S)行(i∈{S+1,S+2,…,m})最大值的所在列l(wèi)∈{1,2,…,k},即將vi劃分到子區(qū)Gl內(nèi)。

(10)

2 控制子區(qū)靜態(tài)劃分

本節(jié)基于密度峰值理論,重新定義了局部密度概念,用于自動(dòng)識(shí)別控制子區(qū)的穩(wěn)定塊,同時(shí)運(yùn)用狄利克雷問題的求解模型實(shí)現(xiàn)控制子區(qū)的劃分。子區(qū)劃分流程如圖1所示。

圖1 控制子區(qū)劃分流程Fig.1 Partition procedure of control sub-regions

2.1 局部密度定義

由于交通路網(wǎng)屬于稀疏網(wǎng)絡(luò),因此本文對(duì)傳統(tǒng)局部密度概念中節(jié)點(diǎn)的度進(jìn)行加權(quán),運(yùn)用路段與其鄰域內(nèi)其他路段的相似度來求解局部密度,使之適用于實(shí)際路網(wǎng)。

基于密度峰值理論[15],將任意路段vi到每一個(gè)更高局部密度路段vj的最短路徑記為pij,并將其中的最小值記為pi。局部密度ρi的定義如式(11)和式(12)所示:

(11)

(12)

其中,θ是一個(gè)截?cái)嚅撝?ρi表示在vi的鄰域內(nèi)其他點(diǎn)與該點(diǎn)大于θ值的相似度之和。上述局部密度只對(duì)θ的相對(duì)大小敏感,說明基于局部密度的劃分算法具有很好的魯棒性。θ的敏感度分析詳見本文第4節(jié)。

2.2 控制子區(qū)穩(wěn)定塊識(shí)別

控制子區(qū)穩(wěn)定塊識(shí)別算法步驟如下:

輸入路段集合V,局部密度集合{ρ1,ρ2,…,ρm}

步驟2若任意多個(gè)質(zhì)心在空間上相鄰,則只保留局部密度最大的質(zhì)心,依次選擇高局部密度的路段作為新的質(zhì)心。循環(huán)該過程,直到所有質(zhì)心互不相鄰。此時(shí),保證質(zhì)心周圍是低密度路段,以避免質(zhì)心選取到異常點(diǎn)。若獲得的質(zhì)心數(shù)小于k,則返回步驟1,重新賦k值。

步驟3計(jì)算剩余的任意路段vi到各質(zhì)心的最短路徑。若pi=pij=1,則將vi歸屬于質(zhì)心vj所在的穩(wěn)定塊;若vi與多個(gè)質(zhì)心的最短路徑均為1,則將其歸屬于與之具有最大相似性的質(zhì)心所在的穩(wěn)定塊;否則跳過該路段,重復(fù)此步驟,直到遍歷完所有路段,穩(wěn)定塊集合的更新結(jié)束。

通過改進(jìn)的局部密度概念,算法能夠自動(dòng)獲取具有最大密度峰值的k個(gè)質(zhì)心并識(shí)別控制子區(qū)的穩(wěn)定塊,然后將穩(wěn)定塊作為輸入?yún)?shù)進(jìn)行靜態(tài)劃分模型的求解。

2.3 基于狄利克雷問題的控制子區(qū)靜態(tài)劃分

狄利克雷問題的求解模型能夠解決子區(qū)內(nèi)的最大關(guān)聯(lián)性辨識(shí)問題[16]。本節(jié)將改進(jìn)的局部密度概念運(yùn)用于求解模型中,達(dá)到將高相似性路段聚類成簇的目的。

控制子區(qū)靜態(tài)劃分算法步驟如下:

輸出子區(qū)劃分結(jié)果G={G1,G2,…,Gk}

步驟1將路網(wǎng)內(nèi)路段分為VS(劃分到子區(qū)的穩(wěn)定塊)與VU(未分配路段),通過求解狄利克雷問題,對(duì)VU內(nèi)的元素進(jìn)行劃分。

(13)

步驟3將具有最大緊密度的路段劃分到對(duì)應(yīng)子區(qū)內(nèi)。若路段與多個(gè)子區(qū)具有相同的最大緊密度,則任選其一,并重復(fù)此步驟,直到所有的子區(qū)內(nèi)部連通時(shí),靜態(tài)劃分結(jié)束。

步驟2和步驟3是針對(duì)算法在執(zhí)行控制子區(qū)劃分時(shí)缺乏考慮路網(wǎng)拓?fù)浣Y(jié)構(gòu)及子區(qū)平滑性的不足,進(jìn)行子區(qū)平滑性優(yōu)化的過程。

2.4 評(píng)價(jià)指標(biāo)

將子區(qū)內(nèi)部勻質(zhì)性的均值NSk[17]與歸一化總方差TVn[7]作為評(píng)價(jià)指標(biāo),對(duì)比不同分區(qū)下的路網(wǎng)劃分性能,定義如式(14)～式(17)所示。兩者的取值越小,表明劃分效果越好。

(14)

(15)

(16)

(17)

其中,ab(Gl,Gk)=1表示控制子區(qū)Gl、Gk相鄰,NGl表示子區(qū)Gl內(nèi)的路段數(shù)。

3 控制子區(qū)動(dòng)態(tài)劃分

由于交通量動(dòng)態(tài)分布,若對(duì)每一時(shí)刻的路網(wǎng)都執(zhí)行靜態(tài)劃分,計(jì)算復(fù)雜性較高,因此本文提出一種動(dòng)態(tài)劃分算法存儲(chǔ)前一時(shí)刻穩(wěn)定路段的劃分結(jié)果,同時(shí)對(duì)異質(zhì)性高的路段進(jìn)行微調(diào),從而得到后一時(shí)刻較好的劃分結(jié)果,準(zhǔn)確捕捉控制子區(qū)的演化趨勢(shì)。

本文提出的動(dòng)態(tài)劃分算法采用迭代的聚類過程。在初始時(shí)刻t控制子區(qū)靜態(tài)劃分結(jié)果的基礎(chǔ)上,計(jì)算各子區(qū)(t+1)時(shí)刻的飽和度均值,并更新相似度矩陣,取飽和度與所在子區(qū)飽和度均值差異最小的路段作為新的質(zhì)心,以識(shí)別(t+1)時(shí)刻控制子區(qū)的交通狀態(tài)。在此基礎(chǔ)上,將質(zhì)心作為初始的穩(wěn)定塊,迭代地捕捉與穩(wěn)定塊具有最大相似度wmax的路段,并將其添加到穩(wěn)定塊集合中。需要注意的是,穩(wěn)定塊必須包含在該子區(qū)內(nèi)。但隨著迭代次數(shù)的增多,該塊的異質(zhì)性呈非線性增長趨勢(shì)。因此,此處設(shè)置限制條件wmax>δ,使得穩(wěn)定塊達(dá)到一定覆蓋率時(shí)截止擴(kuò)展并縮短運(yùn)行時(shí)間。本文設(shè)置δ=0.3。最后利用控制子區(qū)靜態(tài)劃分算法對(duì)剩余路段進(jìn)行劃分。動(dòng)態(tài)劃分算法僅將異質(zhì)性高的路段作為研究對(duì)象,降低了計(jì)算復(fù)雜性,具體描述如下:

算法動(dòng)態(tài)劃分算法

輸入控制子區(qū)數(shù)k,終止時(shí)刻t′,局部密度{ρ1,ρ2,…,ρm},ρ1>ρ2>…>ρm

輸出路網(wǎng)劃分結(jié)果G={G1,G2,…,Gk}

1.For i∈[1,k] do//t時(shí)刻穩(wěn)定塊識(shí)別

3.End For

4.For i∈[k+1,m] do

5.If (pi=pil=1) then

7.Elseif (pi=pil=…=pik=1) then

8.w(i,l)=max{w(i,l),w(i,l+1),…,w(i,k)};

10.Else (pi>1) then

11.++i;

12.End If

13.End For

14.While (t

16.If (控制子區(qū)內(nèi)部連通) then

18.Else (存在孤立路段集) then

19.搜索二次劃分的目標(biāo){vi,vi+1,…,vj};

22.End If

23.t←t+1//時(shí)段更新

24.For i∈[1,k] do

27.End For

28.End While//動(dòng)態(tài)劃分穩(wěn)定塊識(shí)別

4 案例分析

4.1 數(shù)據(jù)集與θ值的敏感度分析

考慮數(shù)據(jù)與問題來源的真實(shí)性,本文以美國法默布蘭奇市[18]某區(qū)域的真實(shí)數(shù)據(jù)集為例進(jìn)行分析。該路網(wǎng)包含211條路段,道路拓?fù)鋱D如圖2所示。數(shù)據(jù)集包含所有路段在2014年10月所有工作日的飽和度均值。本文將全天00:00—23:15的時(shí)段取15 min為間隔,得到93個(gè)時(shí)段,以飽和度為特性進(jìn)行研究。

圖2 美國法默布蘭奇市的道路拓?fù)鋱DFig.2 Road topology map of Farmers Branch,USA

截?cái)嚅撝郸仁强刂谱訁^(qū)劃分中一個(gè)關(guān)鍵參數(shù),其取值直接決定了分區(qū)效果。本文選取晚高峰期(t=69)時(shí)的路網(wǎng)進(jìn)行劃分。當(dāng)分區(qū)數(shù)k=2～4時(shí),θ值對(duì)NSk與TVn的影響如圖3所示。

圖3 2分區(qū)～4分區(qū)下θ對(duì)NSk與TVn的影響Fig.3 Influence of θ to NSk and TVn under two partitions～four partitions

由圖3可見,在不同分區(qū)數(shù)下,NSk與TVn指標(biāo)值隨著θ的增大逐漸變小,表明算法的劃分性能逐漸增強(qiáng)?？刂谱訁^(qū)數(shù)k分別為2、3、4時(shí),路網(wǎng)的最優(yōu)θ值為0.95、0.95、0.25,此時(shí)NSk與TVn最小,即算法的劃分效果最佳。最優(yōu)θ值下的路網(wǎng)評(píng)價(jià)指標(biāo)如表1所示。

表1 最優(yōu)θ值下的路網(wǎng)評(píng)價(jià)指標(biāo)Table 1 Evaluation index of road network underoptimal θ value

4.2 不同分區(qū)下靜態(tài)劃分效果分析

t=69時(shí)刻的控制子區(qū)靜態(tài)劃分結(jié)果如圖4所示。結(jié)合圖5中各控制子區(qū)內(nèi)飽和度的頻率分布可知:當(dāng)t=69時(shí),2分區(qū)時(shí)的子區(qū)2內(nèi)部通暢,多數(shù)路段的飽和度集中在0.2～0.5,子區(qū)1為飽和區(qū)域;4分區(qū)下的3、4子區(qū)內(nèi)飽和度相似,但連接兩者的公共路段較少,因此,將其劃分為兩部分。由于執(zhí)行了子區(qū)邊界平滑處理,因此各控制子區(qū)內(nèi)部完全連通,為交通信號(hào)控制策略提供了準(zhǔn)確的依據(jù)。

將譜聚類算法、Newman算法[19]、密度峰值聚類算法[20]以及本文算法分別從NSk與TVn兩個(gè)方面對(duì)比算法性能,如表2所示,表中數(shù)據(jù)均以NSk/TVn的形式列出。

圖4 2分區(qū)～4分區(qū)下控制子區(qū)的分布Fig.4 Distribution of control sub-regions under two partitions～four partitions

圖5 2分區(qū)～4分區(qū)下飽和度的頻率分布Fig.5 Frequency distribution of saturation under two partitions～four partitions

表2 2分區(qū)～4分區(qū)下不同算法的評(píng)價(jià)指標(biāo)對(duì)比Table 2 Comparison of evaluation indexes of differentalgorithms under two partitions～four partitions

由表2可見,在3種分區(qū)模式下,本文算法相較其他算法的NSk與TVn值均最小,即控制子區(qū)的勻質(zhì)性最高。其中,2分區(qū)時(shí)本文算法相較密度峰值算法的NSk、TVn分別降低22%和11%,體現(xiàn)了算法的有效性。

4.3 連續(xù)時(shí)段內(nèi)動(dòng)態(tài)劃分效果分析

此處分析2分區(qū)下t=69～75時(shí)段內(nèi)本文算法與兩層動(dòng)態(tài)劃分算法的動(dòng)態(tài)劃分效果。不同時(shí)刻路網(wǎng)的飽和度分布如圖6所示,控制子區(qū)的劃分結(jié)果如圖7所示。

由圖7(a)可見,本文算法與兩層動(dòng)態(tài)劃分算法[13]在大部分時(shí)刻的劃分結(jié)果相較隨著時(shí)間的步進(jìn)一直保持原劃分結(jié)果的靜態(tài)劃分具有更好的效果。其中,本文算法在除t=71時(shí)的其他劃分結(jié)果相較兩層動(dòng)態(tài)劃分算法性能更好,體現(xiàn)了本文算法的有效性。由圖7(b)可見,t=69～75時(shí)段內(nèi)2個(gè)控制子區(qū)的飽和度逐漸減小,說明路網(wǎng)處于擁堵消散階段。同時(shí)由圖8可見,擁堵子區(qū)1(虛線區(qū)域)呈現(xiàn)先擴(kuò)大后縮小的變化趨勢(shì)。

圖6 路網(wǎng)飽和度分布Fig.6 Saturation distribution of road network

圖7 2分區(qū)下t=69～75時(shí)段算法劃分性能Fig.7 Partition performance of algorithms att=69～75 under two partitions

圖8 2分區(qū)下t=69～75時(shí)段控制子區(qū)演化過程Fig.8 Evolution process of control sub-regions att=69～75 under two partitions

5 結(jié)束語

本文結(jié)合密度峰值理論和狄利克雷問題求解模型,提出一種路網(wǎng)控制子區(qū)的動(dòng)態(tài)劃分算法,用以實(shí)現(xiàn)控制子區(qū)的快速尋優(yōu),同時(shí)提高子區(qū)邊界的平滑性并捕捉控制子區(qū)的動(dòng)態(tài)演化趨勢(shì)。以美國法默布蘭奇市的真實(shí)路網(wǎng)數(shù)據(jù)集作為案例進(jìn)行分析,結(jié)果表明,該算法能夠有效提升子區(qū)內(nèi)部勻質(zhì)性均值與歸一化總方差,增強(qiáng)控制子區(qū)動(dòng)態(tài)劃分的時(shí)效性。下一步擬將該動(dòng)態(tài)劃分算法應(yīng)用于邊界控制中,并結(jié)合具體需求加以優(yōu)化。