鄭黎黎 王世廣 王 偉 丁同強(qiáng)

(吉林大學(xué)汽車仿真與控制國家重點(diǎn)實(shí)驗(yàn)室1) 長春 130022) (吉林大學(xué)交通學(xué)院2) 長春 130022)(吉林大學(xué)吉林省道路交通重點(diǎn)實(shí)驗(yàn)室3) 長春 130022)

城市道路交通網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)辨識方法研究*

鄭黎黎1,2,3)王世廣2)王 偉2)丁同強(qiáng)2)

(吉林大學(xué)汽車仿真與控制國家重點(diǎn)實(shí)驗(yàn)室1)長春 130022) (吉林大學(xué)交通學(xué)院2)長春 130022)(吉林大學(xué)吉林省道路交通重點(diǎn)實(shí)驗(yàn)室3)長春 130022)

綜合考慮城市道路網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)特征和交通流特性，建立城市道路交通網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)評價指標(biāo)體系；設(shè)計了基于P-灰色加權(quán)關(guān)聯(lián)分析的關(guān)鍵節(jié)點(diǎn)辨識方法，利用長春市區(qū)域路網(wǎng)進(jìn)行了實(shí)例分析，并和其他方法的排序結(jié)論進(jìn)行了對比，證實(shí)文中提出的方法可行、有效.通過進(jìn)一步數(shù)據(jù)擬合，給出了節(jié)點(diǎn)重要度和相關(guān)指標(biāo)的擬合公式.

交通工程；關(guān)鍵節(jié)點(diǎn)辨識；復(fù)雜網(wǎng)絡(luò)理論；主成分分析；灰色加權(quán)關(guān)聯(lián)分析

0 引 言

就城市交通網(wǎng)絡(luò)的演化特征而言，網(wǎng)絡(luò)拓?fù)鋵Τ鞘薪煌ňW(wǎng)絡(luò)上的流量分布、出行阻抗分布，以及其他動力學(xué)過程具有潛在的巨大影響[1-2].從這一角度，許多學(xué)者借鑒其他領(lǐng)域利用復(fù)雜網(wǎng)絡(luò)理論幾何特征指標(biāo)對節(jié)點(diǎn)重要性評價的思路開展了交通領(lǐng)域的研究[3-6].文獻(xiàn)[7-9]分別提出最短路徑介數(shù)、最小生成樹和參數(shù)I(i)=Ce(i)×M(i)×K(i)等作為指標(biāo)來衡量節(jié)點(diǎn)的重要性.文獻(xiàn)[10]提出了一種以路段阻抗為權(quán)重、以凝聚度為指標(biāo)的加權(quán)節(jié)點(diǎn)收縮方法.另外，從路網(wǎng)的交通流特性角度出發(fā)，文獻(xiàn)[11]基于節(jié)點(diǎn)刪除法提出了考慮級聯(lián)失效的交通網(wǎng)絡(luò)節(jié)點(diǎn)重要度評價方法，認(rèn)為出行網(wǎng)絡(luò)結(jié)構(gòu)、出行者行為對節(jié)點(diǎn)重要度有重要影響.文獻(xiàn)[12]選取行程車速、延誤和飽和度等對城市道路交通關(guān)鍵節(jié)點(diǎn)進(jìn)行辨別.本文綜合考慮城市道路網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)特征和交通流特性，提出基于道路等級的節(jié)點(diǎn)度、基于行程時間的節(jié)點(diǎn)介數(shù)和平均路徑長度變化率與交通流主要特性指標(biāo)共同構(gòu)成關(guān)鍵節(jié)點(diǎn)評價體系，并運(yùn)用主成分分析與灰色加權(quán)關(guān)聯(lián)分析相結(jié)合的方法來實(shí)現(xiàn)城市道路交通網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)的辨識，最后進(jìn)行實(shí)例分析.

1 城市道路交通網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)評價指標(biāo)體系的構(gòu)建及優(yōu)化

1.1 交叉口重要度函數(shù)

圖1為關(guān)鍵節(jié)點(diǎn)評價體系.定義交叉口重要度λ是評價指標(biāo)體系中各參數(shù)的一個函數(shù)，若設(shè)A為復(fù)雜網(wǎng)絡(luò)特性指標(biāo)集合；B為交通特性指標(biāo)集合,則有λ=f(A;B).

圖1 關(guān)鍵節(jié)點(diǎn)評價指標(biāo)體系

1.2 復(fù)雜網(wǎng)絡(luò)特性指標(biāo)

1) 基于道路等級的節(jié)點(diǎn)度k結(jié)合復(fù)雜網(wǎng)絡(luò)理論中節(jié)點(diǎn)度的概念，本文定義基于道路等級的節(jié)點(diǎn)度為交叉口所連路段各進(jìn)口道與出口道車道數(shù)之和的均值.

(1)

式中:n為交叉口進(jìn)口道數(shù)；kjo為交叉口出口道車道數(shù)；kji為交叉口進(jìn)口道車道數(shù).

通常，度越大代表著該節(jié)點(diǎn)在網(wǎng)絡(luò)中越重要，它描述了節(jié)點(diǎn)的連接程度.

2) 平均路徑長度變化率ΔL基于行程時間的平均路徑長度變化率

(2)

式中：L0為在自由行駛條件下的平均路徑長度；Li為任意節(jié)點(diǎn)i刪除后道路交通網(wǎng)絡(luò)的平均路徑長度.

其中，平均路徑長度是交通網(wǎng)絡(luò)中所有節(jié)點(diǎn)對之間距離的平均值，即

(3)

式中：N為道路交通網(wǎng)絡(luò)中節(jié)點(diǎn)的個數(shù)；dij為從節(jié)點(diǎn)i到節(jié)點(diǎn)j的最短距離；V為道路交通網(wǎng)絡(luò)中的節(jié)點(diǎn)集.

通常，平均路徑長度變化率越大，表明該節(jié)點(diǎn)在交通網(wǎng)絡(luò)中越重要.

3) 基于行程時間的介數(shù)Bi基于行程時間的節(jié)點(diǎn)介數(shù)可定義為道路交通網(wǎng)絡(luò)中所有的最短路徑中經(jīng)過該節(jié)點(diǎn)的數(shù)量比例.節(jié)點(diǎn)i的介數(shù)Bi由下式計算.

(4)

式中：njk為任意連接點(diǎn)j和k的最短路徑的數(shù)量；njk(i)為連接點(diǎn)j和k且經(jīng)過點(diǎn)i最短路徑的數(shù)量.此處最短路徑是指從i到j(luò)所需行程時間最小的路徑，可通過Floyd算法計算出所有節(jié)點(diǎn)對之間的最短路徑.

依據(jù)最短行程時間計算的介數(shù)反映了節(jié)點(diǎn)在整個交通網(wǎng)絡(luò)中的作用和影響力，具有很強(qiáng)的現(xiàn)實(shí)意義.

對于交通特性指標(biāo)的詳細(xì)定義參見相關(guān)書籍，限于篇幅在此不再贅述.

1.3 評價指標(biāo)的優(yōu)化

為了提高算法的精度和效率，選取主成分分析法(principal component analysis)來確定關(guān)鍵節(jié)點(diǎn)的主要影響因素.它是一種設(shè)法將原來變量重新組合成一組新的互相無關(guān)的幾個綜合變量，同時根據(jù)實(shí)際需要從中可以取出幾個較少的總和變量盡可能多地反映原來變量的信息的統(tǒng)計方法，在數(shù)學(xué)上經(jīng)常用于處理降維問題.

在獲得各個指標(biāo)xi(i=1,2,…,n)的數(shù)據(jù)之后，對其進(jìn)行主成分分析，選取特征值大于1且一般累積貢獻(xiàn)率大于85%的成分作為主成分yj(j=1,2,…,m)(m≤n)，則λ=f(y1,y2,…,ym).

2 基于P-灰色加權(quán)關(guān)聯(lián)分析的城市道路交通網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)評估算法

基于P-灰色關(guān)聯(lián)分析的城市道路交通網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)評價步驟如下.

步驟1 假設(shè)路網(wǎng)中共有N個節(jié)點(diǎn)，m個節(jié)點(diǎn)評價指標(biāo)，則第α(1≤α≤N)個節(jié)點(diǎn)的比較數(shù)列為

yα(j)=[yα(1),yα(2),yα(3),...,yα(m)]

式中：yα(j)為第α個節(jié)點(diǎn)的第j個主成分.

步驟2 綜合比較后得出這些節(jié)點(diǎn)的評價指標(biāo)參考序列Y= [Y(1)，Y(2)，…，Y(m)].其中：該序列中的Y(j)是所有節(jié)點(diǎn)中第j個主成分的最優(yōu)值.

步驟3 數(shù)據(jù)量綱一的量化處理 這里可以采用SPSS對數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理，得到比較數(shù)據(jù)序列

量綱一的量化后得到參考數(shù)據(jù)序列

Y*= [Y*(1)，Y*(2)，…，Y*(m)]

根據(jù)

(5)

分別求出最大值Δmax和最小值Δmin.

步驟4 確定各指標(biāo)對應(yīng)的權(quán)重 可由主成分分析中的特征值近似確定各指標(biāo)對應(yīng)的權(quán)重w=w(j),j=(1,2,…,m).

步驟5 計算判斷指標(biāo)關(guān)聯(lián)系數(shù)

(6)

式中：ρ為分辨系數(shù)，取值在0-1之間，通常取ρ=0.5.

步驟6 計算灰色加權(quán)關(guān)聯(lián)度，得到交叉口重要度

(7)

步驟7 計算每個節(jié)點(diǎn)的灰色加權(quán)關(guān)聯(lián)度大小，一般地，關(guān)聯(lián)度越大節(jié)點(diǎn)就越重要，關(guān)聯(lián)度最大的節(jié)點(diǎn)為關(guān)鍵節(jié)點(diǎn).

3 實(shí)例分析

3.1 數(shù)據(jù)獲取及指標(biāo)優(yōu)化

本文選取長春市亞泰大街、解放大路、民康路和三道街包圍的路網(wǎng)作為分析對象，見圖2.根據(jù)2013年12月24日早高峰調(diào)查的基礎(chǔ)數(shù)據(jù)并經(jīng)

過相關(guān)計算得到10個節(jié)點(diǎn)的7類評價指標(biāo)，見表1.

圖2 交通網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

序號指標(biāo)kΔLBi流量q/(pcu·h-1)飽和度x排隊(duì)長度l/m延誤/s16.750.04760.07456530.51730.0924.8727.800.08040.10475110.69822.6440.2036.000.03820.06724340.6956.6431.1442.500.06420.11121470.49710.1012.9453.000.09840.09628980.5497.3012.5064.000.04570.06717510.6798.2018.1277.330.03680.08951990.74119.6223.9086.000.02450.16364230.53012.417.7392.500.10200.12614480.3036.2412.84102.250.12500.1049890.4042.1410.31

利用SPSS對數(shù)據(jù)進(jìn)行主成分分析，選取2個主成分yj(j=1,2)，經(jīng)標(biāo)準(zhǔn)化的各個指標(biāo)xi(i=1,2,…,7)分別代表節(jié)點(diǎn)度、平均路徑變化率、介數(shù)、流量、飽和度、排隊(duì)長度、延誤.則有各主成分表達(dá)式

y1= 0.48x1-0.33x2-0.13x3+

0.41x4+0.38x5+0.39x6+0.42x7

(8)

y2= 0.08x1+0.03x2+0.77x3+

0.44x4-0.39x5+0.21x6-0.10x7

(9)

第一主成分y1中，除平均路徑變化率和介數(shù)與其呈負(fù)相關(guān)之外，y1與其他指標(biāo)為正相關(guān)關(guān)系，且各系數(shù)大體相當(dāng)，可看成是反映這些變量的綜合指標(biāo)；第二主成分y2中，與其呈負(fù)相關(guān)關(guān)系的指標(biāo)是飽和度和延誤，介數(shù)、流量、排隊(duì)長度的系數(shù)比較大，可以看成是主要反映這些變量的綜合指標(biāo).不難看出，兩個主成分對于城市路網(wǎng)拓?fù)湫再|(zhì)和交通流特性的反映各有側(cè)重.

3.2 關(guān)鍵節(jié)點(diǎn)評估與分析

利用式(8),(9)計算初始數(shù)據(jù)，然后按照評估算法計算可得到如下的交叉口重要度分布圖，見圖3.

圖3 重要度分布

由圖3可見，交叉口2的重要度最大，為該路網(wǎng)的關(guān)鍵節(jié)點(diǎn).這與交通流運(yùn)行情況相符，調(diào)查日區(qū)域交通擁擠最先出現(xiàn)在該交叉口，因而該方法具有一定的有效性和可行性.

為了進(jìn)一步說明本文算法的精度，下面將把本文算法與經(jīng)典的節(jié)點(diǎn)刪除法、節(jié)點(diǎn)收縮法和灰色關(guān)聯(lián)度法[13]進(jìn)行對比分析.需要指出，交通網(wǎng)絡(luò)為加權(quán)復(fù)雜網(wǎng)絡(luò)，節(jié)點(diǎn)收縮法考慮了交通阻抗的影響；而灰色關(guān)聯(lián)度法采用的是本文選取的指標(biāo),重要度排序?qū)Ρ纫姳?.

由表2可見，本例中各個方法對于關(guān)鍵節(jié)點(diǎn)的判定結(jié)果是一致的，對于其他節(jié)點(diǎn)的重要度排序存在較大差異.經(jīng)過對比分析可獲得以下結(jié)論.

1) 節(jié)點(diǎn)刪除法與本文算法對比 排序第2的節(jié)點(diǎn)分別為8和7.雖然兩個節(jié)點(diǎn)皆為主次干路相交，但節(jié)點(diǎn)7中民康路為雙向六車道，而節(jié)點(diǎn)8中大經(jīng)路為雙向4車道；刪除節(jié)點(diǎn)7后路網(wǎng)平均路徑長度變化幅度更大；節(jié)點(diǎn)7的飽和度、排隊(duì)長度、延誤明顯高于節(jié)點(diǎn)8.因而按照本文關(guān)鍵節(jié)點(diǎn)的定義，節(jié)點(diǎn)7對路網(wǎng)結(jié)構(gòu)安全、可靠及路網(wǎng)整體性能發(fā)揮更為重要.其他分析過程類似.故本文算法更優(yōu).節(jié)點(diǎn)刪除法認(rèn)為去掉該節(jié)點(diǎn)以及相關(guān)聯(lián)的鏈路后使得圖的生成樹數(shù)目最小的為關(guān)鍵節(jié)點(diǎn).對交通網(wǎng)絡(luò)來講，單純從路網(wǎng)拓?fù)浣Y(jié)構(gòu)的角度考慮是不盡合理的.因而本文借鑒其思路進(jìn)行了改進(jìn)，并且取得了更強(qiáng)的解釋性.

表2 重要度排序?qū)Ρ?/p>

2) 節(jié)點(diǎn)收縮法與本文算法對比 排序第2的節(jié)點(diǎn)分別為9和7.首先，節(jié)點(diǎn)7為主次干路相交，節(jié)點(diǎn)9為次干路與支路相交；節(jié)點(diǎn)7和9的高峰小時流量分別為5 199,1 448 pcu/h，交通功能相差懸殊.因而本文認(rèn)為節(jié)點(diǎn)7更為重要.其他分析過程類似.故本文算法更優(yōu).節(jié)點(diǎn)收縮法認(rèn)為收縮后使得網(wǎng)絡(luò)凝聚程度越高的節(jié)點(diǎn)就越重要，其定義的凝聚度的概念對于交通網(wǎng)絡(luò)突出特性的體現(xiàn)并不充分；(3)灰色關(guān)聯(lián)度法與本文算法對比.兩種方法的爭議主要在排序第2的節(jié)點(diǎn)：節(jié)點(diǎn)1和7.由重要度分布圖中不難看出，兩者的重要度非常相近.為了表現(xiàn)本文算法的辨識性深入對比分析一下.兩個節(jié)點(diǎn)都是主次干路相交，但節(jié)點(diǎn)7中民康路為雙向6車道，節(jié)點(diǎn)1中大經(jīng)路為雙向4車道，且大經(jīng)路西北-東南方向?yàn)樘厥獾?車道，東嶺街為支路；有更多的最短路徑經(jīng)過節(jié)點(diǎn)7；流量大體相當(dāng)?shù)那闆r下節(jié)點(diǎn)7的飽和度明顯高于節(jié)點(diǎn)1.因而節(jié)點(diǎn)7對于路網(wǎng)整體性能的發(fā)揮、穩(wěn)定更為關(guān)鍵.可以認(rèn)為，本文算法的結(jié)論更合理一些.

綜合以上分析，P-灰色加權(quán)關(guān)聯(lián)分析算法更為合理、有效.

3.3 模型簡化

城市道路交通網(wǎng)絡(luò)中該算法參數(shù)同時獲取難度較大、計算相對復(fù)雜，下文將根據(jù)算例對模型進(jìn)行簡化分析，以期獲得更好的應(yīng)用.

首先，將重要度與SPSS給出的標(biāo)準(zhǔn)化數(shù)據(jù)進(jìn)行逐步回歸分析，得到

λ=3.708+0.480k′+0.364q′

(10)

式中：λ為重要度；k′為標(biāo)準(zhǔn)化的節(jié)點(diǎn)度；q′為標(biāo)準(zhǔn)化的流量.修正R2=0.979.

然后，從單個變量入手進(jìn)一步探究各指標(biāo)與結(jié)論之間的關(guān)系.其中與排序相關(guān)系數(shù)較大的指標(biāo)有節(jié)點(diǎn)度、流量、延誤、排隊(duì)長度，相關(guān)系數(shù)分別為0.963，0.944，0.848，0.838，相互關(guān)系見圖4.

圖4 排序結(jié)論與相關(guān)變量的關(guān)系

此處延誤與排隊(duì)長度變化趨勢大體一致，未給出對比圖.其中基于道路等級的節(jié)點(diǎn)度可以反映城市路網(wǎng)的拓?fù)湫再|(zhì)，流量、延誤、排隊(duì)長度可以反映城市路網(wǎng)的交通流特性.考慮到各指標(biāo)的獲取難度和相關(guān)程度，分別對節(jié)點(diǎn)度和流量與重要度進(jìn)行擬合，可以根據(jù)實(shí)際情況進(jìn)行參照使用.擬合關(guān)系式為

λ=3.708+0.794k′

(11)

λ=3.708+0.777q′

(12)

式中：λ為重要度；k′為標(biāo)準(zhǔn)化的節(jié)點(diǎn)度；q′為標(biāo)準(zhǔn)化的流量.

4 結(jié) 束 語

本文基于道路交通網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)特征和交通流特性，研究并建立了路網(wǎng)中關(guān)鍵節(jié)點(diǎn)的評價指標(biāo)體系及辨識方法，并通過實(shí)例分析驗(yàn)證了該方法的有效性和實(shí)用性，根據(jù)實(shí)際數(shù)據(jù)給出了可供參考的關(guān)鍵節(jié)點(diǎn)重要度與相關(guān)指標(biāo)的擬合公式，為交通管理者在交通控制和應(yīng)急管理方面確定關(guān)鍵節(jié)點(diǎn)提供了新方法和新思路.

[1]沈鴻飛,賈利民,王笑京,等.基于公路網(wǎng)結(jié)構(gòu)特性的關(guān)鍵節(jié)點(diǎn)評價指標(biāo)與辨識方法[J].公路交通科技,2012,29(9):137-142.

[2]吳建軍.城市交通網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)復(fù)雜性研究[D].北京:北京交通大學(xué),2008.

[3]BONACICH P. Factoring and weighting approa-ches to status scores and clique identification[J].The Journal of Mathematical Sociology,1972,2(1):113-120.

[4]FREEMAN L C. Centrality in social networks conceptual clarification[J].Social Networks,1979(3):215-239.

[5]陳 勇,胡愛群,胡 駿,等.通信網(wǎng)中最重要節(jié)點(diǎn)的確定方法[J].高技術(shù)通訊,2004,14(1):21-24.

[6]譚躍進(jìn),吳 俊,鄧宏鐘.復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)重要度評估的節(jié)點(diǎn)收縮方法[J].系統(tǒng)工程理論與實(shí)踐,2006,26(11):79-83,102.

[7]高 潔.交通運(yùn)輸網(wǎng)絡(luò)節(jié)點(diǎn)重要度評價體系研究[J].聊城大學(xué)學(xué)報:自然科學(xué)版,2010,23(3):92-95,110.

[8]ENRICO N, GUIDO P, PETER W. Finding the most vital node of a shortest path[J].Theoretical Computer Science,2003(1):167-177.

[9]LIU Y J, TAN Y. Complexity modeling and stability analysis of urban subway network:wuhan city case study[J]. Procedia-social and Behavioral Sciences,2013,96:1611-1621.

[10]李穎宏,王 力,尹怡欣.區(qū)域交通信號系統(tǒng)節(jié)點(diǎn)分析及優(yōu)化策略研究[J].計算機(jī)應(yīng)用,2010,30(4):1107-1109.

[11]王正武,況愛武,王賀杰.考慮級聯(lián)失效的交通網(wǎng)絡(luò)節(jié)點(diǎn)重要度測算[J].公路交通科技,2012,29(5):96-101.

[12]王建強(qiáng),代磊磊,李 婭,等.基于交通流運(yùn)行特征的城市干線關(guān)鍵交叉口判別方法[J].交通信息與安全,2013,31(3):49-52.

[13]管 青.區(qū)域交通信號控制與交通誘導(dǎo)協(xié)同理論與關(guān)鍵技術(shù)研究[D].長春:吉林大學(xué),2009.

Study on the Identification Method of Hub Node in Urban Road Network

ZHENG Lili1,2,3)WANG Shiguang2)WANG Wei2)DING Tongqiang2)

(StateKeyLaboratoryofAutomobileSimulationandControl,JilinUniversity,Changchun130022,China)1)(CollegeofTransportation,JilinUniversity,Changchun130022,China)2)(JilinProvinceKeyLaboratoryofRoadTraffic,JilinUniversity,Changchun130022,China)3)

Identifying the key node of urban road network is an important technical problem in the current urban traffic control and emergency management. An evaluation index system of key node is raised, which includes the road network topology indicators and traffic flow main characteristics. The key node is identified by using a P-gray weighted correlation analysis method. At last, a road network in Changchun is used as a test area to validate the proposed approach compared with other ways. The result shows that the method is feasible and effective. Through further data fitting, the fitting formulas between the node importance degree and the related indicators are given.

traffic engineering; key node identification; complex network theory; principal component analysis; weighted gray correlational analysis

2015-03-10

*國家自然科學(xué)基金項(xiàng)目(批準(zhǔn)號：51308249)、國家科技支撐計劃(批準(zhǔn)號：2014BAG03B03)、山東省省管企業(yè)科技創(chuàng)新項(xiàng)目(批準(zhǔn)號：20122150251-5)資助

U491

10.3963/j.issn.2095-3844.2015.04.001

鄭黎黎(1975- )：女，工學(xué)博士，副教授，主要研究領(lǐng)域?yàn)榻煌ㄏ到y(tǒng)控制與優(yōu)化理論