姜文， 秦其明

(1.北京大學地球與空間科學學院遙感與地理信息系統(tǒng)研究所，北京 100871； 2.空間信息集成與3S工程應用北京市重點實驗室，北京 100871； 3.地理信息基礎軟件與應用國家測繪地理信息局工程技術研究中心，北京 100871)

0 引言

城市道路交通系統(tǒng)是分布區(qū)域廣泛的網(wǎng)狀系統(tǒng)，該網(wǎng)狀系統(tǒng)的運行狀態(tài)對災害的抵抗能力不強，災害發(fā)生的種類和頻率會隨著城市規(guī)模的增大和現(xiàn)代化程度的增高而增加。因此，對路網(wǎng)應急疏散問題的研究受到國內外的廣泛關注。應急疏散主要為了解決當發(fā)生災害時，危險地區(qū)的人們如何盡快轉移到安全區(qū)域的問題。作為一個整體的交通運輸網(wǎng)，牽一發(fā)而動全身，往往一個“瓶頸”路段的交通堵塞就能導致整個交通運輸網(wǎng)的癱瘓從而影響應急疏散。因此,開展城市交通路網(wǎng)脆弱性研究對城市應急疏散具有重要意義，同時可以通過確定和分析城市交通路網(wǎng)的脆弱點來衡量其通行能力。

考察路網(wǎng)疏散方面的研究開始于20世紀70年代，Houston提出了最早用于疏散分析的疏散率模型[1](dissipation rate model)和用于估算疏散時間的簡單統(tǒng)計公式； 隨后，Voorhess和Sheffi等也相繼提出了應急疏散的各種模型[2-4]，并在不同的條件下進行了應用。對于應急疏散脆弱性分析，國內開展的相關研究更晚些，大多從路網(wǎng)應急疏散路徑選擇、人員應急疏散行動的決策行為和公路交通應急物資運輸保障等方面開展研究[5-7]。劉小明等[8]指出國內外應急疏散理論與技術研究關鍵之一是如何在有效的時間內，將事故發(fā)生地點集結的待疏散車輛盡快疏散到安全區(qū)域； 宋永朝等[9]運用最小費用最大流理論建立了局域路網(wǎng)疏散分配模型，通過查找最小截量組成弧的分布位置，并對路網(wǎng)中最小截量組成弧的容量進行改造，進而有效提高局域路網(wǎng)的應急疏散能力； 尹洪英等[10]對路網(wǎng)脆弱性的評估方法進行了分類?？梢钥闯觯壳皯笔枭⒋嗳跣苑治龇较虻难芯?，多偏向于在數(shù)學和運籌學領域開展。地理信息系統(tǒng)(GIS)具有強大的空間信息分析功能，能夠直觀地展示空間分布模式和發(fā)展趨勢，比傳統(tǒng)學科更有利于開展交通路網(wǎng)脆弱性研究。

本文為了彌補傳統(tǒng)的數(shù)學和運籌學方法的不足，充分發(fā)揮GIS在空間分析領域的技術優(yōu)勢，提出了結合最小費用最大流(minimal cost maximal flow,MCMF)算法搭建GIS平臺來尋找具體交通路網(wǎng)網(wǎng)絡模型脆弱點、分析路網(wǎng)脆弱性的新方法。首先，構建了應急疏散路網(wǎng)模型，并在各路段容量有限的條件下，以疏散交通個體數(shù)量最多和總疏散時間成本最小為目標，利用最短路徑快速算法(shortest path faster algorithm，SPFA)計算路網(wǎng)系統(tǒng)容量; 其次，在此模型基礎上，獲取限制路網(wǎng)系統(tǒng)疏散能力的“瓶頸路段”，指導路網(wǎng)容量的提升，降低路網(wǎng)應急疏散的脆弱性?；谏鲜隼碚摲治?，搭建了尋找具體交通路網(wǎng)網(wǎng)絡模型脆弱點的GIS平臺，運用修正模型方法模擬建立了某實地及其周圍地區(qū)的路網(wǎng)疏散分配模型; 最后，將該模型在GIS平臺上進行了試驗，準確找到路網(wǎng)的脆弱之處，同時還得到了在路網(wǎng)最大流時，疏散時間最短的流量分布。將道路網(wǎng)擴容前后的路網(wǎng)容量進行對比，證實應急疏散脆弱性分析的必要性和有效性。

1 應急疏散路網(wǎng)模型構建

1.1 路網(wǎng)容量定義

路網(wǎng)容量分為狹義與廣義路網(wǎng)容量。前者指單位時間內城市道路網(wǎng)可通行的最大車流量或人流量，后者為一定的時間段內，在各種條件的約束下，城市道路網(wǎng)上可容納的行人或交通個體數(shù)； 對于外部約束條件來說，路網(wǎng)容量可分為環(huán)境容量Cev、物理容量Cph和經(jīng)濟容量Cec，這3類容量彼此獨立存在，同時影響著城市道路網(wǎng)容量，不計其他因素影響，則在外部條件的制約下，城市交通廣義容量為C=min(Cph,Cev,Cec)。本文從狹義路網(wǎng)容量角度，分析局部(區(qū)域)道路網(wǎng)在一定服務水平下所能承擔的最大交通容量，即允許通行的最大人流量。

1.2 應急疏散路網(wǎng)模型

災害事件發(fā)生時，如何在最短時間內通過疏散路徑從危險區(qū)到達安全區(qū)是人們關心的，所以應急疏散路徑選擇的優(yōu)先考慮條件是總路徑疏散時間最小。這里從網(wǎng)絡及網(wǎng)絡流和路網(wǎng)應急疏散的交通分配2方面來建立應急疏散路網(wǎng)模型。

定義一個網(wǎng)絡：N=(V,E,c,X,Y)，其中V為該網(wǎng)絡圖的頂點集；E為有向邊(即弧)集；c為弧上的容量；X與Y分別為發(fā)點集與收點集。如果滿足以下條件： ①G=(V,E)是一個有向圖； ②c(e)是邊e的容量，為E上的非負函數(shù)，定義為容量函數(shù)； ③X與Y分別為G的發(fā)點集與收點集，二者是V的2個非空且不相交子集，I=V(X∪Y)稱為G的中間點集。X的頂點稱為發(fā)點(源)，Y的頂點稱為收點(匯)，I的頂點稱為中間點。若|X|=1，|Y|=1，稱N為單源單匯網(wǎng)絡，如圖1所示。

圖1 單源單匯網(wǎng)絡圖Fig.1 Single source-single terminal network

若|X|>1，|Y|>1，稱N為多源多匯網(wǎng)絡，如圖2所示。

圖2 多源多匯網(wǎng)絡圖Fig.2 Multisource-multiterminal network

設N為一個網(wǎng)絡，f是E上的非負函數(shù)，如果：

1)容量限制條件

0≤f(e)≤c(e),?e∈E

；

(1)

2)流量守恒條件

(2)

式(1)表示通過該邊的流量不能超過該邊的容量。式(2)中，N+(v)為過v的所有出弧的集；N-(v)為v的所有入弧的集；f為網(wǎng)絡N的一個流；f(e)為邊e的流量。每個中間點流進的流量等于流出的流量，中間點流量保持平衡。值得注意的是，任一網(wǎng)絡至少存在一個流，如零流(f(e)=0,e∈V)。圖2表示一個網(wǎng)絡及網(wǎng)絡流，它的發(fā)點集為X={x1,x2}； 收點集為Y={y1,y2}； 中間點集為I={v1,v2,v3,v4}。

1.2.1 路網(wǎng)模型構建

城市道路交通網(wǎng)都可看作一個賦權有向圖。圖中的結點代表實際問題中的道路交叉口(包括高架橋的出入口)，圖中的邊代表相鄰結點之間的道路。一般情況下，可將邊的權重歸結為路的寬度、長度和擁塞程度等其他因素； 而災時疏散過程中，與空間距離和運輸費用相比較，人們更關注疏散所需的時間，因此本文將道路的通行時間作為路網(wǎng)模型中邊的權重。

依據(jù)災害事件的類型及其影響范圍，路網(wǎng)疏散問題可分為點事件和面事件[11]。無論是建筑物內疏散還是露天大范圍疏散，都可以轉化為疏散網(wǎng)絡的問題，本文的應急疏散脆弱性分析主要以網(wǎng)絡流優(yōu)化為基礎，疏散的優(yōu)化目標是發(fā)揮整個路網(wǎng)交通系統(tǒng)的最大效率[12]。點事件的路網(wǎng)疏散分配問題可視為單源單匯或單源多匯問題； 面事件的路網(wǎng)疏散分配問題可視為多源多匯問題。

1.2.2 路網(wǎng)模型簡化

實際研究中，可將單(多)源多匯網(wǎng)絡轉換成一個單源單匯網(wǎng)絡。在解決實際問題時，常采用這種方法，假設每條邊的容量無限，于多個發(fā)點前添加一個發(fā)點s，多個收點后添加一個收點t，如圖3所示。

圖3 多源多匯網(wǎng)絡的轉化Fig.3 Transformation of multisource- multiterminal network

1)V′=V∪{s,t} ，

(3)

式中s和t分別為N′的發(fā)點與收點；

2)E′=E∪{(s,t)|x∈X}∪{(y,t)|y∈Y} ；

(4)

3)c′=c(e),e∈E；c′(s,x)=,x∈X，

c′(y,t)=,y∈Y。

(5)

2 應急疏散脆弱性分析算法

2.1 最大流最小割定理及增廣鏈

最大流最小割定理：

1)設f是流，K是割，若Valf=C(K)，則f是最大流，K是最小割。

2)網(wǎng)絡N的最大流的流量等于最小割的容量。

該定理是圖論的重要核心，在適當?shù)倪x擇網(wǎng)絡后，應用這個定理往往能夠獲得解決。從該定理的證明中，可以引出求網(wǎng)絡最大流的一個算法。但這種方法實際做起來有困難，因為沒解決如何尋找增廣鏈的問題。

(6)

若l(P)=0，則稱P鏈為飽和鏈； 若l(P)>0，則稱P鏈為非飽和鏈。

設f是一個流，P是從源s到匯t的一條鏈，若P滿足： ①在弧e∈P+上，0 ≤f(e)

2.2 MCMF算法

一般的網(wǎng)絡最大流算法沒有考慮到網(wǎng)絡上產(chǎn)生最大流的費用問題，費用因素在許多實際問題中也占有很重要的地位。對于應急疏散問題將疏散時間作為路徑費用，必須在保證路網(wǎng)流量一定的情況下，盡可能縮短疏散時間。因此需要求解網(wǎng)絡的最小費用最大流問題。

求最小費用最大流常采用求最短路徑的SPFA算法，該算法能夠處理負邊，能在O(kE)的時間復雜度內求出源點到其他所有點的最短路徑。

設Fee代表s到i點的當前最小費用，Pred代表s到i的當前最短路徑中i點之前的一個點的編號。開始時Dist全部為+∞，只有Dist[s]=0，Pred全部為0。 建立一個隊列，將所有需要迭代的點存入隊列，初始時隊列中只有一個點s。用一個布爾數(shù)組記錄并判斷每個點是否處在隊列中。每次迭代，取出隊頭的點v，依次枚舉從v出發(fā)的邊v→u，設邊的費用為fee，判斷Fee[v]+fee是否小于Fee[u]，若小于則改進Fee[u]，將Pred[u]記為v，并且由于s到u的最小費用變小了，有可能u可以改進其他的點，所以若u不在隊列中，就將它放入隊尾。就這樣一直進行迭代，直到隊列變空，也就是s到所有的最短距離都確定下來，結束算法，流程如圖4所示。

圖4 SPFA算法流程Fig.4 Flow chart of SPFA algorithm

3 實驗與結果

本文選用北京市某區(qū)域的路網(wǎng)信息作為實驗數(shù)據(jù)。該區(qū)域如圖5所示，周邊配套設施完整，幼兒園、中小學、大學、綜合商場、醫(yī)院、郵局、銀行、賓館公園等均有，是個典型的社區(qū)。從路網(wǎng)結構上分析，2條主干道相鄰，支路分布均勻，但存在斷頭路。這些斷頭路勢必會影響某個路段或交叉口的通行能力，影響整個路網(wǎng)容量的增加，從而影響應急疏散的效率。

圖5 北京市某區(qū)域及其周圍路網(wǎng)分布Fig.5 Distribution of road network in a region of Beijing

3.1 路網(wǎng)建立

對照該衛(wèi)星地圖的二維地圖，運用ArcGIS軟件對其路網(wǎng)進行矢量化操作，得到初始路網(wǎng)，導入要素集，再進行拓撲檢查，從而得到路網(wǎng)模型如圖6所示。

圖6 應急疏散路網(wǎng)模型Fig.6 Road network model of emergency evacuation

假設突發(fā)災害事件發(fā)生在結點1和結點2，此次分析的路網(wǎng)是多源多匯型，利用修正模型法將其轉化為單源單匯型。由于該小區(qū)及其周圍路網(wǎng)屬于局域路網(wǎng)，且本文選擇了狹義的路網(wǎng)容量，即城市道路網(wǎng)單位時間內可以通行的最大的人流量或者車流量，而路網(wǎng)為社區(qū)路網(wǎng)，選取人為要疏散的交通個體，因此路網(wǎng)容量為每條路每分鐘所能疏散的人的數(shù)量。根據(jù)路段長度大致估算路段的容量，由于社區(qū)街道相對較窄，假設一條路并排可以容納4人，前后相距為1 m，算出每條道路上可以容納的人數(shù)，并假設每條道路上所容納的人數(shù)在1 min中內疏散完全； 路段上的時間消耗為路段長與速度之比，取人群疏散的平均速度為1 m/s； 然后把每條弧段的起點，終點補充好，至此，路網(wǎng)建立完畢。圖中每條弧段的標注為(路網(wǎng)容量和時間費用)，路網(wǎng)容量單位為個/min，時間費用單位為min。

3.2 基于GIS的應急疏散脆弱性分析

本文采用ArcEngine二次開發(fā)，實現(xiàn)的功能是將符合條件的路網(wǎng)數(shù)據(jù)加載，進行道路網(wǎng)的脆弱性分析： MCMF及其脆弱性分析。首先，路網(wǎng)數(shù)據(jù)必須包含4個字段，分別是： content(短整型)——容量、fee(雙精度)——時間費用、start_vex(短整型)——開始結點、end_vex(短整型)——結束結點； 其次，該路網(wǎng)是要經(jīng)過拓撲檢查，確定各個交叉口道路選擇的靈活性。

3.2.1 系統(tǒng)設計及結果計算

系統(tǒng)界面包括菜單欄、工具欄、窗口顯示欄和狀態(tài)欄4大部分，如圖7所示。

圖7 系統(tǒng)界面設計圖Fig.7 Design diagram of system interface

系統(tǒng)主要實現(xiàn)的功能是MCMF計算，最小費用時的流量分布和找出路網(wǎng)的脆弱之處； 輔助功能有查看圖層屬性和修改圖層符號等。

將圖6建立的路網(wǎng)數(shù)據(jù)加載進入GIS平臺，分別點擊“最小費用最大流”和“脆弱性分析”，運行結果如圖8所示。圖8中的最小費用計算結果指的是2 637個人平均的疏散時間為16.361 min； 高亮部分是路網(wǎng)中的飽和弧，即路網(wǎng)系統(tǒng)疏散能力的“瓶頸路段”，對該組成弧進行擴容處理，就能達到改造少量路段，有效增大路網(wǎng)容量，提高該社區(qū)路網(wǎng)應急疏散能力的效果。圖9為MCMF下的流量分布。

(a) 流量分布(b) 脆弱性分析

圖8流量分布與脆弱性分析

Fig.8Flowdistributionandanalysisofvulnerability

圖9 MCMF下的流量分布Fig.9 Flow distribution under minimal cost maximal flow

由圖9的流量標注中可以看出，圖8中高亮部分的流量都已達到飽和值，為該小區(qū)應急疏散的脆弱之處。每條弧段的標注為(路網(wǎng)容量和實際流量)。

3.2.2 模擬計算結果

為了證實系統(tǒng)的可靠性，本文用運籌學的觀點求解了該區(qū)域及其周圍路網(wǎng)的最大流及最小時間費用下流量的分布情況，并進行驗證。管理運籌學軟件2.5版，是《管理運籌學》[13]的隨書軟件。該軟件的模塊有線性規(guī)劃、最短路徑、最小費用最大流等共15個子模塊。本文采用最小費用最大流模塊進行模擬，由運行的結果可知，最大流為2 637，和3.2.1節(jié)計算的結果完全契合，不僅如此，在最小時間費用最大流情況下的流量分布也完全契合。由此可以證明，上文搭建的GIS平臺非常可靠，且圖文一體，直觀快捷。

3.2.3 道路網(wǎng)絡優(yōu)化效果分析

對3.2.2節(jié)中計算所得的路網(wǎng)瓶頸擴容一倍，擴容之前與擴容之后的最大流量與平均時間費用如表1所示。

表1 道路網(wǎng)擴容前后情況對比Tab.1 Minimal time cost and maximal flow before and after road network expansion

由表1可以看出，盡管平均疏散時間減少得不明顯，但是擴容之后路網(wǎng)的最大流擴大了將近一倍。由此可以看出，圖9中找到的道路瓶頸確實阻礙了整個路網(wǎng)容量的增加，該路段也就是路網(wǎng)改造的關鍵之處。

4 結論

本文充分發(fā)揮了GIS在空間分析領域的技術優(yōu)勢，提出了結合最小費用最大流(MCMF)算法搭建GIS平臺來尋找具體交通路網(wǎng)網(wǎng)絡模型脆弱點，分析路網(wǎng)脆弱性的新方法。通過實際算例分析，以最大流-最小割，最小費用最大流和GIS相結合的方法，對北京市某區(qū)域進行了應急疏散脆弱性分析，找到了路網(wǎng)的脆弱地方，通過處理路網(wǎng)的這些“瓶頸之處”，就能在改造少量路段的條件下，實現(xiàn)有效增大路網(wǎng)容量的目的，從而提高路網(wǎng)的應急疏散能力。主要結論如下：

1)路網(wǎng)容量和費用方面。本文中疏散的對象是人，費用為疏散時間，但搭建的GIS平臺的功能并不局限于此。從大的范疇來講，疏散的對象是交通個體，費用可以為金錢時間等其他疏散成本。

2)路網(wǎng)建模方面。選取的實例為多源多匯網(wǎng)絡，而多源多匯網(wǎng)絡可轉化成單源單匯網(wǎng)絡，且點事件的路網(wǎng)疏散分配問題為單源單匯或單源多匯問題，面事件的路網(wǎng)疏散分配問題為多源多匯問題，因此，此路網(wǎng)模型可以涵蓋路網(wǎng)疏散問題的兩大事件： 點事件和面事件，應用性比較強。

3)脆弱性分析方面。本文方法不僅能夠找到整個疏散路網(wǎng)的瓶頸之處，還能計算出基于最小時間的最大流在各個路段上的分布，可給實際疏散工作提供數(shù)據(jù)支持和決策輔助。

4)擴容前后對比方面。對于“瓶頸路段”的擴容，能夠顯著增加路網(wǎng)容量，減少路網(wǎng)的脆弱性。