面向脈沖需求的應急資源調度方法

面向脈沖需求的應急資源調度方法

眾所周知，時間緊張是應急管理的一個最顯著特征。決策者應在最短的時間內完成應急救援計劃的制定和資源計劃的決策。應急活動總是伴隨著資源的消耗。根據(jù)agu等人的研究，通過脈沖播種方法，任何接收器都可以控制傳染病的傳播。確保每個脈沖的需要在感染前能夠滿足脈沖的需要，應急活動不受應急資源供應不足的影響。為了應對傳染病的疾病，通常很難通過一次性資源計劃來控制傳染病的傳播。因此，有效控制傳染病傳播一直是學術界研究的重點。Shulgin等通過分析SIR模型,也得出同樣的結論.文獻在研究傳染病擴散問題時,都認為應用脈沖接種方法來控制傳染病的擴散比采用一次性接種方法更有效,更有實際意義.Marc等應用動態(tài)系統(tǒng)理論研究了具有脈沖接種的傳染病問題,研究表明脈沖接種可以使傳染病擴散有效收斂.Meng等研究了一類新的具有潛伏期延遲和非線性擴散的SEIRS脈沖接種模型,并給出了已有的應急資源調度滿足這種脈沖需求的充要條件.Gao等分析了具有延遲脈沖接種的SIR模型,提出脈沖接種比例小于某臨界值時無法有效地控制疾病擴散.Gakkhar等研究了具有非常規(guī)擴散比率的SIRS脈沖接種模型,給出了脈沖接種全局穩(wěn)定的條件和超臨界分叉的閾值.因此,在傳染病災害發(fā)生后,只要通過合理的資源調度,使得到達的應急資源量在每次脈沖需求來臨前滿足需求即可有效地控制傳染病擴散.目前,國內學者有關應急物流的研究更多地集中在一次性資源調度和基于連續(xù)消耗的資源調度方面,Tzeng等研究了具有脈沖特性的應急資源調度問題,構建了一個多目標規(guī)劃模型,并將應急脈沖需求的滿意度納入了應急調度模型.Sheu針對關鍵救援期中響應緊急物資需求的應急物流協(xié)同調度問題,提出了一種混合模糊聚簇優(yōu)化方法.何健敏等針對應急系統(tǒng)多點出救問題的特點,引入了連續(xù)可行方案的概念,并提出了以最早應急開始時間為目標的數(shù)學模型及相應的求解算法,得出了一些具有啟發(fā)性的結論.本文在此基礎上,充分考慮生物恐怖襲擊或傳染病爆發(fā)等特殊應急救援情況下,一次性的資源調度很難完全滿足實際的各種應急需求,而基于連續(xù)消耗的資源調度又過于繁雜且成本太高的實際情況,提出面向脈沖需求的應急資源調度問題.本文首先建立了具有脈沖需求的應急資源調度模型,給出了相關理論研究分析.在滿足應急資源脈沖需求的基礎上,著重考慮在資源調度研究過程中應急時間最早、出救點數(shù)最少的情況并給出求解算法,同時從理論上進行歸納證明.最后,應用一個簡單的算例驗證模型的有效性.1tn把應急資源量tn限定到資源應急能力tn設已知應急資源需求點為A,應急資源需求的脈沖周期為T,每個脈沖周期的需求量為P1,P2,…,Pl,其中脈沖周期數(shù)為l,設A1,A2,…,An表示n個應急資源供應點(可行出救點),Ai的資源可用量為xi(xi>0),且n∑i=1xi>l∑j=1Ρj,從Ai將應急資源送到A所需時間為ti(ti>0),不防設t1≤t2≤…≤tn,則任意方案φ可以表示為φ={(Ai1,x′i1,ti1),(Ai2,x′i2,ti2),…,(Aim,x′im,tim)}(1)式中,0<x′ik≤xik表示該點所供給的應急資源量不超過其資源可用量;i1,i2,…,im(m≤n)為1,2,…,n的一個子排列,則存在C1n+C2n+…+Cnn=2n-1種可能.如果對?q<l,則稱在保證∑m∈{k|tik<qΤ}x′im>q∑j=1Ρj的情況下資源調度問題稱為脈沖消耗應急問題.設N(φ)表示方案φ的出救點數(shù),Tmin(φ)表示最早應急調度開始時間,Tmax(φ)表示最遲應急調度開始時間,T(φ)=Tmax(φ)-Tmin(φ)為方案的應急活動時間,其中Tmin(φ)=min{ti1,ti2,…,tim},Tmax(φ)=max{ti1,ti2,…,tim},即脈沖消耗首先要保證在每個脈沖來臨之前有足夠的資源可供消耗.2最早應急調度方案定義1若調度方案φ={(Ai1,x′i1,ti1),(Ai2,x′i2,ti2),…,(Aim,x′im,tim)}可行,則對于?k≤l,有∑{m|tim<kΤ}x′im≥k∑j=1Ρj,反之亦成立.定義2若已有資源可以滿足調度需求,則存在一個可行的調度方案,反之亦成立.定理1若在已經排好序的時間序列中插入周期的時間:t1≤t2≤…≤tc1<T≤tc1+1≤tc1+2≤…≤tc2<2T≤…≤tcl<lT成立,則已有資源滿足調度需求的充要條件為:對?k<l,有∑{i|i≤ck}xi≥k∑j=1Ρj(2)證明①充分性:對?k<l,有∑{i|i≤ck}xi≥k∑j=1Ρj,只需取方案φ={(A1,x1,t1),(A2,x2,t2),…,(Acl,xcl,tcl)}即可.②必要性:已有資源滿足調度需求,則存在一個可行的調度方案,令其為φ*={(As1,x′s1,ts1),(As2,x′s2,ts2),…,(Asm,x′sm,tsm)}(3)式中,0≤x′si≤xsi,i=1,2,…,m表示該點所供給的應急資源量不超過其資源可用量,s1,s2,…,sm(m≤n)為1,2,…,n的一個子排列.由定義1知∑{m|tsm<kΤ}x′sm≥k∑j=1Ρj,又x′sm≤xsm,tsm≤tck<kT.則對?k<l,有∑{i|i≤ck}xi≥∑{m|tsm<kΤ}xsm≥∑{m|tsm<kΤ}x′sm≥k∑j=1Ρj,即有∑{i|i≤ck}xi≥k∑j=1Ρj.證畢.定理2若已有資源滿足資源調度需求,則最早應急調度方案為φ={(A1,x1,t1),(A2,x2,t2),…,(Am-1,xm-1,tm-1),(Am,x′m,tm)}(4)式中,tm≤tcl,x1>0,x2>0,?,xm-1>0,x′m>0,x′m=l∑j=1Ρj-m-1∑i=1xi,并且有m∑i=1xi≥l∑j=1Ρj>m-1∑i=1xi.證明首先,由條件易知Tmin(φ)=t1,T(φ)=tm-t1,Tmax(φ)=tm.因為t1=min{t1,t2,…,tn},所以,此方案為最早應急調度方案.其次,由于方案φ滿足需求,所以m∑i=1xi≥l∑j=1Ρj,令φ*為任意一個滿足調度需求的調度方案,因為x′m>0,所以存在l∑j=1Ρj>m-1∑i=1xi,即前面m-1個出救點無法滿足調度需求,任意滿足最早調度時間大于等于tm,即min{Tmax(φ*)}≥tm,所以φ為最早應急調度方案,并且有m∑i=1xi≥l∑j=1Ρj>m-1∑i=1xi.證畢.從上面的證明中可以找到應急時間最早的算法如下:算法1應急時間最早的算法.①對已有的時間和周期進行排序得到t1<t2<…<tc1<T≤tc1+1<tc1+2<…<tc2<2T≤…<tcl<lT②判斷?k<l,∑{i|i≤ck}xi≥k∑j=1Ρj是否成立,若等式成立,轉③;否則,調度失敗,退出.③計算m,使得m∑i=1xi≥l∑j=1Ρj>m-1∑i=1xi,則調度方案為φ=(A1,x1,t1),(A2,x2,t2),…,Am,l∑j=1Ρj-m-1∑i=1xi,tm)}(5)式(5)即為通過算法1所得到的應急時間最早方案.同時Tmin(φ)=t1,Tmax(φ)=tm,T(φ)=tm-t1,N(φ)=m.在脈沖需求的資源調度中,已經考慮了資源的時間性,即脈沖周期,只要調度的資源在一定時間內能夠滿足需求,則說明調度成功.由定義1可知,在脈沖資源需求下,考慮出救點數(shù)最少比考慮應急時間最早更有實際意義,因此,本文將進一步研究出救點數(shù)最少的資源調度問題.算法2出救點數(shù)最少的算法.①對時間和周期進行排序得到t1<t2<…<tc1<T≤tc1+1<tc1+2<…<tc2<2T≤…<tcl<lT②判斷?k<l,∑{i|i≤ck}xi≥k∑j=1Ρj是否成立,若等式成立,轉③;否則,調度失敗,退出.③令k=1,Ttotal=0,I=?.④求解ik:xik=maxxii∈{c|tc<kΤ,c?Ι}.⑤若Τtotal+xik≥∑j=1lΡj則得出救點數(shù)最少的方案為φ=(Ai1,xi1,ti1),(Ai2,xi2,ti2),…,Aik,∑j=1lΡj-∑c=1k-1xic,tik)}(6)出救點數(shù)為N(I)=k,否則令Ttotal=Ttotal+xik,I=I+{ik}轉⑥.⑥求m:若∑j=1mΡj>Τtotal≥∑j=1m-1Ρj,則令k=m,轉④.通過算法2得到的方案φ=(Ai1,xi1,ti1),(Ai2,xi2,ti2),…,Aik,∑j=1lΡj-∑c=1k-1xic,tik就是所需要的出救點數(shù)最少的方案,同時Tmin(φ)=ti1,Tmax(φ)=tik,T(φ)=tik-ti1,N(φ)=k.為了驗證算法2的有效性,本文將從理論上進一步證明這個結論.定理3算法2得到的結果是出救點數(shù)最少的方案.證明令Ii表示脈沖數(shù)為i條件下的出救點下標代碼的集合,N(Ii)表示集合Ii中元素的個數(shù),N(Pi)表示滿足i次脈沖需求的最少出救點數(shù),下面用數(shù)學歸納法證明.假設只有一次脈沖,即只是一次性的需求,此時l=1,通過算法得到的出救點數(shù)為N(I1).首先由算法2中步驟④可知?x′∈{xii∈I1}和?x″∈{x1,x2,…,xj1},有x′>x″,又因為有∑i∈Ι1xi>Ρ1,所以N(P1)≤N(I1);同時要使得出救點數(shù)最少,必定在{Aii∈I1}中選取;其次通過算法2中步驟⑥還可得到?x∈{xii∈I1},有∑xi∈{xi|i∈Ι1}-{x}xi<Ρ1,在{xii∈I1}中去掉任何一個出救點都不可能滿足資源需求,即N(P1)>N(I1)-1,N(P1)≥N(I1),所以N(P1)=N(I1),而且通過算法2獲得的方案φ是出救點數(shù)最少的方案,為N(I1).假設有α次脈沖,即當l=α時,上述結論成立,即當出救點數(shù)為N(Iα)時,方案為φα=(Ai1,xi1,ti1),(Ai2,xi2,ti2),…,Aik,∑j=1αΡj-∑m=1Ν(φα)-1xim,tik)}(7)當l=α+1時,對于前α次調度需求,根據(jù)算法2中步驟⑥可以得到滿足前α次調度的方案為φ′α={(Ai1,xi1,ti1),(Ai2,xi2,ti2),…,(Aik,xik,tik)}(8)當∑m=1kxim≥∑j=1α+1Ρi,此時的調度方案為φα+1=(Ai1,xi1,ti1),(Ai2,xi2,ti2),…,Aik,∑j=1α+1Ρj-∑m=1Ν(φα+1)-1xim,tik)}(9)當∑m=1kxim<∑j=1α+1Ρj時,由算法2進一步得到Iα+1=Iα+I′,其中I′是通過算法得到的點的下標.由算法2知,?x′∈I′和?x″∈{x1,x2,…,xjα+1}-Iα+1,有x′>x″,要滿足多出來的需求必定在I′選擇出救點,即總的出救點在Iα+1中選擇,有N(Iα+1)≥N(Pα+1);其次,由算法2步驟⑥知:?x∈Iα+1,有∑xi∈{xi|i∈Ια+1}-{x}xi<∑j=1α+1Ρj,因此N(Pα+1)≥N(Iα+1),所以可以進一步得到:N(Pα+1)=N(Iα+1),即N(Iα+1),當l=α+1時結論也成立.綜上所述:算法2得到的結果是出救點數(shù)最少的方案.同時從證明過程和算法2易知:Tmin(φ)=ti1,Tmax(φ)=tik,T(φ)=tik-ti1,N(φ)=k.證畢.3預調方案證明假設應急資源需求脈沖周期是2,需求脈沖次數(shù)是4,需求量分別為20,16,13,10,各應急資源供應點數(shù)據(jù)如表1所示.首先驗證式(2):15+10+5=30>2030+12+7=49>36=20+1649+10+12=71>49=36+1371+7+8=86>59=49+10所以,已有資源可以滿足資源調度的需求.通過算法1得到應急時間最早調度方案為φ1={(A1,15,1),(A2,10,1),(A3,5,1),(A4,12,2),(A5,7,3),(A6,10,4)}式中,Tmin(φ1)=1,Tmax(φ1)=4,T(φ1)=4-1=3,N(φ1)=6.通過算法2得到出救點數(shù)最少的調度方案為φ2={(A1,15,1),(A2,10,1),(A4,12,2),(A7,12,5),(A6,10,4)}式中,Tmin(φ2)=1,Tmax(φ2)=5,T(φ2)=5-1=4,N(φ2)=5.通過上述簡單的算例驗證了本文提出的2