基于狄利克雷問題的路網控制子區動態劃分

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

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

0 概述

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

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

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

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

1 狄利克雷問題求解模型

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

(1)

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

D=diag{di}

(2)

(3)

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

(4)

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

(5)

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

(6)

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

(7)

求D[rU]關于rU的倒數,并找到臨界點:

BTrS+LUrU

(8)

(9)

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

(10)

2 控制子區靜態劃分

本節基于密度峰值理論,重新定義了局部密度概念,用于自動識別控制子區的穩定塊,同時運用狄利克雷問題的求解模型實現控制子區的劃分。子區劃分流程如圖1所示。

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

2.1 局部密度定義

由于交通路網屬于稀疏網絡,因此本文對傳統局部密度概念中節點的度進行加權,運用路段與其鄰域內其他路段的相似度來求解局部密度,使之適用于實際路網。

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

(11)

(12)

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

2.2 控制子區穩定塊識別

控制子區穩定塊識別算法步驟如下:

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

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

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

通過改進的局部密度概念,算法能夠自動獲取具有最大密度峰值的k個質心并識別控制子區的穩定塊,然后將穩定塊作為輸入參數進行靜態劃分模型的求解。

2.3 基于狄利克雷問題的控制子區靜態劃分

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

控制子區靜態劃分算法步驟如下:

輸出子區劃分結果G={G1,G2,…,Gk}

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

(13)

步驟3將具有最大緊密度的路段劃分到對應子區內。若路段與多個子區具有相同的最大緊密度,則任選其一,并重復此步驟,直到所有的子區內部連通時,靜態劃分結束。

步驟2和步驟3是針對算法在執行控制子區劃分時缺乏考慮路網拓撲結構及子區平滑性的不足,進行子區平滑性優化的過程。

2.4 評價指標

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

(14)

(15)

(16)

(17)

其中,ab(Gl,Gk)=1表示控制子區Gl、Gk相鄰,NGl表示子區Gl內的路段數。

3 控制子區動態劃分

由于交通量動態分布,若對每一時刻的路網都執行靜態劃分,計算復雜性較高,因此本文提出一種動態劃分算法存儲前一時刻穩定路段的劃分結果,同時對異質性高的路段進行微調,從而得到后一時刻較好的劃分結果,準確捕捉控制子區的演化趨勢。

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

算法動態劃分算法

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

輸出路網劃分結果G={G1,G2,…,Gk}

1.For i∈[1,k] do//t時刻穩定塊識別

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 (控制子區內部連通) 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//動態劃分穩定塊識別

4 案例分析

4.1 數據集與θ值的敏感度分析

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

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

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

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

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

表1 最優θ值下的路網評價指標Table 1 Evaluation index of road network underoptimal θ value

4.2 不同分區下靜態劃分效果分析

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

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

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

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

表2 2分區～4分區下不同算法的評價指標對比Table 2 Comparison of evaluation indexes of differentalgorithms under two partitions～four partitions

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

4.3 連續時段內動態劃分效果分析

此處分析2分區下t=69～75時段內本文算法與兩層動態劃分算法的動態劃分效果。不同時刻路網的飽和度分布如圖6所示,控制子區的劃分結果如圖7所示。

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

圖6 路網飽和度分布Fig.6 Saturation distribution of road network

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

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

5 結束語

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