災(zāi)害應(yīng)急救援中的物資分配調(diào)度問題

災(zāi)害應(yīng)急救援中的物資分配調(diào)度問題

應(yīng)急是指在特定地區(qū)發(fā)生的、規(guī)模重大、對社會(huì)產(chǎn)生重大影響的緊急情況和災(zāi)難，如自然災(zāi)害和公共衛(wèi)生事件。突發(fā)事件發(fā)生后,由于人們的正常生活被中斷,生存所必需的資源遭到破壞,所以,在事件發(fā)生地點(diǎn)需在短時(shí)間內(nèi)進(jìn)行大量資源補(bǔ)充和求助,以進(jìn)行傷員求助、衛(wèi)生防疫和災(zāi)后重建等,從而產(chǎn)生應(yīng)急環(huán)境下的救災(zāi)物資分配調(diào)度問題。由于合理及時(shí)地分配調(diào)度救災(zāi)物資可以在很大程度上緩解災(zāi)情,保障人民群眾的生命財(cái)產(chǎn)安全,因此,對于救災(zāi)物資的分配調(diào)度進(jìn)行研究有著極為重要的現(xiàn)實(shí)意義。國內(nèi)外關(guān)于救災(zāi)物資調(diào)度方法已經(jīng)開展了一些相關(guān)研究。Knott研究了應(yīng)急管理中大規(guī)模救災(zāi)物資的分配問題,并使用了基于知識的推理技術(shù)求解該問題。Chen等研究了以受災(zāi)點(diǎn)系統(tǒng)損失最小為目標(biāo)的救災(zāi)物資分配模型。Pan等以資源的連續(xù)消耗為背景,提出了一個(gè)多目標(biāo)的應(yīng)急資源分配模型。模型中考慮了每個(gè)出救點(diǎn)的運(yùn)輸能力約束,并給出了一個(gè)基于粒子群算法的優(yōu)化算法。Wang等研究了對受災(zāi)點(diǎn)的救災(zāi)物資分配最優(yōu)計(jì)劃進(jìn)行調(diào)整的算法。Ozdamar等研究了在物資數(shù)量有限、災(zāi)區(qū)需求物資數(shù)量已知情況下的的救災(zāi)物資運(yùn)輸調(diào)度問題。Fiedrich等研究了在時(shí)間、救災(zāi)物資數(shù)量以及質(zhì)量有限的情況下,以死亡人數(shù)最少為目標(biāo),在災(zāi)情后向受災(zāi)地點(diǎn)分配和運(yùn)輸救災(zāi)物資的優(yōu)化模型。Barbarosoglu等建立了應(yīng)急救災(zāi)物資運(yùn)輸?shù)膬呻A段隨機(jī)規(guī)劃模型。Sheu提出了一種混合模糊聚類的優(yōu)化算法來解決救災(zāi)物資分配問題。Yi等使用蟻群優(yōu)化算法解決救災(zāi)活動(dòng)中的物流問題。劉春林等研究了物資需求約束條件下多出救點(diǎn)的緊急物資調(diào)度問題。根據(jù)連續(xù)應(yīng)急問題的特點(diǎn),給出了應(yīng)急時(shí)間最早前提下出救點(diǎn)數(shù)目最少以及限制期條件下出救點(diǎn)數(shù)目最少的應(yīng)急模型。戴更新等根據(jù)多資源情況下應(yīng)急調(diào)度問題的特點(diǎn),建立了多資源應(yīng)急調(diào)度問題的數(shù)學(xué)模型,利用現(xiàn)有單資源調(diào)度問題的研究成果,提出了連續(xù)可行方案的概念,實(shí)現(xiàn)多資源應(yīng)急調(diào)度問題的求解。劉春林等研究了出救點(diǎn)到應(yīng)急地點(diǎn)所需時(shí)間為常數(shù)或區(qū)間數(shù)時(shí)多出救點(diǎn)組合優(yōu)化方案的求取問題;此外,還研究了運(yùn)用模糊優(yōu)化方法求解多出救點(diǎn)組合模型的問題。當(dāng)前研究多是考慮在單個(gè)受災(zāi)點(diǎn)的應(yīng)急情況,而在實(shí)際的突發(fā)事件應(yīng)急處理中,受災(zāi)點(diǎn)往往是多個(gè)。如2008年的汶川地震,四川甘肅等省份有多處受災(zāi)。此外,現(xiàn)有研究很少考慮救災(zāi)物資在多個(gè)受災(zāi)點(diǎn)之間的分配和調(diào)度問題,以及滿足各受災(zāi)點(diǎn)對不同種類救災(zāi)物資的需求等問題。因此,本文基于應(yīng)急管理中的實(shí)際需求,提出了一種新的面向多受災(zāi)點(diǎn)的救災(zāi)物資分配調(diào)度模型。1問題描述1.1連續(xù)時(shí)積b的優(yōu)化模型本文研究的救災(zāi)物資分配調(diào)度問題可具體描述如下:①災(zāi)害發(fā)生時(shí)的受災(zāi)點(diǎn)集合為A.有一個(gè)出救點(diǎn)S(相當(dāng)于救災(zāi)物資集散中心)為各受災(zāi)點(diǎn)提供救災(zāi)物資。③共有m種救災(zāi)物資,受災(zāi)點(diǎn)a∈A對第j種救災(zāi)物資的需求量為Daj.③設(shè)出救點(diǎn)中的所有救災(zāi)物資集合為M,第j種救災(zāi)物資的集合為Mj(假設(shè)集合M中的物資足夠滿足受災(zāi)點(diǎn)的需求)。對于每件救災(zāi)物資k∈M,均有一個(gè)體積sk,此外,考慮到各種救災(zāi)物資是由全國各地運(yùn)輸?shù)匠鼍赛c(diǎn)S,故而救災(zāi)物資有一個(gè)到達(dá)時(shí)間rk.④所有救災(zāi)物資組成批后由救災(zāi)車隊(duì)運(yùn)往不同的受災(zāi)點(diǎn)。設(shè)所有批的集合為B,救災(zāi)車隊(duì)集合為L,由車隊(duì)l∈L運(yùn)輸?shù)呐蠟锽l.由于車隊(duì)一次的運(yùn)輸量有限,故任意一批b∈B的總體積sb不能超過車隊(duì)的運(yùn)輸量C(為簡化模型,這里假設(shè)所有車隊(duì)具有相同的運(yùn)輸量)。此外,批中所有物資到達(dá)后才能開始運(yùn)輸,即批b的可用時(shí)間RTb=max{rk|k∈b}。⑤車隊(duì)每次運(yùn)輸一批救災(zāi)物資到受災(zāi)點(diǎn)。從出救點(diǎn)S到受災(zāi)點(diǎn)a的運(yùn)輸時(shí)間為ta.車隊(duì)只有完成前一批的運(yùn)輸任務(wù)后才可以開始下一批物資的運(yùn)輸,并且下一批物資要全部到達(dá)出救點(diǎn)S才可以運(yùn)輸。記批b的開始運(yùn)輸時(shí)間為STb,完成運(yùn)輸時(shí)間為CTb,則有CTb=STb+ta(若批b被運(yùn)往受災(zāi)點(diǎn)a)。優(yōu)化目標(biāo)為滿足所有受災(zāi)點(diǎn)物資需求的時(shí)間最小。該問題的數(shù)學(xué)模型可描述如下:minCΤmax=maxb∈B{CΤb}(1)s.t.∑b∈Bxkb=1,?k∈Μ(2)∑l∈L|Bl|∑n=1ylbn=1,?b∈B(3)∑a∈Azka=1,?k∈Μ(4)∑k∈Μskxkb≤C,?b∈B(5)RΤb≥rkxkb,?k∈Μ,b∈B(6)SΤb≥RΤb,?b∈B(7)SΤb′≥CΤb,(?b,b′∈Bl)∩(?n≤|Bl|,n∑i=1ylbi≥n∑i=1ylb′i)(8)CΤb=SΤb+ta,?b∈B(9)∑k∈Μjzka≥Daj,?a∈A,j=1,?,m(10)xkb,ylbn,zka∈{0,1},?k∈Μ,b∈B,l∈L,n=1,?,|Bl|,a∈A(11)在該模型中,式(1)為目標(biāo)函數(shù)。式(2)保證每一份救災(zāi)物資只能被分到一個(gè)批中。式(3)保證每個(gè)批只能由一個(gè)車隊(duì)運(yùn)輸,并且有一個(gè)特定的次序。式(4)確保每批物資只能被運(yùn)送到一個(gè)受災(zāi)點(diǎn)。式(5)為批的體積約束。在式(6)中,RTb表示批的準(zhǔn)備時(shí)間,其值由批中物資的最大到達(dá)時(shí)間決定。式(7)表示當(dāng)批b中所有物資都到達(dá)出救點(diǎn)S后,批b才可以被運(yùn)輸。式(8)表示車隊(duì)只有完成了一批的運(yùn)輸工作之后才可以開始下一批的運(yùn)輸。式(9)計(jì)算出每一批完成運(yùn)輸?shù)臅r(shí)間。式(10)保證運(yùn)輸?shù)木葹?zāi)物資必須滿足受災(zāi)點(diǎn)對各種物資的需求。式(11)為決策變量。若救災(zāi)物資k被安排在批b中,則xkb=1,否則xkb=0;若批b由車隊(duì)l在第n個(gè)位次運(yùn)輸,則ylbn=1,否則ylbn=0;若救災(zāi)物資k被運(yùn)往受災(zāi)點(diǎn)a,則zka=1,否則zka=0。1.2救災(zāi)物資分配調(diào)度顯然,上述問題是一個(gè)極為復(fù)雜的組合優(yōu)化問題。實(shí)際上,我們有如下定理。定理1以滿足所有受災(zāi)點(diǎn)物資需求時(shí)間最小的救災(zāi)物資分配調(diào)度問題是強(qiáng)NP難的。證明問題的求解包括三個(gè)重要的環(huán)節(jié)。一是決定某種救災(zāi)物資被運(yùn)往哪個(gè)受災(zāi)點(diǎn),對應(yīng)于決策變量zka.二是決定救災(zāi)物資如何分批,對應(yīng)于決策變量xkb.三是如何安排車隊(duì)對各批救災(zāi)物資進(jìn)行運(yùn)輸調(diào)度,對應(yīng)于決策變量ylbn.考慮問題的一個(gè)特例,即只有一個(gè)受災(zāi)點(diǎn),一種救災(zāi)物資和有一個(gè)運(yùn)輸車隊(duì),并且所有救災(zāi)物資都在rk=0時(shí)刻到達(dá)出救點(diǎn)S.此時(shí),由于只有一個(gè)受災(zāi)點(diǎn),對于任意救災(zāi)物資k∈M均有zka=1。此外,由于只有一個(gè)車隊(duì),各批次的救災(zāi)物資均由該車隊(duì)運(yùn)輸。故而當(dāng)分批給定后,滿足所有受災(zāi)點(diǎn)物資需求時(shí)間為:CΤmax=∑b∈Bta=|B|ta(12)可以看出,此時(shí)各批救災(zāi)物資的運(yùn)輸次序與目標(biāo)函數(shù)值無關(guān)。并且由于出救點(diǎn)S到受災(zāi)點(diǎn)a的運(yùn)輸時(shí)間ta事先給定,因此目標(biāo)函數(shù)CTmax完全由批的數(shù)量|B|決定。再考慮一個(gè)箱子容量為C的裝箱問題,對于每一件救災(zāi)物資k,定義一個(gè)體積為sk的物品。于是,在這種情況下裝箱問題的最優(yōu)解即為救災(zāi)物資分配問題的最優(yōu)解。由于裝箱問題是經(jīng)典的強(qiáng)NP難問題,救災(zāi)物資分配調(diào)度問題的這一特例也是強(qiáng)NP難的。從而以滿足所有受災(zāi)點(diǎn)物資需求時(shí)間最小的救災(zāi)物資分配調(diào)度問題是強(qiáng)NP難的。2dstep1計(jì)算方法由于上述問題是強(qiáng)NP難問題,除非P=NP,否則不存在多項(xiàng)式時(shí)間的精確求解算法。而為檢驗(yàn)近似算法的性能,通常需要找出原問題最優(yōu)解的一個(gè)下界,通過該算法所得解與下界的接近程度來判斷算法優(yōu)劣,好的下界應(yīng)該盡可能接近問題的最優(yōu)解。然而,當(dāng)救災(zāi)物資被運(yùn)往的受災(zāi)點(diǎn)未知時(shí),問題的下界并不容易計(jì)算。一個(gè)可能的方案是將救災(zāi)物資松弛為單位體積并按照ERT(EarliestReleaseTime)規(guī)則分批,然后以到距離最近受災(zāi)點(diǎn)的運(yùn)輸時(shí)間來計(jì)算各批次物資的運(yùn)輸時(shí)間。但若各受災(zāi)點(diǎn)之間的運(yùn)輸時(shí)間差別較大,則該下界會(huì)遠(yuǎn)低于最優(yōu)解。注意到若救災(zāi)物資被運(yùn)往的受災(zāi)點(diǎn)事先給定,則可較為容易得到下界,先引入幾個(gè)相關(guān)概念。定義1車隊(duì)將單位體積的救災(zāi)物資運(yùn)輸一個(gè)時(shí)間單位所需的運(yùn)力,稱為一個(gè)運(yùn)輸單元。體積為sk,被運(yùn)往受災(zāi)點(diǎn)a的救災(zāi)物資需要消耗sk·ta個(gè)運(yùn)輸單元。定義2車隊(duì)l在t時(shí)刻承擔(dān)的運(yùn)輸單元個(gè)數(shù),稱為車隊(duì)l在t時(shí)刻的負(fù)載,記為Ll(t)。下面的算法給出了受災(zāi)點(diǎn)事先給定情況下的一個(gè)下界。其基本思想是,將對救災(zāi)物資的運(yùn)輸問題轉(zhuǎn)化為對運(yùn)輸單元的消耗問題,當(dāng)所有運(yùn)輸單元消耗完畢,則所有救災(zāi)物資也都被運(yùn)往受災(zāi)點(diǎn)。算法LowerBoundStep1:將物資集合M中的每件救災(zāi)物資k,轉(zhuǎn)化為sk·ta個(gè)運(yùn)輸單元。其中a是物資k所要運(yùn)往的受災(zāi)點(diǎn)。第h個(gè)運(yùn)輸單元的可用時(shí)間rkh=rk+|ˉ(h-1)/skˉ|?h=1,2,?,ta?sk.Step2:記H為Step1中后得到的運(yùn)輸單元集合,對H中元素按其可用時(shí)間升序排列。Step3:初始化時(shí)間t=0。設(shè)HU(t)表示在t時(shí)刻尚未可用的運(yùn)輸單元集合,令HU(0)=H;HW(t)表示t時(shí)已可用但尚未消耗的運(yùn)輸單元集合,令HW(t)=?;HP(t)表示t時(shí)正在消耗的運(yùn)輸單元集合,令HP(t)=?;HC(t)表示t時(shí)刻前已被消耗的運(yùn)輸單元集合,令HC(t)=?.Step4:將HU(t)中滿足可用時(shí)間rh=t的運(yùn)輸單元h移入集合HW(t)中。將集合HP(t)中的所有元素移入集合HC(t)。若HC(t)≠H,轉(zhuǎn)Step5。若HC(t)=H,轉(zhuǎn)Step7。Step5:將集合HW(t)中的前C|L|個(gè)運(yùn)輸單元移入集合HP(t),若集合HW(t)中的運(yùn)輸單元不足C|L|個(gè),則全部移入集合HP(t)。Step6:時(shí)間t=t+1,轉(zhuǎn)Step4。Step7:輸出時(shí)間t為問題的一個(gè)下界。為了證明算法LowerBound的輸出結(jié)果是問題的一個(gè)有效下界,先證明如下引理。引理1設(shè)X和Y分別表示問題的兩個(gè)實(shí)例,sol(X)和sol(Y)分別是問題X和Y的兩個(gè)解。記Fsol(X)(t)=t∑i=0∑l∈LLsol(X)l(i)為sol(X)中到t時(shí)刻后消耗的運(yùn)輸單元總數(shù),Fsol(Y)(t)=t∑i=0∑l∈LLsol(Y)l(i)為sol(Y)中到t時(shí)刻后消耗的運(yùn)輸單元總數(shù)。且滿足:①X和Y具有相同的運(yùn)輸單元總數(shù),即∑k∈ΜXskta=∑k∈ΜYskta.②Fsol(X)(t)≥Fsol(Y)(t),?t∈Z+.則sol(X)比sol(Y)具有更小的運(yùn)輸時(shí)間,即CTsol(X)max≤CTsol(Y)max.證明因?yàn)檐囮?duì)l在任意時(shí)刻t的負(fù)載Ll(t)非負(fù)。故Fsol(X)(t)和Fsol(Y)(t)均為Z+上的增函數(shù)。假設(shè)CTsol(X)max>CTsol(Y)max,則有:Fsol(X)(CΤsol(Y)max)<Fsol(X)(CΤsol(X)max)=∑k∈ΜXskta(13)Fsol(Y)(CΤsol(Y)max)=∑k∈ΜYskta(14)由條件①可知∑k∈ΜXskta=∑k∈ΜYskta,故Fsol(X)(CTsol(Y)max)<Fsol(Y)(CTsol(Y)max)。這與條件②中假設(shè)Fsol(X)(t)≥Fsol(Y)(t),?t∈Z+相矛盾,所以CTsol(X)max≤CTsol(Y)max.通過引理1,接下來可以證明下界算法lowerbound是有效的。定理1若救災(zāi)物資被運(yùn)往的受災(zāi)點(diǎn)事先給定,則算法lowerbound可以得到問題的一個(gè)有效下界。證明設(shè)CTLBmax是算法lowerbound得到的下界,CTOPmax是原問題的一個(gè)最優(yōu)解的值。FLB(t)為算法lowerbound中到t時(shí)刻后消耗的運(yùn)輸單元總數(shù),FOP(t)為最優(yōu)解的方案中到t時(shí)刻后消耗的運(yùn)輸單元總數(shù)。先證明FLB(t)≥FOP(t),?t∈Z+.①當(dāng)t=0時(shí):記R(t)為t時(shí)刻到達(dá)出救點(diǎn)S的救災(zāi)物資集合,則FΟΡ(0)≤min{∑k∈R(0)sk,C|L|}。由算法lowerbound中的Step1可知,R(0)中的救災(zāi)物資被轉(zhuǎn)化為∑k∈R(0)(sk?ta)個(gè)運(yùn)輸單元,且有∑k∈R(0)sk個(gè)在t=0時(shí)刻可用。故FLB(0)=min{∑k∈R(0)sk,C|L|},于是FLB(0)≥FOP(0)。②假設(shè)當(dāng)t=T時(shí)FLB(T)≥FOP(T)成立,則當(dāng)t=T+1時(shí):在任意時(shí)刻t,任意運(yùn)輸單元h∈M′總處在以下四種狀態(tài)之一:(a)運(yùn)輸單元在該時(shí)刻尚不可用;(b)運(yùn)輸單元已可用,但在該時(shí)刻未被消耗,處在等待狀態(tài);(c)運(yùn)輸單元在該時(shí)刻正在被消耗;(d)運(yùn)輸單元在該時(shí)刻已經(jīng)被消耗。四種狀態(tài)分別對應(yīng)于算法lowerbound中Step3的四個(gè)集合。若用|U|表示集合U中的元素個(gè)數(shù),則在t=T+1時(shí)刻,有下式成立:|ΗΟΡU(Τ+1)|+|ΗΟΡW(Τ+1)|+|ΗΟΡΡ(Τ+1)|+|ΗΟΡC(Τ+1)|=∑k∈Μskta(15)|ΗLBU(Τ+1)|+|ΗLBW(Τ+1)|+|ΗLBΡ(Τ+1)|+|ΗLBC(Τ+1)|=∑k∈Μskta(16)根據(jù)定義,函數(shù)F(t)為到t時(shí)刻后消耗的運(yùn)輸單元總數(shù),對于CTLBmax和CTOPmax,均有:F(Τ+1)=|ΗC(Τ+1)|+|ΗΡ(Τ+1)|=F(Τ)+|ΗΡ(Τ+1)|(17)若在t=T+1時(shí)刻,算法lowerbound中所有車隊(duì)均滿載,即|HLBP(T+1)|=C|L|。由于任何車隊(duì)負(fù)載均不超過車隊(duì)容量C,于是|HLBP(T+1)|≥|HOPP(T+1)|。由假設(shè)FLB(T)≥FOP(T),代入式(17),得FLB(T+1)≥FOP(T+1)。若在t=T+1時(shí)刻,算法lowerbound中并非所有車隊(duì)均滿載的,即|HLBP(T+1)|<C|L|。根據(jù)算法lowerbound中的Step5可知,此時(shí)已可用但尚未消耗的運(yùn)輸單元集合HLBW(T+1)必為空(否則由于車隊(duì)負(fù)載不滿,HLBW(T+1)中的運(yùn)輸單元會(huì)被移入集合HLBP(T+1)),即|HLBW(T+1)|=0。又由Step1知算法lowerbound在將救災(zāi)物資轉(zhuǎn)換為運(yùn)輸單元時(shí)保留了各運(yùn)輸單元的可用時(shí)間,故|HOPU(T+1)|=|HLBU(T+1)|,于是有:|ΗΟΡU(Τ+1)|+|ΗΟΡW(Τ+1)|≥|ΗLBU(Τ+1)|+|ΗLBW(Τ+1)|(18)將式(15)、式(16)代入上式,可得:|HOPP(T+1)|+|HOPC(T+1)|≤|HLBP(T+1)|+|HLBC(T+1)|,即FLB(T+1)≥FOP(T+1)。從而FLB(t)≥FOP(t),?t∈Z+.即引理1中的條件②滿足。又因?yàn)樗惴╨owerbound的轉(zhuǎn)化過程并沒有改變原問題中的運(yùn)輸單元數(shù),故引理1中的條件①也滿足。于是根據(jù)引理1,CTLBmax≤CTOPmax,即算法lowerbound可以得到問題的一個(gè)有效下界。3救災(zāi)物資批量分配算法由問題的模型描述可知,整體問題的求解可分為三個(gè)階段,即決定各救災(zāi)物資被運(yùn)往哪個(gè)受災(zāi)點(diǎn),對救災(zāi)物資如何分批,以及如何調(diào)度車隊(duì)對各批救災(zāi)物資進(jìn)行運(yùn)輸。將救災(zāi)物資分配到各受災(zāi)點(diǎn),有兩種不同的基本策略。一是依次滿足各救災(zāi)點(diǎn)的所有需求。對應(yīng)于現(xiàn)實(shí)中,各地點(diǎn)受災(zāi)程度不同,因此救災(zāi)工作有輕重緩急之分。但這種策略也會(huì)造成某些受災(zāi)點(diǎn)較長時(shí)間得不到救助。此外,由于是依次滿足各受災(zāi)點(diǎn)的需求,在一個(gè)時(shí)間段內(nèi),運(yùn)輸車隊(duì)會(huì)集中往相同的受災(zāi)點(diǎn)運(yùn)輸,給通往受災(zāi)點(diǎn)的交通帶來較大壓力。另外一種策略是均勻地滿足各受災(zāi)點(diǎn)的需求。這種策略考慮了緩解所有受災(zāi)點(diǎn)的災(zāi)情,但當(dāng)運(yùn)力不足時(shí),受災(zāi)嚴(yán)重的地區(qū)可能無法及時(shí)得到大量救災(zāi)物資。根據(jù)這兩種不同的策略,下面兩個(gè)啟發(fā)式算法將救災(zāi)物資分配到各受災(zāi)點(diǎn)。算法A1:依次滿足各受災(zāi)點(diǎn)的所有需求。Step1:將救災(zāi)物資集合M中的所有元素,按照其到達(dá)時(shí)間rk升序排列。即ERT(EarliestReleaseTime)規(guī)則。Step2:將受災(zāi)點(diǎn)集合A中的所有受災(zāi)點(diǎn),按照其運(yùn)輸時(shí)間ta降序排列。Step3:對于集合M中的每一個(gè)元素k,依次檢查集合A中的受災(zāi)點(diǎn)a,若受災(zāi)點(diǎn)對k所屬救災(zāi)物資類別的需求已滿足,則繼續(xù)檢查下一個(gè)受災(zāi)點(diǎn);否則將k分配給受災(zāi)點(diǎn)a.Step4:重復(fù)Step3直到所有的救災(zāi)物資都被分配完畢。算法A2:平均滿足各受災(zāi)點(diǎn)的需求。Step1:將救災(zāi)物資集合M中的所有元素,按照其到達(dá)時(shí)間rk升序排列。即ERT(EarliestReleaseTime)規(guī)則。Step2:將受災(zāi)點(diǎn)集合A中的所有受災(zāi)點(diǎn),按照其運(yùn)輸時(shí)間ta降序排列。Step3:對于集合A中的每一個(gè)元素a,依次檢查集合M中的物資k,若a對k所屬救災(zāi)物資類別的需求已滿足,則繼續(xù)檢查下一個(gè)物資;否則將k分配給受災(zāi)點(diǎn)a.Step4:重復(fù)Step3直到所有的救災(zāi)物資都被分配完畢。當(dāng)所有救災(zāi)物資被運(yùn)往的受災(zāi)點(diǎn)確定之后,接下來的任務(wù)是對救災(zāi)物資進(jìn)行分批。由于批的可用時(shí)間由該批中所有物資中最遲的到達(dá)時(shí)間決定,因此,一個(gè)理想的分批方案應(yīng)該使每批中救災(zāi)物資的到達(dá)時(shí)間盡可能接近,以避免為等待某件救災(zāi)物資的到達(dá)而推遲整個(gè)批的運(yùn)輸時(shí)間。此外,為了減少運(yùn)輸次數(shù),每批中的剩余空間應(yīng)該盡量減少。下面給出分批的兩個(gè)啟發(fā)式算法。算法B1:ERTFF(EarliestReleaseTimeFirstFit)Step1:根據(jù)救災(zāi)物資被運(yùn)往的受災(zāi)點(diǎn)不同,將救災(zāi)物資分為|A|個(gè)組。Step2:對于每一組中的所有物資,按照其到達(dá)時(shí)間rk升序排列。Step3:選擇各組中的第一件未分批物資,將其放進(jìn)第一個(gè)可以容納該物資的批中。如果當(dāng)前沒有批可以容納該物資,則創(chuàng)建一個(gè)新批。Step4:重復(fù)Step3直到所有的救災(zāi)物資都被分配到某個(gè)批中。算法B2:ERTBF(EarliestReleaseTimeBestFit)Step1:根據(jù)救災(zāi)物資被運(yùn)往的受災(zāi)點(diǎn)不同,將救災(zāi)物資分為|A|個(gè)組。Step2:對于每一組中的所有物資,按照其到達(dá)時(shí)間rk升序排列。Step3:選擇各組中的第一件為分批物資,找出所有可以容納該物資的批,并將其放入剩余空間最小的批中。如果當(dāng)前沒有批可以容納該物資,則創(chuàng)建一個(gè)新批。Step4:重復(fù)Step3直到所有的救災(zāi)物資都被分配到某個(gè)批中。算法ERTFF和ERTBF分別采用了首次適應(yīng)和最佳適應(yīng)的分批規(guī)則。一般來說,由于采用了最佳適應(yīng)的分批規(guī)則,算法ERTBF會(huì)得到較少的批數(shù),但可能會(huì)造成批中各物資的到達(dá)時(shí)間差別較大,從而推遲批的運(yùn)輸時(shí)間。而在算法ERTFF中,同一批內(nèi)的物資到達(dá)時(shí)間接近,但得到的批數(shù)會(huì)較多。最后的任務(wù)是安排各批救災(zāi)物資往受災(zāi)點(diǎn)的運(yùn)輸,下面的啟發(fā)式算法綜合考慮了各批物資的可用時(shí)間及運(yùn)輸時(shí)間。算法DispatchingRuleStep1:將批集合B中的所有的批按照其可用時(shí)間RTb升序排列。Step2:找出救災(zāi)車隊(duì)集合L中最早空閑的車隊(duì)l,即最早完成上一次運(yùn)輸任務(wù)的車隊(duì),并記錄其完成上一次任務(wù)的時(shí)間tl.Step3:將批集合中滿足RTb≤tl的所有批移動(dòng)到一個(gè)的可用的批集合Avb中。Step4:從Avb中選擇運(yùn)往最遠(yuǎn)受災(zāi)點(diǎn)的批b,將其從集合Avb中刪除,并交給車隊(duì)l運(yùn)輸。若集合Avb為空,則從批集合B中找出最早可用的批交給車隊(duì)l運(yùn)輸。Step5:重復(fù)Step2～Step4直到集合B和Avb均為空。4算例2:某本文通過隨機(jī)生成算例進(jìn)行仿真實(shí)驗(yàn)。隨機(jī)算例的生成考慮了如下要素:受災(zāi)點(diǎn)數(shù)目|A|,運(yùn)輸車隊(duì)數(shù)目|L|,出救點(diǎn)到受災(zāi)點(diǎn)的運(yùn)輸時(shí)間t,受災(zāi)物資種類m及各受災(zāi)點(diǎn)對物資的需求量Daj,救災(zāi)物資的體積s以及到達(dá)時(shí)間r.對于受災(zāi)點(diǎn)數(shù)目,設(shè)置了5個(gè)不同的值,以觀察各算法性能隨受災(zāi)點(diǎn)數(shù)目變化的趨勢。對于運(yùn)輸車隊(duì)數(shù)目,設(shè)置了高低兩個(gè)水平,分別對應(yīng)于實(shí)際救災(zāi)中運(yùn)力充足和運(yùn)力不足的情況。此外,對于救災(zāi)物資到達(dá)出救點(diǎn)的時(shí)間,按下列公式設(shè)定:rmax=RE(t)E(s)|Μ|C|L|(19)式中,rmax表示物資到達(dá)的最大時(shí)間。救災(zāi)物資的到達(dá)時(shí)間服從[0,rmax]的離散均勻分布。E(t)和E(s)分別是運(yùn)輸時(shí)間和物資尺寸的數(shù)學(xué)期望。|M|和|L|分別是總的救災(zāi)物資數(shù)量和車隊(duì)數(shù)量。C是車隊(duì)的運(yùn)輸量,在所有算例中該值均設(shè)為10。R是救災(zāi)物資到達(dá)的頻率系數(shù),當(dāng)R值較低時(shí),救災(zāi)物資在短時(shí)間內(nèi)頻繁達(dá)到出救點(diǎn),對應(yīng)于現(xiàn)實(shí)中物資集散中心救災(zāi)品充足的情況;R值較高時(shí),救災(zāi)物資到達(dá)出救點(diǎn)的時(shí)間間隔會(huì)變長,對應(yīng)于現(xiàn)實(shí)中物資集散中心救災(zāi)品相對不足的情況。各因素及其取值范圍如表1。每一類型的算例可用符號AaLbRc(a=1,…,5;b=1,2;c=1,2)來表示。例如受災(zāi)點(diǎn)數(shù)目為4,運(yùn)輸車隊(duì)數(shù)目為4,救災(zāi)物資到達(dá)頻率系數(shù)為0.5的問題可以表示成A2L2R1。實(shí)驗(yàn)中一共包括20類(5×2×2)不同的算例,每類型算例隨機(jī)產(chǎn)生10個(gè)樣本。實(shí)驗(yàn)中總共測試200個(gè)樣本。實(shí)驗(yàn)中共測試四類算法。即由不同的救災(zāi)物資分配算法和分批算法組合而成,例如算法A1B2表示首先用算法A1將救災(zāi)物資分批到各受災(zāi)點(diǎn),再使用算法B2:ERTBF進(jìn)行分批,最后用算法DispatchingRule安排運(yùn)輸車隊(duì)的調(diào)度。此外,實(shí)驗(yàn)中的下界按照如下方式得到:分別使用算法A1和A2指派救災(zāi)物資所運(yùn)往的受災(zāi)點(diǎn),然后使用算法LowerBound分別得到兩個(gè)下界LB1和LB2,最終的下界LB=max{LB1,LB2}。表2列出了各算法在不同類型算例下的結(jié)果,表中單元格的數(shù)值為某算法在10個(gè)樣本下的平均值。可以看出,在大部分算例中,各算法的性能由好到至壞分別是A1B2,A1B1,A2B2,A2B1。尤其是使用算法A1分配物資到受災(zāi)點(diǎn)明顯優(yōu)于A2。這是因?yàn)樗惴ˋ1根據(jù)物資的到達(dá)時(shí)間,逐個(gè)滿足受災(zāi)點(diǎn)的所有需求,這樣到達(dá)時(shí)間接近的物資會(huì)被運(yùn)往相同的受災(zāi)點(diǎn)。這些物資成批后,批的可用時(shí)間不會(huì)因?yàn)殚L久等待某個(gè)未到達(dá)的物資而延后,從而耽誤整個(gè)運(yùn)輸。而算法A2平均滿足各受災(zāi)點(diǎn)的需求,這會(huì)造成運(yùn)往相同受災(zāi)點(diǎn)的物資的到達(dá)時(shí)間可能有相當(dāng)大的差距,這樣成批后可能會(huì)因?yàn)榈却澄镔Y的到達(dá)而延遲整個(gè)批的運(yùn)輸。此外,算法B2也較B1有優(yōu)勢,因?yàn)槠洳捎米罴堰m應(yīng)算法生成批,其得到的總批數(shù)會(huì)小于算法B1。從而總的運(yùn)輸次數(shù)減少。為了更