基于WGN算法的城市路網擁堵路段診斷分析

梁曉輝, 陳松利, 李丹嵐

(內蒙古農業大學能源與交通工程學院， 呼和浩特 010018)

隨著機動車保有量的增加，交通需求持續增長，交通擁堵開始成為城市交通的普遍問題，嚴重影響了居民的工作效率與生活質量。根據產生原因的不同，交通擁堵可分為常發性和偶發性兩類。與偶發性擁堵的隨機性不同，常發性擁堵由交通需求超出道路設施正常容量所致，一般發生在高峰時間，具有可預測性。所以，常發性擁堵的識別成為我國交通管理工作的重中之重[1]。

以往研究中對于常發性擁堵的評價多是對擁堵時間和空間進行簡要融合或單維分析。張婧[2]將不確定性處理技術和軌跡信息挖掘在線分析技術融入交通擁堵時空分布特征的分析研究，構建了在線緩堵控制框架。楊海強等[3]提出基于車輛全球定位系統(gobal positioning system,GPS)軌跡數據的網格級別的擁堵判別方法，并利用基于密度的空間聚類算法識別城市常發性擁堵區域。江航[4]通過構建宏觀基本圖信號控制評估方法主動引導交通演化，均衡路網交通負荷，實現預防路網交通擁堵的目標。韓值[5]從交通流在時間與空間上的等效性基礎上，建立了道路交通流時空關系模型。王妍穎等[6]通過大數據技術對道路的擁堵評價指標進行計算和分析，得到了道路網交通擁堵的潛在規律。賈若等[7]從傳統交通流理論與機器學習兩方面綜述了交通擁堵判別的方法。胡啟洲等[8]根據交通擁堵在時間和空間上的分布特性，建立基于價值函數的城市路網交通擁堵的測定指標體系。曹堉[9]提出了一種基于貝葉斯網絡的城市道路交通擁堵多原因自動實時識別方法。熊勵等[10]針對城市道路交通擁堵及持續時間辨識問題，構建了基于Mapreduce的多元對數線性回歸交通擁堵預測模型和基于生存分析的交通擁堵持續時間模型。周輝宇[11]從時間和大數據規則挖掘角度對擁堵建模，使用時間序列規則挖掘算法建立交通擁堵傳導規律模型，并基于傳導規則預測未來交通流狀況。王芹等[12]通過提取實時路況數據，借助Arcgis軟件，運用廣義G統計量、熱點分析方法對交通擁堵進行研究。諸云等[13]在分析城市道路網絡交通擁堵博弈關系的基礎上，建立了以交通擁堵程度為下層決策目標、經濟費用為上層決策目標的城市路網優化雙層規劃模型。

綜上所述，中外在交通擁堵評價和交通擁堵識別領域均已開展了許多研究和實際應用工作，有較強的指導性，但著眼于結構性擁堵的研究較少。交通需求在空間上的分布是不均勻的，這與一個城市的交通網絡拓撲結構形式、城市用地性質、區域就業崗位、區域經濟發展狀況等諸多因素有關。交通需求的空間不均勻性是導致交通擁擠路段和交通高負荷地區的重要因素。道路網絡是一個復雜的網絡系統，道路結構不盡合理是導致擁堵形成的一個重要原因。既有研究中，往往按照行政區域對道路網絡進行區域劃分，并沒有考慮到路網結構本身的性質，因此不能發現路網結構中存在的一些問題，對進一步的研究和分析造成了一定的不良影響。因此，現從中觀路網結構角度出發，以道路網絡的結構性質為依據，對城市道路網絡進行組團劃分，然后找出路網結構中的關鍵路段，再以小區間OD(origin-destination)量，即起訖點交通量作為權重，進一步找出路網中的擁堵路段，為后續的研究分析做鋪墊。并嘗試進一步運用到案例城市道路網絡中，以驗證方法的準確性。

1 WGN算法理論依據

1.1 算法思想

WGN(weighted Girvan-Newman)算法，即加權組團劃分算法，是由復雜網絡理論中的非重疊社區識別算法-GN(Girvan-Newman)算法改進得到。如圖1所示，網絡由不同的組團組成，這些組團的特征是：組團內部的節點緊密相連，而組團之間的節點聯系較少。那么位于不同組團的節點之間的最短路徑必將經過那些少量的組團之間的邊。這樣，連接不同組團的邊將比組團內的邊具有更高的介數值，記為Bij。

其中邊介數的定義為：以網絡中每一個節點i為源節點，計算它到其他節點j的最短路徑，并以這些最短路徑經過的每條邊的次數作為該邊的介數[14]。邊的介數越大，說明在交通流移動中通過該邊的交通量也會越大，也越容易發生交通堵塞，該邊在網絡中也會越重要。通過逐步移去這些邊介數較高的邊就能夠把它們連接的組團分割開來。組團結構網絡如圖1所示。

圖1 小型組團結構網絡示意圖Fig.1 Network of small group structures

1.2 算法假設

城市道路交通系統本身是由道路系統、流量系統和管理系統組成的一個復雜巨系統。城市道路網絡由交叉口和連接它們的路段組成，交通流在網絡上流動。本文中把交叉口和路段分別抽象為網絡中的節點和邊，車輛在邊上行駛遇到的阻抗(如行駛時間等) 對應于邊上的權重，考慮路段的方向性，把城市交通網絡抽象為一個復雜的雙向加權網絡。由于城市道路網絡具有其獨特的性質，將WGN算法應用到城市道路網絡的組團劃分時，本文中做了以下假設。

(1)所有用戶都試圖選擇最短路徑到達其目的地。

(2)所有用戶都根據同一評判標準判斷路徑長短。

(3)所有用戶都可以得到當前交通狀態下可供路徑選擇的全部信息[15]。

目前GPS導航系統、高德地圖等智能化誘導系統在城市交通中的廣泛應用，保證了上述假設的有效性。

1.3 算法關鍵參數

把交叉口和路段分別抽象為網絡中的節點和邊，即以C=(N,A)表示城市道路網絡，其中N表示為城市道路交叉口的集合，A表示為城市道路路段的集合。把道路交叉口等效為網絡中的節點i，路段等效為網絡中的邊，采用 (eij,eji,tij,wij)表示。其中eij為路段ij的正向弧，eji為路段ij的反向弧，tij為通過該路段的自由流時間，wij為該路段的單位流量權重系數，它表征了在單位時間內能通過路段ij斷面的單位流量。假設路段ij中eij和eji的使用情況完全相同，則其tij和wij都相等。

2 道路網絡組團劃分步驟

假設將城市交通網絡劃分為k個組團。定義一個k×k維的對稱矩陣E=(eij)k×k，其中元素eij表示網絡中連接兩個不同組團間節點的路段在所有路段中占的比例；這兩個節點分別位于第i個組團和第j個組團。在這里所說的所有的路段是在原始網絡中的，而不必考慮是否被WGN算法移除。另外每個路段的單位流量權重系數為wij。

定義每行(或者列)中各元素與其路段單位流量權重乘積之和為

(1)

式(1)表示與第i個組團中的節點相連的權重路段在所有權重路段中所占的比例。其中wij=wji，在此基礎上，定義模塊度的衡量標準為

(2)

式(2)中：eij表示網絡中連接兩個不同組團間節點的路段在所有路段中占的比例；wij表示組團內部各路段的單位流量權重。

式(2)的物理意義是：網絡中連接兩個同種類型的節點的路段(即組團內部路段)的占比減去在同樣的組團下任意連接這兩個節點的路段的期望值。如果組團內部邊的比例不大于任意連接時的期望值，則有Q=0。Q的上限為Q=1，Q越接近這個值，就說明網絡的組團越明顯。有研究表明，Q的最大值對應的組團就是網絡的組團，且在實際網絡中該值通常位于0.3～0.7。

模塊度存在的意義在于，網絡的組團劃分時無法確定何時停止刪除關鍵邊，這樣就無法判斷它所得的組團是否是實際網絡中的組團。因此，在算法中，同時計算模塊度的值，當模塊度值達到最大時，便停止刪減關鍵邊，并把模塊度最大時的組團劃分情況作為最后的組團劃分結果。算法的基本流程如圖2所示。

圖2 WGN算法步驟Fig.2 Workflow of WGN algorithm

3 案例城市路網關鍵路段診斷

3.1 路網組團劃分依據

選擇武漢市武昌區作為研究對象，開展案例分析。由于武漢市是被長江、漢江分割的城市，形成了兩江三片的格局。武昌、漢口、漢陽三個區鎮之間，只能靠橋梁、隧道或者輪渡連接，橋梁、隧道承擔主要的交通量，輪渡只承擔少量的行人交通量，現有橋梁和隧道數目較少。因此，三鎮形成了三個大組團，從路網結構的角度上看，將武昌區作為一個獨立的研究對象是可取的。

在對武漢市主城區路網進行組團劃分的過程中，將道路交叉口抽象為節點，交叉口間的路段抽象為邊，根據《2020年版武漢市交通旅游圖》，繪制出2020年武漢市主城區道路網絡系統圖。并且根據《武漢市骨架路網建設時序研究》中2020年骨架路網的建設時序圖，及其他相關資料，將研究區域的交通網絡按4個等級進行劃分：快速路、主干路、次干路、支路。

根據《城市道路交通規劃設計規范》等相關資料，整理后得到各類道路的車道數、設計車速及單車道設計通行能力如表1所示。以自由流時間作為網絡邊長的衡量標準，其中自由流時間由路段的長度與其設計速度的比值表示。

由表1中數據，把雙向6車道快速路的通行能力轉化為單位流量權重系數后作為標準，則其他道路相對單位流量權重系數如表2所示。

表1 各類道路特征

表2 單位流量權重系數

3.2 路網組團劃分結果

3.2.1 武昌區路網組團劃分

根據路網本身結構，用WGN算法對武昌主城區范圍內的路網進行組團劃分，得到以下結果：組團數9個，組團劃分效果如圖3所示。

圖3 武昌區路網組團劃分效果圖Fig.3 Grouping of Wuchang District road network

3.2.2 關鍵路段診斷結果

由算法原理可知，連接兩個組團的路段數量遠遠少于組團內部的路段數量，因此組團間的連接路段，必定為關鍵路段。關鍵路段的存在，說明路網結構有不完善的地方，導致兩個組團之間缺乏相當的連通度，所以，關鍵路段既是可能產生擁堵的路段。利用WGN算法，診斷出武昌主城區范圍內的關鍵路段共有51條，如表3所示。

表3 武昌區關鍵路段診斷結果

4 考慮出行需求后的擁堵路段診斷

4.1 擁堵路段診斷原理

經過對城市道路網絡進行組團劃分，可以發現，城市道路網絡結構中存在諸多問題，例如，組團之間連接路段過少，關鍵路段等級過低等。與此同時，在土地利用強度和功能分區的影響下，城市各區域交通出行的發生與吸引強度分布不均勻，進一步造成了部分路段交通流量過大，形成交通擁堵。

因此，在對武昌區道路網絡結構問題進行分析診斷的基礎上，對WGN算法進行了改進，將交通小區間的OD量作為權重，對路網中路段的介數值(作為最短路徑的次數)進行加權計算，并根據路段加權之后的介數值判斷其重要性。本方法除考慮路段在路網結構中的重要性外，同時考慮了路段在實際交通需求中的重要性，對診斷實際路網中的擁堵路段具有重要意義。

4.2 擁堵路段診斷模型與結果

4.2.1 擁堵路段診斷模型

設路網中每一個節點均是一個交通起止點，以路網中各路段自由流時間為判斷依據，用BFS(breadth first search)算法，即廣度優先搜索法搜索出路網中每對節點之間的最短路徑。

(1)BFS算法搜索最短路徑，將每對節點之間的最短路徑記為三維數組Dij，最短路長度記為二維數組Sij，即

Dij=[i,j][i,…，x,…，j]

(3)

(2)計算每條路段的介數值bij，既每條路段作為最短路的次數。與組團劃分模型不同的是，由于考慮每對節點之間的OD(出行需求)，因此，介數值bij要以最短路經過此路段的節點對之間的OD量為權重，即

bij=∑ODxy，節點對xy之間的最短路徑Dxy經過路段ij

(4)

(3)找出介數值最大的路段max{bij}。

(4)刪除介數值最大的邊，同時，計算此時網絡的模塊度Q，即

(5)

擁堵路段診斷步驟如圖4所示。

圖4 擁堵路段診斷算法步驟Fig.4 Workflow of the congestion diagnosis algorithm

4.2.2 武昌地區擁堵路段診斷結果

按照上述方法，在充分考慮路段在路網中的重要性的基礎上，同時考慮路段在交通需求中的重要程度，對武昌區路網進行擁堵路段分析，共診斷出擁堵路段14條，如表4和圖5所示。

表4 武昌區擁堵路段診斷結果

圖5 武昌區擁堵路段示意圖Fig.5 Congested road segments in Wuchang District

5 結論

主要從中觀路網結構的角度，對武昌區的道路網絡的供需情況進行診斷，研究主要結論如下。

(1)為了探究城市道路網絡局部路段出現擁堵的結構性原因，找出現狀路網、規劃路網中可能發生擁堵的關鍵路段，首先對武昌區道路網絡進行了組團劃分，從而診斷出路網中的關鍵路段，即各組團之間的連接路段；而后考慮到城市中不同區域的居民出行需求的分布并不均勻，將居民出行OD加載到道路網絡組團劃分算法的最短路徑計算中，從而診斷出路網中的擁堵路段。

(2)從組團劃分的結果上看，武昌區路網結構存在一定問題：組團內部路網密度較大，連通度較好；各組團間，道路數量較少，缺乏一定的聯通度。而組團間連接路段的數量與組團內部路段的數量之間較大的差異，造成了道路供給的不均衡現象，是形成道路擁堵的原因之一。

(3)診斷出的關鍵路段，即是可能發生擁堵的路段。在對武昌區現狀路網的診斷中，發現了51條關鍵路段，這些路段是由于道路網絡結構不合理而產生的瓶頸路段，然而由于不同路段交通需求不同，并非所有的關鍵路段都會產生擁堵現象。因此，在診斷出結構性關鍵路段的基礎上，考慮了出行需求，發現了14條擁堵路段，這些路段即是最容易發生擁堵的路段。參考現實交通狀況與相關資料，如《武漢市主要道口交通堵點疏解初步方案研究》等，通過對比發現，診斷出的部分關鍵路段和大部分擁堵路段在現實中確實是經常發生擁堵的路段。

(4)研究結果可以對規劃路網的潛在問題做出預判，在可能的擁堵發生之前，及時采取措施，緩解擁堵。

(5)根據對現狀路網進行診斷的結果，可以對關鍵路段進行分類，對于不同道路等級的關鍵路段，提出相應的優化措施：對于道路等級較低的關鍵路段，可以采用提高道路等級的方法；對于道路等級本身較高的關鍵路段，可以采取在附近修建平行路段，來增加相應組團的連通度。