基于改進GN 算法的路網脆弱性診斷模型＊

吳俊荻 朱順應 王 紅 劉 兵 丁乃侃

（武漢理工大學交通學院 武漢 430063）

0 引 言

道路網絡結構的不盡合理和交通需求分布的過分集中，常導致路網中的部分路段較其他路段容易發生擁堵，從而顯著降低網絡的通達性，表現出路網的脆弱性.有效識別道路網絡的脆弱路段，可幫助道路規劃和管理部門預防、監督和管理交通事件的發生.

目前，國內外對路網脆弱性的研究逐漸增多.Husdal［1］認為路網脆弱性是“在某些特定情況下道路運輸網絡的不可運轉性”；而Jenelius［2］Bell［3］和尹洪英［4］認為路網脆弱性的概念包括成2個部分：（1）發生危險事件的概率；（2）在特定地點發生事件的后果.本文中脆弱性的含義與Taylor［5］等定義的類似，即將少量連接的失效（或退化）顯著地降低了節點的可達性稱為網絡節點的脆弱性，將失效的連接稱為網絡的關鍵連接.關于路網脆弱性評估方法的研究，Jenelius等假定路網中某些路段失效，把路段失效時廣義旅行成本的增加作為評估指標，分析了路段失效的后果.Bell等利用博弈論的方法，預先指定路網的中斷或攻擊，考慮如何使用混合路徑策略使路網期望損失最小化.

這些研究多是針對網絡中某些路段失效的特定情況，探究路網功能受到的影響，較少從路網結構和交通需求耦合角度探究脆弱性的產生，本文試圖從事這方面的研究，為路網脆弱性問題的改善提供另一視角.

GN 算法是一種通過計算路段介數（網絡中所有節點的最短路徑經過該路段的次數）識別復雜網絡中社團結構的算法［6］，它可以從路網結構角度反映路段的重要程度和發生失效的可能性.目前，該算法已經被應用到了電力系統等領域的連鎖故障和脆弱性的研究中［7］.從宏觀角度來說，道路網絡與其他復雜網絡有相似的復雜特征［8］，可借鑒復雜網絡的理論來研究它們的結構特征.與其他網絡不同的特點是，道路網絡的邊具有權重和方向性，多數節點的度（與該節點連接的其他節點數目）都小于或等于4.目前還沒有研究將GN 算法應用于對道路交通網絡進行脆弱性識別的深入研究中.

利用復雜網絡理論中GN 算法的思想，結合交通網絡的出行需求分布，改進了GN 算法中介數值的計算，然后對路網中的脆弱路段進行識別，并驗證該算法應用于道路網絡研究中的可行性.

1 模型構建

首先將道路網絡中的交叉口和路段分別抽象為網絡中的節點和邊，與其他復雜網絡類似，路網中存在內部節點聯系緊密，而對外連接路段較少的組團結構，即路網組團.路網組團之間的連接路段，即是結構性脆弱路段.

本文中，路網脆弱性的含義包括兩方面內容.一方面是路網中結構性脆弱路段的分布.另一方面是考慮了交通需求后，路段發生失效的可能性.在確定其結構脆弱性的基礎上，將路段的加權介數值（通過某一路段的所有最短路的出行需求之和）與其通行能力比值大于1的路段定義為失效路段，比值越大失效的可能性越大.發生失效說明路段供不應求，容易發生常態擁堵，失去其正常的交通功能.

1.1 模型框架

路網脆弱性識別模型分為兩大部分，一是結構性脆弱路段的診斷，二是脆弱路段失效順序的判斷.模型框架見圖1.

圖1 基于GN 算法的路網脆弱性識別模型

1.2 關鍵方法

為了探究路網自身結構和交通需求分布對路網脆弱性的影響，通過網絡介數值反映出用戶對路段的選擇傾向，從而找出路網中“潛在”的脆弱路段，本模型暫時不考慮交通流的動態變化情況對路網脆弱性的影響，假定用戶都試圖選擇最短路徑到達其目的地，并根據同一標準（自由流時間）判斷路徑長短.

1）介數值計算 首先利用BFS 算法［9］（breadth－first－search）搜索出路網中每一 個節點對的最短路徑Dij.

（1）路段介數值bij與原GN 算法中介數值定義類似，路段介數值bij等于每條路段ij 作為最短路段的次數.

（2）OD 加權介數值Bmn考慮了交通需求后改進GN 算法中介數值的計算.在給定路網組團間的OD（發生吸引量）的基礎上，將每兩個組團間的脆弱路段合并成一條通道，每條通道mn的OD 加權介數值Bmn，等于經過通道mn的所有最短路徑出行需求ODxy之和.

式中：ODxy為OD 對xy 之間的出行需求量.

（3）介數值最大路段的刪除 路段的介數值越大，說明通過該路段的潛在交通量可能越大，在網絡中的作用越重要，也最容易產生問題.因此，刪除介數值最大的路段，相當于模擬該路段交通功能完全失效，路網結構發生變化，從而繼續尋找其他易失效的連接路段.計算步驟如下.

步驟1 刪除介數值最大的路段max（bij）.

2）路網模塊度計算 為確定何時停止刪除介數最大路段，Newman等人引進了一個衡量網絡劃分質量的標準——模塊度.每次刪除介數值最大的路段之后，都計算一次模塊度Q 值，并將每次計算的Q 值繪制成模塊度曲線圖.他們的研究表明，網絡模塊度Q 在0到1之間，當Q 等于最大值Qmax時，對應的組團劃分能明顯體現網絡結構問題，且在實際網絡中Qmax通常位于0.3到0.7之間.因此，取模塊度值達到最大時的組團劃分結果作為最后結果.

模塊度Q 的計算公式為

2 案例分析

選取武漢市漢口地區道路網絡作為實證研究對象.研究區域的道路網絡共有節點140個，路段234條，由4個等級的路段構成：快速路、主干路、次支路、支路，見圖2.

圖2 道路網絡結構

2.1 結構性脆弱路段

通過編程實現模型計算，得到該路網的模塊度曲線變化見圖3，模塊度的最大值為0.724，此時，對應的組團數目為8個，結構性脆弱路段30條.

圖3 模塊度曲線變化情況

圖4 路網結構性脆弱路段及組團劃分情況

圖4呈現了結構性脆弱路段與路網組團的分布情況.從圖中可以看出，與大部分組團內部的路網密度相比，組團之間的連接路段數量很少.其中，組團2－3、組團2－5、組團4－8、組團5－6、組團5－8之間，都僅有一條連接路段.一旦惟一的連接路段失效，組團之間的交通將嚴重受阻，周圍路網和其他組團間的連接路段交通壓力將大大增加.這8個組團之間的30條連接路段，是該路網的結構脆弱性所在.要改善該路網結構，提升路網整體通行能力，應從這些結構性脆弱路段入手.

經過統計，案例路網的30條結構性脆弱路段占路網路段總數量的12.8%，其中，有12條主干路、11條快速路、5條次干路和2條支路.

針對以上情況，將結構性脆弱路段分成3類，提出相應的優化措施：（1）高路網密度地區的低等級脆弱路段，分析其日常交通流量，以及周圍連接道路的等級，合理提升其道路等級；（2）高路網密度地區的高等級脆弱路段，改善其周圍連接道路的通行能力，為該路段分流；（3）低路網密度地區的高等級脆弱路段，提高附近地區的路網密度，修建平行道路，與其共同承擔路網組團之間的連通壓力.

2.2 脆弱路段失效順序

路網結構決定了結構性脆弱路段的空間分布，而它們失效的順序則受交通需求的分布的影響.在組團劃分的基礎上，把道路網絡中的組團簡化為其網絡質心節點，組團之間的連接路段簡化為一條連接質心節點間的通道，可得到如圖5所示的簡化路網.

圖5 簡化路網示意

在已知各組團間發生吸引量ODmn的前提下，通過模型計算得到通道的OD 加權介數值Bmn.通道的通行能力為其合并路段通行能力之和，將介數值與通行能力的比值（B／C）大于1的路段按（B／C）的大小排序見表1.

表1 組團間脆弱通道的失效順序

通道的OD 加權介數值越高，說明這些組團間的交通需求越大；而通道的B／C 比值越大，說明這些連接路段的供給越不能滿足組團間的需求，其脆弱性比其他組團間的連接路段更明顯.從上表可以看出，連接組團3－4的通道介數值雖然不高，但是其B／C 值最大，說明組團3－4之間的連接路段的需求大于供給，脆弱性最高、最易失效.其次容易失效的路段分別是組團2－4、組團5－6、組團5－7、組團4－8和組團1－2之間的連接路段.

應從增大脆弱路段的通行能力，增加其他組團之間的連接度，以及均衡組團間的交通需求三個方面改善路網的脆弱性.

2.3 模型實用性分析

根據日常觀察、交通調查及相關統計資料，可得到當前實際經常發生擁堵路段，為驗證改進后GN 算法的準確性，表2對實際擁堵路段與診斷出的部分脆弱路段進行了對比.

表2 實際擁堵路段與脆弱路段（部分）對比表

盡管模型未考慮交通流和其他因素對用戶路徑選擇的影響，但從上表的對比可以發現，模型診斷出的脆弱路段與實際中發生擁堵的路段匹配度較高.說明路網結構的不合理制約了用戶對出行路徑的多重選擇，使其選擇偏好不能完全體現出來，只能選擇結構上的最短路.

3 結束語

路網脆弱性的研究在交通運輸系統規劃、管理過程中具有重要的研究價值.然而，目前對于路網脆弱性的概念界定還很不一致，對脆弱性識別研究的角度也不盡相同.本文從路網結構和交通需求的角度入手，以復雜網絡理論的GN 算法為基礎，考慮交通需求的權重后對算法中介數值的計算進行改進，構建了路網脆弱性的診斷模型，得到路網的結構性脆弱路段和一定需求分布下脆弱路段的失效情況.對比實際擁堵情況可知，該模型對路網脆弱性的識別具有一定準確性.

與以往研究不同的是，本模型可從路網結構入手對“潛在”的脆弱路段進行判斷.可利用本模型對不同類型、不同形態路網的脆弱性進行對比分析，研究結構性脆弱路段的空間分布規律.并可對規劃路網設定不同的需求分布，研究其在不同需求下的脆弱性，從而在路段發生失效之前提前采取預防措施.

由于處在研究的初期階段，模型中最短路的判斷標準較為單一，2種介數值的計算方法亦未進行深入的分析評價.未來的研究將進一步探索介數值的計算方法及其合理性，進而全面研究路網脆弱性的影響因素、動態變化及優化措施.

［1］HUSDAL J.Reliability and vulnerability versus cost and benefits［C］／／Queenstown and Christchurch，New Zealand，The 2nd International Symposium on Transportation Network Reliability，2004：180－186.

［2］JENELIUS E.Network structure and travel patterns：Explaining the geographical disparities of road network vulnerability［J］.Journal of Transport Geography，2009（17）：234－244.

［3］BELL M G H，KANTURSKA U，SCHM＾ECKER J D，et al.Attacker－defender models and road network vulnerability［J］.Philosophical Transactions of the Royal Society A－Mathematical Physical and Engineering Sciences，2008，366（1872）：1893－1906.

［4］尹洪英，徐麗群.道路交通網絡脆弱性評估研究現狀與展望［J］.交通運輸系統工程與信息，2010，10（3）：7－13.

［5］TAYLOR M，SEKHAR S，D′ESTE G.Application of accessibility based methods for vulnerability analysis of strategic road networks ［J］.Networks and Spatial Economics，2006（6）：267－291.

［6］NEWMAN M E J，GIRVAN M.Finding and evaluating community structure in networks［J］.Phys.Rev.E，2004，69：113－126.

［7］徐 林，王秀麗，王錫凡.電氣介數及其在電力系統關鍵線路識別中的應用［J］.中國電機工程學報，2010，30（1）：33－39.

［8］LAMMER S，GEHLSEN B，HELBING D.Scaling laws in the spatial structure of urban road networks［J］.Physica A，2006，363：89－95.

［9］AWERBUCH B G.Distributed BFS algorithms［J］.Foundations of Computer Science，1985（10）：250－256.