城市道路交通網絡關鍵節點辨識方法研究*

鄭黎黎 王世廣 王 偉 丁同強

(吉林大學汽車仿真與控制國家重點實驗室1) 長春 130022) (吉林大學交通學院2) 長春 130022)(吉林大學吉林省道路交通重點實驗室3) 長春 130022)

城市道路交通網絡關鍵節點辨識方法研究*

鄭黎黎1,2,3)王世廣2)王 偉2)丁同強2)

(吉林大學汽車仿真與控制國家重點實驗室1)長春 130022) (吉林大學交通學院2)長春 130022)(吉林大學吉林省道路交通重點實驗室3)長春 130022)

綜合考慮城市道路網絡的拓撲結構特征和交通流特性，建立城市道路交通網絡關鍵節點評價指標體系；設計了基于P-灰色加權關聯分析的關鍵節點辨識方法，利用長春市區域路網進行了實例分析，并和其他方法的排序結論進行了對比，證實文中提出的方法可行、有效.通過進一步數據擬合，給出了節點重要度和相關指標的擬合公式.

交通工程；關鍵節點辨識；復雜網絡理論；主成分分析；灰色加權關聯分析

0 引 言

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

1 城市道路交通網絡關鍵節點評價指標體系的構建及優化

1.1 交叉口重要度函數

圖1為關鍵節點評價體系.定義交叉口重要度λ是評價指標體系中各參數的一個函數，若設A為復雜網絡特性指標集合；B為交通特性指標集合,則有λ=f(A;B).

圖1 關鍵節點評價指標體系

1.2 復雜網絡特性指標

1) 基于道路等級的節點度k結合復雜網絡理論中節點度的概念，本文定義基于道路等級的節點度為交叉口所連路段各進口道與出口道車道數之和的均值.

(1)

式中:n為交叉口進口道數；kjo為交叉口出口道車道數；kji為交叉口進口道車道數.

通常，度越大代表著該節點在網絡中越重要，它描述了節點的連接程度.

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

(2)

式中：L0為在自由行駛條件下的平均路徑長度；Li為任意節點i刪除后道路交通網絡的平均路徑長度.

其中，平均路徑長度是交通網絡中所有節點對之間距離的平均值，即

(3)

式中：N為道路交通網絡中節點的個數；dij為從節點i到節點j的最短距離；V為道路交通網絡中的節點集.

通常，平均路徑長度變化率越大，表明該節點在交通網絡中越重要.

3) 基于行程時間的介數Bi基于行程時間的節點介數可定義為道路交通網絡中所有的最短路徑中經過該節點的數量比例.節點i的介數Bi由下式計算.

(4)

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

依據最短行程時間計算的介數反映了節點在整個交通網絡中的作用和影響力，具有很強的現實意義.

對于交通特性指標的詳細定義參見相關書籍，限于篇幅在此不再贅述.

1.3 評價指標的優化

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

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

2 基于P-灰色加權關聯分析的城市道路交通網絡關鍵節點評估算法

基于P-灰色關聯分析的城市道路交通網絡關鍵節點評價步驟如下.

步驟1 假設路網中共有N個節點，m個節點評價指標，則第α(1≤α≤N)個節點的比較數列為

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

式中：yα(j)為第α個節點的第j個主成分.

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

步驟3 數據量綱一的量化處理 這里可以采用SPSS對數據進行標準化處理，得到比較數據序列

量綱一的量化后得到參考數據序列

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

根據

(5)

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

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

步驟5 計算判斷指標關聯系數

(6)

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

步驟6 計算灰色加權關聯度，得到交叉口重要度

(7)

步驟7 計算每個節點的灰色加權關聯度大小，一般地，關聯度越大節點就越重要，關聯度最大的節點為關鍵節點.

3 實例分析

3.1 數據獲取及指標優化

本文選取長春市亞泰大街、解放大路、民康路和三道街包圍的路網作為分析對象，見圖2.根據2013年12月24日早高峰調查的基礎數據并經

過相關計算得到10個節點的7類評價指標，見表1.

圖2 交通網絡拓撲結構

序號指標kΔLBi流量q/(pcu·h-1)飽和度x排隊長度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對數據進行主成分分析，選取2個主成分yj(j=1,2)，經標準化的各個指標xi(i=1,2,…,7)分別代表節點度、平均路徑變化率、介數、流量、飽和度、排隊長度、延誤.則有各主成分表達式

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中，除平均路徑變化率和介數與其呈負相關之外，y1與其他指標為正相關關系，且各系數大體相當，可看成是反映這些變量的綜合指標；第二主成分y2中，與其呈負相關關系的指標是飽和度和延誤，介數、流量、排隊長度的系數比較大，可以看成是主要反映這些變量的綜合指標.不難看出，兩個主成分對于城市路網拓撲性質和交通流特性的反映各有側重.

3.2 關鍵節點評估與分析

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

圖3 重要度分布

由圖3可見，交叉口2的重要度最大，為該路網的關鍵節點.這與交通流運行情況相符，調查日區域交通擁擠最先出現在該交叉口，因而該方法具有一定的有效性和可行性.

為了進一步說明本文算法的精度，下面將把本文算法與經典的節點刪除法、節點收縮法和灰色關聯度法[13]進行對比分析.需要指出，交通網絡為加權復雜網絡，節點收縮法考慮了交通阻抗的影響；而灰色關聯度法采用的是本文選取的指標,重要度排序對比見表2.

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

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

表2 重要度排序對比

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

綜合以上分析，P-灰色加權關聯分析算法更為合理、有效.

3.3 模型簡化

城市道路交通網絡中該算法參數同時獲取難度較大、計算相對復雜，下文將根據算例對模型進行簡化分析，以期獲得更好的應用.

首先，將重要度與SPSS給出的標準化數據進行逐步回歸分析，得到

λ=3.708+0.480k′+0.364q′

(10)

式中：λ為重要度；k′為標準化的節點度；q′為標準化的流量.修正R2=0.979.

然后，從單個變量入手進一步探究各指標與結論之間的關系.其中與排序相關系數較大的指標有節點度、流量、延誤、排隊長度，相關系數分別為0.963，0.944，0.848，0.838，相互關系見圖4.

圖4 排序結論與相關變量的關系

此處延誤與排隊長度變化趨勢大體一致，未給出對比圖.其中基于道路等級的節點度可以反映城市路網的拓撲性質，流量、延誤、排隊長度可以反映城市路網的交通流特性.考慮到各指標的獲取難度和相關程度，分別對節點度和流量與重要度進行擬合，可以根據實際情況進行參照使用.擬合關系式為

λ=3.708+0.794k′

(11)

λ=3.708+0.777q′

(12)

式中：λ為重要度；k′為標準化的節點度；q′為標準化的流量.

4 結 束 語

本文基于道路交通網絡的拓撲結構特征和交通流特性，研究并建立了路網中關鍵節點的評價指標體系及辨識方法，并通過實例分析驗證了該方法的有效性和實用性，根據實際數據給出了可供參考的關鍵節點重要度與相關指標的擬合公式，為交通管理者在交通控制和應急管理方面確定關鍵節點提供了新方法和新思路.

[1]沈鴻飛,賈利民,王笑京,等.基于公路網結構特性的關鍵節點評價指標與辨識方法[J].公路交通科技,2012,29(9):137-142.

[2]吳建軍.城市交通網絡拓撲結構復雜性研究[D].北京:北京交通大學,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]陳 勇,胡愛群,胡 駿,等.通信網中最重要節點的確定方法[J].高技術通訊,2004,14(1):21-24.

[6]譚躍進,吳 俊,鄧宏鐘.復雜網絡中節點重要度評估的節點收縮方法[J].系統工程理論與實踐,2006,26(11):79-83,102.

[7]高 潔.交通運輸網絡節點重要度評價體系研究[J].聊城大學學報:自然科學版,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]李穎宏,王 力,尹怡欣.區域交通信號系統節點分析及優化策略研究[J].計算機應用,2010,30(4):1107-1109.

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

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

[13]管 青.區域交通信號控制與交通誘導協同理論與關鍵技術研究[D].長春:吉林大學,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

*國家自然科學基金項目(批準號：51308249)、國家科技支撐計劃(批準號：2014BAG03B03)、山東省省管企業科技創新項目(批準號：20122150251-5)資助

U491

10.3963/j.issn.2095-3844.2015.04.001

鄭黎黎(1975- )：女，工學博士，副教授，主要研究領域為交通系統控制與優化理論