基于空間流量度的城市路網關鍵節點挖掘方法

張 誠，汪成銀，陳志偉，張正向，張子磊

(1.河南省交通運輸廳行政執法局，河南 鄭州 450000；2.北京航空航天大學 可靠性與系統工程學院，北京 100191；3.鄭州海為電子科技有限公司，河南 鄭州 450000)

0 引 言

近年來，隨著城市規模與人口的不斷擴大，城市交通需求呈現出快速增長。城市交通壓力逐年增加，導致交通承載能力趨向飽和，交通擁堵問題日益突出：以北京市為例，據《2019年北京交通發展年報》統計[1]，北京市城區工作日出行總量為3 924萬人次，早晚高峰平均出行時間消耗分別達到47.2和48.2 min，平均日均擁堵時間共計170 min，全年中度以上擁堵共計205 d?？梢姡煌〒矶乱呀洺蔀槌鞘邪l展的突出問題，不僅增加了社會經濟成本，還帶來嚴重的環境污染問題。

路網上的關鍵節點是路網脆弱性來源之一，通過識別關鍵節點，對其進行重點管控和保護，是有效緩解擁堵和提高路網魯棒性的方法之一[2-3]。這不僅為管理規劃提供了決策依據，同時為從路段管理向路網管理轉變提供了方法支撐。目前，國內外學者圍繞路網上的關鍵節點識別展開了廣泛的研究。

常見關鍵節點識別方法可分為3種：

1)基于局部近鄰結的方法，如度中心性算法[4]，把節點重要性等價為節點的鄰居數；此外，局部近鄰連接方法典型的還有半局部中心性與集中影響度[5]，揭示節點二階以上的鄰居結構信息；WAN Neng等[6]提出了空間加權度來綜合考慮結構與公路長度對路網節點重要度的影響，但城市道路長度往往分布集中差異較小，因此道路長度的加權空間度在較大尺度的公路網絡(省級、全國的公路網絡)上效果較好，不適用于較小尺度的城市路網關鍵節點識別；ZHU Guangyu等[7]將地理位置信息和道路長度綜合考慮到空間加權度，一定程度上反映了道路功能和空間結構；

2)基于流量的方法，如路由介數中心性[8]、流介數中心性[9]、連通介數中心性[10]、隨機游走中心性[11]等。王琳璨[12]綜合考慮了網絡拓撲結構和流量分布因素對路段關鍵程度進行評估，但各因素層次分析加權的系數采用主觀判斷的方法，評估結果將嚴重依賴于權重系數;

3)基于特征中心性，即利用特征向量識別關鍵節點的方法，前兩類方法主要從網絡結構出發，基于特征中心性的方法不僅考慮結構信息，同時把節點的權威性和樞紐性都納入考慮，如特征向量中心性[13]，PageRank算法[14]，LeaderRank算法[15]等方法。

現有不同的關鍵節點識別方法具有一定局限性，主要體現在：①尚未掌握擁堵的發生、傳播與演化規律，評估指標具有局限性；②現有方法不能很好適應路網流量與結構耦合、流量動態變化的特點；③缺乏快速有效的關鍵節點識別與評價方法。

綜上所述，筆者針對現有狀況綜合考慮網絡拓撲結構和流量特點，提出了基于空間流量度的多級流量加權關鍵節點識別模型。并且引入了節點空間流量度和網絡結構流量熵兩個新概念，提出用空間流量度來刻畫節點重要程度，用結構流量熵來描述網絡流量的分布均勻性，避免確定參量權重時存在的主觀不確定性問題。最后借鑒統計物理中的滲流理論，研究對比模型和傳統常見方法在路網關鍵節點識別上的性能差異，并分析產生這些差異的原因。

1 模型構建

1.1 有向含權路網模型

筆者以北京市四環內道路網絡為例，構建了有向含權路網模型，即把城市路網抽象為網絡對象，該網絡的邊具有方向性，且每條邊具有一定權重，以匹配其速度、流量等參數。具體做法為：將道路交叉口抽象為節點，用V(t)={v1,…,vn}表示。將主干道路、次干道及支路抽象為連邊，用E(t)={e1,…,en}?V(t)×V(t)表示，網絡用G(t)=(V(t),E(t))表示。權重是不同時刻道路(邊)的平均車速，在網絡的鄰接矩陣中，若兩個節點vi與vj之間存在邊，則網絡G(t)的鄰接矩陣A(t)滿足aij=vij(t)，否則aij=0，其中vij(t)表示t時刻i到j的平均車速。

假設網絡的連邊僅考慮單向和雙向道路，不考慮多車道對連邊的影響。該有向網絡連邊權值——速度的估算數據，是通過采集2015年10月26日24 h的出租車GPS實時軌跡數據計算得到(數據的新舊程度不影響方法的科學性，只作為驗證的資源和手段)，源數據包括出租車ID編號，時間，經、緯度。道路邊權取該條道路上所有車輛的在某一時刻的速度平均值，如式(1)：

(1)

式中：sj(t)=[lonj(t),latj(t)]；sj(t+1)∈eij表示第j輛車在t時刻的經緯度，且該車在t時刻和t+1時刻均在邊eij上。由此，根據軌跡可以構建得到北京市四環內道路網絡，其拓撲結構如圖1，該網絡由27 877個節點，39 609條邊構成，平均度為2.841。

1.2 流量-速度計算關系

城市道路交通流的流量-速度關系模型構建一直是研究熱點，是道路通行能力的評價基礎。由于城市級別的流量數據采集較為困難，為深入研究城市道路服務水平和通行能力，可利用流量-速度模型估算不同道路的平均出行時間和道路流量。

宏觀上，描述交通流特征的主要參數包括交通流量、速度和密度，三者滿足流量是速度與密度的乘積關系；微觀上，單個車輛的跟馳行為影響道路通行狀態。Green-Shield拋物線模型是經典的流量預測模型，但該模型未考慮道路通行條件(交通阻抗)，流量預測結果不夠準確。因此，采用美國聯邦公路局(BPR)路阻函數模型，如式(2)：

(2)

式中：vij(t)為t時刻的平均速度；vf為自由流速度；q(t)為流量；λ、θ和c均為變換系數。通過簡單變換，可以得到流量計算如式(3)：

(3)

根據不同的速度，可以求得對應流量。由于不同級別道路對應的通行能力不同[16]，考慮主干道路與分支道路兩種類型。另外，道路在不同運行時間車流量和速度關系也存在較大差異，同時還考慮非飽和與超飽和兩種狀態下的模型取值，各參變量取值如表1。

表1 城市主干道/次干道路(支路)速度-流量關系參數Table 1 Urban trunk road/secondary trunk road (branch road) speed-flow relationship parameters

1.3 關鍵節點識別算法

網絡上關鍵節點識別是一個NP完全問題，不能在多項式時間內被解決，需要開發高效、準確的方法，特別是針對城市路網這類大型網絡，更亟需綜合有效的關鍵節點識別方法。

1.3.1 關鍵節點定義及內涵

路網上的關鍵節點是指，擁堵故障會導致網絡全局連通性、通行能力以及彈性產生較大影響的節點。關鍵節點擁堵，不僅導致自身通行能力的降低或喪失，還可能影響周圍其他節點，形成擁堵的級聯失效，最終導致大面積交通癱瘓。

關鍵節點內涵應從兩個方面理解：①在結構上具有馬太效應，連接許多其他部分的節點，如度高的節點；②在功能上，承載較大負載的節點。關鍵節點識別需要綜合考慮上述兩個特征。

1.3.2 空間流量度

為綜合考慮結構和功能兩個方面因素，引入節點的空間流量度概念，以評價節點的重要度。空間流量度是指節點局部流量在空間結構上的總和，如式(4)：

(4)

式中：fd,i表示節點i的空間流量度；ki表示節點i的度；tf,j表示通過節點j的流量；j∈?i表示節點i的所有鄰域節點j；α和β是權衡網絡流量和結構重要度的控制參數。

1.3.3 網絡性能評價指標

網絡性能評價綜合反映網絡的連通能力、流量負載和均衡能力，綜合考慮兩類不同的指標：最大連通子團G的相對大小和結構流量熵E。網絡的最大連通子團是一個圖的極大子圖，且是頂點數最多的極大子圖，其中子圖中任何兩個頂點通過路徑相互連接，即任意兩個節點之間都存在可連通的路徑。因此，最大連通子團強調兩個含義，第一是相互連通，第二是節點數最大。結構流量熵反映網絡流量的分布均勻性，如式(5)：

(5)

式中：E表示網絡結構流量熵；Ii表示歸一化的空間流量度。

結構流量熵越大表示流量分布越均勻，當網絡為完全規則網絡時，結構流量熵最大；反之則表示流量分布越不均勻，當網絡為星形網絡時，結構流量熵最小。

1.3.4 評價方法流程

路網上關鍵節點評價方法流程主要包括以下6個步驟：

1)數據預處理，包括速度計算和數據清洗補充等，建立道路網絡鄰接矩陣；

2)根據流量-速度模型預估計算每條道路流量；

3)根據定義，計算每個節點的空間流量度；

4)移除空間流量度最高的節點；

5)計算網絡的最大連通子團尺寸和結構流量熵，重復第3步和4步，直到網絡最大連通子團小于規定閾值(如1%)，結束計算；

6)按空間流量度降序輸出節點序列，排序靠前的即為所得關鍵節點。

2 結果驗證

以北京市四環內路網為主要研究對象，具體從該路網度分布、速度分布、不同時間階段關鍵節點排序和不同識別方法的有效性三個方面展開詳細分析。

2.1 路網度分布及速度分布

節點度是指和該節點相關聯的邊的條數，又稱關聯度。路網中每個節點也可以用度來描述道路的連邊情況。由于道路是具有方向的，用入度表示進入該節點邊的條數，出度表示從該節點出發的邊的條數。網絡的拓撲結構特征可以通過度分布反映，如圖2。統計入度和出度總和，可以看出，大部分節點的度在2～5之間，極少數節點度較高，達到了6，甚至7。一般而言，均質網絡的度分布相對均勻，絕大多數節點度分布在集中區域內，不存在節點度非常大的節點；異質網絡的度分布具有“長尾效應”，呈現冪律分布，即絕大多數節點的度都比較小，但存在少數節點的度非常高。由圖2的度分布形式看，該道路網絡連接相對均勻，且不具有冪律分布的“長尾”特征，該路網屬于均質規則網絡，符合實際道路網絡特征。

圖2 北京市四環路網拓撲結構Fig.1 Topological structure of Beijing Fourth Ring Road network

圖2 北京市四環內路口節點度分布Fig.2 Distribution of node degree of intersections in Beijing fourth ring road

選取了早高峰08：00～09：00的估算速度，估算速度由式(1)估算得到，估算速度分布結果如圖3。由圖3可知，早高峰期間絕大多數路段的速度位于20～40 km/h區間范圍內。低于40 km/h可定義為中度擁堵[1]，則超過80%的路段均為擁堵路段?？梢娫绺叻鍟r間段，對關鍵節點進行重點監控和管理具有重要意義。

圖3 北京市四環內路口估算速度分布Fig.3 Estimated velocity distribution at intersections of Beijing fourth ring road

針對節點空間流量度的分布，結果如圖4。由圖4可知，約83%節點空間流量度位于500～2 000間，約有17%的節點空間流量度較大，遠遠超過節點度較大(大于5)的節點比例。這表明，節點度低的節點流量不一定低，必須綜合考慮網絡的結構和流量兩個方面因素，才能更有效識別網絡上的關鍵節點。

圖4 北京市四環內路口空間流量度分布Fig.4 Spatial-flow degree distribution at intersections of Beijing fourth ring road

2.2 不同時段路網關鍵節點排序

路網上的流量隨時間動態變化，因此關鍵節點也隨流量變化，如早高峰期間通勤流量主要集中于從居住地和市中心辦公集中區域，平峰期間往往流量靠近商業中心或城市中心，晚高峰期間則與早高峰相反，呈現潮汐現象。

為了解不同時間段的車輛出行時間占比，根據文獻[1]的數據，統計了2018年車輛出行出發時間與到達時間的分布情況，如圖5。由圖5可知，車輛出發和到達時間分布變化趨勢基本一致，而到達時間與出發時間相比存在一定延遲。早高峰流量主要集中于08：00～09：11；10：00～12：00流量下降，屬于平峰期；18：00～19：00為晚高峰。

圖5 車輛出行出發與到達時間段占比統計Fig.5 Statistics of vehicle departure and arrival time

對路網劃分了3個不同的時間階段各一個小時進行分析，分別是08：00～09：00(早高峰)，11：00～12：00(午平峰)及18：00～19：00(晚高峰)。通過計算節點空間流量度，對不同節點降序排列，計算結果如表2。結果顯示了排序前十的關鍵節點識別情況，從表2可以看出，不同時間段的關鍵路口有6個節點完全重合，分別是東三環北路 &朝陽路交叉口、昌平路 &北土城西路交叉口、東三環南路輔路 &勁松路交叉口、德勝門西大街 &新街口北大街交叉口、東三環北路 &順源街交叉口、西大望路 &通惠河北路交叉口，說明重合路口在路網結構和承載流量兩方面均發揮了重要作用，需要重點加強管控。但重合的路口晚高峰空間流量度明顯高于早高峰，這表明節點度相同的情況下，晚高峰流量往往高于早高峰流量。盡管節點按照空間流量度降序排列，識別的關鍵節點的節點度排序靠前，速度也相對處于較低水平，所識別的關鍵節點在結構和流量兩方面均屬于網絡中的重要節點，需在高峰期考慮加強監控與交通疏導。

表2 不同時間段關鍵路口排序結果(前十)Table 2 Ranking results of key intersections in different time periods (top 10)

2.3 有效性對比

為進一步對比筆者提出的關鍵節點識別方法與傳統方法的有效性，從不同方法、不同參數兩方面對比，分析基于空間流量度的關鍵節點識別方法。

2.3.1 不同關鍵節點識別方法

在北京市路網基礎上，選取了基于空間流量度、基于節點流量、基于節點度和基于PageRank算法4種方法，以早高峰為例，結果如圖6。

圖6 早高峰不同方法結果對比Fig.6 Comparison of results of different methods in early peak

由圖6(a)可知最大連通子團相對大小隨節點移除比例的變化曲線。對比不同方法的結果可以發現，網絡連通性能隨節點移除比例增加而降低，表明連通性能越來越差?；诳臻g流量度的關鍵節點識別方法，在移除較少節點時和其方法效果相近，但當移除比例(擁堵節點比例)>18%后，基于空間流量度的節點移除策略，會極大降低網絡連通性能，表明基于空間流量度節點識別具有有效性。

圖6(b)為結構流量熵隨節點移除比例在不同算法下的仿真結果。結構流量熵主要反映移除節點后，流量的分布情況，值越大表明分布越均勻。由圖6可知，結構流量熵隨節點移除比例增加而降低，表明隨著節點移除比例的增加，網絡流量分布變得越不均勻。還發現基于空間流量度算法的結構流量熵比其他算法更大，可見基于空間流量度識別的節點是流量相對較大的節點，這樣才能使網絡的流量在這些節點移除后，比其他節點相對更加均勻。

2.3.2α和β

針對不同參數對識別效果的影響，α和β參數主要控制結構與流量在評價算法中的權重比例，當α=1，β=0時，完全由結構決定關鍵節點，當α=0，β=1時，完全由流量決定關鍵節點。圖7展示了參數α和β變化對于最大連通子團和結構流量熵的影響。由圖7(a)可知，網絡的連通性能隨α增加而增加，即網絡的結構對于網絡的連通性能有決定性影響。

由圖7(b)可知，結構流量熵隨移除比例下降，表明隨著節點移除，路網上的流量分布更加不均勻。但結構流量熵隨α增加而降低，表明α增加不利于流量的均衡分布，因此需要綜合網絡的結構和流量分布需求，綜合選擇合適的參數，識別路網上的關鍵節點，才能對路網實現更有效的管控。

圖7 早高峰不同α對最大連通子團合結構流量熵的影響Fig.7 Influence of different α of early peak on the maximum connected component and entropy of structural flow

3 結 語

針對路網上的關鍵節點挖掘，筆者提出了基于空間流量度的關鍵節點識別方法。該方法綜合考慮了網絡拓撲結構和流量特征，充分利用了所采集數據的不同維度信息，該方法克服了傳統方法主觀選取參數權重的問題。在北京市四環內路網的實測數據上進行了實際案例驗證，對比并分析了不同關鍵節點識別方法和不同參數對關鍵節點識別效果的影響及相關原因，研究結果表明：

1)基于空間流量度的關鍵節點識別方法效果顯著，能夠同時識別出網絡上流量較大和結構重要的節點。

2)節點度低的節點流量可能較大，并且節點度高的節點流量不一定高。

3)參數α增加和β降低有利于提高網絡連通性能，即尋得結構上的關鍵節點。但α增加和β降低不利于流量的均衡分布，即不利于平衡結構流量熵。

因此，根據結構和流量的不同側重，合理調節參數α和β，可以控制實現不同的關鍵節點識別效果。另外，筆者僅考慮了路面交通對于路網連通性能和通行流量的影響，未充分考慮軌道交通、行人因素等其他耦合作用，也未考慮擁堵影響力及延時指數對交通的影響，今后將綜合考慮多種影響因素，建立空間耦合網絡，分析多層網絡耦合情況下的關鍵節點識別問題。