基于改進GN 算法的路網(wǎng)脆弱性診斷模型＊

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

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

0 引 言

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

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

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

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

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

1 模型構建

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

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

1.1 模型框架

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

圖1 基于GN 算法的路網(wǎng)脆弱性識別模型

1.2 關鍵方法

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

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

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

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

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

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

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

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

模塊度Q 的計算公式為

2 案例分析

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

圖2 道路網(wǎng)絡結構

2.1 結構性脆弱路段

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

圖3 模塊度曲線變化情況

圖4 路網(wǎng)結構性脆弱路段及組團劃分情況

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

經(jīng)過統(tǒng)計，案例路網(wǎng)的30條結構性脆弱路段占路網(wǎng)路段總數(shù)量的12.8%，其中，有12條主干路、11條快速路、5條次干路和2條支路.

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

2.2 脆弱路段失效順序

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

圖5 簡化路網(wǎng)示意

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

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

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

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

2.3 模型實用性分析

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

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

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

3 結束語

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

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

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

［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］尹洪英，徐麗群.道路交通網(wǎng)絡脆弱性評估研究現(xiàn)狀與展望［J］.交通運輸系統(tǒng)工程與信息，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］徐 林，王秀麗，王錫凡.電氣介數(shù)及其在電力系統(tǒng)關鍵線路識別中的應用［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.