盧守峰,陶黎明,江勇東
(長沙理工大學交通運輸工程學院,長沙410114)
隨著汽車保有量的激增,城市交通擁堵呈現(xiàn)出了區(qū)域特性,使得區(qū)域交通的宏觀建模得到關(guān)注.Daganzo等基于Godfrey對路網(wǎng)平均密度與平均流量相關(guān)性的發(fā)現(xiàn),在2008年提出了反映區(qū)域交通網(wǎng)絡狀態(tài)特性的宏觀基本圖(Macroscopic Fundamental Diagram,MFD)概念[1].之后利用實測數(shù)據(jù)創(chuàng)建宏觀交通基本圖成為研究熱點,盧守峰等[2]利用線圈檢測器數(shù)據(jù)和出租車GPS數(shù)據(jù)對宏觀交通基本圖的創(chuàng)建進行了研究.Geroliminis等[3]利用實測數(shù)據(jù)創(chuàng)建宏觀基本圖,發(fā)現(xiàn)交通網(wǎng)絡中車輛密度空間分布的均質(zhì)性是影響MFD形狀的關(guān)鍵因素.MFD的出現(xiàn)為交通控制策略提供了新思路,邊界交通控制研究得到發(fā)展.國內(nèi)學者張遜遜等提出基于MFD的多子區(qū)邊界反饋控制策略[4],結(jié)果表明多子區(qū)控制策略可進一步減少擁堵,這也體現(xiàn)了子區(qū)劃分的重要意義.
研究發(fā)現(xiàn)路網(wǎng)的均質(zhì)性是得到準確MFD的重要前提,因此服務于MFD創(chuàng)建的非均質(zhì)路網(wǎng)劃分研究開始得到關(guān)注.Ji等[5]以路段為聚類對象,在2012年提出利用譜聚類中的歸一化分割(Normalized cut,Ncut)方法進行路網(wǎng)劃分.該方法以路段的車輛密度屬性為對象,利用相似度函數(shù)計算權(quán)重矩陣,并通過求解矩陣特征系統(tǒng),將交通網(wǎng)絡劃分為密度分布均質(zhì)性較高的路段集合.譜聚類應用最早和最廣泛的是圖像分割領(lǐng)域,具有堅實的理論基礎(chǔ),但其存在兩個主要缺點:①劃分結(jié)果對參數(shù)值敏感;②需求解矩陣特征系統(tǒng),對于聚類規(guī)模較大的應用,計算和存儲壓力大.繼Ncut算法之后,Saeedmanesh等在2016年針對擁堵在路網(wǎng)中的傳播特性,提出一種三步聚類算法[6].該方法在規(guī)模較大及存在數(shù)據(jù)缺失的路網(wǎng)劃分中表現(xiàn)良好,但對于時間上的動態(tài)變化未考慮.因此,Saeedmanesh等在2017年又對該方法進行了改進[7],對歸屬穩(wěn)定的路段進行確定性聚類,然后再基于最小化目標函數(shù)對穩(wěn)定性低的路段進行合并或拆分.同年,Dimitriou等對K均值算法和METIS算法的路網(wǎng)劃分效果進行了對比[8].研究表明,K均值算法在單純的數(shù)值屬性對象聚類上性能優(yōu)于METIS算法,但其無法處理交通網(wǎng)絡的空間連接性與交通流運行的組合特性.
本文通過考慮路網(wǎng)空間結(jié)構(gòu)及其交通量分布在時間上的變化,對K均值算法在路網(wǎng)劃分中的應用進行改進.然后利用車牌照自動識別實測數(shù)據(jù)對改進的方法進行測試,并利用子區(qū)的宏觀基本圖對劃分結(jié)果進行分析.相比Saeedmanesh等在2016年提出的合并相似均勻路徑方法,以及其他分層處理聚類對象連續(xù)性要求的方法[9],本文將路網(wǎng)連接性約束事先融入于聚類算法中,實現(xiàn)聚類與連接性約束同步,避免聚類子區(qū)內(nèi)路段不連續(xù),聚類后需再根據(jù)連接性調(diào)整結(jié)果的不足.
K均值聚類作為一種經(jīng)典的聚類算法,因具有簡單高效的特點在各領(lǐng)域得到廣泛應用[10].雖然傳統(tǒng)的K均值聚類算法具有原理簡單、運算快捷、易于實現(xiàn)、可擴展空間大等優(yōu)勢,但其在路網(wǎng)劃分應用中的主要缺點有:①K值直接影響聚類結(jié)果,難以事先給出;②初始聚類中心的選擇對聚類結(jié)果干擾大;③對不穩(wěn)定的孤立點數(shù)據(jù)敏感;④聚類子區(qū)的路網(wǎng)連接性無法得到保障.這些問題使得傳統(tǒng)K均值聚類算法難以實現(xiàn)路網(wǎng)的有效劃分.
道路網(wǎng)絡劃分的目標是將具有強相似性和高關(guān)聯(lián)度的路段聚類成簇,方便準確把握區(qū)域交通狀態(tài).基于此,路網(wǎng)劃分結(jié)果要盡量滿足3點:
(1)同一簇內(nèi)路段之間的屬性差異和不同簇之間的相似性盡可能??;
(2)簇的數(shù)量要少,以減小控制策略的設(shè)計壓力和實施成本;
(3)在空間上確保子區(qū)路網(wǎng)的連通性和良好的緊湊性[11].
然而,在現(xiàn)實交通網(wǎng)絡中,上述3點要求相互沖突.第1點的最優(yōu)解要求簇數(shù)量盡可能大,每個路段本身單獨為1個簇,這與第2點沖突.連接性和緊湊性屬于空間要求,而第1點是數(shù)值上的要求,因此第1點對第3點具有限制.從可行性角度考慮,設(shè)計一個能夠在這些要求之間實現(xiàn)良好平衡的聚類機制成為了主要研究目標.對于路網(wǎng)劃分的結(jié)果評價,常用ANSK和TV值表示,其定義為[5]
式(4)可以轉(zhuǎn)化為以方差和平均值來表示的形式,即
同時
式中:K代表劃分得到的子區(qū)個數(shù);A、B代表兩個不同子區(qū);Neighbor(A)為空間上與聚類A相鄰的子區(qū);Fi和Fj分別為A和B中的對象屬性值;uA和uB分別為A和B中的對象屬性平均值;C為子區(qū)集合;NA表示A中對象個數(shù);d表示數(shù)據(jù)對象屬性個數(shù).
當不同子區(qū)的屬性平均值差越大,評價子區(qū)內(nèi)部方差越小,則NSk值越小,說明子區(qū)A的劃分效果越好.由于一個具有較小方差和NSk值的集群可能伴隨著一個具有較大方差和NSk值的相鄰子區(qū),所以用平均值A(chǔ)NSk對整區(qū)劃分的效果評價.
K均值算法改進的思想是通過路網(wǎng)連接矩陣保證路段的連接性,先利用最大最小距離[12]公式確定初始聚類中心和路段差異,再捕捉差異性最小的路段.算法改進后具體步驟如下:
Step1 構(gòu)建路網(wǎng)連接矩陣.
設(shè)路網(wǎng)中路段數(shù)為N,則先對其進行1~N的編號,然后建立N×N維的連接矩陣M,設(shè)連接道路i和j之間的權(quán)值M(i,j)為1;反之,為0.
Step2 選取初始聚類中心.
利用歐式公式計算路網(wǎng)中所有路段對車輛密度的距離集合U={D|D=,并取最大距離的路段對max{D}的路段i和j作為初始子區(qū)的聚類中心I和J.
Step3 路段捕捉.
先利用連接矩陣M,同步搜索分別與質(zhì)心路段I和J相連的路段;然后計算這些連接路段與質(zhì)心的歐式距離,并將距離值最小的路段捕捉至其對應質(zhì)心所在的子區(qū)(當某一路段與I和J都相連且都是距離最小路段時,我們定義為“競爭路段”.則通過對比該路段與兩個質(zhì)心的距離,將其歸屬于值小的子區(qū)).
Step4 子區(qū)更新.
搜索與子區(qū)內(nèi)已存在路段相連的路段,并按Step3的計算原則循環(huán)執(zhí)行路段捕捉,直至路網(wǎng)中所有路段得到劃分.
Step5 迭 代.
計算準則函數(shù)SSE值和子區(qū)的路段密度平均值,然后以子區(qū)內(nèi)密度值與其平均值最接近的路段作為新質(zhì)心,返回Step3直到SSE值不再減小.其中,p為數(shù)據(jù)對象,mj是簇Cj的平均值.
Step6 連續(xù)二分.
選取已分得子區(qū)中密度方差最大的一個子區(qū)作為再次劃分的新路網(wǎng),重復Step1~Step5,每次增加一個子區(qū),當子區(qū)劃分前后ANSK不再減小則終止劃分,并確定子區(qū)數(shù)量為K.
Step7 補充劃分.
對于規(guī)模較大的路網(wǎng),繼續(xù)進行二分,對比ANSK和ANSK+n的大小,其中n為整數(shù),且K+1 傳統(tǒng)K均值聚類算法應用時,初始K值很難確定,Step6可以在路網(wǎng)劃分中解決該問題.K值不提前給出,而是以劃分前后ANSK的變化為依據(jù),確定K值.但是,Step6通過比較連續(xù)二分后的ANSK大小,進行劃分終止的判定,當路網(wǎng)內(nèi)部交通荷載呈多區(qū)域均質(zhì)分布時,可能出現(xiàn)非最佳劃分狀況.例如,Step6劃分計算得到ANSK 考慮到子區(qū)的緊湊性和內(nèi)部交通動態(tài)變化,利用聚類中處理“噪聲”對象的常用思想,對連續(xù)時間間隔下的道路交通網(wǎng)絡進行劃分.通過統(tǒng)計路段在分區(qū)內(nèi)的頻數(shù)[9],對“噪聲”路段(定義為相鄰子區(qū)之間的‘連接路段’和與‘連接路段’相連的路段)進行拆分與合并調(diào)整,以減小不穩(wěn)定路段對劃分結(jié)果帶來的干擾.假設(shè)有t個時間段,具體操作如下: (1)根據(jù)每個時間段的交通狀態(tài)屬性值劃分路網(wǎng),并統(tǒng)計每條路段在不同子區(qū)內(nèi)出現(xiàn)的次數(shù)Fq,q代表子區(qū)編號. (2)進行“噪聲”路段判定,找出各子區(qū)的“噪聲”路段. (3)對比“噪聲”路段在不同子區(qū)內(nèi)出現(xiàn)的次數(shù),若其在某個子區(qū)內(nèi)出現(xiàn)次數(shù)Fq>t/K,且滿足連接性條件,則將其進行拆分后合并至該子區(qū). 為檢測改進后的K均值聚類算法在路網(wǎng)劃分中的效果,基于浙江紹興柯橋城區(qū)道路的車牌照數(shù)據(jù),進行路網(wǎng)劃分試驗.算法通過Matlab實現(xiàn),路段密度由CUPRITE模型[13]計算得到.為與文獻[5]的算法結(jié)果進行對比,密度單位,輛/m.初始路網(wǎng)如圖1所示. 該路網(wǎng)由39個交叉口和62條路段構(gòu)成,將某天6:10-21:50的時段取10 min為間隔,得到94個時間段.不同時段路段車輛密度變化如圖2所示.路網(wǎng)密度方差變化如圖3所示. 圖1 初始路網(wǎng)Fig.1 Initial road network 圖2 路段密度時間變化Fig.2 Time variation of links density 對于車輛密度均質(zhì)性最低(方差最大)的第70個時段(17:40-17:50)路網(wǎng)密度進行分割,由于該路網(wǎng)規(guī)模較小,子區(qū)數(shù)量上限H設(shè)為3.劃分結(jié)果如圖4和圖5所示,劃分子區(qū)的評價指標如表1所示. 路網(wǎng)經(jīng)過1次劃分后,在K=2時方差和TV的值相比初始路網(wǎng)(K=1)明顯變小.路網(wǎng)在經(jīng)過2次劃分后(K=3),其方差和TV值較第1次劃分前后,減小幅度大大降低,且ANSK值變大.基于此,確定K的值為2,然后進行“噪聲”路段的調(diào)整. 我們對94個時間間隔下的路網(wǎng)進行劃分,“噪聲”路段在兩個子區(qū)中出現(xiàn)次數(shù)情況如圖6所示. 圖4 1次劃分結(jié)果Fig.4 The first partition result 圖5 次劃分結(jié)果Fig.5 The second partition result 表1 子區(qū)評價指標值Table 1 Evaluation index values of sub regions 圖6 “噪聲”路段在不同子區(qū)內(nèi)出現(xiàn)次數(shù)統(tǒng)計Fig.6 Statistics on the number of"noise"links in different sub regions 根據(jù)這些路段在不同子區(qū)的出現(xiàn)次數(shù),若出現(xiàn)次數(shù)大于t K的子區(qū)與其現(xiàn)所在子區(qū)不同,且滿足與新區(qū)連接性條件,則將其拆分后合并至出現(xiàn)次數(shù)大的子區(qū).調(diào)整前后子區(qū)劃分如圖7所示.調(diào)整后的路網(wǎng)子區(qū)內(nèi),道路在空間上的緊湊性得到明顯提高. 為分析該路網(wǎng)劃分方法的優(yōu)劣,我們將試驗結(jié)果與傳統(tǒng)K均值聚類和歸一化分割的結(jié)果進行對比.其中,考慮到歸一化分割算法的參數(shù)敏感性問題,對其相似度函數(shù)exp(-α(Fi-Fj))2中的α取103和104,F(xiàn)代表路段i和j的車輛密度.兩個方法的子區(qū)劃分結(jié)果如圖8所示,對應評價指標如表2所示. 圖7 “噪聲”路段調(diào)整前和調(diào)整后子區(qū)圖Fig.7 Subarea graphs before and after adjustment of"noise"links 圖8 不同方法劃分結(jié)果Fig.8 Partition result of different method 表2 各方法子區(qū)評價指標值Table 2 Sub-region evaluation index values of different method 通過劃分結(jié)果的圖像和相關(guān)指標對比,可以發(fā)現(xiàn)傳統(tǒng)K均值聚類算法得到的子區(qū)方差、TV值和ANSK值最小,但同一個子區(qū)內(nèi)的路段在空間位置上不相連,無法應用.歸一化分割算法得到的子區(qū),在空間連接性和緊湊性上優(yōu)于另外兩種方法,但其在不同數(shù)量級的參數(shù)下,對同一狀態(tài)的路網(wǎng)劃分結(jié)果不同.本文提出的考慮連接性的K均值算法,在評價指標上不及傳統(tǒng)的K均值算法,但其很好地保證了子區(qū)路網(wǎng)的連接性,實現(xiàn)了其在路網(wǎng)劃分中的有效應用.同時,其聚類結(jié)果不存在對參數(shù)尺度敏感的問題. 為進一步證明改進后算法在路網(wǎng)劃分中的應用價值,我們繪制了劃分前后的MFD,如圖9所示. 在圖9中,路網(wǎng)經(jīng)劃分后可清晰看出各子區(qū)的最大流量是不同的,這可以為分析交通路網(wǎng)運行狀況和交通管控措施提供更準確的依據(jù). 在傳統(tǒng)K均值聚類算法中引入連接性約束,保證聚類子區(qū)內(nèi)道路的連接性.通過最大最小距離算法確定初始聚類中心和路段差異性,利用聚類評價指標ANSK確定K值,避免初始聚類中心和子區(qū)數(shù)量選取所導致的劃分結(jié)果不可靠現(xiàn)象.最后,從子區(qū)路網(wǎng)緊湊性角度出發(fā),統(tǒng)計連續(xù)時間內(nèi)多次劃分的路段子區(qū)出現(xiàn)的頻數(shù),對噪聲路段進行調(diào)整,進一步優(yōu)化子區(qū)路網(wǎng)的空間結(jié)構(gòu).利用自動車牌識別實測數(shù)據(jù),將該算法與傳統(tǒng)K均值聚類和歸一化分割算法進行對比.結(jié)果表明,該算法可以實現(xiàn)路段連續(xù),劃分結(jié)果不受參數(shù)尺度影響.通過路網(wǎng)劃分前后的宏觀基本圖對比,證明該算法可使非均質(zhì)路網(wǎng)得到有效劃分,更準確地分析交通運行狀況和實施交通管控措施.本文提出的路網(wǎng)劃分算法不區(qū)分方向,進一步研究將從交通流的方向性和動態(tài)變化角度展開.2 劃分試驗
2.1 實 例
2.2 效果分析
3 結(jié)論