余建星，周健狀，柴 松，梁 靜，張 謙

(天津大學(xué) 水利工程仿真與安全國家重點實驗室，天津 300072)

0 引 言

近年來,國際能源市場發(fā)生了重大的歷史變化，國際油價持續(xù)上升，屢創(chuàng)歷史新高,海洋石油一躍成為重要的戰(zhàn)略資源。海洋石油的開發(fā)在近年的不斷摸索和研究中取得長足的進步。目前，海洋石油開發(fā)主要依靠海洋平臺和FPSO進行油氣勘探、采集和加工等活動。海洋作業(yè)平臺上，作業(yè)種類多樣，生活區(qū)工作區(qū)劃分復(fù)雜，路徑也相對曲折，一旦發(fā)生緊急事件，容易造成人員恐慌、擁擠踩踏和傷亡。本文針對海洋平臺以及船舶甲板，提出突發(fā)事件下的緊急疏散方法，以盡可能短的時間完成疏散過程，在最大程度上保證人員安全。

緊急疏散是指颶風(fēng)、海嘯等自然災(zāi)害以及火災(zāi)、爆炸泄漏等突發(fā)事件條件下，將處于危險區(qū)域的人群快速疏散至安全地點。國內(nèi)外的諸多學(xué)者采用不同方法對此進行了研究?，F(xiàn)行的疏散方法大體分為計算機仿真和路徑規(guī)劃兩類。計算機仿真基于疏散需求對運行過程進行隨機模擬，常用軟件如DYNASMART和DynaMIT。但對大規(guī)模運輸網(wǎng)絡(luò)，模擬過程耗時長。

路徑規(guī)劃方法多基于網(wǎng)絡(luò)流算法。Hamacher等綜述了疏散問題的宏觀模型，將時間作為主要因素，給出了多個疏散數(shù)學(xué)模型[1]。高明霞等將交通管制措施考慮在內(nèi)，將疏散路線的優(yōu)化描述為分方向點權(quán)網(wǎng)絡(luò)中的最小費用流問題，提出基于圖形表示，在分方向點權(quán)網(wǎng)絡(luò)中尋找最小費用流的改進最小費用路算法[2]。張江華等基于啟發(fā)式算法利用網(wǎng)絡(luò)優(yōu)化思想，研究了存在優(yōu)先順序的多源點和容量受限的應(yīng)急疏散[3]。楊建芳等利用最短路徑盡可能飽和疏散的思想，設(shè)計出多出口建筑物突發(fā)事件應(yīng)急疏散算法，通過對網(wǎng)絡(luò)進行不斷更新來確定每條路徑實際流量，從而確定最優(yōu)疏散方案[4]。Lu，Huang和Shekhar三位學(xué)者提出了2個啟發(fā)式的容量受限的原型算法,即SRCCP和MRCCP，并且使用小型網(wǎng)絡(luò)對它們做了性能測試[5]。SRCCP為每個起始結(jié)點指定了一條可用路徑，它雖具有較快的運行時間，但效果很差。MRCCP為每個起始結(jié)點分配了多條路徑，解的質(zhì)量不錯，同時相對線性規(guī)劃法來說，具有較少的時間成本。但MRCCP在一些大型道路網(wǎng)絡(luò)上由于計算成本較大效果不太令人滿意。后來，以上三位學(xué)者又對其進行改進，提出了CCRP算法[6]。CCRP算法利用基本的網(wǎng)絡(luò)拓?fù)鋱D和容量限制屬性來生成一個次優(yōu)的疏散方案，它以最短疏散時間為算法的最終目標(biāo)。CCRP算法可以將時間成本降低到0(p·nlogn)。

上述研究往往針對不同的背景建立差異化模型。本文基于CCRP算法，針對船舶與海洋工程中的特點，研究緊急疏散的模型和算法實現(xiàn)。

1 問題描述

已知：

一賦權(quán)網(wǎng)絡(luò)圖G=(poi,edg)表示疏散空間的連接和節(jié)點布置情況，poi是節(jié)點集合，edg是邊集合；

每個節(jié)點的2個屬性：節(jié)點容量cap_poi和初始疏散人數(shù)ini_num；

每條邊的2個屬性：邊容量cap_edg和權(quán)重c。邊容量cap_edg是在任一時刻，該條邊可同時容納的疏散人數(shù)的最大值；權(quán)重c是疏散者通過該條邊所需的時間；

總疏散人數(shù)以及疏散人員在建筑物內(nèi)各個節(jié)點的布置情況ini_num；

疏散起點數(shù)量和標(biāo)號、終點數(shù)量和標(biāo)號；

緊急事件類型，范圍，影響程度。用來求解當(dāng)量長度；

假設(shè)終點容量無限大。

求解：緊急疏散方案(包括：若干條從起點到終點的路線；不同疏散路線的疏散人數(shù)；不同疏散人群在到達各個路線節(jié)點的時刻以及等待時間)。

目標(biāo)：疏散總時間最短。

原則：先進先出——即當(dāng)2組疏散人員相遇，需要使用同一路徑時，先開始疏散的人員優(yōu)先通過。

2 CCRP疏散算法

CCRP算法是求解緊急疏散問題的啟發(fā)式算法的典型代表。它能在相對較低的計算成本下，求解得到質(zhì)量損失較小的疏散方案。一般而言，由CCRP計算得到的解的質(zhì)量與線性規(guī)劃最優(yōu)解的偏差不超過10%，而計算時間卻只需要線性規(guī)劃求解時間的一半以內(nèi)。同時，CCRP算法對疏散人數(shù)、起點規(guī)模以及網(wǎng)絡(luò)規(guī)模具有可拓展性。

CCRP算法的基本思想是，將節(jié)點可用容量和邊可用容量模擬成隨時間變化的系列值，使得更接近實際疏散過程中的節(jié)點和邊的情況。使用Dijkstra最短路算法找到最短路徑并不斷修正節(jié)點和邊可用容量。計算中，將每個疏散起點的疏散者分成若干小組，并為每個小組指定疏散路徑和時刻表。根據(jù)路徑的容量限制，為每條路徑預(yù)留流量。基于新的路徑容量，重新計算最短路，直到所有疏散者疏散完畢。

3 改進的CCRP疏散算法

3.1 抽象疏散網(wǎng)絡(luò)圖

抽象疏散網(wǎng)絡(luò)圖將實際布置圖和疏散網(wǎng)絡(luò)圖聯(lián)系在一起，對于海洋平臺等小范圍疏散對象的疏散過程非常重要。筆者查閱大量文獻，沒有找到說明抽象網(wǎng)絡(luò)圖的相關(guān)資料。以下是筆者根據(jù)反復(fù)試驗總結(jié)出的網(wǎng)絡(luò)圖的抽象方法，難免有不足之處，有待完善。

抽象疏散網(wǎng)絡(luò)圖大體分為劃分節(jié)點、確定邊以及相關(guān)參數(shù)設(shè)置3個步驟。通常劃分節(jié)點和確定邊2個步驟同時進行。

網(wǎng)絡(luò)圖中的節(jié)點與實際海洋平臺上的房間劃分并不完全一致。網(wǎng)絡(luò)圖中的節(jié)點劃分，一方面受到實際平臺上的房間劃分的影響，一方面與各個房間的出口布置有關(guān)。節(jié)點劃分的基本原則是：① 每個房間首先劃分為1個節(jié)點，再根據(jù)房間出口布置和數(shù)量將該節(jié)點劃分為若干節(jié)點；② 每個節(jié)點有1個節(jié)點中心，代表節(jié)點的實際位置，一般設(shè)置在節(jié)點的出口處；③ 邊是有向邊，連接2個節(jié)點中心，代表2個節(jié)點之間的連接情況；④ 當(dāng)2條邊有沖突時，通過額外劃分虛節(jié)點解決；⑤ 邊的方向以疏散到出口為準(zhǔn)，當(dāng)無法確定時，允許出現(xiàn)雙向邊；⑥當(dāng)網(wǎng)絡(luò)圖過于復(fù)雜時，可簡化處理。當(dāng)若干個房間互相之間的連通性較好，整體面積不大，而且整體和外界相對封閉，沒有過多的出口時，可以將這若干個房間作為一個整體處理，不考慮整體內(nèi)部的房間布置情況，只考慮整體的出口，劃分為與出口數(shù)相等的節(jié)點數(shù)，節(jié)點中心一般設(shè)置在該整體的出口處。

相關(guān)參數(shù)設(shè)置主要指邊參數(shù)和點參數(shù)的設(shè)置。邊參數(shù)又包括邊通過時間和邊通量2項內(nèi)容。邊通過時間和邊總長度成正比；邊通量與邊的最小寬度成正比。點參數(shù)包括節(jié)點容量和節(jié)點初始疏散人數(shù)2項內(nèi)容。節(jié)點容量與節(jié)點大小、用途有關(guān)。節(jié)點初始人數(shù)是隨機的。

以上工作完成，將相關(guān)參數(shù)標(biāo)識在節(jié)點和邊上，可得到疏散網(wǎng)絡(luò)圖。

3.2 當(dāng)量長度概念的應(yīng)用

緊急疏散往往是應(yīng)對某些緊急事件，如火災(zāi)、爆炸、毒氣泄漏等。緊急事件的發(fā)生，一方面提出了緊急疏散的必要性，另一方面，也會影響到疏散的結(jié)果。具體表現(xiàn)為：處于危險區(qū)域的疏散路徑，很可能不再適于人員通行，或者人員通過危險路徑的難度增加。傳統(tǒng)的CCRP算法能有效解決緊急疏散問題，但卻沒有將緊急事件的影響考慮在內(nèi)。

本文對此進行改進的基本思想為：針對特定的緊急事件，修改路徑信息，引入當(dāng)量長度的概念[7]。

第i條路徑的當(dāng)量長度

li=ki·ωi·lri。

式中：ki=v1i/v2i，ki為疏散路徑i的通行難度系數(shù)，v1i為正常通行速度，v2i為特定疏散情況下的通行速度；ωi為危險系數(shù)，表征路徑i的危險程度，與緊急事件的類型、發(fā)生地點、影響范圍等有關(guān)，ω∈[1,+∞)；lri為路徑i的實際長度。

此外，當(dāng)緊急事件發(fā)生時，危險區(qū)域的范圍和危險程度都隨時間變化。為了模擬該現(xiàn)象，令當(dāng)量長度是隨時間和空間變化的函數(shù)，該函數(shù)受到疏散區(qū)域通風(fēng)條件和布置情況等的影響。即li=f(w,a,e)，w是通風(fēng)條件，a是布置情況，e是其他條件。

3.3 雙向邊的應(yīng)用

傳統(tǒng)的CCRP算法，針對單向有向網(wǎng)絡(luò)圖。但在實際疏散網(wǎng)絡(luò)中，由于各個節(jié)點中人數(shù)的隨機性，常不能確定疏散過程中各條連接邊的疏散方向。為此，本文引入雙向邊，以證明CCRP算法在雙向邊條件下仍適用。

證明：CCRP算法中，雙向邊的2個方向在實際疏散中不會發(fā)生沖突。

基于CCRP疏散算法的1次疏散過程中，1條邊的2個方向不可能均被疏散使用?題目。

反證法：

假設(shè)，在基于CCRP疏散算法的疏散過程中，1條邊的2個方向均被疏散使用。

圖示假設(shè)情景：

圖1 雙向邊示意圖
Fig.1 Bidirectional edge

圖1中，AB代表雙向邊，BD代表從B節(jié)點到達某一出口的路徑，AC代表從A節(jié)點到達某一出口的路徑。

存在如下2條疏散路徑：A-B-D和B-A-C。2條路徑的疏散人數(shù)分別是flowA和flowB，出發(fā)時刻分別是tA和tB， 且flowA,flowB≥1。

由此可證明，上述情景在實際疏散中不可能出現(xiàn)。

若tA≤tB(即flowA先出發(fā))，根據(jù)CCRP的最短路原則，A-B-D路徑都是tA時刻的最短路。

而由圖易知，dBD

所以，ABD不是tA時刻的最短路，該結(jié)論與CCRP的最短路原則矛盾，tB≤tA時同理可證，

所以，圖示情景不可能出現(xiàn)，即，在CCRP疏散算法的一次疏散過程中，1條邊的2個方向不可能均被使用，題目得證。

3.4 改進的CCRP算法流程

綜合上述對CCRP的改進方案，提出以下改進CCRP算法流程：

1)從海洋平臺布置圖中抽象出疏散網(wǎng)絡(luò)圖；

2)給網(wǎng)絡(luò)添加超起點S0，用邊連接超起點S0和其他起點。邊容量是+∞，通過時間是0；

3)處理每條邊，以當(dāng)量長度代替實際長度。li=ki·ωi·lri；

4)當(dāng)任一起點還有疏散人員時，應(yīng)用Dijkstra最短路算法求解從超起點S0到任一終點的路徑R。R滿足：

① 在所有的起點到終點的路徑中，通過時間最少；

② 路徑上的每條邊的可用邊容量在對應(yīng)時刻大于0；

③ 路徑上每個節(jié)點的可用點容量在對應(yīng)時刻大于0。

5)確定人流量flow。flow=min(節(jié)點處的疏散人員數(shù)量，可用邊容量，可用點容量)。

6)修正邊參數(shù)及點參數(shù)?？捎眠吶萘?可用邊容量-flow；可用點容量=可用點容量-flow；

7)檢查所有起點，是否還有未被疏散的人員。若有，返回第3步；否則，轉(zhuǎn)到第8步；

8)疏散完成，輸出疏散方案。

4 算例分析

假定一海洋平臺或船舶甲板的布置圖如圖2所示。在該海洋平臺或甲板的四周，是一圈逃生通道。各房間之間及與走廊的連接情況如圖2所示。根據(jù)疏散網(wǎng)絡(luò)圖的繪制原則，得到節(jié)點劃分路徑連接情況及疏散網(wǎng)絡(luò)圖分別如圖3～圖4所示。

圖2 布置圖Fig.2 Map of layout

圖3 節(jié)點劃分以及路徑連接情況Fig.3 Node divide and path connection

圖4 疏散網(wǎng)絡(luò)圖(邊長度為當(dāng)量長度)Fig.4 Map of evacuation network

根據(jù)改進的CCRP算法，利用Matlab編程工具輔助計算，得到疏散方案如表1所示。該表詳細(xì)給出了若干條疏散路徑、每條路徑的疏散人數(shù)、疏散者在不同節(jié)點的到達時間、等待時間、各條疏散路徑的結(jié)束時間及疏散總時間等信息。

表1 疏散方案

以第3條路徑為例說明：該路徑上有1個疏散者，路徑順序是11-18-36。該疏散者在11節(jié)點上等待1個時間單位，然后從11節(jié)點出發(fā)，依次來到18節(jié)點、36節(jié)點，完成疏散。除了在11節(jié)點等待1個時間單位，疏散者在其他位置不做停留。該疏散者在該條路徑上完成疏散的總時刻是第3個時間單位。

圖5 典型節(jié)點疏散人數(shù)變化Fig.5 Changes of number of people in typical nodes

為了驗證算法的有效性，圖5給出了3個典型節(jié)點的疏散人數(shù)變化情況。節(jié)點12，24和36分別是中間節(jié)點、起點和終點。由圖可知，節(jié)點12作為中間節(jié)點，該節(jié)點的疏散人數(shù)呈波動狀態(tài)，這與該節(jié)點在不同路徑中的使用情況有關(guān)；節(jié)點24是起點，該節(jié)點的疏散人數(shù)單調(diào)減少，疏散者不斷從起點離開；節(jié)點36是終點，該節(jié)點的疏散人數(shù)呈單調(diào)增加狀態(tài)，這表征疏散人員不斷被疏散到該節(jié)點，與實際情況相符。此外，這3個節(jié)點在任一時刻的疏散人數(shù)均不大于其節(jié)點容量，符合實際情況。

5 結(jié) 語

本文針對海洋平臺以及船舶甲板的緊急疏散問題，基于CCRP算法，提出了疏散網(wǎng)絡(luò)圖的繪制方法，并在計算中使用了當(dāng)量長度、雙向邊2個概念，將緊急事件和疏散人員分布情況對疏散方案的影響考慮在內(nèi)，給出了多起點、多終點、容量受限的疏散算法。通過算例驗證了算法的有效性和可行性。文中的點參數(shù)、邊參數(shù)、以及求解當(dāng)量長度的有關(guān)參數(shù)，需要試驗數(shù)據(jù)不斷完善修正。

[1] HAMACHER H W,TJANDRA S A.Mathematical modeling of evacuation problems：a state of the art[C].Berlin:Springer,2002：227-226.

[2] 高明霞，賀國光.考慮交通管控影響的疏散組織措施優(yōu)化研究[D].天津：天津大學(xué)，2007.

[3] 張江華，劉治平，朱道立.多源點突發(fā)災(zāi)害事故應(yīng)急疏散模型與算法[J].管理科學(xué)學(xué)報，2009，12(3)：111-118.

[4] 楊建芳，高巖.多出口建筑物突發(fā)事件應(yīng)急疏散模型和算法[J].系統(tǒng)工程理論與實踐,2011，31：147-153.

[5] LU Qing-song,HUANG Yan.Evacuation planning:a cap-acity constrained routing approach[J].Department of Computer Science,2003：1-11.

[6] LU Qing-song,GEORGE B.Capacity constrained routing algorithm for evacuation planning: a summary of results[J].2005：291-306.

[7] 肖國清，溫麗敏.基于遺傳算法的毒氣泄漏時最佳疏散路徑的研究[J].湘潭礦業(yè)學(xué)院學(xué)報，2001，16(4)：9-12.