应急物资配送的多目标随机规划模型

应急物资配送的多目标随机规划模型

1灾灾信息应对中的多目标规划与随机规划结合随着各种灾难的频繁发生，应急救援物流受到了广泛关注。地震、台风、洪水、干旱等人为灾害以及恐怖主义活动将造成巨大的生命和财产损失。药物、食品、帐篷等应急物资的及时有效配送是一个重要问题。关于一般情况下(灾情信息不随时间发生变化)的应急物资配送问题,一些学者已对其展开研究.从随机规划的角度,Barbarosoglu、Beraldi、Chang针对应急物流的不确定性都曾建立随机规划模型.从多目标规划的角度,Tzeng和Araz亦分别研究了应急物资配送和应急车辆选址问题.Salmeron等则将多目标规划与随机规划结合运用到解决人道主义物流设施扩建、物资配送问题中.而有关灾情信息变化情况下的应急物资配送问题的研究较为少见.由于灾情信息的复杂多变,需要解决如何既快速又有效地对应急物资进行配送,因此研究一般情况下的应急物资配送问题已远远不够.作为时间的函数,灾害预测的准确性和物流成本效率之间是悖反关系(tradeoff).在灾害刚刚发生或发生初期配送物资,可以将其及时送到灾区,但低准确度的灾害情景信息影响了物流配送的有效性与公平性;而高准确度的灾害情景信息又是以牺牲配送及时性为代价的.因此研究灾情信息更新下的应急物资配送问题具有现实意义.将贝叶斯信息更新应用于物流与供应链领域的研究最初出现在服装行业的订货与库存策略中,如Iyer、Eppen、Choi等人的研究.Choi等人研究了生产成本与需求预测精度的悖反关系,设计了一个关于单次订货策略的最优停止问题.Lodree和Taskin借鉴了该思想将其应用到飓风灾害发生时的库存控制策略中.而目前尚未见将统计决策中的贝叶斯分析和最优停止问题应用于应急物流的选址-配送问题中的研究,鉴于此,本文研究了多出救点、多受灾点、多物资、多车型的应急车辆选址、路径选择和物资配送问题.本文的主要创新是,将统计决策与运筹规划相结合.设计了一个基于灾情信息更新的应急物资配送的最优停止问题.2应急决策过程本文研究多出救点、多受灾点、多物资、多车型的车辆选址、路径选择和物资配送问题.应急物资配送网络体系如图1所示.当灾害发生之前,决策者在既有的出救点上进行车辆数量和类型的安排;当灾害发生之后,决策者在合适的时间做出车辆路径选择和物资配送决策.本文将整个应急决策过程划分为两个阶段(stage):灾前阶段与灾后阶段.与之相对应,在灾害发生之前的车辆选址决策(包括对车辆数量与类型的安排)称为第一阶段决策,亦称here-and-now决策;在灾情发生之后的车辆路径选择和物资配送决策称为第二阶段决策,或称wait-and-see决策.这样,本文研究的问题通过建模可以设计成两阶段带补偿的随机规划模型.此外,本文通过设定多个具有固定时间间隔的观测时刻将第二阶段划分为多个具有固定时长的时段(period).决策者在观测时刻通过观测某些反映灾情特征的信息来对目前所掌握的(不一定准确的)灾情信息进行更新和修正,并选择是否继续等待,观测、更新信息,还是停止观测,做出车辆路径选择和物资配送决策.如图2所示.因此,本文研究的问题是建立在多个观测时刻上的单次决策问题.2.1灾害情景信息更新前的表现(1)同文献,假设存在有限种灾害情景.需求和路径连通性的随机性质通过离散的灾害情景来表达.(2)由于应急车辆只能到达一定“距离标准”(distancestandard)范围内的需求点以提高应急服务水平因此假设出救点对受灾点具有最大覆盖范围限制.(3)在出救点进行车辆选址的时间忽略不计.(4)更新后的灾害情景信息比更新前的灾害情景信息更加准确.2.2该符号(1)应急物资集合I为受灾点i的集合,i∈I.J为出救点j的集合,j∈K为应急物资k的集合,k∈K.M为车型m的集合,m∈M.Ω为受灾情景ω的集合,ω∈Ω.S为观测时刻s的集合,s∈S.(2)应急物资c的初始发生概率Tij为出救点j到受灾点i的距离.T为出救点对受灾点的覆盖范围的阈值,即出救点只对距离T以内的受灾点进行物资配送,对距离超过T的受灾点不安排物资配送.gm为车辆m单位距离的运输时间.fm为车辆m单位距离的运输成本.cjm为车辆m在出救点j的单位增设成本.Ujm为车辆m在出救点j的最大规模.wk为应急物资k的单位重量.Vm为车辆m的最大装载重量.为情景ω下受灾点i对应急物资k的需求.pω为情景ω的初始发生概率.为时刻s情景ω的发生概率.H为每两个观测时刻之间的固定时间间隔.为情景ω下出救点j到受灾点i的连通性.为简单起见,只能取0或1:当j到i连通时取1，当j到i不连通时取0.为情景ω下出救点j到受灾点i的有效距离.当路径连通时,等于实际距离Tij;当路径不连通时,取无穷大.(3)应急物资配送量表axjm为整数变量,表示安排车辆m在出救点j的数量.为整数变量,表示确定情景ω下负责出救点j到受灾点i物资配送的车辆m的数量.为情景ω下应急物资k通过车辆m由出救点j到受灾点i的运输数量.为情景ω下受灾点i对应急物资k的未满足需求量.2.3灾害情景下的降水量假设当受灾情景ω发生时,某一可观测信息θ发生的概率已知,即pθ|ω已知,其值可以通过历史统计数据得出.比如,每次洪涝灾害时,通过观测不同严重程度的灾害情景下的降水量可以得到降水量的条件概率分布.因此,可以通过观测某一特定信息在不同阶段的取值θ(s),对灾害情景ω的发生概率进行更新和修正.设smax为最大的观测时刻,由贝叶斯定理，得到时刻s灾害情景ω的发生概率为pw实质上为灾害情景发生的先验概率,为经过贝叶斯更新的灾害情景发生的后验概率.2.4车辆运营效率目标函数约束条件为:从物资配送的及时性、有效性以及经济性三方面出发,建立物资配送的效率、公平和成本目标.其中,式(2)为效率目标,为最小化物资配送和信息观测的总时间.式(3)为公平目标,为最小化未满足需求.式(4)为成本目标,为最小化车辆选址和物资配送的总成本.式(5)是车辆在出救点的最大规模约束.式(6)表示车辆投入使用量不超过保有量.式(7)是车辆对应急物资的最大承载重量约束.式(8)表示对应急物资的供应量不超过需求量.式(9)是未满足需求量的求解公式.式(10)是有效距离的表达式.式(11)是最大覆盖范围约束,同时保证了配送路径的连通性,当有效距离大于阈值时,j到i不安排车辆.式(12)-(14)规定了决策变量的取值范围.3多目标函数参考文献“Chapter4”中的“Definition8”,本文在这里引入一个类似的定义1:定义1ω为自然状态(这里指灾害情景),为其后验分布,L(ω,a,s)为行为a(这里指车辆选址、路径选择和物资配送决策)的损失函数,(*)为对*按后验概率取数学期望,则时刻s行为a的后验期望损失为通过将原模型的稍微变形,易得等价于同理,分别等价于可以看出,原模型的三个目标函数皆为不同种决策组合的后验期望损失.根据文献,时刻s三个目标函数的贝叶斯风险可以分别表示为定义2设λ1和λ2分别为单位配送时间的延误损失(以资金来衡量)和单位未满足需求的短缺损失(以资金来衡量),且其值已知,则时刻s的加权贝叶斯风险为:通过式(22),将原模型三个不同量纲的目标函数用统一的量纲来衡量,实际上将多目标决策问题转化为单目标决策问题.定理1设三(s)为r(s)的最优解集,s1和s2为某两个时刻,则当作比较时,才是时刻s1的实际贝叶斯风险.证明根据假设(4),更新后的灾害情景信息比更新前的灾害情景信息更加准确.当时刻s1的贝叶斯风险拿到时刻s2与该时刻的贝叶斯风险作比较时,此时的情景概率比时刻s1的情景概率更符合现实,用置换得到的贝叶斯风险才是实际贝叶斯风险.设(xjm)*、为的最优解,则决策规则设smax为最大观测时刻,s1和s2为某两个时刻,则决定最优停止观测时刻的决策规则为:Step1初始化s1和s2:置s1=1,s2=2;Step2若s2>smax,停止运算,并返回;若s2≤smax,比较,转到Step3;若,转到Step4;Step3置s2=s2+1,转到Step2;Step4置s1=s1+1,s2=s1+1,转到Step2.由该求解步骤可以推断,原模型实际上为一个统计决策中的最优停止问题(optimalstoppingproblem).模型求解涉及大规模复杂的混合整数规划,以及循环比较求解问题,一般数学规划软件难以在短时间内快速求解.DashOptimization公司开发的运筹学仿真软件Xpress对于求解大规模复杂混合整数规划具有很高的求解速度与精度.因其具有预解决(presolving)、割平面(cuttingplanes)、分支变量选择(branchingvariableselection)、节点预处理(nodepreprocessing)、启发式算法(heuristics)等先进算法技术,可以很好地克服用分支定界树法进行深层次搜索而引起的节点呈指数增长的问题,已被证明可以迅速有效地解决大规模复杂混合整数规划问题.因此本文拟通过Xpress进行编程求解.4计算与分析4.1最优解的求解某地拟在8个候选地址安排应急车辆,以服务附近8个居民区域.当暴雨灾害发生时,需要为灾区配送3种应急物资(药品、食物、帐篷).有3种灾害情景(轻度、中度、重度),3种交通工具(轻型车、中型车、重型车).有5个观测时刻,决策者可以在时刻1不观测降水量直接做出决策,亦可以在以后的每个时刻通过观测降水量来选择适当的时间做出较为准确的决策.后4个时刻观测到的降水量分别为200、300、400、500毫米.具体参数设置见表1-7.另有:T为30000米,H为3600秒,λ1为0.2元/秒,λ2为50元/件.在CPU为2.5GHz、内存为2GB的笔记本电脑上,通过Xpress7.0编程求解.通过编写语句setparam(“XPRS＿MIPRELSTOP”,0.005)设置所求解与最优边界的误差在5‰以内.求得最优停止观测时刻为时刻4,该时刻的贝叶斯风险为966964元,各个目标的最优值分别为:件,元.在求解速率上,Xpress求解本模型花的时间非常少,整个过程只花了9秒钟时间.在求解精度上,由图3的最优解与最优界的差距可知,本模型的最优解与模型的最优边界十分接近(差值为3.9‰<5‰),说明该最优解具有很高的精确性.4.2种情景下车辆选址决策中的灾害情境下xjm图4-6分别描绘了不同灾害情景下的车辆选址、路径选择决策(物资配送决策由于涉及的决策变量很多,鉴于篇幅限制无法详细列出,故略).正如前面所述,由于车辆类型和数量的安排(即xjm的确定)发生在灾害发生之前,属于第一阶段决策,因此其取值不受灾害情景变化的影响,图4-6显示了这一事实:三种情景下的车辆选址决策是统一的.区别于xjm在不同灾害情景下的高度统一性,路径选择决策却依情景的变化而变化.图4-6描绘了这种变化.当灾害不断加重时,一方面,由于灾区对应急物资的需求增大,既有配送路径上的车辆数量也增多;另一方面,某些配送路径的有效性被破坏而失去了连通性,因此实际存在车辆流量的配送路径会减少.可见,本文提出的模型和解法可以灵活应对不同的灾害情景,以便决策者做出合理的决策,这也是两阶段随机规划的优势所在.4.3信息更新效果由假设(4)可知越后面时刻的灾害情景信息越准确,由于本文只考虑5个时刻,因此假设时刻5的灾害情景信息是最终正确的信息.如果决策者对降水量不进行任何观测,在时刻1直接做出决策,此时将求得的最优解集Ξ(1)运用正确的灾害情景发生概率(即)计算得到实际贝叶斯风险为1075940元.而将本文的最优停止问题求得的最优解集Ξ(4)也运用正确的灾害情景发生概率计算得到实际贝叶斯风险为1066870元.两者的差值为9070元,原因在于:虽然信息更新导致应急物资配送的延迟,但是由于更新后的灾害情景信息具有更高的准确性,不仅足以弥补配送延迟造成的损失,还使总体损失降到最低,使得物资配送决策更为合理.信息更新的价值亦体现于此.4.4时间丰富与约束变化众所周知,对于任意一款软件或一种算法,求解速度与精度总是呈悖反关系,即一方随着另一方的增大而减小.本文前面在求解算例时将所求解与最优边界的最大误差设置在5‰,使得Xpress求解模型只花了9秒钟时间.通过改变所求解与最优边界的最大误差值,可以得到Xpress求解本模型的速度变化趋势,如图7所示.随着误差的逐步增小,求解模型所花的时间也逐渐增多,但是花费时间的变化曲线总体上仍然处于令人满意的区间之内(在误差为极小的2‰时,仍然只花费95秒时间).如果合理地调节误差的取值,可以获得十分惊人的求解速度,而又能保持较高的精度.因此当面对现实中更为复杂的大规模应急物资配送问题时,一方面通过合理调节误差的取值,另一方面依靠Xpress“反-分支定界树节点指数增长”的强大的算法技术,相信可以满足应急物资配送快速决策的要求.5贝叶斯更新的优势本文研究了多出救点、多受灾点、多物资、多车型的应急车辆选址、路径选择和物资配送问题.考虑到灾害预测准确性和物流成本效率之间的悖反关系,从多目标规划和随机规划的角度,建立了应急物资配送的多目标随机规划模型.本文的主要创新是,将统计决策与运筹规划相结合,通过构建一个贝叶斯风险函数,以及一个决定最优停止观测时刻的决策规则,使