俞武揚

(1.杭州電子科技大學 管理學院，浙江 杭州 310018; 2.浙江省信息化與經(jīng)濟社會發(fā)展研究中心，浙江 杭州 310018)

?

基于情景分析的應急疏散車輛配置模型

俞武揚

(1.杭州電子科技大學 管理學院，浙江 杭州 310018; 2.浙江省信息化與經(jīng)濟社會發(fā)展研究中心，浙江 杭州 310018)

在情景模式影響疏散點疏散人員數(shù)量及疏散最晚完成時間限制的條件下，研究了避難所應急疏散車輛配置計劃及各種情景模式下的車輛出車任務安排，以疏散車輛出車安排為下層模型，以期望疏散總時間最小化車輛配置計劃為上層模型建立了車輛配置及出車任務安排的雙層規(guī)劃模型。設計了結合CPLEX內置算法的模擬退火算法，最后用算例進行了仿真研究。

情景分析；車輛配置；應急疏散；雙層規(guī)劃模型

0 引言

對于許多突發(fā)性災害事件，防止和減少人員傷亡的關鍵措施之一就是制定合理的應急疏散決策。早在20世紀60年代已經(jīng)有國外學者針對應急疏散決策的一般概念與研究框架進行了一定的探討[1]。此后隨著近年來突發(fā)事件的頻繁發(fā)生，眾多學者對應急疏散問題進行了多方面研究。從模型研究的角度看可大致分為微觀模型與宏觀模型兩大類，其中微觀模型著重于研究疏散個體的特性，通過模擬各種可能因素對疏散個體選擇疏散路徑的影響并對人員疏散過程中的一些動力學特征進行研究。如將行人視為相互作用的粒子考慮人員疏散影響的社會力模型[2]；通過構造一系列規(guī)則通過元胞之間簡單的相互作用來模擬應急疏散動態(tài)過程的元胞自動機模型[3]；考慮疏散個體在疏散過程中排斥作用的格子氣模型[4]等。微觀模型的優(yōu)點是針對疏散個體直接建模，表現(xiàn)疏散個體的思考能力和對環(huán)境刺激的響應能力，結合不同的因素能對疏散過程中出現(xiàn)的典型動力學現(xiàn)象進行模擬和分析。微觀模型的缺點是這類模型主要是針對疏散者個體的研究，當出現(xiàn)區(qū)域性突發(fā)事件需要應急疏散時，很難為決策部門組織應急疏散決策提供有效的參考。

宏觀模型一般是從區(qū)域疏散情況出發(fā)研究疏散方案，可以為決策部門提供有效的參考。宏觀模型方面，Campos等[5]基于圖論中的最短路算法，以最大化總通行能力與行駛時間比為目標建立了應急疏散路線決策模型，并在核電站事故背景下研究了疏散點與避難所的k條獨立疏散路線；Konyeomewkewkul等[6]在颶風或洪災情景模式下考慮避難所選址對待疏散人員應急疏散路線選擇以及總疏散時間的影響，建立了一個雙層規(guī)劃模型用于選擇避難所以及相應的疏散路線，設計了求解該模型的遺傳算法；Yamada[7]運用最小成本流模型對交通流疏散分配問題提出了最短路撤退計劃方案，該模型是以疏散者撤離至所選避難所的行程總和最小化為目標函數(shù)；Yi等[8]考慮了受傷人員應急疏散、應急物資調度以及醫(yī)院救治傷員速率等多種因素，建立了人員疏散與應急物資協(xié)同調度的網(wǎng)絡流優(yōu)化模型，并設計了求解該模型的兩階段蟻群優(yōu)化算法；張江華等[9]在容量限制情形條件下研究了存在優(yōu)先順序的多源點應急疏散問題，引入k最短路概念設計了網(wǎng)絡優(yōu)化啟發(fā)式算法以求解所建立的模型；宋瑞等[10]考慮利用公交車進行應急疏散情況下的公交車輛運行計劃優(yōu)化問題，以最小化疏散總時間為目標建立了不確定需求情況下的選址-路徑優(yōu)化模型，并設計了求解該模型的混合啟發(fā)式算法；霍良安等[11]以展會應急疏散問題為背景，研究了應急通道設置對應急疏散情況下路網(wǎng)用戶均衡影響的雙層規(guī)劃模型；馬浩博等[12]在考慮災害擴散的實時影響前提下，以最小化通過疏散路徑所需的總時間為目標建立了應急疏散路徑選擇優(yōu)化模型；王永明等[13]構建了非常規(guī)突發(fā)事件背景下具有時間限制的區(qū)域路網(wǎng)疏散能力評估與交通組織設計模型并且進行了仿真研究。

本文針對避難所車輛配置計劃問題進行研究，在考慮不同情景模式下所負責疏散點具有不同待疏散人員數(shù)量及疏散最晚完成時間限制情況下，合理配置車輛并針對各種情景模式安排每一車輛的疏散出車任務以使期望疏散總時間最小化。

1 數(shù)學模型

1.1 問題描述

在許多自然災害情況下需要將受威脅群眾進行疏散，設某個避難所負責所在地區(qū)的N個疏散點的群眾疏散任務，根據(jù)歷史資料統(tǒng)計該地區(qū)共有M種情景模式需要對群眾進行疏散，不同情景模式下各疏散點待疏散人員數(shù)量及最晚疏散完成時間限制有所不同，各種情景模式出現(xiàn)的概率可由統(tǒng)計數(shù)據(jù)給出。該避難所需要從H種不同車型中選擇配置一定數(shù)量的車輛以應對各種情景模式下的應急疏散任務，每一輛車根據(jù)其車型不同具有不同的平均速度、單位載人量以及配置所需單位成本，避難所可用于配置應急疏散車輛的總可用資金具有一定的限制。在給定避難所的車輛配置方案前提下，可以通過合理組織安排車輛的多車次疏散出車任務使得各種情景模式下所需疏散時間最短，為避免疏散時的組織混亂假設同一輛車只負責一個疏散點的應急疏散任務。在滿足現(xiàn)有的限制條件下，如何合理配置所需的車輛以及每一車輛在各種情景模式下的疏散出車任務使得疏散所需期望總時間最短？

建模之前根據(jù)問題背景作如下假設：a)各種情景模式下各疏散點待疏散人員數(shù)量及疏散最晚完成時間限制已知；b)各種情景模式出現(xiàn)的概率已知；c)避難所至各疏散點的距離已知；d)各種類型的運輸工具屬性已知(平均速度、單位載人量、配置所需單位成本)；e)可用于配置車輛的資金限額已知。

1.2 參數(shù)和變量設置

1)參數(shù)設置

2)變量設置

Xh：車型的車輛配置數(shù)量，h∈H；xkn：第k輛車至疏散點n的出車次數(shù)；ykn：當?shù)趉輛車負責疏散點n的疏散任務時則取值為1，否則取值為0。

1.3 建立模型

將所研究的問題分解成一個雙層規(guī)劃模型，上層模型以可用配置資金為限制，以所有情景模式的總期望為目標函數(shù)；下層模型在給定情景模式及車輛配置方案前提下安排車輛的疏散出車任務，具體模型如下：

上層模型：

(P1)

(1)

(2)

Xh≥0，且為整數(shù)

(3)

說明：目標函數(shù)(1)中T(ξi，X)為情景模式ξi下根據(jù)車輛配置方案X進行最優(yōu)車輛出車安排時所得最小疏散總時間，而E(x)即為給定所有情景模式時疏散總時間的期望值；約束條件(2)表示配置應急疏散車輛所需的總費用不超過可用資金總額；約束條件(3)表示車輛配置數(shù)應為非負整數(shù)。下層模型在給定情景模式以及車輛配置方案前提下求解每一車輛的疏散出車任務以最小化上層模型中的T(ξi，X)。

下層模型：

(4)

(5)

(6)

(P2)ykn≤xkn≤ykn·M，?k∈KX，?n∈N

(7)

(8)

(9)

xkn≥0且為整數(shù)，ykn∈{0，1}，?k∈KX，?n∈N

(10)

說明：約束條件(5)表示每輛車最多只安排一個負責服務的疏散點；約束條件(6)表示每一個疏散點至少有一輛車負責該點的疏散任務；約束條件(7)建立了0-1變量ykn與非負整數(shù)變量xkn之間的內在關系，其中M為充分大的正數(shù)；約束條件(8)表示每個疏散點所到達車輛總載人次不低于疏散點待疏散人數(shù)；約束條件(9)表示各疏散點所有到達的車輛完成疏散任務的最大時間不超過該疏散點的疏散時間限制；約束條件(10)表示變量的約束。(P2)為整數(shù)線性規(guī)劃模型，利用CPLEX軟件的內置算法可對下層模型(P2)進行有效的計算。

2 模型求解

求解雙層模型時，下層模型是整數(shù)線性規(guī)劃問題可利用CPLEX12.4內置算法進行求解，而由于上層問題中T(ξi，X)對于X是非線性的，從而上層模型實際上是一個非線性整數(shù)規(guī)劃模型，一般的優(yōu)化算法很難求解，由于智能優(yōu)化方法具有很強的全局搜索能力，因此在對該模型求解時，應用智能算法可以得到相對滿意的解。本文利用模擬退火算法求解上層模型，算法流程如下：

算法流程：

Step 1 設置初始值，令Ts:=100，r:=0.9，Tend:=1；生成初始可行解：令Hset:=H，任取h∈Hset，令Xh為[0,Xup]之間的任意整數(shù)，其中Xup:=?C/ch」，這里?x」表示不超過x的整數(shù)，更新Hset:=Hseth，C:=C-ch·Xh，重復這一過程，直到Hset=?；

Step 5 更新Ts:=Ts·r，若Ts>Tend則轉Step3，否則停止，輸出最優(yōu)目標函數(shù)值為bestEX，最優(yōu)車輛配置方案為bestX。

說明：Step4中采用了Metropolis準則的鄰域移動方法，若新解的目標函數(shù)值小于當前解的目標函數(shù)值，則進行無條件移動，否則依據(jù)一定的概率進行有條件移動，其中U(0,1)表示區(qū)間[0,1]上的均勻分布。

3 數(shù)值例子

算例．設某避難所需要配置應急疏散車輛以應對各種情景模式下所負責的N=6個疏散點人員的疏散任務，各疏散點到避難所的距離為dn={60,48,37,55,84,18}(單位：km)；已知現(xiàn)有車輛類型H=4種，各車型的單位載客量w(h)(單位：人/輛)、平均速度v(h)(單位：km/小時)以及配置所需的費用c(h)(單位：萬元)見表1。

表1 各車型車輛屬性表

表2 疏散點情景模式數(shù)據(jù)表

利用上述算法結合MatlabR 2010b編程，求解下層模型(P3)時調用CPLEX 12.4內置算法，對上述算例進行了10次計算，結果如下表3所示：

表3 算例10次求解結果示意表

從表3可知，10次計算所得最優(yōu)目標函數(shù)值為1510.1分鐘，平均目標函數(shù)值為1516.8分鐘；最優(yōu)解為X=[0,0,4,7]，總配置費用為490萬元。在車輛最優(yōu)配置方案下，各種情景模式的出車安排xkn見表4。

表4 最優(yōu)配置方案下各種情景模式出車安排表

說明：表4中括號內5個數(shù)字分別代表5種情景模式下，每一車輛對各疏散點的出車次數(shù)，如k=2行、N3列處(0,2,1,0,0)表示第2輛車在ξ2情景模式下對N3進行2次疏散出車任務，在ξ3情景模式下對N3進行1次疏散出車任務，而在其它情景模式下對N3無疏散出車任務。

4 小結

本文研究基于應急疏散情景模式的避難所應急疏散車輛配置問題，假設各疏散點待疏散人員以及最晚疏散完成時間限制由情景模式?jīng)Q定，在考慮各種情景模式前提下，尋求最優(yōu)的車輛配置方案以使得總的期望疏散時間最小化。模型的假設具有較強的現(xiàn)實意義，可為涉及類似的應急決策問題時為決策者提供一定的借鑒作用。通過建立雙層模型將車輛配置問題分解成兩個子問題，上層模型給定可行的車輛配置方案，下層模型根據(jù)所給定的車輛配置方案就各種情景模式安排最優(yōu)疏散出車任務以最小化疏散總時間，下層模型的目標函數(shù)值作為參數(shù)反饋至上層模型。模型的建立過程考慮了求解的因素，通過變形與約束條件增維降低了模型求解的難度，設計了一種結合CPLEX內置算法的模擬退火算法以求解該雙層規(guī)劃模型，最后以一個算例說明了模型與算法的有效性。

[1] Green L V, Kolesar P J. Improving emergency responsiveness with management science[J]. Management Science, 2004, 50(8): 1001-1014.

[2] Helbing D, Molnar P. Social force model for pedestrian dynamics[J]. Phys. Rev. E, 1995, 51(5): 4282- 4286.

[3] Kirchner A, Schadschneider A. Simulation of evacuation processes using a bionics inspired cellular automaton model for pedestrian dynamics[J]. Phys. A, 2002, 312: 260-276.

[4] Muramatsu M, Nagatani T. Jamming transition of pedestrian traffic at a crossing with open boundaries[J]. Phys. A, 2000, 286: 377-390.

[5] Campos V B G, Silva P A L, Netto P O B. Evacuation transportation planning: a method of identifying optimal independent routes. Surcharov L J. Proceedings of Urban Transport V: Ryan Transport and the Environment for the 21st Century[C]. Southampton: WIT Press, 2000: 555-564.

[6] Kongsomsaksakul S, Yang C, Chen A. Shelter location-allocation model for flood evacuation planning[J]. Journal of the eastern Asia Society for Transportation Studies, 2005, 6: 4237- 4252.

[7] Yamada T. A network of approach to a city emergency evacuation planning[J]. International Journal of Systems Science, 1996, 27(10): 931-936.

[8] Yi W, Kumar A. Ant colony optimization for disaster relief operations[J]. Transportation Research Part E. 2007, 43: 660- 672.

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

[10] 宋瑞，何世偉，章力.緊急疏散情況下的公交車運行計劃優(yōu)化研究[J].交通運輸系統(tǒng)工程與信息，2009,9(6):154-160.

[11] 霍良安，黃培清，程云龍.基于疏散效率的展會應急優(yōu)化問題研究[J].工業(yè)工程與管理，2011，16(4)：108-112.

[12] 馬浩博，季建華，何冰.大規(guī)模人流多出口應急疏散預案的優(yōu)化與研究[J].系統(tǒng)管理學報,2011,20(2):238-243.

[13] 王永明，周磊山，劉鐵民.非常規(guī)突發(fā)事件中的區(qū)域路網(wǎng)疏散能力評估與交通組織方案設計[J]. 系統(tǒng)工程理論與實踐，2011，31(8):1608-1616.

Emergency Vehicle Disposition Model Based on Scenario Analysis

YU Wu-yang

(1.SchoolofManagement,HangzhouDianziUniversity,Hangzhou310018,China; 2.TheResearchCenterofInformationTechnology&EconomicandSocialDevelopment,Hangzhou310018,China)

This paper is concerned with the emergency vehicle disposition problem and the scheduling problem for emergency evacuation in different scenario, which influence the evacuees quantity and the time limitation of evacuation. A bi-level programming model is established in which scheduling problem for emergency evacuation as a lower-level model and minimizes the total expectation of evacuation time as a up-level model. A simulated annealing algorithm embedded with the CPLEX algorithm is presented and a numerical example is given.

scenario analysis; vehicle disposition; emergency evacuation; bi-level programming model

2012- 06-10

教育部人文社會科學青年基金資助項目(10YJC630360)；杭州電子科技大學“管理科學與工程”省高校人文社科重點研究基地(ZD01-201403)

俞武揚(1974-)，男，博士，副教授，研究方向：物流建模與優(yōu)化計算。

F016

A

1007-3221(2015)02- 0135- 05