面向脉冲需求的应急资源调度方法

面向脉冲需求的应急资源调度方法

众所周知，时间紧张是应急管理的一个最显著特征。决策者应在最短的时间内完成应急救援计划的制定和资源计划的决策。应急活动总是伴随着资源的消耗。根据agu等人的研究，通过脉冲播种方法，任何接收器都可以控制传染病的传播。确保每个脉冲的需要在感染前能够满足脉冲的需要，应急活动不受应急资源供应不足的影响。为了应对传染病的疾病，通常很难通过一次性资源计划来控制传染病的传播。因此，有效控制传染病传播一直是学术界研究的重点。Shulgin等通过分析SIR模型,也得出同样的结论.文献在研究传染病扩散问题时,都认为应用脉冲接种方法来控制传染病的扩散比采用一次性接种方法更有效,更有实际意义.Marc等应用动态系统理论研究了具有脉冲接种的传染病问题,研究表明脉冲接种可以使传染病扩散有效收敛.Meng等研究了一类新的具有潜伏期延迟和非线性扩散的SEIRS脉冲接种模型,并给出了已有的应急资源调度满足这种脉冲需求的充要条件.Gao等分析了具有延迟脉冲接种的SIR模型,提出脉冲接种比例小于某临界值时无法有效地控制疾病扩散.Gakkhar等研究了具有非常规扩散比率的SIRS脉冲接种模型,给出了脉冲接种全局稳定的条件和超临界分叉的阈值.因此,在传染病灾害发生后,只要通过合理的资源调度,使得到达的应急资源量在每次脉冲需求来临前满足需求即可有效地控制传染病扩散.目前,国内学者有关应急物流的研究更多地集中在一次性资源调度和基于连续消耗的资源调度方面,Tzeng等研究了具有脉冲特性的应急资源调度问题,构建了一个多目标规划模型,并将应急脉冲需求的满意度纳入了应急调度模型.Sheu针对关键救援期中响应紧急物资需求的应急物流协同调度问题,提出了一种混合模糊聚簇优化方法.何健敏等针对应急系统多点出救问题的特点,引入了连续可行方案的概念,并提出了以最早应急开始时间为目标的数学模型及相应的求解算法,得出了一些具有启发性的结论.本文在此基础上,充分考虑生物恐怖袭击或传染病爆发等特殊应急救援情况下,一次性的资源调度很难完全满足实际的各种应急需求,而基于连续消耗的资源调度又过于繁杂且成本太高的实际情况,提出面向脉冲需求的应急资源调度问题.本文首先建立了具有脉冲需求的应急资源调度模型,给出了相关理论研究分析.在满足应急资源脉冲需求的基础上,着重考虑在资源调度研究过程中应急时间最早、出救点数最少的情况并给出求解算法,同时从理论上进行归纳证明.最后,应用一个简单的算例验证模型的有效性.1tn把应急资源量tn限定到资源应急能力tn设已知应急资源需求点为A,应急资源需求的脉冲周期为T,每个脉冲周期的需求量为P1,P2,…,Pl,其中脉冲周期数为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(φ)表示方案φ的出救点数,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可知,在脉冲资源需求下,考虑出救点数最少比考虑应急时间最早更有实际意义,因此,本文将进一步研究出救点数最少的资源调度问题.算法2出救点数最少的算法.①对时间和周期进行排序得到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则得出救点数最少的方案为φ=(Ai1,xi1,ti1),(Ai2,xi2,ti2),…,Aik,∑j=1lΡj-∑c=1k-1xic,tik)}(6)出救点数为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就是所需要的出救点数最少的方案,同时Tmin(φ)=ti1,Tmax(φ)=tik,T(φ)=tik-ti1,N(φ)=k.为了验证算法2的有效性,本文将从理论上进一步证明这个结论.定理3算法2得到的结果是出救点数最少的方案.证明令Ii表示脉冲数为i条件下的出救点下标代码的集合,N(Ii)表示集合Ii中元素的个数,N(Pi)表示满足i次脉冲需求的最少出救点数,下面用数学归纳法证明.假设只有一次脉冲,即只是一次性的需求,此时l=1,通过算法得到的出救点数为N(I1).首先由算法2中步骤④可知∀x′∈{xii∈I1}和∀x″∈{x1,x2,…,xj1},有x′>x″,又因为有∑i∈Ι1xi>Ρ1,所以N(P1)≤N(I1);同时要使得出救点数最少,必定在{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获得的方案φ是出救点数最少的方案,为N(I1).假设有α次脉冲,即当l=α时,上述结论成立,即当出救点数为N(Iα)时,方案为φα=(Ai1,xi1,ti1),(Ai2,xi2,ti2),…,Aik,∑j=1αΡj-∑m=1Ν(φα)-1xim,tik)}(7)当l=α+1时,对于前α次调度需求,根据算法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得到的结果是出救点数最少的方案.同时从证明过程和算法2易知:Tmin(φ)=ti1,Tmax(φ)=tik,T(φ)=tik-ti1,N(φ)=k.证毕.3预调方案证明假设应急资源需求脉冲周期是2,需求脉冲次数是4,需求量分别为20,16,13,10,各应急资源供应点数据如表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得到出救点数最少的调度方案为φ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