基于分支定界算法的應(yīng)急疏散選址方法

馬國(guó)普，徐俊韜

（陸軍勤務(wù)學(xué)院，重慶 401311）

0 引言

中國(guó)幅員遼闊，是重大突發(fā)事件發(fā)生最頻繁的國(guó)家之一。國(guó)家就重大突發(fā)事件建立的應(yīng)急保障機(jī)制與所需的保障力相比仍有差距。突發(fā)事件造成的破壞和損失巨大，事件中的人員轉(zhuǎn)移和安置一直是非常重要的問(wèn)題。

目前，重大突發(fā)事件應(yīng)急疏散研究較少把后方安置點(diǎn)與前線(xiàn)救援點(diǎn)聯(lián)系起來(lái)考慮人員轉(zhuǎn)移和物資運(yùn)輸。人員轉(zhuǎn)移是從事件發(fā)生點(diǎn)先轉(zhuǎn)移到前線(xiàn)救援點(diǎn)，再轉(zhuǎn)到安置點(diǎn)，而物資運(yùn)輸是從安置點(diǎn)運(yùn)輸?shù)骄仍c(diǎn)，再?gòu)木仍c(diǎn)運(yùn)輸?shù)绞录l(fā)生點(diǎn)。如果救援需求沒(méi)有得到滿(mǎn)足，會(huì)造成重大損失，但如果物資供應(yīng)遠(yuǎn)遠(yuǎn)大于需求，同樣也是一種經(jīng)濟(jì)損失。事件初期并不能完全把握住需求，只能通過(guò)場(chǎng)景加概率，大致推算出預(yù)期需求，由地區(qū)政府提供預(yù)算資金。本文的目標(biāo)是在預(yù)算范圍之內(nèi)最小化未被轉(zhuǎn)移的人數(shù)，同時(shí)盡可能滿(mǎn)足救援物資的需求。

1 突發(fā)事件人員疏散模型

1.1 突發(fā)事件中人員轉(zhuǎn)移分析

在重大突發(fā)事件中，洪水是一類(lèi)典型災(zāi)害，下文以洪災(zāi)為例進(jìn)行問(wèn)題分析。洪災(zāi)中受災(zāi)點(diǎn)區(qū)域的大多道路被水淹沒(méi)，陸地交通工具不能直接進(jìn)入，所以要在事件發(fā)生點(diǎn)附近設(shè)置救援點(diǎn)，在這里轉(zhuǎn)換成水路交通工具進(jìn)行物資和人員的輸送，依此提出“受災(zāi)點(diǎn)-救援點(diǎn)-安置點(diǎn)”概念模型。在確定場(chǎng)景的情況下，每個(gè)事件發(fā)生點(diǎn)的物資需求量、受災(zāi)人數(shù)和傷病人員數(shù)量可以估算，并且安置點(diǎn)的人口容量也是確定的，預(yù)置安置點(diǎn)的預(yù)置成本也可以估算。在轉(zhuǎn)移過(guò)程中，不僅要考慮這些，還要考慮運(yùn)輸過(guò)程中安置點(diǎn)到救援點(diǎn)運(yùn)輸工具的容量，及救援點(diǎn)到受災(zāi)點(diǎn)的運(yùn)輸工具容量等。在實(shí)際情況中，由于很多未知條件的限制，對(duì)災(zāi)區(qū)需求和受災(zāi)人員數(shù)量的評(píng)估有一定的誤差，在此就需要使用情景與概率結(jié)合的分析方式減小誤差，得出不確定需求情況下的分析方案。

1.2 最佳安置點(diǎn)的確定

臨時(shí)安置點(diǎn)的選擇需要考慮安置點(diǎn)容量、轉(zhuǎn)移到安置點(diǎn)的距離、安置點(diǎn)的成本等影響因素。

1.2.1 影響因子

影響人員轉(zhuǎn)移過(guò)程中臨時(shí)安置點(diǎn)的確定因素很多，主要有總預(yù)算、運(yùn)輸工具的有效運(yùn)量、運(yùn)輸工具單位時(shí)間成本、救援品費(fèi)用，安置點(diǎn)選址費(fèi)用、運(yùn)輸工具總量、運(yùn)輸工具工作時(shí)長(zhǎng)、安置點(diǎn)到救援點(diǎn)的距離、救援點(diǎn)到受災(zāi)點(diǎn)的距離、安置區(qū)的容量等因素。

1.2.2 場(chǎng)景的設(shè)置

根據(jù)以往洪災(zāi)統(tǒng)計(jì)數(shù)據(jù)情況，先綜合根據(jù)各個(gè)受災(zāi)點(diǎn)的受災(zāi)情況、人口、道路環(huán)境、地理位置等因素生成一種需求場(chǎng)景1。讓每個(gè)受災(zāi)點(diǎn)的需求與位于［1.0，1.5］的一個(gè)隨機(jī)數(shù)相乘，這樣可以得到一種災(zāi)情偏重的場(chǎng)景2。再將隨機(jī)數(shù)的生成區(qū)間改成［0.5，1.0］，將場(chǎng)景1 的需求乘以隨機(jī)數(shù)，得到一種災(zāi)情偏輕的場(chǎng)景3。將各場(chǎng)景概率依次設(shè)置為0.4，0.3，0.3。

1.3 應(yīng)急疏散優(yōu)化模型

1.3.1 模型相關(guān)假設(shè)

抗洪搶險(xiǎn)中人員疏散作如下假設(shè)：

1）假設(shè)運(yùn)輸工具為勻速；2）不考慮人員在運(yùn)輸中的傷亡；3）運(yùn)輸工具為災(zāi)前配置，不計(jì)入預(yù)算；4）在人員運(yùn)輸方面僅只考慮數(shù)量因素；5）運(yùn)輸過(guò)程中道路看成通暢狀態(tài)；6）不考慮運(yùn)輸救援人員的問(wèn)題；7）設(shè)定人員在兩段路程的運(yùn)輸中是相等的，沒(méi)有在救援點(diǎn)不轉(zhuǎn)移的人。物資運(yùn)輸也采用同類(lèi)假設(shè)。

1.3.2 模型參數(shù)說(shuō)明

模型構(gòu)建所使用的參數(shù)較多，這里統(tǒng)一進(jìn)行參數(shù)符號(hào)說(shuō)明。

1）基本參數(shù)

I：臨時(shí)安置點(diǎn)集合，i∈I；J：受災(zāi)點(diǎn)集合，j∈J；K：災(zāi)區(qū)所需救援品集合，k∈K；F：救援點(diǎn)集合，f∈F；M：安置點(diǎn)運(yùn)輸工具類(lèi)型集合，m∈M；M：救援點(diǎn)運(yùn)輸工具類(lèi)型集合，m∈M；ξ：災(zāi)情情景集合，δ∈ξ。

2）與情景不直接相關(guān)的參數(shù)

B：總預(yù)算費(fèi)用（元）；W：臨時(shí)安置點(diǎn)i 的容量（人）；Q：?jiǎn)闻_(tái)m 型運(yùn)輸工具的有效運(yùn)量（kg 或人）；C：?jiǎn)闻_(tái)m 型運(yùn)輸工具運(yùn)行單位時(shí)間所需成本（元）；e：安置點(diǎn)選址費(fèi)用（元）；S：救援品在安置點(diǎn)i 的總量（kg）；C：采辦救援品的單位費(fèi)用（元）；T：m 型運(yùn)輸工具有效時(shí)長(zhǎng)（h）；V：i 點(diǎn)m 型運(yùn)輸工具總量（臺(tái)）；V：f 點(diǎn)m 型運(yùn)輸工具總量（臺(tái)）；V：m 型運(yùn)輸工具的速度（km/h）；L：安置點(diǎn)i 到救援點(diǎn)f 的距離（km）；L：救援點(diǎn)f 到受災(zāi)點(diǎn)j 的距離（km）；x：1表示選定臨時(shí)安置點(diǎn)，0 表示不選。

3）與情景直接相關(guān)參數(shù)

k：受災(zāi)點(diǎn)j 的物資需求量（kg）；K：用m 型運(yùn)輸工具運(yùn)輸?shù)绞転?zāi)點(diǎn)j 的物資量（kg）；d：受災(zāi)點(diǎn)j的受災(zāi)人員數(shù)量（人）；D：用m 型運(yùn)輸工具轉(zhuǎn)移到受災(zāi)點(diǎn)j 的受災(zāi)人員數(shù)量（人）；t：m 型運(yùn)輸工具從救援點(diǎn)f 到受災(zāi)點(diǎn)j 的時(shí)間（h）；t：m 型運(yùn)輸工具從安置點(diǎn)i 到救援點(diǎn)f 的時(shí)間（h）；V：m 型運(yùn)輸工具從救援點(diǎn)f 到受災(zāi)點(diǎn)j 的運(yùn)輸次數(shù)（次）；V：m型運(yùn)輸工具從安置點(diǎn)i 到救援點(diǎn)f 的運(yùn)輸次數(shù)（次）；U：m 型運(yùn)輸工具從受災(zāi)點(diǎn)j 到救援點(diǎn)f 的運(yùn)輸次數(shù)（次）；U：m 型運(yùn)輸工具從救援點(diǎn)f 到安置點(diǎn)i 的運(yùn)輸次數(shù)（次）；q：未滿(mǎn)足物資需求的懲罰因子（人/kg）；A：在受災(zāi)點(diǎn)j 未能轉(zhuǎn)移的受災(zāi)人員數(shù)量（人）；G：受災(zāi)點(diǎn)j 未能滿(mǎn)足的物資需求量（kg）；P：情景概率，P∈P。

1.3.3 優(yōu)化模型構(gòu)建

Aruna Apte 的數(shù)學(xué)模型在各種抗災(zāi)救援運(yùn)輸建模中被廣泛應(yīng)用。但是，經(jīng)典模型中沒(méi)有考慮“受災(zāi)點(diǎn)-救援點(diǎn)-安置點(diǎn)”3 點(diǎn)協(xié)同運(yùn)輸方式，并且也沒(méi)有考慮救援物資的運(yùn)輸情況。針對(duì)以上問(wèn)題，本文作了如下改進(jìn)。

本文模型是在研究受災(zāi)人員疏散方式的基礎(chǔ)上得出最佳臨時(shí)安置點(diǎn)的選址，即從預(yù)定臨時(shí)安置點(diǎn)方案中選中最佳安置點(diǎn)。所以模型自變量為取值0～1 的變量x。運(yùn)輸工具的運(yùn)輸次數(shù)、運(yùn)輸距離、運(yùn)輸時(shí)間、運(yùn)輸?shù)娜藛T和物資為因變量。

基于上述問(wèn)題描述，本文所建立的模型如下：

式（1）為系統(tǒng)目標(biāo)，即最小化未轉(zhuǎn)移的受災(zāi)人員和未滿(mǎn)足的受災(zāi)點(diǎn)物資需求，可以看出式（1）是一個(gè)雙目標(biāo)問(wèn)題。因?yàn)榫仍镔Y不充足會(huì)導(dǎo)致救援不力，所以假設(shè)在受災(zāi)情況下，救援物資運(yùn)輸和受災(zāi)人員轉(zhuǎn)移具有同樣重要的意義，這里引入懲罰因子q（人/kg），將救災(zāi)物資與受災(zāi)人員轉(zhuǎn)化為同一目標(biāo)類(lèi)型。

式（2）表示約束總成本要在預(yù)算之內(nèi)，總成本包括運(yùn)輸人員與物資的運(yùn)輸成本、救援物資的采購(gòu)成本、安置點(diǎn)的建設(shè)成本等。

式（3）和式（4）分別表示已滿(mǎn)足的物資需求加上未滿(mǎn)足的物資需求等于受災(zāi)點(diǎn)總需求，已轉(zhuǎn)移的受災(zāi)人數(shù)加上未轉(zhuǎn)移的受災(zāi)人數(shù)等于受災(zāi)點(diǎn)受災(zāi)總?cè)藬?shù)。

式（5）表示運(yùn)輸工具單次物資容量乘上運(yùn)輸次數(shù)等于已滿(mǎn)足物資需求量。

式（6）表示運(yùn)輸工具單次人員容量乘上運(yùn)輸次數(shù)等于已轉(zhuǎn)移的受災(zāi)人員數(shù)。

式（7）表示受災(zāi)點(diǎn)轉(zhuǎn)移到救援點(diǎn)的人員等于救援點(diǎn)運(yùn)輸?shù)桨仓命c(diǎn)的人員。

式（8）表示轉(zhuǎn)移到安置點(diǎn)i 的人員數(shù)不能超過(guò)安置點(diǎn)i 的人員容量，式（9）表示從安置點(diǎn)i 運(yùn)輸出去的救援物資不能大于安置點(diǎn)i 的救援物資的總量。

式（10）表示通過(guò)安置點(diǎn)、救援點(diǎn)、受災(zāi)點(diǎn)間的距離和運(yùn)輸工具行駛速度得出單次運(yùn)輸時(shí)間。

式（11）表示承擔(dān)運(yùn)輸任務(wù)的運(yùn)輸工具的工作時(shí)長(zhǎng)不能超過(guò)運(yùn)輸工具的有效時(shí)長(zhǎng)。

式（12）～式（15）是變量約束。

2 疏散模型算法設(shè)計(jì)

2.1 場(chǎng)景分解和最優(yōu)值下界的確定

考慮到模型P1 中決策變量x與情景無(wú)關(guān)，且x為取值0～1 的變量，則將x分別轉(zhuǎn)化為x，并加上相關(guān)非期望約束。即，用x來(lái)替換P1 中的x，定義非期望約束如下：

將式（16）代入到P1，獲得模型P2。

假設(shè)1 模型P1 和模型P2 等價(jià)。

證畢。

從模型P2 的結(jié)構(gòu)來(lái)看，除期望約束外，可以把其他的約束條件及目標(biāo)函數(shù)按場(chǎng)景分解。因此，考慮松弛這個(gè)約束，并基于拉格朗日松弛把它加入到目標(biāo)函數(shù)，得到模型P3。

假設(shè)2 式（18）的最優(yōu)目標(biāo)值是問(wèn)題P2 最優(yōu)目標(biāo)值的下界。

證明根據(jù)弱對(duì)偶理論可得到上述結(jié)論，其證明過(guò)程可參見(jiàn)文獻(xiàn)［6］。

通過(guò)上面的迭代方式可以把拉格朗日對(duì)偶問(wèn)題按情境分解為多個(gè)獨(dú)立的子問(wèn)題求解。

2.2 拉格朗日對(duì)偶問(wèn)題的分支定界算法流程

圖1 算法流程圖

3 實(shí)例研究

3.1 方案設(shè)計(jì)

設(shè)計(jì)一個(gè)簡(jiǎn)單的模擬場(chǎng)景來(lái)驗(yàn)證本文提出模型的有效性。數(shù)值計(jì)算是基于計(jì)算機(jī)軟件進(jìn)行，并通過(guò)C++來(lái)實(shí)現(xiàn)模型的分解和算法流程控制。

在模擬場(chǎng)景中，共有受災(zāi)點(diǎn)3 處，受災(zāi)點(diǎn)被洪水包圍，在水域邊緣設(shè)置救援點(diǎn)2 個(gè)，救援點(diǎn)里的救援人員會(huì)前往受災(zāi)點(diǎn)，將受災(zāi)人員通過(guò)水路運(yùn)輸工具運(yùn)輸?shù)骄仍c(diǎn)。為使救援效率最大化，安置點(diǎn)的陸地運(yùn)輸工具之前會(huì)將救援物資運(yùn)輸?shù)骄仍c(diǎn)，再將受災(zāi)人員轉(zhuǎn)移回安置點(diǎn)。在安全地區(qū)設(shè)置安置點(diǎn)3 個(gè)。由于洪水的可預(yù)測(cè)性和不可避免性，在洪水爆發(fā)前，在安置點(diǎn)準(zhǔn)備救援物資，采購(gòu)救援物資的成本計(jì)算在預(yù)算范圍之內(nèi)。在一張洪水淹沒(méi)范圍圖的基礎(chǔ)上，設(shè)計(jì)了簡(jiǎn)化的固定設(shè)施布局圖，如圖2所示。

圖2 固定設(shè)施布局示意圖

其中，受災(zāi)點(diǎn)（圓圈標(biāo)記）根據(jù)洪水災(zāi)情淹沒(méi)范圍情況確定，共計(jì)3 個(gè)。救援點(diǎn)（三角形標(biāo)記）根據(jù)受災(zāi)點(diǎn)的分布和交通運(yùn)輸條件等因素選取，共計(jì)2個(gè)。安置點(diǎn)（四邊形標(biāo)記）根據(jù)人口容量，安全范圍等條件進(jìn)行選取，共計(jì)3 個(gè)。

3.2 參數(shù)設(shè)置情況

受災(zāi)點(diǎn)的情況，如下頁(yè)表1 所示。

表1 受災(zāi)點(diǎn)情況

安置點(diǎn)的情況，如表2 所示。

表2 安置點(diǎn)的基本情況

安置點(diǎn)運(yùn)輸工具情況，如表3 所示。

表3 安置點(diǎn)運(yùn)輸工具基本情況

救援點(diǎn)運(yùn)輸工具情況，如表4 所示。

表4 救援點(diǎn)運(yùn)輸工具基本情況

表5 和表6 分別為受災(zāi)點(diǎn)與救援點(diǎn)的距離和救援點(diǎn)與安置點(diǎn)的距離。

表5 受災(zāi)點(diǎn)與救援點(diǎn)的距離

表6 救援點(diǎn)與安置點(diǎn)的距離

最后未滿(mǎn)足物資需求的懲罰因子設(shè)定為0.3。將預(yù)算設(shè)置為10 萬(wàn)元、20 萬(wàn)元、30 萬(wàn)元和40 萬(wàn)元4種情況。

3.3 結(jié)果分析

如表7 所示，在經(jīng)費(fèi)較低時(shí)，受固定設(shè)施成本影響，系統(tǒng)傾向于選擇少量固定設(shè)施。隨著預(yù)算的增加，安置點(diǎn)的人口容量限制了目標(biāo)最小值，被選中的安置點(diǎn)量也增加。此外，先期被選中的安置點(diǎn)在經(jīng)費(fèi)增加的過(guò)程中一定會(huì)選中，這種現(xiàn)象也為應(yīng)急選址決策帶來(lái)啟發(fā)。

表7 不同經(jīng)費(fèi)情況下的選址結(jié)果

表8 表示不同經(jīng)費(fèi)預(yù)算情況下，各種運(yùn)輸工具的運(yùn)輸次數(shù)和最小目標(biāo)值。在自然災(zāi)害發(fā)生時(shí)，優(yōu)先采用運(yùn)輸效率（單次運(yùn)量/單次運(yùn)輸成本）大的運(yùn)輸工具。當(dāng)最佳運(yùn)輸工具使用飽和后，會(huì)選擇次優(yōu)運(yùn)輸工具。就此例而言，所需的預(yù)算費(fèi)用為30萬(wàn)元。

預(yù)算/萬(wàn)元目標(biāo)值/人1041115504 060 1552942321282 800 25522742324881 000 3052354232649200 3552354232649200大卡車(chē)/次越野車(chē)/次沖鋒舟/次氣墊船/次

在現(xiàn)實(shí)情況中，可以通過(guò)這種方式得到一個(gè)大致的預(yù)算情況，并且通過(guò)計(jì)算運(yùn)輸工具效率，選擇效率最高的運(yùn)輸工具。本文所建模型，能夠幫助發(fā)現(xiàn)應(yīng)急救援時(shí)的薄弱環(huán)節(jié)，如預(yù)算、運(yùn)輸工具效率、固定設(shè)施數(shù)量和容量等。

4 結(jié)論

本文針對(duì)重大突發(fā)事件情況，提出了“發(fā)生點(diǎn)-救援點(diǎn)-安置點(diǎn)”人員轉(zhuǎn)移模型，并研究了基于多種場(chǎng)景情況下的轉(zhuǎn)移模型分析算法。但研究過(guò)程中進(jìn)行了一些簡(jiǎn)化假設(shè)，比如運(yùn)輸過(guò)程僅僅是以最短距離進(jìn)行計(jì)算，沒(méi)有考慮道路堵塞等情況。在人員疏散中，沒(méi)有考慮人員的心理因素對(duì)人群行為造成的影響。后面的研究會(huì)考慮將這些簡(jiǎn)化因素一一加入到理論模型中，尋找突發(fā)事件中人員疏散的最優(yōu)決策方法。