考慮連續(xù)消耗的多出救點(diǎn)、多物資的應(yīng)急調(diào)度問(wèn)題的研究

王 勝 劉 勇

（三峽大學(xué) 智能視覺(jué)與圖像信息研究所，湖北 宜昌 443002）

應(yīng)急事件發(fā)生后，為了盡可能地減小災(zāi)區(qū)人民的生命財(cái)產(chǎn)損失，維持災(zāi)區(qū)人民的正常生活，就必須在盡可能短的時(shí)間內(nèi)向?yàn)?zāi)區(qū)運(yùn)送所需要的相關(guān)物資，才能進(jìn)行及時(shí)的救援.而災(zāi)區(qū)的需求往往是多樣的，且數(shù)量巨大，一個(gè)出救點(diǎn)在物資的種類(lèi)和數(shù)量上常常不能滿(mǎn)足其需求.同時(shí)為了降低成本，通常會(huì)從多個(gè)出救點(diǎn)中選取盡可能少的幾個(gè)出救點(diǎn)來(lái)對(duì)災(zāi)區(qū)進(jìn)行物資輸送.關(guān)于多出救點(diǎn)、多物資應(yīng)急調(diào)度問(wèn)題，近些年來(lái)國(guó)內(nèi)外都取得了一些進(jìn)展.

高本河、伍慧飛等［1]提出將運(yùn)輸限制下的多資源調(diào)度問(wèn)題轉(zhuǎn)化為一個(gè)n階段決策模型，將n種物資的需求作為n個(gè)階段，將m個(gè)出救點(diǎn)的運(yùn)輸量作為決策變量，而將出救點(diǎn)的剩余運(yùn)輸能力作為狀態(tài)變量，進(jìn)而運(yùn)用貪心算法在時(shí)間最短的條件下，求出了出救點(diǎn)最少的調(diào)度方案.針對(duì)多出救點(diǎn)、多物資、多目標(biāo)應(yīng)急調(diào)度的特點(diǎn)，胡飛虎、耿澤飛等［2]提出建立一種以時(shí)間最短、成本最小為目標(biāo)的數(shù)學(xué)模型，應(yīng)用模糊理想點(diǎn)法作為多目標(biāo)模糊判決的求解算法，把多目標(biāo)決策問(wèn)題轉(zhuǎn)化為單目標(biāo)規(guī)劃問(wèn)題來(lái)求解.李周清、馬祖軍［3]設(shè)計(jì)了一種多目標(biāo)協(xié)進(jìn)化遺傳算法對(duì)區(qū)域救援物資中轉(zhuǎn)調(diào)度的多目標(biāo)優(yōu)化問(wèn)題進(jìn)行了求解.應(yīng)急管理是一個(gè)復(fù)雜的多目標(biāo)優(yōu)化問(wèn)題，Suleyman、William［4]認(rèn)為采取折中的決策方法對(duì)有限的資源進(jìn)行調(diào)度是最好的方法.Barbarosoglu［5]提出了一個(gè)兩階段多運(yùn)輸方式、多種類(lèi)物資的網(wǎng)絡(luò)流模型用于解決救援物資的運(yùn)輸計(jì)劃.

但是，近些年來(lái)，對(duì)有時(shí)間限制的、物資連續(xù)消耗的多出救點(diǎn)多物資調(diào)度問(wèn)題的研究卻相對(duì)較少.本文結(jié)合文獻(xiàn)［2]在進(jìn)行多目標(biāo)決策時(shí)提出的非劣解的概念，不但考慮了各個(gè)出救點(diǎn)的滿(mǎn)足能力，還分析了其對(duì)選擇下一個(gè)出救點(diǎn)的范圍的影響.同時(shí)在借鑒文獻(xiàn)［6]對(duì)出救點(diǎn)滿(mǎn)足災(zāi)區(qū)需求的能力進(jìn)行量化評(píng)估方法的基礎(chǔ)上，提出了一種新的考慮連續(xù)消耗的多出救點(diǎn)、多物資應(yīng)急調(diào)度算法.

1 問(wèn)題描述

假設(shè)A為受災(zāi)地區(qū)，需要n種應(yīng)急物資的數(shù)量分別為P1，P2，…，Pn，各種物資的時(shí)間限制分別為T(mén)d1，Td2，…，Tdn，各種物資的消耗速度分別為v1，v2，…，vn.有A1，A2，…，Am共m個(gè)出救點(diǎn)可以參與出救，它們到A的時(shí)間分別為T(mén)1，T2，…，Tm.各出救點(diǎn)擁有各物資的數(shù)量分別為Pij（i＝1，2，…，m；j＝1，2，…，n），且有

式中，P′ij為出救點(diǎn)Ai提供給災(zāi)區(qū)第j種物資的數(shù)量.

約束條件：①調(diào)度過(guò)程中，災(zāi)區(qū)不能出現(xiàn)物資短缺，導(dǎo)致消耗中斷；②所有被選取的出救點(diǎn)必須同時(shí)開(kāi)始出救；要求找到出救點(diǎn)最少的出救方案.

2 考慮連續(xù)消耗的多出救點(diǎn)、多物資應(yīng)急調(diào)度算法

文獻(xiàn)［6]中的多出救點(diǎn)、多物資應(yīng)急調(diào)度算法在尋找下一個(gè)出救點(diǎn)時(shí)，總是選擇在時(shí)間限制內(nèi)滿(mǎn)足災(zāi)區(qū)需求能力最大的出救點(diǎn)，缺乏整體考慮，是一種典型的貪婪算法，具有所有貪婪算法的共有缺點(diǎn)，即它所得到的只能是某種意義上的近似最優(yōu)方案，很難得到全局最優(yōu)方案.

為了使最終找到的出救點(diǎn)最少，本算法將先對(duì)各出救點(diǎn)的滿(mǎn)足能力，以及該出救點(diǎn)的選取對(duì)災(zāi)區(qū)選擇下一個(gè)出救點(diǎn)范圍的影響大小分別進(jìn)行量化，再進(jìn)行綜合考慮，試圖找到出救點(diǎn)最少的出救方案.本算法首先按照各出救點(diǎn)滿(mǎn)足能力的大小，對(duì)在災(zāi)區(qū)的時(shí)間限制內(nèi)還未被選取的出救點(diǎn)進(jìn)行排名，再檢查排名相對(duì)靠后的出救點(diǎn)，是否能使災(zāi)區(qū)在選擇該出救點(diǎn)后，在選擇下一個(gè)出救點(diǎn)時(shí)有一個(gè)更大的選擇范圍，如果是，則將其加入到候選出救點(diǎn)的行列.從而得到一組值得嘗試被選取參與出救的候選出救點(diǎn).在候選出救點(diǎn)中，任何一個(gè)出救點(diǎn)在滿(mǎn)足能力和擴(kuò)大下一個(gè)出救點(diǎn)的選擇范圍方面，不會(huì)同時(shí)比其他出救點(diǎn)更好或者更差，這樣就保留了那些比較優(yōu)質(zhì)的出救點(diǎn).然后按照滿(mǎn)足能力非遞增的順序讓候選出救點(diǎn)依次參與出救，如果某一個(gè)候選出救點(diǎn)參與出救時(shí)，災(zāi)區(qū)的需求已滿(mǎn)足，則可得到最優(yōu)出救方案.如果某一層的候選出救點(diǎn)已全部嘗試參與出救，并且都沒(méi)有滿(mǎn)足災(zāi)區(qū)的需求，則求出以選取該層候選出救點(diǎn)為前提的下一層候選出救點(diǎn)，并且讓下一層候選出救點(diǎn)按照它們自己的滿(mǎn)足能力非遞增的順序參與出救.如此往下一層一層地尋找候選出救點(diǎn)，直到找到一個(gè)候選出救點(diǎn)能滿(mǎn)足災(zāi)區(qū)的需求為止.

一些變量的定義如下：xflag［j]為災(zāi)區(qū)第j種物資的需求是否已滿(mǎn)足的標(biāo)志，為1表示已滿(mǎn)足；forb［i]為出救點(diǎn)Ai是否已被選取參與出救的標(biāo)志，為1表示已被選取；Av為存放可參與出救的各出救點(diǎn)的序號(hào)；Can為存放每次選取的候選出救點(diǎn)的序號(hào)；cnt［i]［j]為出救點(diǎn)Ai對(duì)災(zāi)區(qū)第j種物資的滿(mǎn)足能力；sflag［i]為出救點(diǎn)Ai對(duì)災(zāi)區(qū)總的滿(mǎn)足能力；Td為災(zāi)區(qū)的時(shí)間限制；Tdnew［i]為候選出救點(diǎn)Ai被選取后災(zāi)區(qū)新的時(shí)間限制；Tc［j]為已選取的出救點(diǎn)中第j種物資的時(shí)間限制；Tcnew［i]［j]為選取候選出救點(diǎn)Ai后災(zāi)區(qū)第j種物資的時(shí)間限制；Tc′［i]［j]為候選出救點(diǎn)Ai提供的第j種物資被災(zāi)區(qū)消耗完所需的時(shí)間；q［i]為候選出救點(diǎn)Ai帶給災(zāi)區(qū)新的時(shí)間限制內(nèi)物資能到達(dá)災(zāi)區(qū)的出救點(diǎn)的個(gè)數(shù)；qmax為各候選出救點(diǎn)帶給災(zāi)區(qū)新的時(shí)間限制內(nèi)物資能到達(dá)災(zāi)區(qū)的出救點(diǎn)的個(gè)數(shù)的最大值.

2.1 初始化

令forb［i]＝0（i＝1，2，…，m），令xfalg［j]＝0，Tc［j]＝Tdj，Td＝min｛Tc［j]｝（j＝1，2，…，n）.

2.2 選擇候選出救點(diǎn)

1）初始化：清空Av表，把所有Ti≤Td（i∈｛i′｜forb［i′]＝0，i′＝1，2，…，m｝）的出救點(diǎn)的序號(hào)放入Av表中，如果Av為空，則在該前提下沒(méi)有出救點(diǎn)，選擇候選出救點(diǎn)的過(guò)程結(jié)束.否則，跳到（2）.

2）計(jì)算Av表中各出救點(diǎn)對(duì)災(zāi)區(qū)需求的滿(mǎn)足能力.

3）計(jì)算各個(gè)出救點(diǎn)被選中后，災(zāi)區(qū)新的時(shí)間限制及時(shí)間限制內(nèi)可選擇出救點(diǎn)的個(gè)數(shù).

4）將Av表中各個(gè)出救點(diǎn)的序號(hào)按照它們的滿(mǎn)足能力從大到小進(jìn)行排序，得到各個(gè)出救點(diǎn)的排名，對(duì)于排名相同的出救點(diǎn)，把q［i]較大的放在前面.首先將排名第一的出救點(diǎn)的序號(hào)放入Can表，并令

如果

則將排名第二的出救點(diǎn)的序號(hào)放入Can表，并令

否則不將該出救點(diǎn)的序號(hào)放入到Can表，也不對(duì)qmax進(jìn)行更新.依次檢查排在后面的出救點(diǎn)，直到檢查完為止.具體過(guò)程如圖1所示.

2.3 檢驗(yàn)候選出救點(diǎn)

利用式（1）檢驗(yàn)候選出救點(diǎn)，即如果該出救點(diǎn)所在出救方案的所有出救點(diǎn)的各種物資之和要大于或等于災(zāi)區(qū)對(duì)所有物資的需求，則此出救方案是可行的.

圖1 候選出救點(diǎn)選擇流程

2.4 災(zāi)區(qū)的物資需求和時(shí)間限制的更新

假如選擇Ai作為出救點(diǎn)，則對(duì)參數(shù)作如下調(diào)整：

更新只對(duì)該出救點(diǎn)下一層的下一個(gè)出救點(diǎn)有效，對(duì)該出救點(diǎn)同一層的出救點(diǎn)無(wú)效.

2.5 算法流程

算法流程如圖2所示.

圖2 考慮連續(xù)消耗的多出就點(diǎn)、多物資應(yīng)急調(diào)度算法流程

3 實(shí)例分析

假設(shè)A處發(fā)生自然災(zāi)害，需要5種物資X1，X2，…，X5的數(shù)量分別為2 000、300、50、4 200和1 600，其消耗速度分別為400、28、8、500和240，并要求在25個(gè)時(shí)間單位內(nèi)到達(dá).A1，A2，…，A6為受災(zāi)地區(qū)A附近的6個(gè)物資儲(chǔ)備倉(cāng)庫(kù).它們到A的最短時(shí)間分別為28、21、23、29、39和44.各個(gè)出救點(diǎn)擁有各種物資的數(shù)量見(jiàn)表1.

表1 各個(gè)出救點(diǎn)擁有各種物資的數(shù)量

根據(jù)文獻(xiàn)［6]中算法選取的第1個(gè)出救點(diǎn)為A2，不能滿(mǎn)足災(zāi)區(qū)的需求；選取的第2個(gè)出救點(diǎn)為A3，還是不能滿(mǎn)足災(zāi)區(qū)需求；選取的第3個(gè)出救點(diǎn)為A4，可滿(mǎn)足災(zāi)區(qū)的需求量.

最終選擇的出救點(diǎn)有3個(gè)，分別為出救點(diǎn)A2、出救點(diǎn)A3和出救點(diǎn)A4.最終出救方案為

根據(jù)本文中算法選取的第1層非劣候選出救點(diǎn)分別為A2和A3，都不能滿(mǎn)足災(zāi)區(qū)需求；第2層以選A2為前提的非劣出救點(diǎn)只有一個(gè)，即A3，還是不能滿(mǎn)足災(zāi)區(qū)的需求；第2層以選取A3為前提的第1個(gè)非劣出救點(diǎn)為A1，可滿(mǎn)足災(zāi)區(qū)需求.

最終選擇的出救點(diǎn)有2個(gè)，分別為出救點(diǎn)A3和出救點(diǎn)A1.最終出救方案為

顯然，本算法能有效地解決物資連續(xù)消耗的的多出救點(diǎn)、多物資應(yīng)急調(diào)度的問(wèn)題.而且在此實(shí)例中本算法找到的最優(yōu)方案選擇的出救點(diǎn)的個(gè)數(shù)，要少于文獻(xiàn)［6]中多出救點(diǎn)、多物資應(yīng)急調(diào)度算法找到的最優(yōu)方案，并且本算法通過(guò)尋找非劣出救點(diǎn)的方法，大大減少了所需要考慮的出救方案的個(gè)數(shù).

由本算法的計(jì)算過(guò)程可知它考慮的所有方案中已包含了文獻(xiàn)［6]中的算法找到的最優(yōu)方案.所以該算法找到的方案一定不會(huì)比文獻(xiàn)［6]中的算法找到的最優(yōu)方案差，并且由本實(shí)例可以看出在某些多出救點(diǎn)、多物資應(yīng)急調(diào)度任務(wù)中本算法找到的方案還會(huì)相對(duì)較好.所以本文中的多出救點(diǎn)、多物資應(yīng)急調(diào)度算法要優(yōu)于文獻(xiàn)［6]中的算法.

4 結(jié) 語(yǔ)

本文提出了一種考慮連續(xù)消耗的多出救點(diǎn)、多物資應(yīng)急調(diào)度算法.總體上，該算法在出救點(diǎn)的滿(mǎn)足能力與它們對(duì)時(shí)間限制的放寬程度呈反相關(guān)，滿(mǎn)足能力較強(qiáng)的出救點(diǎn)離災(zāi)區(qū)較遠(yuǎn)時(shí)，能比文獻(xiàn)［6]中的應(yīng)急調(diào)度算法得出更好的出救方案.雖然本算法利用非劣解的概念，一定程度上縮小了搜索范圍，但是當(dāng)大部分出救點(diǎn)的滿(mǎn)足能力與它們對(duì)時(shí)間限制的放寬程度呈反相關(guān)時(shí)，利用尋找非劣出救點(diǎn)的方法縮小搜索范圍的效果可能會(huì)比較差.而且當(dāng)出救點(diǎn)的個(gè)數(shù)較多時(shí)，要考慮的候選出救方案可能會(huì)很多，使得本算法尋找出最優(yōu)方案的時(shí)間可能會(huì)比較長(zhǎng).如何在不丟失最優(yōu)方案的同時(shí)，進(jìn)一步縮小算法搜索的范圍，提高算法的效率，還值得進(jìn)一步研究.

［1]高本河，伍慧飛.多資源調(diào)度中應(yīng)急物流出救點(diǎn)最少問(wèn)題的優(yōu)化［J].物流技術(shù)，2009，28（1）：68－69，74.

［2]胡飛虎，耿澤飛，陳慧敏，等.多資源組合多目標(biāo)應(yīng)急調(diào)度問(wèn)題的研究［J].控制管理，2009，7（3）：9－10，199.

［3]李周清，馬祖軍.區(qū)域救援物資中轉(zhuǎn)調(diào)度的多目標(biāo)優(yōu)化問(wèn)題研究［J].計(jì)算機(jī)工程與應(yīng)用，2010，46（12）：28－31.

［4]Suleyman T，William A W.The Emerging Area of E－mergency Management and Engineering［J].IEE Transaction on Engineering Managemen，1998，45（2）：103－105.

［5]Barbarosoglu G，Arda Y.A Two－stage Stochastic Programming Framework for Transportation Planning in Disaster Response［J].Journal of the Operational Research Society，2004，55：43－53.

［6]柴秀榮，王儒敬.多出救點(diǎn)、多物資應(yīng)急調(diào)度算法研究［J].計(jì)算機(jī)工程與應(yīng)用，2010，46（6）：224－226.