基于最小最大后悔值的應(yīng)急救災(zāi)網(wǎng)絡(luò)構(gòu)建魯棒優(yōu)化模型與算法

張 玲，陳 濤，黃 鈞

（1.惠州學(xué)院經(jīng)濟(jì)管理系，廣東惠州516007；2.中國(guó)科學(xué)院大學(xué)數(shù)學(xué)科學(xué)學(xué)院，北京100049）

基于最小最大后悔值的應(yīng)急救災(zāi)網(wǎng)絡(luò)構(gòu)建魯棒優(yōu)化模型與算法

張 玲1，陳 濤2，黃 鈞2

（1.惠州學(xué)院經(jīng)濟(jì)管理系，廣東惠州516007；2.中國(guó)科學(xué)院大學(xué)數(shù)學(xué)科學(xué)學(xué)院，北京100049）

應(yīng)急救災(zāi)過(guò)程分為兩個(gè)階段：第一階段啟動(dòng)應(yīng)急救災(zāi)網(wǎng)絡(luò)構(gòu)建，在災(zāi)區(qū)附近設(shè)立臨時(shí)應(yīng)急配送中心，并由應(yīng)急資源供應(yīng)方向其緊急調(diào)配應(yīng)急資源；第二階段將應(yīng)急資源從臨時(shí)應(yīng)急配送中心向?yàn)?zāi)區(qū)受災(zāi)點(diǎn)進(jìn)行調(diào)度，以保證救災(zāi)過(guò)程順利進(jìn)行。本文研究第一階段應(yīng)急救災(zāi)網(wǎng)絡(luò)的構(gòu)建問(wèn)題，考慮到突發(fā)災(zāi)害初期災(zāi)情相關(guān)參數(shù)概率分布情況難以獲取，建立了基于情景的最小最大后悔值準(zhǔn)則的應(yīng)急救災(zāi)網(wǎng)絡(luò)構(gòu)建魯棒優(yōu)化模型。求解模型時(shí)，利用有限情景集表示第二階段的不確定性數(shù)據(jù)，并將模型化為與其等價(jià)的混合整數(shù)規(guī)劃模型，利用情景松弛的迭代算法進(jìn)行求解。數(shù)值試驗(yàn)中給出相應(yīng)的絕對(duì)魯棒模型與本文偏差魯棒模型作了比較，結(jié)果表明基于最小最大后悔值準(zhǔn)則的應(yīng)急救災(zāi)網(wǎng)絡(luò)優(yōu)化模型具有良好的魯棒性，而且算法也是有效的。

應(yīng)急救災(zāi)網(wǎng)絡(luò)；不確定條件；兩階段規(guī)劃；最小最大后悔準(zhǔn)則；魯棒優(yōu)化；情景松弛

1 引言

近年來(lái)，頻繁發(fā)生的自然災(zāi)害，對(duì)人類造成了深遠(yuǎn)的影響。特別是雪災(zāi)、地震、臺(tái)風(fēng)等自然災(zāi)害，由于其突發(fā)性強(qiáng)，破壞力大，易造成人員傷亡等特點(diǎn)，造成的損失更是不計(jì)其數(shù)。2012年發(fā)生在歐洲，美洲，亞洲等多地的雪災(zāi)，極大影響了人們的正常生活，造成的經(jīng)濟(jì)損失難以估量；2008年發(fā)生在我國(guó)的5.12汶川大地震，奪去了近七萬(wàn)人的生命，直接經(jīng)濟(jì)損失超過(guò)1萬(wàn)億元［1］；2005年8月底登陸美國(guó)東海岸的颶風(fēng)“卡特里娜”，致使近兩千人死亡，經(jīng)濟(jì)損失高達(dá)812億美元，被認(rèn)為是美國(guó)歷史上損失最大的自然災(zāi)害之一。自然災(zāi)害發(fā)生后，有效應(yīng)對(duì)的方法是立即啟動(dòng)應(yīng)急響應(yīng)預(yù)案，構(gòu)建應(yīng)急救災(zāi)網(wǎng)絡(luò)，將應(yīng)急資源快速運(yùn)送到災(zāi)區(qū)，以提高應(yīng)急物資的調(diào)度效率和效果，降低災(zāi)害帶來(lái)的影響和損失。

目前，災(zāi)后的應(yīng)急物流活動(dòng)的研究集中在應(yīng)急資源的調(diào)度問(wèn)題。Fiedrich等［2］人利用受傷人數(shù)隨時(shí)間變化的生存函數(shù)，建立動(dòng)態(tài)規(guī)劃模型，解決地震災(zāi)害發(fā)生后的應(yīng)急資源的調(diào)度問(wèn)題；劉春林等［3］討論物資需求約束條件下多出救點(diǎn)的緊急物資調(diào)度問(wèn)題。Ozdamar等［4］人通過(guò)建立多物資，多模式網(wǎng)絡(luò)流模型，解決災(zāi)后的應(yīng)急物流和人員的疏散問(wèn)題；曾敏剛等［5］從LRP的角度研究災(zāi)后應(yīng)急物流系統(tǒng)的構(gòu)建過(guò)程。李進(jìn)等［6］人針對(duì)災(zāi)害鏈中多資源應(yīng)急調(diào)度問(wèn)題，建立了多資源多受災(zāi)點(diǎn)應(yīng)急調(diào)度模型，設(shè)計(jì)了基于圖論中網(wǎng)絡(luò)優(yōu)化和線性規(guī)劃優(yōu)化思想的啟發(fā)式算法求解。這些研究的共同點(diǎn)是將應(yīng)急資源的調(diào)度過(guò)程考慮為多階段決策過(guò)程，這在實(shí)際應(yīng)急資源調(diào)度過(guò)程中是合理的。本文考慮的應(yīng)急響應(yīng)階段的準(zhǔn)備工作，即應(yīng)急救災(zāi)網(wǎng)絡(luò)構(gòu)建問(wèn)題，涉及的臨時(shí)配送中心選擇與應(yīng)急資源的配置過(guò)程，與應(yīng)急資源調(diào)度過(guò)程有著本質(zhì)的區(qū)別。

兩階段模型早期的決策方法是利用隨機(jī)規(guī)劃模型，即假設(shè)不確定參數(shù)服從某種隨機(jī)分布［7-8］。Chang［9］針對(duì)所有洪水情景，建立應(yīng)急選址和配送的兩階段隨機(jī)規(guī)劃模型；Salmeron和Apte［10］利用兩階段隨機(jī)規(guī)劃模型計(jì)算獲取應(yīng)急救災(zāi)資產(chǎn)預(yù)算的配置計(jì)劃；黃鈞等［11］研究了災(zāi)害準(zhǔn)備和反應(yīng)決策，建立了災(zāi)前應(yīng)急物資儲(chǔ)備庫(kù)的選址和應(yīng)急物資配置的兩階段隨機(jī)規(guī)劃模型，并利用基于情景松弛的算法求解該模型。可以看出，以上應(yīng)急決策的兩階模型主要用于災(zāi)前應(yīng)急資源布局問(wèn)題的研究，并且以隨機(jī)變量的分布已知為前提。本文借鑒兩階段模型的思想，在應(yīng)急響應(yīng)決策的研究中，由于災(zāi)害初期詳細(xì)的受災(zāi)情況不能夠準(zhǔn)確獲得，在短時(shí)間內(nèi)災(zāi)區(qū)的需求、應(yīng)急物資的運(yùn)輸時(shí)間等分布未知，但在此時(shí)又必須構(gòu)建應(yīng)急救災(zāi)網(wǎng)絡(luò)，為接下來(lái)的應(yīng)急資源調(diào)度配送做準(zhǔn)備。因此，將災(zāi)害發(fā)生的應(yīng)急處置階段分為兩個(gè)階段，第一階段構(gòu)建應(yīng)急救災(zāi)網(wǎng)絡(luò)，迅速在災(zāi)區(qū)附近選擇集送條件較好的地點(diǎn)設(shè)立臨時(shí)應(yīng)急配送中心，并根據(jù)初步獲取的災(zāi)情不確定信息，決策有關(guān)應(yīng)急供應(yīng)方立刻向臨時(shí)應(yīng)急配送中心調(diào)配相應(yīng)的應(yīng)急物資；而將向受災(zāi)點(diǎn)的資源配送調(diào)度作為應(yīng)急救災(zāi)的第二階段，并以此輔助第一階段的決策，以有效提高應(yīng)急資源救災(zāi)的效率。

災(zāi)害發(fā)生后，不確定信息的概率分布難以在短時(shí)間內(nèi)獲得，利用隨機(jī)規(guī)劃方法不能很好的解決應(yīng)急決策的實(shí)際問(wèn)題。由于＂情景-應(yīng)對(duì)＂模式比傳統(tǒng)的＂預(yù)測(cè)-應(yīng)對(duì)＂模式更適應(yīng)應(yīng)急決策科學(xué)性要求，這對(duì)應(yīng)急救援兩階段規(guī)劃決策提出新的研究問(wèn)題。近些年發(fā)展起來(lái)的魯棒優(yōu)化方法，是解決不確定性問(wèn)題的有效方法，其理論在近年來(lái)得到了深入研究［12-17］，已經(jīng)應(yīng)用于制定管理決策的各個(gè)領(lǐng)域［18-19］。魯棒優(yōu)化分為絕對(duì)魯棒優(yōu)化、相對(duì)魯棒優(yōu)化與偏差魯棒優(yōu)化等。Kouvelis等人［20］對(duì)魯棒優(yōu)化方法及相關(guān)應(yīng)用進(jìn)行了系統(tǒng)的總結(jié)。利用魯棒優(yōu)化研究應(yīng)急決策問(wèn)題的研究還比較少，如Ali等人［8］建立了不確定條件下災(zāi)害應(yīng)急物流的多目標(biāo)魯棒隨機(jī)規(guī)劃。在他們的研究中雖然提到魯棒優(yōu)化的思想，但實(shí)質(zhì)還是利用隨機(jī)優(yōu)化模型解決問(wèn)題。本文正是借鑒魯棒優(yōu)化的解決思路，考慮到突發(fā)事件相關(guān)參數(shù)概率分布情況難以獲取的情況下，無(wú)法采用隨機(jī)規(guī)劃方法解決應(yīng)急準(zhǔn)備工作，而將自然災(zāi)害按照其發(fā)生的特征劃分成有限個(gè)情景集合，建立基于最小最大后悔值（偏差）準(zhǔn)則的應(yīng)急救災(zāi)網(wǎng)絡(luò)魯棒優(yōu)化模型，這使得模型更符合實(shí)際。求解時(shí)，只需要利用較少的情景數(shù)據(jù)，就能得到可靠的結(jié)果。

2 應(yīng)急救災(zāi)網(wǎng)絡(luò)規(guī)劃模型描述

2.1 基本模型描述

假設(shè)在應(yīng)急布局時(shí)已經(jīng)確定了應(yīng)急資源供應(yīng)方。自然災(zāi)害發(fā)生后，救災(zāi)過(guò)程分為兩個(gè)階段，如圖1所示，第一個(gè)階段，災(zāi)害剛發(fā)生的初期，應(yīng)急救災(zāi)部門需要立即進(jìn)行應(yīng)急決策。根據(jù)某些技術(shù)條件如GIS與遙感技術(shù)可以獲得初步的信息，確定受災(zāi)點(diǎn)的范圍，大致估計(jì)受災(zāi)點(diǎn)的受災(zāi)程度，并以此確定災(zāi)害發(fā)生所帶來(lái)的應(yīng)急物資需求的若干情景，依據(jù)這些情景在災(zāi)區(qū)附近設(shè)立若干臨時(shí)應(yīng)急資源配送中心，并確定從哪些應(yīng)急物資供應(yīng)方籌集多少種類和數(shù)量的應(yīng)急救災(zāi)物資，運(yùn)送到臨時(shí)應(yīng)急資源配送中心。第二個(gè)階段，從臨時(shí)應(yīng)急資源配送中心向各受災(zāi)點(diǎn)調(diào)度應(yīng)急物資，更新應(yīng)急需求信息，以保障應(yīng)急救援的物資需求。將調(diào)度階段作為第二個(gè)階段是為了簡(jiǎn)化建模過(guò)程的需要。第二個(gè)階段救援保障程度的高低顯然受到第一階段決策是否穩(wěn)健的影響。

圖1 基本模型圖示

本文考慮的問(wèn)題是解決某個(gè)地區(qū)面對(duì)災(zāi)害時(shí)構(gòu)建應(yīng)急救災(zāi)網(wǎng)絡(luò)，即救災(zāi)過(guò)程第一階段的決策，具體包括確定臨時(shí)應(yīng)急救災(zāi)設(shè)施（應(yīng)急配送中心）的選址，從各應(yīng)急資源供應(yīng)方向臨時(shí)應(yīng)急配送中心配置的各類應(yīng)急物資的數(shù)量，目標(biāo)是希望整個(gè)應(yīng)急救災(zāi)的代價(jià)最小若臨時(shí)應(yīng)急配送中心物資總量不足或受災(zāi)點(diǎn)的需求未滿足，則引入補(bǔ)償策略，對(duì)未滿足的需求進(jìn)行懲罰；若臨時(shí)應(yīng)急配送中心最終積壓或超出受災(zāi)點(diǎn)的需求而造成物資冗余，同樣也要懲罰。

災(zāi)害發(fā)生后，能夠獲得災(zāi)害的級(jí)別等初步信息，但是詳細(xì)的不確定數(shù)據(jù)取值還不能確定，這時(shí)候引入情景估計(jì)，即根據(jù)災(zāi)情（房屋受破壞程度，人口統(tǒng)計(jì)信息）的不同組合方式，利用經(jīng)驗(yàn)估計(jì)方法確定第二階段不確定數(shù)據(jù)取值。并對(duì)得到經(jīng)驗(yàn)估計(jì)值進(jìn)行合理的浮動(dòng)，從而確定第二階段災(zāi)害的若干種情景。

I：應(yīng)急資源供應(yīng)方i集合

J：候選臨時(shí)應(yīng)急資源配送中心j集合

K：受災(zāi)地區(qū)k集合

S：提供的應(yīng)急資源的種類s集合

M：一個(gè)大數(shù)

Fj：臨時(shí)應(yīng)急資源配送中心j的建設(shè)成本

bsi：供應(yīng)方i提供的應(yīng)急資源s的單位費(fèi)用

Csi：供應(yīng)方i提供的應(yīng)急資源s的總量

tωsij：將某種應(yīng)急資源s從供應(yīng)方i運(yùn)往臨時(shí)應(yīng)急資源配送中心j的單位費(fèi)用

tωsjk：將應(yīng)急資源s從臨時(shí)應(yīng)急資源配送中心j運(yùn)往災(zāi)區(qū)k的單位費(fèi)用

psk：災(zāi)區(qū)k未滿足的應(yīng)急資源s的單位懲罰費(fèi)用

qsk：災(zāi)區(qū)k多余應(yīng)急資源s的單位處置費(fèi)用

vs：應(yīng)急資源s的單位體積

Vj：臨時(shí)應(yīng)急資源配送中心j的最大容量

dωsk：情景ω發(fā)生時(shí)災(zāi)區(qū)k對(duì)應(yīng)急資源s的需求量

決策變量為：

Xj：臨時(shí)應(yīng)急配送中心j被選址，則為1，否則，為0

xsij：應(yīng)急資源供應(yīng)方i運(yùn)往臨時(shí)應(yīng)急配送中心j的應(yīng)急資源s的數(shù)量

輔助決策變量為：

yωsjk：情景ω下臨時(shí)應(yīng)急資源配送中心j分配到災(zāi)區(qū)k的應(yīng)急資源s的數(shù)量

zωsk：情景ω下災(zāi)區(qū)k未滿足的應(yīng)急資源s的數(shù)量

rωsk：情景ω下災(zāi)區(qū)k剩余的應(yīng)急物資的s的數(shù)量

目標(biāo)函數(shù)中：

模型P是一個(gè)兩階段混合整數(shù)規(guī)劃模型。目標(biāo)函數(shù)（1）為應(yīng)急救災(zāi)兩個(gè)階段的總費(fèi)用，第一階段：（1a）表示臨時(shí)應(yīng)急配送中心選址的建設(shè)費(fèi)用；（1b）為應(yīng)急資源供應(yīng)方運(yùn)往臨時(shí)應(yīng)急配送中心的物資運(yùn)輸費(fèi)用；第二階段：（1c）為情景ω下從供應(yīng)方往臨時(shí)應(yīng)急配送中心的應(yīng)急資源運(yùn)輸費(fèi)用；（1d）表示情景ω下從臨時(shí)應(yīng)急配送中心往災(zāi)區(qū)的應(yīng)急資源運(yùn)輸費(fèi)用；（1e）表示未滿足需求的懲罰費(fèi)用；（1f）表示當(dāng)需求點(diǎn)物資有剩余時(shí)，應(yīng)急資源的處置費(fèi)用。約束（2）表示供應(yīng)方提供應(yīng)急資源的總量不能夠超過(guò)其供應(yīng)能力。約束（3）表示每個(gè)臨時(shí)應(yīng)急配送中心應(yīng)急資源配置的容量要求。約束（4）表示在情景ω下，只有臨時(shí)配送中心選址，才能為其配置資源。約束（5）表示從某個(gè)臨時(shí)應(yīng)急配送中心運(yùn)往災(zāi)區(qū)的應(yīng)急資源總量不能超過(guò)供應(yīng)方提供給該配送中心的應(yīng)急資源總量。約束（6）表示每個(gè)災(zāi)區(qū)對(duì)某種應(yīng)急資源的需求量盡量滿足，對(duì)于未滿足的資源，引入懲罰策略，策略的代價(jià)即目標(biāo)函數(shù)（1e）項(xiàng)，可認(rèn)為未滿足的需求所造成的損失；對(duì)于多余資源，也需要處置費(fèi)用，即（1f）項(xiàng)。約束（7）是對(duì)臨時(shí)應(yīng)急配送中心選址變量的整型約束，以及其余決策變量的非負(fù)約束。

從目標(biāo)和約束條件中可以看出，模型綜合考慮了應(yīng)急救災(zāi)網(wǎng)絡(luò)構(gòu)建中所遵循的幾個(gè)原則，如目標(biāo)函數(shù)體現(xiàn)了應(yīng)急救災(zāi)代價(jià)的經(jīng)濟(jì)性，約束條件保證了應(yīng)急資源保障的可靠性，而下面的處理方法則考慮所有情景，所做決策保證了決策的魯棒性。

2.2 基于最小最大后悔值的魯棒優(yōu)化模型

為簡(jiǎn)化描述，令{X，（Yω，Zω）｝分別表示兩個(gè)階段的決策變量集合{（Xj，xsij），yωsjk，zωsk，?s，i，j，k，ω｝。對(duì)突發(fā)事件的任一情景ω∈，與情景ω相關(guān)的最優(yōu)決策{X*，（Yω*，Zω*）｝可以利用下列模型求解

但是，構(gòu)建應(yīng)急救災(zāi)網(wǎng)絡(luò)時(shí)，在所有情景發(fā)生前就要完成對(duì)臨時(shí)應(yīng)急配送中心的選址及應(yīng)急資源的配置工作，模型P只有對(duì)第一階段所估計(jì)的所有受災(zāi)點(diǎn)需求情景ω∈都考慮才有實(shí)際意義。為此建立基于情景的最小最大后悔值魯棒優(yōu)化模型。

最小最大后悔值的思想來(lái)源于非確定型決策中的后悔值準(zhǔn)則，即最小機(jī)會(huì)損失法（Savage法），其基本思想是從機(jī)會(huì)損失值，即某種情形發(fā)生時(shí)，決策者所選方案的成本與因此放棄的可能最小成本之間的差額最小的角度考慮制定決策。對(duì)于本問(wèn)題，建立下列最小最大后悔值魯棒優(yōu)化模型：

其中：

模型（9）又稱為偏差魯棒優(yōu)化模型，指的是進(jìn)行第一階段的應(yīng)急決策時(shí)，選擇具有最小的最大后悔值的方案作為最優(yōu)決策。后悔值Zω*（X）-Cω*指對(duì)于某個(gè)情景ω∈，選擇應(yīng)急救災(zāi)網(wǎng)絡(luò)規(guī)劃方案X后，其總費(fèi)用與該情景ω下可能的最優(yōu)規(guī)劃方案目標(biāo)值的差。模型（9）得到的決策結(jié)果是針對(duì)所有可能發(fā)生的情景進(jìn)行的決策，這保證了應(yīng)急決策的公平性和穩(wěn)健性。

3 求解模型的算法描述

3.1 模型求解思路

當(dāng)情景集合Ω包含有限個(gè)情景ω時(shí)，最小最大后悔魯棒優(yōu)化模型（9）等價(jià)于下列混合整數(shù)規(guī)劃問(wèn)題：

模型（11）是（9）的擴(kuò)展形式。如果（11）的最優(yōu)解存在，則其解的分量{X=（Xj，xsij）?s，i，j｝即為模型（9）的最優(yōu)解。但在實(shí)際求解過(guò)程中，突發(fā)事件的情景集合的規(guī)模一般比較大，求解模型（11）將會(huì)花費(fèi)很多的時(shí)間，這對(duì)時(shí)效性要求很高的應(yīng)急救災(zāi)過(guò)程來(lái)說(shuō)不能接受?；诖耍疚脑O(shè)計(jì)一種新的基于情景松弛的迭代優(yōu)化算法求解最小最大后悔值魯棒優(yōu)化模型（9）。

4.2 最小最大后悔值魯棒優(yōu)化模型的情景松弛算法

有了以上討論的基礎(chǔ)，下面給出求最小最大后悔值魯棒優(yōu)化應(yīng)急決策模型（9）的算法：

S2：（求解松弛問(wèn)題并進(jìn)行最優(yōu)性檢驗(yàn)）求解由子集合Ω構(gòu)成的模型（11）的松弛問(wèn)題。

若松弛問(wèn)題不可行，則算法終止，模型（9）不存在魯棒最優(yōu)解；否則，令XΩ=X*（松弛問(wèn)題的最優(yōu)解），LB=δ*（松弛問(wèn)題的最優(yōu)目標(biāo)值）。若UBLB≤ε，XΩ即可作為全局ε-最優(yōu)魯棒解，算法結(jié)束，否則，轉(zhuǎn)S3

S4：若W1≠?，執(zhí)行S5；否則，更新UB：= min（UB，。若UB-LB≤ε，X=XΩ即可作為滿足

的全局ε-最優(yōu)魯棒解，算法結(jié)束；否則，轉(zhuǎn)S6

S6：選擇非空子集W′?W，更新集合Ω：=Ω∪W′，轉(zhuǎn)S2

注：因?yàn)楸舅惴ǖ哪康氖枪?jié)約求解時(shí)間，后面的實(shí)驗(yàn)結(jié)果可以看到，即使問(wèn)題的情景集合和包含多個(gè)情景，但是在用本算法求解時(shí)，只需要極少數(shù)目的情景，即情景集合Ω的數(shù)目很小。因此，在選取情景集合Ω時(shí)，初始步驟一般隨機(jī)選擇一個(gè)情景ω∈Ω即可。

④如果X*是原問(wèn)題（9）的最優(yōu)解，則X*也是模型（11）的松弛問(wèn)題的可行解

由a），b），若算法因?yàn)槟Ｐ停?）不可行或者模型（11）的松弛問(wèn)題不可行而終止，則最小最大后悔值魯棒問(wèn)題（9）也不可行。

現(xiàn)假定算法由于S2或者S4中條件UB=LB而終止，得到解XΩ。

由于算法只有在XΩ對(duì)于所有情景均可行，或者是W1=?時(shí)，才能在以上步驟中結(jié)束，并且此時(shí)有

定理1 情景松弛算法在有限次迭代后終止，當(dāng)算法終止于ε=0時(shí)，或者算法不可行，或者求得原問(wèn)題的最優(yōu)魯棒解。

證明：注意到模型（11）的松弛問(wèn)題也是原最小最大后悔模型（9）的松弛問(wèn)題，模型（8）的可行域包含（9）的可行域，這個(gè)事實(shí)表明：

①如果模型（8）不可行，則原最小最大后悔值魯棒問(wèn)題（9）不可行

②如果模型（11）的松弛問(wèn)題不可行，則問(wèn)題（9）也不可行

因此，如果UB=LB，則：

顯然，XΩ是原最小最大后悔魯棒問(wèn)題（9）的最優(yōu)解。

由于只有有限個(gè)可能的XΩ的組合和參數(shù)設(shè)置，因此，該算法在有限步迭代后終止。

4 算例分析

算例考慮我國(guó)云南省應(yīng)對(duì)地震災(zāi)害的應(yīng)急救災(zāi)網(wǎng)絡(luò)規(guī)劃問(wèn)題。該省位于幾個(gè)地震帶上，屬地震多發(fā)地區(qū)。2009年7月9日，楚雄彝族自治州發(fā)生6. 0級(jí)地震，陣中位于姚安縣，如圖2所示。地震造成楚雄、大理、麗江3州市十幾個(gè)縣不同程度受災(zāi)，緊急轉(zhuǎn)移安置25萬(wàn)人。

圖2 楚雄地震震級(jí)圖示

地震發(fā)生后，立即啟動(dòng)應(yīng)急響應(yīng)，在災(zāi)區(qū)附近建立臨時(shí)應(yīng)急配送中心，負(fù)責(zé)應(yīng)急物資的收集及分配工作。根據(jù)實(shí)際情況將災(zāi)區(qū)劃分為15個(gè)需求點(diǎn)，應(yīng)急物資儲(chǔ)備庫(kù)或者應(yīng)急物資生產(chǎn)商，共8個(gè)，分布在8個(gè)城市，如圖3所示。由于臨時(shí)應(yīng)急配送中心在災(zāi)區(qū)附近建立，因此，15個(gè)需求點(diǎn)也是待選的臨時(shí)應(yīng)急物資配送中心，且每個(gè)配送中心的容積均相等?？紤]三種應(yīng)急物資：水，食物和帳篷，其相關(guān)配置參數(shù)如表1所示。

圖3 案例圖示

第一階段的地震級(jí)別以及震源信息已經(jīng)獲得，但是具體的受災(zāi)情況還未知，根據(jù)建模時(shí)情景的獲取方法，確定每個(gè)需求點(diǎn)包含16個(gè)情景。由于食物和水在應(yīng)急期（10天）內(nèi)屬于消耗性物品，因此，其需求乘以時(shí)間系數(shù)10天。而帳篷數(shù)量根據(jù)需求總?cè)藬?shù)除以3而得出。表3列出了各個(gè)供應(yīng)點(diǎn)能夠提供的應(yīng)急物資的數(shù)量。

給出上面實(shí)例的參數(shù)值設(shè)置后，利用MATLAB2012a編程，中間在求解規(guī)劃問(wèn)題時(shí)，采用LINGO11.0，得到應(yīng)急救災(zāi)網(wǎng)絡(luò)規(guī)劃如表4所示。

表1 應(yīng)急物資配置相關(guān)參數(shù)

表2 需求點(diǎn)應(yīng)急物資需求列表（103/單位）

表3 供應(yīng)方提供的應(yīng)急物資數(shù)量（103/單位）

表4 臨時(shí)應(yīng)急配送中心選址及應(yīng)急資源配置表（103/單位）

從表4的結(jié)果中可以觀察，臨時(shí)應(yīng)急資源配送中心選在祿豐，祥云2個(gè)地點(diǎn)；在8個(gè)供應(yīng)方中，迪慶，大理和臨滄主要負(fù)責(zé)向臨時(shí)配送中心祥云提供應(yīng)急資源，而后面5個(gè)城市主要負(fù)責(zé)向祿豐供應(yīng)應(yīng)急物資，提供的食物，水和帳篷的總數(shù)量如表4中最后一行三維向量所示，從資源總量來(lái)看，祿豐提供的應(yīng)急資源的數(shù)量也非常大，這是由于祿豐距離各個(gè)配送中心距離不太遠(yuǎn)，而且，距離5個(gè)配送中心的距離也比較近。

由于本模型價(jià)值體現(xiàn)在決策針對(duì)所有情景的公平性，為了觀察決策值和每個(gè)情景的最優(yōu)決策值之間的差距，實(shí)驗(yàn)畫出了最優(yōu)決策目標(biāo)值和16個(gè)情景每個(gè)最優(yōu)決策目標(biāo)值之間的差值，即后悔值折線圖，如圖4所示。從折線圖中可以看出，每個(gè)情景和最優(yōu)決策的最大差值為770×103元，即本模型的最優(yōu)解對(duì)大部分情景下的后悔值比較均衡，均在最優(yōu)目標(biāo)值附近，其中，后悔值最小的為情景7，為280.5× 103元，其次為情景4，后悔值為448×103元，其余的情景后悔值均在最優(yōu)目標(biāo)值附近，這說(shuō)明本模型的應(yīng)急決策結(jié)果具有較強(qiáng)的魯棒性，能夠滿足針對(duì)不同情景的應(yīng)急救災(zāi)網(wǎng)絡(luò)救災(zāi)的構(gòu)建要求。

應(yīng)急救災(zāi)網(wǎng)絡(luò)需要在較短的時(shí)間內(nèi)構(gòu)造，因此對(duì)時(shí)效性的要求比較高。在執(zhí)行算法的過(guò)程中，情景集合大小對(duì)于求解時(shí)間的影響較大，若花費(fèi)的時(shí)間較長(zhǎng)，則不能算作有效算法。為了驗(yàn)證求解算法的有效性，算法檢驗(yàn)了不同規(guī)模情景集合的模型，分別包含16，64，256（兩類）與1024（兩類）個(gè)情景集合，與單純計(jì)算擴(kuò)展形式（11）的時(shí)間相比較。比較結(jié)果如表5所示。

圖4 各情景后悔值折線圖

表5 本算法與擴(kuò)展形式的計(jì)算性能對(duì)比

其中Zω（X）如式子（10）所示。模型（12）仍然可以利用本文中的情景松弛算法求解，只需要將模型的目標(biāo)函數(shù) （（XΩ）-）修改為函數(shù)Zω（X），以及步驟S1去掉即可，其余步驟不變。表6列出了不同魯棒優(yōu)化準(zhǔn)則下的決策結(jié)果。從表中可以看出，不同的魯棒優(yōu)化準(zhǔn)則下其應(yīng)急救災(zāi)網(wǎng)絡(luò)的構(gòu)建結(jié)果是不同的，將絕對(duì)魯棒優(yōu)化準(zhǔn)則下的決策結(jié)果帶入到最小最大后悔值準(zhǔn)則的目標(biāo)函數(shù)中，其值為2801.5×103，遠(yuǎn)大于其最優(yōu)目標(biāo)函數(shù)值770 ×103，這說(shuō)明基于最小最大后悔值準(zhǔn)則的魯棒優(yōu)化模型在構(gòu)建應(yīng)急救災(zāi)網(wǎng)絡(luò)時(shí)是比較有效的。

從表5中的模型計(jì)算結(jié)果可以看出，基于情景松弛的魯棒優(yōu)化算法在計(jì)算時(shí)間上明顯優(yōu)于單純求解擴(kuò)展形式所用的時(shí)間。如模型6包含了1024個(gè)情景，利用本文的算法只需要444秒，而單純求解其擴(kuò)展形式，需要38630秒，大約為10.6個(gè)小時(shí)，這對(duì)于時(shí)效性很強(qiáng)的救災(zāi)網(wǎng)絡(luò)構(gòu)建行為顯然是不可行的。由此，情景松弛算法在求解應(yīng)急救災(zāi)網(wǎng)絡(luò)的最小最大后悔值魯棒優(yōu)化模型時(shí)是非常有效的。

值得注意的是，基于最小最大后悔值的魯棒優(yōu)化方法與其它魯棒優(yōu)化方法在目標(biāo)值上并不具備直接可比性。但為了反映不同的魯棒優(yōu)化準(zhǔn)則對(duì)決策結(jié)果的影響，本文將基于最小最大后悔魯棒優(yōu)化模型得到的結(jié)果與絕對(duì)魯棒優(yōu)化模型的結(jié)果進(jìn)行對(duì)比。建立的應(yīng)急救災(zāi)網(wǎng)絡(luò)絕對(duì)魯棒優(yōu)化模型為：

表6 不同魯棒決策準(zhǔn)則下的應(yīng)急救災(zāi)網(wǎng)絡(luò)決策結(jié)果對(duì)比

5 結(jié)語(yǔ)

本文通過(guò)建立二階段災(zāi)后應(yīng)急救災(zāi)網(wǎng)絡(luò)模型，解決了應(yīng)對(duì)自然災(zāi)害臨時(shí)應(yīng)急配送中心選擇和應(yīng)急救災(zāi)物資配置問(wèn)題，并根據(jù)情景預(yù)測(cè)結(jié)果，將模型轉(zhuǎn)化為最小最大后悔值的魯棒優(yōu)化模型。在求解該模型時(shí)，針對(duì)災(zāi)害造成的不確定數(shù)據(jù)的情景預(yù)測(cè)結(jié)果，構(gòu)建了基于情景松弛的魯棒優(yōu)化算法。該模型能夠有效用于應(yīng)急救災(zāi)網(wǎng)絡(luò)構(gòu)建過(guò)程中，試驗(yàn)結(jié)果表明基于最小最大后悔值準(zhǔn)則的應(yīng)急救災(zāi)網(wǎng)絡(luò)優(yōu)化模型具有良好的魯棒性，而且基于情景松弛的魯棒優(yōu)化算法的有效性也得到了驗(yàn)證。

本文的應(yīng)急決策模型綜合考慮了應(yīng)急響應(yīng)遵循的原則：應(yīng)急資源保障的可靠性，針對(duì)不同情景的決策魯棒性，以及救災(zāi)代價(jià)的經(jīng)濟(jì)性等目標(biāo)。但是，仍然有一些目標(biāo)沒(méi)能夠很好的解決，如未能考慮第二階段各個(gè)受災(zāi)點(diǎn)的均衡性，以及各點(diǎn)的需求滿足率情況。另外，針對(duì)第二階段的應(yīng)急資源調(diào)度只是根據(jù)情景簡(jiǎn)單考慮了不確定參數(shù)的取值情況，在實(shí)際救災(zāi)過(guò)程中應(yīng)急資源的調(diào)度問(wèn)題比較復(fù)雜。如何綜合考慮以上問(wèn)題展開(kāi)研究，從而使應(yīng)急決策更加符合實(shí)際救災(zāi)的需求，是接下來(lái)將要需要考慮的。

［1］Hakimi S L.Optimum locations of switching centers and the absolute centers and medians of a graph［J］.Operations Research，1964，12：450-459.

［2］Fiedrich F，Gehbauer F，Rickers U.Optimized resource allocation for emergency response after earthquake disasters［J］.Safety Science，2000，35：41-57.

［3］劉春林，何建敏，施建軍.一類應(yīng)急物資調(diào)度的優(yōu)化模型研究［J］.中國(guó)管理科學(xué)，2001，9（3）：29-36.

［4］Ozdamar L，Ekinci E，Kucukyzici B.Emergency logistics planning in natural disasters［J］.Annals of Operations Research，2004，129：217-245.

［5］曾敏剛，崔增收，余高輝.基于應(yīng)急物流的減災(zāi)系統(tǒng)LRP研究［J］.中國(guó)管理科學(xué)，2010，2（18）：75-80.

［6］李進(jìn)，張江華，朱道立.災(zāi)害鏈中多資源應(yīng)急調(diào)度模型與算法［J］.系統(tǒng)工程理論與實(shí)踐，2011，3（11）：488-495.

［7］Tzeng G H，Cheng H J，Huang T D.Multi-objective optimal planning for designing relief delivery systems［J］.Transportation Research Part E，2007，43（6）：673 -686.

［8］Ali B A，Jabalameli M S.Mirzapour S M.A multi-objective robust stochastic programming model for disaster relief logistics under uncertainty［J］.OR Spectrum，2011，8：1-30.

［9］Chang M S，Tseng Y L，Chen J W.A scenario planning approach for the flood emergency logistics preparation problem under uncertainty［J］.Transportation Research Part E：Logistics and Transportation Review，2007，43（6）：737-754.

［10］Salmeron J，Apte A.Stochastic optimization for natural disaster asset pre-positioning［J］.Production and Operating Management，2010，19（5）：561-574.

［11］張玲，黃鈞，韓繼業(yè).應(yīng)對(duì)自然災(zāi)害的應(yīng)急資源布局模型與算法［J］.系統(tǒng)工程理論與實(shí)踐，2010，9（30）：1615-1621.

［12］El-Ghaoui L，Lebret H，Oustry F.Robust solutions to uncertain semi-definite programs［J］.SIAM Journal of Optimization，1998，9（1）：33-52.

［13］Ben-Tal A，Nemirovski A.Robust Convex Optimization［J］.Mathematics of Operations Research，1998，23（4）：769-805.

［14］Ben-Tal A，Nemirovski A.Robust solutions of Linear Programming problems contaminated with uncertain data［J］.Mathematical Programming，2000，88（3）：411-424.

［15］Ben-Tal A，Nemirovski A.Robust optimizationmethodology and applications［J］.Mathematical Programming，2002，92（3）：453-480.

［16］Bertsimas D，Sim M.Robust discrete optimization and network flows［J］.Mathematical Programming，2003，98（1）：49-71.

［17］Sim M.Robust Optimization［M］.Cambridge：Massachusetts Institute of Technology Sloan School of Management，2004.

［18］王英楠，韓繼業(yè)，孫華.一種不確定需求下庫(kù)存定價(jià)模型的魯棒優(yōu)化方法［J］.應(yīng)用數(shù)學(xué)學(xué)報(bào)，2008，31（5）：910-921.

［19］Nalan G，Dessislava P，Ethem C.Robust strategies for facility location under uncertainty［J］.European Jour-

nal of Operational Research，2013，225（1）：21-35.［20］Kouvelis P，Yu G.Robust discrete optimization and its applications［M］.Dordrecht，The Netherlands：Kluwer Academic Publishers，1997.

Emergency Network Model and Algorithm Based on Min-Max Regret Robust Optimization

ZHANG Ling1，CHEN Tao2，HUANG Jun2
（1.Department of Economics and Management，Huizhou University，Guangdong 516007，China；2.School of Mathematica Science，University of Chinese Academy of Sciences，Beijing 100049，China）

After emergency，rescue process is represented by two stage.First stage is to start the emergency rescue network，including building temporary distribution centers，allocating reasonable emergency resource to assure rescue process working smoothly.The second stage is to dispatch emergency resource from temporary distribution centers to demand points.A min-max regret robust emergency network model is proposed for natural disasters under uncertainty，taking the second stage as auxiliary decision.Uncertain information is random and represented by finite scenarios.The proposed model is solved using scenario relaxation algorithm.Finally，a case study is proposed to highlight efficiency of the proposed model and solution algorithm.

emergency rescue network plan；uncertain information；two-stage programing；min-max regret criterion；robust optimization；scenairio relaxation

O224

A

1003-207（2014）07-0131-09

2013-02-04；

2013-09-01

廣東省優(yōu)秀青年創(chuàng)新人才培養(yǎng)計(jì)劃項(xiàng)目（LYM11119）；廣東省自然基金項(xiàng)目（S2011040004017）；北京市哲學(xué)社會(huì)科學(xué)規(guī)劃項(xiàng)目（13JGC089）

張玲（1980-），女（漢族），山東泰安人，惠州學(xué)院經(jīng)濟(jì)管理系，講師，博士，研究方向：應(yīng)急管理.