应急定位-路径的模糊机会约束规划模型

孙华丽，王循庆，薛耀锋

(1.上海大学管理学院，上海 200444；2.华东师范大学 教育信息化系统工程研究中心，上海 200062;3.上海数字化教育装备工程技术研究中心，上海 200062)

0 引言

近年来，世界各地自然灾害、公共卫生事件、军事冲突和恐怖袭击等突发事件频繁发生。如2005年美国“卡特里娜”飓风、2008年中国汶川地震，2010年中国甘肃舟曲特大泥石流，2011年日本9级特大地震等。这些非常规突发事件给人类和社会造成了巨大的人员伤亡和财产损失，成为阻碍社会发展的主要因素。突发事件发生后，应急救援物资的及时供应是关乎人民群众生命安全和维持社会安定的重大问题。为了最大程度的提高应急资源保障的能力，迫切需要在有限的时间、空间和资源约束下实现应急救援机构的合理选择和应急物资配送体系的科学优化。突发公共事件的突发性和破坏性经常导致需求具有很大的模糊性。此外，自然灾害等突发事件可能造成部分道路毁坏，导致单位时间运输费用不确定。为此，本文拟考虑应急系统总成本和灾害损失成本之和最小，采用模糊机会约束规划理论，建立一个应急资源需求和单位救援运输费用均模糊的应急物流系统定位-路径模型，设计改进的遗传算法对模型进行求解，并用算例验证该模型的正确性和算法的有效性。

1 应急系统LRP模糊机会约束规划模型

1.1 问题描述

突发公共事件发生后，有若干灾区物资需求点，应急设施点和同类型的救援车辆。需求点的需求量和单位运输费用是模糊的，每辆车必须从应急设施点出发，完成运输任务后返回到出发点，每个灾区需求点只能由应急设施点的一辆车为其提供服务，且车辆的物资容量大于任一个灾区点的救援物资需求量。问题是如何选择若干应急设施点，并在满足车容量限制的条件下确定一套从应急设施点到物资需求点的车辆路径，使系统总成本和灾害损失成本最小的方案。

为了方便描述，定义以下变量和符号：

I∈{1 ,2,...,m} 为灾区物资需求点集合；J∈{1 ,2,...,n}为备选的应急设施点集合；K∈{1 ,2,...,k}为应急救援运输车辆集合；i为灾区物资需求点(i∈I)；j为应急设施节点(j∈J)；k表示救援运输车辆(k∈K)；g,h表示物资需求点或应急设施点，g∈(I⋃J),h∈(I⋃J)；pj为应急设施点固定建设费用；rj为应急设施点运营可变费用；qi表示需求点i的救援物资需求量；Q表示救援车辆的最大装载容量；Wj表示应急设施点j的总容量；dgh表示点g到点h的距离；υk为救援车辆的平均行驶速度；Ck为车辆k的单位装载货物费用；Φi表示应急救援开始前受灾点i的灾害损失成本；Φt表示各灾区点的单位时间灾害损失成本；ξ为灾害损失最大成本时间上限；～qi=（qei，qdi,qui）表示灾区需求点i的模糊需求量，其中qei，qui分别表示该模糊数的左右边界，qdi表示该模糊数隶属度为1的点；～Cgh=(Cegh,Cdgh,Cugh)表示救援车辆从点g到点h的模糊单位运输费用。

yj=1，表示选择第j处应急设施点进行物资供应；否则，yj=0。

fij=1，表示应急设施点j为灾区需求点i提供物资服务；否则，fij=0。

sjk=1，表示应急设施点j在救援运输路径k上；否则，sjk=0。

μghk=1，表示第k辆车从节点g到节点h；否则，μghk=0。

1.2 模型建立

其中，目标函数(1)是使系统总成本(包括应急设施点建设和运营成本、救援货物装载成本、救援车辆运输成本、灾害损失成本之和)最小；约束式(2)保证只有选中的应急设施点才能为灾区需求点提供救援物资服务；约束式(3)表示在一条救援运输路径上只能由一个应急设施提供服务；约束式(4)保证每条救援路径上的物资总需求量不超过运输车辆物资运载能力；约束式(5)保证分配给应急设施点j的所有受灾点物资总需求量不能超过该应急设施点总容量；约束(6)保证每个灾区需求点只能在一条巡回运输路线上；约束(7)保证救援运输路线的连续性；约束式(8)保证每辆车的运输路线最多起止于一个应急设施点；约束式(9)表示只有救援路线经过了受灾需求点，该受灾点才能指派给应急设施点；约束式(10)表示救援车辆到达灾区点的时间；约束式(11)、(12)和(13)是决策变量，取值是0或1。

在Liu和Iwamura工作基础上，将模型中带有模糊参数的目标函数(1)和约束条件(4)、(5)转化为如下等价模糊机会约束规划模型：

其他约束与原模型的约束相同。其中，Pos{}表示{}中事件成立的可能性，α，β，γ表示给定的置信水平。模型中目标机会约束(14)表示所求的目标值fˉ应该是在保证置信水平至少是α时所取的最小值；机会约束(15)、(16)和(17)表示约束得到满足的可能性至少应该达到给定的置信度水平α、β、γ。

引理 设三角模糊数r～=(r1,r2,r3)，其隶属函数以μr～(x)表示，则对任意给定的置信水平α(0≤α≤1)，当且仅当z≥(1-α)r1+αr2时，有Pos{r～ ≤z} ≥α。

根据以上引理，将机会约束转变为以下清晰等价形式：

将以上约束分别替代模糊机会约束(15)、(16)和(17)，其他约束与原模型的约束相同，从而将该模型转化为确定性模型求解。

2 模型求解

2.1 染色体编码

将模型变量采用特定的实值进行染色体编码，每个染色体代表该模型的一个解，每个染色体有3段。染色体的第一段有k个基因，k为最大救援车辆数目，每个基因位都由1到n的自然数中随机产生一个，n为候选应急设施点数目；第二段的长度为m，m为受灾需求点数目，每个基因位都由1到k的自然数随机产生；第三段的长度也为m，每个基因位由1到m的自然数产生，并且不能相互重复。得到染色体的长度为k+m+m，如(a1,a2,...,ak‖b1,b2,...bm‖c1,c2,...,cm)。

2.2 初始种群创建

随机产生N个初始种群，用chrom(l)表示每一代种群中的第l(l=1,2,...,N)个染色体。

2.3 计算适应度

染色体适应值是个体生存机会选择的唯一确定性指标。对于违反约束条件的染色体，需加入相应的惩罚确保满足条件的个体具有较高生存机会。为此需要增加惩罚项以确保可行解具有较高的适应值。设δk表示当前种群第k个染色体，则第k个染色体的总成本计算如下：

式中，M为正大数。

2.4 遗传操作

2.4.1 选择

采用轮盘赌选择和精英保留相结合的选择策略。在每次生成下一代种群时，将父代种群以及交叉、变异操作产生的临时种群中的最优个体直接复制进入下一代种群；新种群中的其他个体采用轮盘赌方法从父代种群和临时种群中选择。

2.4.2 交叉和变异

为保持群体的多样化，需要对染色体中各段分别进行交叉变异。对染色体第一段采用单点交叉，并进行对换变异操作；对第二段进行两点交叉操作和对换变异操作；对第三段采用部分匹配交叉操作，并进行逆转变异。

2.4.3 终止条件

若群体代数达到设置的最大迭代次数Maxgen时，则输出当前最优个体，算法结束。

3 实例分析

本文用下面算例说明模型和算法的有效性。采用Matlab 7.0编程，并在CPU为Intel 2.80GHz，内存为2G的计算机上运行。算法参数设置如下：种群规模N=100，最大迭代次数Maxgen=500，代沟率GGAP=0.96，交叉概率pc=0.7,变异概率pm=0.05。

算例1：随机给出4个可供选择的应急设施点，12个受灾物资需求点，6辆同类型的车辆可提供运输服务，受灾点应急救援设施点受灾和的相关数据如表1、表2所示。设应急救援车辆的平均单位行驶速度为30km/h，车辆的最大装载能力为120件，车辆的单位载货量装卸费用为10元/件，受灾点单位时间损失成本为5万元/h，灾害损失成本时间上限为50h，置信水平均为0.8。

对算例进行了10次求解，平均计算时间为13.61s，目标函数值的收敛情况如图1所示，可以看出经过119次迭代后，目标函数值趋于收敛，收敛效果显著，验证了上述模型的正确性和遗传算法的有效性。算法获得最优解的目标函数值为F=2.93×107元，选择编号为1、2和4的应急设施点，对应的车辆路线如图2所示，图中“○”表示受灾点，“□”表示应急设施点，“—”表示运输路线，“…”表示返回路线。

表1 受灾需求点相关数据

表2 应急救援设施点相关数据

表3 应急设施点到受灾点模糊单位运输费用

算例2：对文献[13]的问题进行计算，其中文献[13]的模型中考虑了救援所用总时间最小和成本最小，为方便比较，将本文模型中的总成本分成与文献[13]相同的两部分。对算例进行10次求解，平均计算时间是70.38s，计算所得的救援路线为：车辆 1：1-15-20-7-1；车辆2：1-18-11-1;车辆3：3-12-16-10-3； 车 辆 7： 3-19-13-4-3； 车 辆 8：3-23-14-5-22-3；车辆9：1-17-6-21-1；车辆10：1-9-8-1，与文献[13]计算结果比较如表4所示。从结果对比可以看出，本文实验得到的主要目标函数值Z1比文献[13]的结果缩短了171.5分钟，次要目标函数值Z2与文献结果的相对误差为0.27%，计算时间节约了22.8%，能够更好地迎合应急物流时效性强的特点，对于应急救援物资的高效保障和及时供应具有重要的现实意义。

图1 目标函数值收敛情况

图2 算例计算结果

4 结论

表4 实验求解结果对比

本文以系统总成本和灾害损失成本之和最小为目标，考虑到应急需求量以及运输费用的模糊性，构建了应急系统定位-路径的模糊机会约束规划模型，在此基础上，提出一种遗传算法，并通过算例分析验证了模型的正确性。结果表明，该模型和算法可以有效地解决需求和运输费用不确定的应急物流系统中定位-路径问题，实现应急设施的科学选择和应急救援资源的合理调度。突发公共事件应急系统具有紧急性和动态性，因而考虑应急资源的多种运输方式和动态性的LRP需作下一步研究。

[1] Fiedrich F.,Gehbauer F.,Rickers U.Optimized Resource Allocation for Emergency Response after Earthquake Disasters[J].Safety Sci⁃ence,2000,(35).

[2] BalcikB.,BeamonB.M.FacilityLocationinHumanitarianRelief[J].Inter⁃national Journal of Logistics:Research and Applications,2008,11(2).

[3] Chang M.S.,Tseng Y.L.,Chen J.W.A Scenario Planning Approach for the Flood Emergency Logistics Preparation Problem under Uncer⁃tainty[J].Transportation Research,Part E,2007,43(6).

[4] Sheu J.B.An Emergency Logistics Distribution Approach for Quick Response to Urgent Relief Demand in Disasters[J].Transportation Re⁃search Part,2007,43(6).

[5] Nagy G.,Salhi S.Location-Routing:Issues,Models and Methods[J].European Journal of Operation Research,2007,177(2).

[6] Yi W.,Özdamar L.A Dynamic Logistics Coordination Model for Evac⁃uation and Support in Disaster Response Activities[J].European Jour⁃nal of Operational Research,2007,179(3).

[7] 徐琴,马祖军,李华俊.城市突发公共事件应急物流中的定位－路径问题研究[J].华中科技大学学报,2008,22(6).

[8] 曾敏刚,崔增收,余高辉.基于应急物流的减灾系统LRP研究[J].中国管理科学,2010,18(2).

[9] Liu B.D.,Iwamura K.Chance Constrained Programming with Fuzzy Parameters[J].Fuzzy Sets and Systems,1998,1994(2).

[10] Liu B.D.,Iwamura K.A Note Chance Constrained Programming with Fuzzy Coefficients[J].Fuzzy Sets and Systems,1998,100(1～3).

[11] 赵晓煜,汪定伟.供应链中二级分销网络优化设计的模糊机会约束规划模型[J].控制理论与应用,2002,19(2).

[12] Molla-Alizadeh-Zavardehi S.,Hajiaghaei-Keshteli M.,Tavakko⁃li-Moghaddam R.Solving A Capacitated Fixed-charge Transporta⁃tion Problem by Artificial Immune and Genetic Algorithms with A Prüfer Number Representation[J].Expert Systems with Applications,2011,38(8).

[13] 郑斌,马祖军,方涛.应急物流系统中的模糊多目标定位-路径问题[J].系统工程,2009,27(8).