基于狄利克雷問題的路網(wǎng)控制子區(qū)動態(tài)劃分

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

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

0 概述

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

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

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

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

1 狄利克雷問題求解模型

構(gòu)建一個路網(wǎng)無向圖G=(V,E),其中,節(jié)點V={v1,v2,…,vi,vj,…,vm}表示m條路段,邊集合E={eij}表示所有路段間的n個交叉口。令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)交通量的時空分布。定義路網(wǎng)中控制子區(qū)的編號為G={G1,G2,…,Gk}。路網(wǎng)無向圖上狄利克雷問題的求解模型可看作是根據(jù)調(diào)和函數(shù)(定義如式(4)所示)求解路段對于各控制子區(qū)的概率矩陣r,其中,r(i,k)表示vi屬于子區(qū)Gk的概率。

(4)

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

(5)

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

(6)

由于L是半正定的,因此D[r]具有唯一的極小臨界點。將路網(wǎng)內(nèi)的路段分為2個部分,即劃分到控制子區(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ù),并找到臨界點:

BTrS+LUrU

(8)

(9)

對未分配路段對應(yīng)的子矩陣rU進行求解,任意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é)基于密度峰值理論,重新定義了局部密度概念,用于自動識別控制子區(qū)的穩(wěn)定塊,同時運用狄利克雷問題的求解模型實現(xiàn)控制子區(qū)的劃分。子區(qū)劃分流程如圖1所示。

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

2.1 局部密度定義

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

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

(11)

(12)

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

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

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

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

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

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

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

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

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

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

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

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

(13)

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

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

2.4 評價指標

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

(14)

(15)

(16)

(17)

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

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

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

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

算法動態(tài)劃分算法

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

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

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

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.搜索二次劃分的目標{vi,vi+1,…,vj};

22.End If

23.t←t+1//時段更新

24.For i∈[1,k] do

27.End For

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

4 案例分析

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

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

圖2 美國法默布蘭奇市的道路拓撲圖Fig.2 Road topology map of Farmers Branch,USA

截斷閾值θ是控制子區(qū)劃分中一個關(guān)鍵參數(shù),其取值直接決定了分區(qū)效果。本文選取晚高峰期(t=69)時的路網(wǎng)進行劃分。當分區(qū)數(shù)k=2～4時,θ值對NSk與TVn的影響如圖3所示。

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

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

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

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

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

將譜聚類算法、Newman算法[19]、密度峰值聚類算法[20]以及本文算法分別從NSk與TVn兩個方面對比算法性能,如表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ū)下不同算法的評價指標對比Table 2 Comparison of evaluation indexes of differentalgorithms under two partitions～four partitions

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

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

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

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

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

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

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

5 結(jié)束語

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