灾害应急救援中的物资分配调度问题

灾害应急救援中的物资分配调度问题

应急是指在特定地区发生的、规模重大、对社会产生重大影响的紧急情况和灾难，如自然灾害和公共卫生事件。突发事件发生后,由于人们的正常生活被中断,生存所必需的资源遭到破坏,所以,在事件发生地点需在短时间内进行大量资源补充和求助,以进行伤员求助、卫生防疫和灾后重建等,从而产生应急环境下的救灾物资分配调度问题。由于合理及时地分配调度救灾物资可以在很大程度上缓解灾情,保障人民群众的生命财产安全,因此,对于救灾物资的分配调度进行研究有着极为重要的现实意义。国内外关于救灾物资调度方法已经开展了一些相关研究。Knott研究了应急管理中大规模救灾物资的分配问题,并使用了基于知识的推理技术求解该问题。Chen等研究了以受灾点系统损失最小为目标的救灾物资分配模型。Pan等以资源的连续消耗为背景,提出了一个多目标的应急资源分配模型。模型中考虑了每个出救点的运输能力约束,并给出了一个基于粒子群算法的优化算法。Wang等研究了对受灾点的救灾物资分配最优计划进行调整的算法。Ozdamar等研究了在物资数量有限、灾区需求物资数量已知情况下的的救灾物资运输调度问题。Fiedrich等研究了在时间、救灾物资数量以及质量有限的情况下,以死亡人数最少为目标,在灾情后向受灾地点分配和运输救灾物资的优化模型。Barbarosoglu等建立了应急救灾物资运输的两阶段随机规划模型。Sheu提出了一种混合模糊聚类的优化算法来解决救灾物资分配问题。Yi等使用蚁群优化算法解决救灾活动中的物流问题。刘春林等研究了物资需求约束条件下多出救点的紧急物资调度问题。根据连续应急问题的特点,给出了应急时间最早前提下出救点数目最少以及限制期条件下出救点数目最少的应急模型。戴更新等根据多资源情况下应急调度问题的特点,建立了多资源应急调度问题的数学模型,利用现有单资源调度问题的研究成果,提出了连续可行方案的概念,实现多资源应急调度问题的求解。刘春林等研究了出救点到应急地点所需时间为常数或区间数时多出救点组合优化方案的求取问题;此外,还研究了运用模糊优化方法求解多出救点组合模型的问题。当前研究多是考虑在单个受灾点的应急情况,而在实际的突发事件应急处理中,受灾点往往是多个。如2008年的汶川地震,四川甘肃等省份有多处受灾。此外,现有研究很少考虑救灾物资在多个受灾点之间的分配和调度问题,以及满足各受灾点对不同种类救灾物资的需求等问题。因此,本文基于应急管理中的实际需求,提出了一种新的面向多受灾点的救灾物资分配调度模型。1问题描述1.1连续时积b的优化模型本文研究的救灾物资分配调度问题可具体描述如下:①灾害发生时的受灾点集合为A.有一个出救点S(相当于救灾物资集散中心)为各受灾点提供救灾物资。③共有m种救灾物资,受灾点a∈A对第j种救灾物资的需求量为Daj.③设出救点中的所有救灾物资集合为M,第j种救灾物资的集合为Mj(假设集合M中的物资足够满足受灾点的需求)。对于每件救灾物资k∈M,均有一个体积sk,此外,考虑到各种救灾物资是由全国各地运输到出救点S,故而救灾物资有一个到达时间rk.④所有救灾物资组成批后由救灾车队运往不同的受灾点。设所有批的集合为B,救灾车队集合为L,由车队l∈L运输的批集合为Bl.由于车队一次的运输量有限,故任意一批b∈B的总体积sb不能超过车队的运输量C(为简化模型,这里假设所有车队具有相同的运输量)。此外,批中所有物资到达后才能开始运输,即批b的可用时间RTb=max{rk|k∈b}。⑤车队每次运输一批救灾物资到受灾点。从出救点S到受灾点a的运输时间为ta.车队只有完成前一批的运输任务后才可以开始下一批物资的运输,并且下一批物资要全部到达出救点S才可以运输。记批b的开始运输时间为STb,完成运输时间为CTb,则有CTb=STb+ta(若批b被运往受灾点a)。优化目标为满足所有受灾点物资需求的时间最小。该问题的数学模型可描述如下: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)为目标函数。式(2)保证每一份救灾物资只能被分到一个批中。式(3)保证每个批只能由一个车队运输,并且有一个特定的次序。式(4)确保每批物资只能被运送到一个受灾点。式(5)为批的体积约束。在式(6)中,RTb表示批的准备时间,其值由批中物资的最大到达时间决定。式(7)表示当批b中所有物资都到达出救点S后,批b才可以被运输。式(8)表示车队只有完成了一批的运输工作之后才可以开始下一批的运输。式(9)计算出每一批完成运输的时间。式(10)保证运输的救灾物资必须满足受灾点对各种物资的需求。式(11)为决策变量。若救灾物资k被安排在批b中,则xkb=1,否则xkb=0;若批b由车队l在第n个位次运输,则ylbn=1,否则ylbn=0;若救灾物资k被运往受灾点a,则zka=1,否则zka=0。1.2救灾物资分配调度显然,上述问题是一个极为复杂的组合优化问题。实际上,我们有如下定理。定理1以满足所有受灾点物资需求时间最小的救灾物资分配调度问题是强NP难的。证明问题的求解包括三个重要的环节。一是决定某种救灾物资被运往哪个受灾点,对应于决策变量zka.二是决定救灾物资如何分批,对应于决策变量xkb.三是如何安排车队对各批救灾物资进行运输调度,对应于决策变量ylbn.考虑问题的一个特例,即只有一个受灾点,一种救灾物资和有一个运输车队,并且所有救灾物资都在rk=0时刻到达出救点S.此时,由于只有一个受灾点,对于任意救灾物资k∈M均有zka=1。此外,由于只有一个车队,各批次的救灾物资均由该车队运输。故而当分批给定后,满足所有受灾点物资需求时间为:CΤmax=∑b∈Bta=|B|ta(12)可以看出,此时各批救灾物资的运输次序与目标函数值无关。并且由于出救点S到受灾点a的运输时间ta事先给定,因此目标函数CTmax完全由批的数量|B|决定。再考虑一个箱子容量为C的装箱问题,对于每一件救灾物资k,定义一个体积为sk的物品。于是,在这种情况下装箱问题的最优解即为救灾物资分配问题的最优解。由于装箱问题是经典的强NP难问题,救灾物资分配调度问题的这一特例也是强NP难的。从而以满足所有受灾点物资需求时间最小的救灾物资分配调度问题是强NP难的。2dstep1计算方法由于上述问题是强NP难问题,除非P=NP,否则不存在多项式时间的精确求解算法。而为检验近似算法的性能,通常需要找出原问题最优解的一个下界,通过该算法所得解与下界的接近程度来判断算法优劣,好的下界应该尽可能接近问题的最优解。然而,当救灾物资被运往的受灾点未知时,问题的下界并不容易计算。一个可能的方案是将救灾物资松弛为单位体积并按照ERT(EarliestReleaseTime)规则分批,然后以到距离最近受灾点的运输时间来计算各批次物资的运输时间。但若各受灾点之间的运输时间差别较大,则该下界会远低于最优解。注意到若救灾物资被运往的受灾点事先给定,则可较为容易得到下界,先引入几个相关概念。定义1车队将单位体积的救灾物资运输一个时间单位所需的运力,称为一个运输单元。体积为sk,被运往受灾点a的救灾物资需要消耗sk·ta个运输单元。定义2车队l在t时刻承担的运输单元个数,称为车队l在t时刻的负载,记为Ll(t)。下面的算法给出了受灾点事先给定情况下的一个下界。其基本思想是,将对救灾物资的运输问题转化为对运输单元的消耗问题,当所有运输单元消耗完毕,则所有救灾物资也都被运往受灾点。算法LowerBoundStep1:将物资集合M中的每件救灾物资k,转化为sk·ta个运输单元。其中a是物资k所要运往的受灾点。第h个运输单元的可用时间rkh=rk+|¯(h-1)/sk¯|‚h=1,2,⋯,ta⋅sk.Step2:记H为Step1中后得到的运输单元集合,对H中元素按其可用时间升序排列。Step3:初始化时间t=0。设HU(t)表示在t时刻尚未可用的运输单元集合,令HU(0)=H;HW(t)表示t时已可用但尚未消耗的运输单元集合,令HW(t)=∅;HP(t)表示t时正在消耗的运输单元集合,令HP(t)=∅;HC(t)表示t时刻前已被消耗的运输单元集合,令HC(t)=∅.Step4:将HU(t)中满足可用时间rh=t的运输单元h移入集合HW(t)中。将集合HP(t)中的所有元素移入集合HC(t)。若HC(t)≠H,转Step5。若HC(t)=H,转Step7。Step5:将集合HW(t)中的前C|L|个运输单元移入集合HP(t),若集合HW(t)中的运输单元不足C|L|个,则全部移入集合HP(t)。Step6:时间t=t+1,转Step4。Step7:输出时间t为问题的一个下界。为了证明算法LowerBound的输出结果是问题的一个有效下界,先证明如下引理。引理1设X和Y分别表示问题的两个实例,sol(X)和sol(Y)分别是问题X和Y的两个解。记Fsol(X)(t)=t∑i=0∑l∈LLsol(X)l(i)为sol(X)中到t时刻后消耗的运输单元总数,Fsol(Y)(t)=t∑i=0∑l∈LLsol(Y)l(i)为sol(Y)中到t时刻后消耗的运输单元总数。且满足:①X和Y具有相同的运输单元总数,即∑k∈ΜXskta=∑k∈ΜYskta.②Fsol(X)(t)≥Fsol(Y)(t),∀t∈Z+.则sol(X)比sol(Y)具有更小的运输时间,即CTsol(X)max≤CTsol(Y)max.证明因为车队l在任意时刻t的负载Ll(t)非负。故Fsol(X)(t)和Fsol(Y)(t)均为Z+上的增函数。假设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)。这与条件②中假设Fsol(X)(t)≥Fsol(Y)(t),∀t∈Z+相矛盾,所以CTsol(X)max≤CTsol(Y)max.通过引理1,接下来可以证明下界算法lowerbound是有效的。定理1若救灾物资被运往的受灾点事先给定,则算法lowerbound可以得到问题的一个有效下界。证明设CTLBmax是算法lowerbound得到的下界,CTOPmax是原问题的一个最优解的值。FLB(t)为算法lowerbound中到t时刻后消耗的运输单元总数,FOP(t)为最优解的方案中到t时刻后消耗的运输单元总数。先证明FLB(t)≥FOP(t),∀t∈Z+.①当t=0时:记R(t)为t时刻到达出救点S的救灾物资集合,则FΟΡ(0)≤min{∑k∈R(0)sk,C|L|}。由算法lowerbound中的Step1可知,R(0)中的救灾物资被转化为∑k∈R(0)(sk⋅ta)个运输单元,且有∑k∈R(0)sk个在t=0时刻可用。故FLB(0)=min{∑k∈R(0)sk,C|L|},于是FLB(0)≥FOP(0)。②假设当t=T时FLB(T)≥FOP(T)成立,则当t=T+1时:在任意时刻t,任意运输单元h∈M′总处在以下四种状态之一:(a)运输单元在该时刻尚不可用;(b)运输单元已可用,但在该时刻未被消耗,处在等待状态;(c)运输单元在该时刻正在被消耗;(d)运输单元在该时刻已经被消耗。四种状态分别对应于算法lowerbound中Step3的四个集合。若用|U|表示集合U中的元素个数,则在t=T+1时刻,有下式成立:|ΗΟΡU(Τ+1)|+|ΗΟΡW(Τ+1)|+|ΗΟΡΡ(Τ+1)|+|ΗΟΡC(Τ+1)|=∑k∈Μskta(15)|ΗLBU(Τ+1)|+|ΗLBW(Τ+1)|+|ΗLBΡ(Τ+1)|+|ΗLBC(Τ+1)|=∑k∈Μskta(16)根据定义,函数F(t)为到t时刻后消耗的运输单元总数,对于CTLBmax和CTOPmax,均有:F(Τ+1)=|ΗC(Τ+1)|+|ΗΡ(Τ+1)|=F(Τ)+|ΗΡ(Τ+1)|(17)若在t=T+1时刻,算法lowerbound中所有车队均满载,即|HLBP(T+1)|=C|L|。由于任何车队负载均不超过车队容量C,于是|HLBP(T+1)|≥|HOPP(T+1)|。由假设FLB(T)≥FOP(T),代入式(17),得FLB(T+1)≥FOP(T+1)。若在t=T+1时刻,算法lowerbound中并非所有车队均满载的,即|HLBP(T+1)|<C|L|。根据算法lowerbound中的Step5可知,此时已可用但尚未消耗的运输单元集合HLBW(T+1)必为空(否则由于车队负载不满,HLBW(T+1)中的运输单元会被移入集合HLBP(T+1)),即|HLBW(T+1)|=0。又由Step1知算法lowerbound在将救灾物资转换为运输单元时保留了各运输单元的可用时间,故|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中的条件②满足。又因为算法lowerbound的转化过程并没有改变原问题中的运输单元数,故引理1中的条件①也满足。于是根据引理1,CTLBmax≤CTOPmax,即算法lowerbound可以得到问题的一个有效下界。3救灾物资批量分配算法由问题的模型描述可知,整体问题的求解可分为三个阶段,即决定各救灾物资被运往哪个受灾点,对救灾物资如何分批,以及如何调度车队对各批救灾物资进行运输。将救灾物资分配到各受灾点,有两种不同的基本策略。一是依次满足各救灾点的所有需求。对应于现实中,各地点受灾程度不同,因此救灾工作有轻重缓急之分。但这种策略也会造成某些受灾点较长时间得不到救助。此外,由于是依次满足各受灾点的需求,在一个时间段内,运输车队会集中往相同的受灾点运输,给通往受灾点的交通带来较大压力。另外一种策略是均匀地满足各受灾点的需求。这种策略考虑了缓解所有受灾点的灾情,但当运力不足时,受灾严重的地区可能无法及时得到大量救灾物资。根据这两种不同的策略,下面两个启发式算法将救灾物资分配到各受灾点。算法A1:依次满足各受灾点的所有需求。Step1:将救灾物资集合M中的所有元素,按照其到达时间rk升序排列。即ERT(EarliestReleaseTime)规则。Step2:将受灾点集合A中的所有受灾点,按照其运输时间ta降序排列。Step3:对于集合M中的每一个元素k,依次检查集合A中的受灾点a,若受灾点对k所属救灾物资类别的需求已满足,则继续检查下一个受灾点;否则将k分配给受灾点a.Step4:重复Step3直到所有的救灾物资都被分配完毕。算法A2:平均满足各受灾点的需求。Step1:将救灾物资集合M中的所有元素,按照其到达时间rk升序排列。即ERT(EarliestReleaseTime)规则。Step2:将受灾点集合A中的所有受灾点,按照其运输时间ta降序排列。Step3:对于集合A中的每一个元素a,依次检查集合M中的物资k,若a对k所属救灾物资类别的需求已满足,则继续检查下一个物资;否则将k分配给受灾点a.Step4:重复Step3直到所有的救灾物资都被分配完毕。当所有救灾物资被运往的受灾点确定之后,接下来的任务是对救灾物资进行分批。由于批的可用时间由该批中所有物资中最迟的到达时间决定,因此,一个理想的分批方案应该使每批中救灾物资的到达时间尽可能接近,以避免为等待某件救灾物资的到达而推迟整个批的运输时间。此外,为了减少运输次数,每批中的剩余空间应该尽量减少。下面给出分批的两个启发式算法。算法B1:ERTFF(EarliestReleaseTimeFirstFit)Step1:根据救灾物资被运往的受灾点不同,将救灾物资分为|A|个组。Step2:对于每一组中的所有物资,按照其到达时间rk升序排列。Step3:选择各组中的第一件未分批物资,将其放进第一个可以容纳该物资的批中。如果当前没有批可以容纳该物资,则创建一个新批。Step4:重复Step3直到所有的救灾物资都被分配到某个批中。算法B2:ERTBF(EarliestReleaseTimeBestFit)Step1:根据救灾物资被运往的受灾点不同,将救灾物资分为|A|个组。Step2:对于每一组中的所有物资,按照其到达时间rk升序排列。Step3:选择各组中的第一件为分批物资,找出所有可以容纳该物资的批,并将其放入剩余空间最小的批中。如果当前没有批可以容纳该物资,则创建一个新批。Step4:重复Step3直到所有的救灾物资都被分配到某个批中。算法ERTFF和ERTBF分别采用了首次适应和最佳适应的分批规则。一般来说,由于采用了最佳适应的分批规则,算法ERTBF会得到较少的批数,但可能会造成批中各物资的到达时间差别较大,从而推迟批的运输时间。而在算法ERTFF中,同一批内的物资到达时间接近,但得到的批数会较多。最后的任务是安排各批救灾物资往受灾点的运输,下面的启发式算法综合考虑了各批物资的可用时间及运输时间。算法DispatchingRuleStep1:将批集合B中的所有的批按照其可用时间RTb升序排列。Step2:找出救灾车队集合L中最早空闲的车队l,即最早完成上一次运输任务的车队,并记录其完成上一次任务的时间tl.Step3:将批集合中满足RTb≤tl的所有批移动到一个的可用的批集合Avb中。Step4:从Avb中选择运往最远受灾点的批b,将其从集合Avb中删除,并交给车队l运输。若集合Avb为空,则从批集合B中找出最早可用的批交给车队l运输。Step5:重复Step2～Step4直到集合B和Avb均为空。4算例2:某本文通过随机生成算例进行仿真实验。随机算例的生成考虑了如下要素:受灾点数目|A|,运输车队数目|L|,出救点到受灾点的运输时间t,受灾物资种类m及各受灾点对物资的需求量Daj,救灾物资的体积s以及到达时间r.对于受灾点数目,设置了5个不同的值,以观察各算法性能随受灾点数目变化的趋势。对于运输车队数目,设置了高低两个水平,分别对应于实际救灾中运力充足和运力不足的情况。此外,对于救灾物资到达出救点的时间,按下列公式设定:rmax=RE(t)E(s)|Μ|C|L|(19)式中,rmax表示物资到达的最大时间。救灾物资的到达时间服从[0,rmax]的离散均匀分布。E(t)和E(s)分别是运输时间和物资尺寸的数学期望。|M|和|L|分别是总的救灾物资数量和车队数量。C是车队的运输量,在所有算例中该值均设为10。R是救灾物资到达的频率系数,当R值较低时,救灾物资在短时间内频繁达到出救点,对应于现实中物资集散中心救灾品充足的情况;R值较高时,救灾物资到达出救点的时间间隔会变长,对应于现实中物资集散中心救灾品相对不足的情况。各因素及其取值范围如表1。每一类型的算例可用符号AaLbRc(a=1,…,5;b=1,2;c=1,2)来表示。例如受灾点数目为4,运输车队数目为4,救灾物资到达频率系数为0.5的问题可以表示成A2L2R1。实验中一共包括20类(5×2×2)不同的算例,每类型算例随机产生10个样本。实验中总共测试200个样本。实验中共测试四类算法。即由不同的救灾物资分配算法和分批算法组合而成,例如算法A1B2表示首先用算法A1将救灾物资分批到各受灾点,再使用算法B2:ERTBF进行分批,最后用算法DispatchingRule安排运输车队的调度。此外,实验中的下界按照如下方式得到:分别使用算法A1和A2指派救灾物资所运往的受灾点,然后使用算法LowerBound分别得到两个下界LB1和LB2,最终的下界LB=max{LB1,LB2}。表2列出了各算法在不同类型算例下的结果,表中单元格的数值为某算法在10个样本下的平均值。可以看出,在大部分算例中,各算法的性能由好到至坏分别是A1B2,A1B1,A2B2,A2B1。尤其是使用算法A1分配物资到受灾点明显优于A2。这是因为算法A1根据物资的到达时间,逐个满足受灾点的所有需求,这样到达时间接近的物资会被运往相同的受灾点。这些物资成批后,批的可用时间不会因为长久等待某个未到达的物资而延后,从而耽误整个运输。而算法A2平均满足各受灾点的需求,这会造成运往相同受灾点的物资的到达时间可能有相当大的差距,这样成批后可能会因为等待某物资的到达而延迟整个批的运输。此外,算法B2也较B1有优势,因为其采用最佳适应算法生成批,其得到的总批数会小于算法B1。从而总的运输次数减少。为了更