改進(jìn)CCRP疏散算法在船舶與海洋工程中的應(yīng)用

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

(天津大學(xué) 水利工程仿真與安全國家重點(diǎn)實(shí)驗(yàn)室，天津 300072)

0 引 言

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

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

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

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

1 問題描述

已知：

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

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

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

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

疏散起點(diǎn)數(shù)量和標(biāo)號(hào)、終點(diǎn)數(shù)量和標(biāo)號(hào)；

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

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

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

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

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

2 CCRP疏散算法

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

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

3 改進(jìn)的CCRP疏散算法

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

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

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

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

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

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

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

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

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

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

li=ki·ωi·lri。

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

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

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

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

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

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

反證法：

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

圖示假設(shè)情景：

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

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

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

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

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

而由圖易知，dBD

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

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

3.4 改進(jìn)的CCRP算法流程

綜合上述對(duì)CCRP的改進(jìn)方案，提出以下改進(jìn)CCRP算法流程：

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

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

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

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

① 在所有的起點(diǎn)到終點(diǎn)的路徑中，通過時(shí)間最少；

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

③ 路徑上每個(gè)節(jié)點(diǎn)的可用點(diǎn)容量在對(duì)應(yīng)時(shí)刻大于0。

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

6)修正邊參數(shù)及點(diǎn)參數(shù)。可用邊容量=可用邊容量-flow；可用點(diǎn)容量=可用點(diǎn)容量-flow；

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

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

4 算例分析

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

圖2 布置圖Fig.2 Map of layout

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

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

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

表1 疏散方案

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

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

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

5 結(jié) 語

本文針對(duì)海洋平臺(tái)以及船舶甲板的緊急疏散問題，基于CCRP算法，提出了疏散網(wǎng)絡(luò)圖的繪制方法，并在計(jì)算中使用了當(dāng)量長度、雙向邊2個(gè)概念，將緊急事件和疏散人員分布情況對(duì)疏散方案的影響考慮在內(nèi)，給出了多起點(diǎn)、多終點(diǎn)、容量受限的疏散算法。通過算例驗(yàn)證了算法的有效性和可行性。文中的點(diǎn)參數(shù)、邊參數(shù)、以及求解當(dāng)量長度的有關(guān)參數(shù)，需要試驗(yàn)數(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] 張江華，劉治平，朱道立.多源點(diǎn)突發(fā)災(zāi)害事故應(yīng)急疏散模型與算法[J].管理科學(xué)學(xué)報(bào)，2009，12(3)：111-118.

[4] 楊建芳，高巖.多出口建筑物突發(fā)事件應(yīng)急疏散模型和算法[J].系統(tǒng)工程理論與實(shí)踐,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] 肖國清，溫麗敏.基于遺傳算法的毒氣泄漏時(shí)最佳疏散路徑的研究[J].湘潭礦業(yè)學(xué)院學(xué)報(bào)，2001，16(4)：9-12.