不确定应急物流LRP双目标优化模型

高荣，王纯，马业宝

(河北工业大学 经济管理学院，天津 300401)

自然灾害的频繁发生极大危害了人民群众的生命财产安全.自1990年起，受台风、地震、龙卷风、洪水等重大自然灾害影响的人口每年高达3亿人次，直接经济损失占世界GDP的平均比例为17%[1].在灾难发生之后，需要及时为灾民提供必要的生活和医疗等物资，所以自然灾害之后的应急救援是一项非常重要的工作，也是一项复杂的系统工程.因此，应急物资配送中如何减少时间、降低经济成本和减少自然灾害对人们生命财产造成的损失是一个值得深入研究的课题.

为降低自然灾害造成的损失，亟需科学优化应急物资中心选址和应急配送车辆的路径，达到有效快速完成应急物资配送的目的.因此，应急物资配送优化中的选址-路径问题(location-routing problem，LRP)备受关注.确定信息下，楼振凯[2]以救援时间最小和救援成本最低为目标，建立了双层优化模型；Vahdani等[3]考虑道路损坏和修复的影响，建立了以救援时间最少和救援成本最低的双目标优化模型；袁涛等[4]考虑道路损坏和修复的影响，构建多式联运多级应急物流网络，建立了设施点定位、路径规划和道路修复的一体化优化模型.随机信息下，考虑需求量是随机的，Caunhye等[5]以设施建设成本最小和救援时间最短为目标，建立了2阶段LRP随机优化模型；代颖等[6]基于机会约束方法建立了带时间窗的随机选址-路径优化模型；Vahdani等[7]考虑配送中心和仓库的容量不确定性，建立了多周期多物资的三级LRP模型；考虑道路通行能力、供应量和需求量是随机的，Moreno等[8]以配送物流费用最小和灾民损失最小为目标，建立了2阶段的随机规划模型．

在没有数据的不确定信息情形下，需要应用不确定理论来解决应急物流优化问题，如Zhang等[9]假设受灾点之间的服务时间和需求为不确定变量，建立了不确定位置集覆盖模型，解决了应急服务设施的定位问题.随后，Zhang等[10]将应急服务设施定位问题拓展到了应急LRP优化问题中，利用机会约束，建立了以时间最小化为目标的不确定规划模型，解决了应急物流中的闭环LRP问题.而在应急物流中，时间是第1要素，但费用也不可忽视，同时考虑救援时间和费用才更符合现实要求，而现有的不确定应急物流文献中并没有同时考虑这2个因素，因此，本文建立了时间最短和费用最小的双目标模型来解决开环应急LPR问题，进一步丰富了不确定理论成果，并为应急物流优化提供决策支撑.

1 预备知识

定理1[11]设η1,η2,…,ηn为独立的不确定变量，其正则不确定分布为Φ1(x),Φ2(x) ，…,Φn(x).若函数f是连续的且严格单增，则η=f(η1,η2,…,ηn)有逆不确定分布

2 模型

2.1 模型建立

因为在自然灾害发生后，随时可能会发生二次灾害甚至可能会发现更多的受灾人数，这就导致了需求点的需求量是不确定的，因此假设需求点的需求量是一个不确定变量.从救援中心到受灾点或者从受灾点到受灾点的运输时间也是不确定变量，这是因为自然灾害后，通讯可能会中断，使得没办法了解道路的实时情况等原因，造成了运输时间的不确定性，因此假设2个节点之间的运输时间也为一个不确定变量.

救援物资的配送是具有时效性的，将救援物资在某一时刻之前送达灾民手中是有价值的，超过某一时刻就会失去其应有的价值，所以目标之一为救援物资送达需求点的总时间最短;在考虑应急物资配送时效性的基础上，应该考虑整个物流系统的花费，在保证时间的前提下，尽可能地降低经济成本，所以另一个目标为整个配送系统的总费用最小。

在进行优化的过程中，做以下假设：1)每一辆车装载的救援物资的数量不超过车辆容量的可能性不低于预设的置信水平α1；2) 从每一个救援中心运输出来的救援物资的数量不超过救援中心容量的可能性不低于预设的置信水平α2；3) 每一个需求点仅被一辆车服务；4) 只有开设的救援中心拥有配送车辆且必须发车；5) 各需求点的需求量是独立的且其救援物资到达的时间满足限制期要求；6) 每个车辆出发1次，完成自身的配送任务后，须就近停靠在救援中心.因此，救援时间最短和费用最小的双目标模型为

(1)

(2)

(3)

(4)

(5)

2.2 模型转化

在上述模型中，由于D和V中的点数都是有限的，根据定理1和定理2可将式(1)转化为

由于G、V和U中的点数都是有限的，根据定理1和定理2可将式(2)转化为

(6)

同理，可将约束条件式(4)转化为其等价形式

(7)

根据定理1和定理2，可将约束条件式(5)转化为

(8)

3 算法设计与算例

3.1 算法设计

由于应急物流系统的LRP问题属于NP-hard问题，所以无法得到其精确解，这就需要用智能算法来求解该模型.而求解多目标、非线性规划模型时通常使用遗传算法，并能求得不错的解，所以本文设计了遗传算法来求解.

3.1.1 染色体编码

在该模型中，采用自然数编码.3个子串构成一条染色体，子串1代表物资需求点，有n个基因位，对应的数值(从1到K中随机生成的自然数值)表示服务需求点的车辆，且1个需求点只对应1辆救援车.子串2有n个基因位，对应的数值(从1到n随机生成的自然数值)表示需求点的排列顺序.子串3有K个基因位，对应的数值(从n+1到n+m随机生成的自然数值)表示拥有车辆的救援中心的编号.

利用惩罚函数的方法对约束条件进行处理：如果约束不被满足，将给出一个特定的惩罚值，它反映在目标函数和适应度函数中，即将一个极大的数加入目标函数，以降低适应值和被选择的可能性.本文选择对应急救援车辆和应急物资救援中心的容量约束以及时间窗口的约束增加惩罚值.

假设N1、N2、N3是很大的正数，针对约束(6)，在目标函数中加入

针对约束(7)，在目标函数中加入

针对约束(8)，在目标函数中加入

3.1.3 初始化种群和适应度函数

种群规模设置为N，随机产生初始种群，方法如下：根据需求点的数量、候选救援中心的数量以及车辆的数量等，使得染色体的每个基因位都随机产生1个自然数，从而随机产生1条染色体，判断是否满足车辆容量、救援中心的容量限制以及时间窗约束.若满足，则保留；若不满足，则另外生成1条染色体.循环往复，直到生成N条染色体.针对上述的双目标不确定LRP优化模型，采用加权法处理，2个目标的权重分别是ω1和ω2，且ω1+ω2=1.因此目标函数变为

minF=ω1F1/minF1+ω2F2/minF2.

加入惩罚值之后的目标函数为

minF*=ω1F1/minF1+ω2F2/minF2+s(1)+s(2)+s(3).

由于目标函数为Z=minF*，所以取适应度函数g(x)=Mmax-Z，其中Mmzx是一个非常大的正数，因此染色体对应的目标函数值越小其适应度就越大.

3.1.4 交叉和变异操作

高职学生的英语基础相对较弱，跨文化知识欠缺，习惯性用中文的思维和模式交际，文化“休克”现象时有发生；在传播本土文化时，失语现象严重；对合作办学的中小国家的文化缺乏了解。

为了保持群体的多样性，对染色体中的各个字串进行交叉和变异的操作.由于子串1、2、3分别包含了不一样的信息，所以对3个子串采取的交叉方法和变异方法也不同.对子串2采取交叉方法为部分匹配交叉，变异方法为逆转变异；对子串1和3采取的交叉方法为双点交叉，变异方法为对换变异.

3.1.5 选择操作

本文利用精英保留以及轮盘赌相结合的选择方法，即在下一代的种群生成时，先将上一代的种群中适应度最高的个体直接保留到下一代种群，并且用这些个体替换上一代种群中经过交叉和变异之后所产生的新一代种群中适应度最低的个体；采用轮盘赌的方法在当代种群中选择新一代种群中的其他个体.

3.1.6 算法终止条件

当算法的迭代次数达到程序预先设置的最大迭代次数，则终止运算，即假设预先设定MAXGEN为遗传算法的最大迭代次数，当算法迭代次数大于MAXGEN 时，则算法结束.

3.2 算例分析

假设有10个需求点，编号为1～10；有3个候选的救援中心，编号为11～13；有3辆不同型号的车.救援中心的容量以及建设成本见表1，各需求点的需求量为不确定线性变量见表2，救援车辆的各个参数见表3，各节点之间的运输时间为不确定线性变量见表4.

表1 待选救援中心的参数Tab.1 Data of candidate relief centers

表2 应急物资需求点的参数Tab.2 Data of points needing emergency materials

表3 救援车辆的参数Tab.3 Data of rescue vehicles

表4 2节点之间的时间参数Tab.4 Time data between two nodes

本文采用MATLAB软件进行编程，迭代次数设置为300，初始种群设置为40，交叉概率Pc=0.8，变异概率Pm=0.1，此时取时间权重ω1=0.6，成本权重ω2=0.4，预设的置信水平α1=α2=0.95,程序运行50次，显示计算的结果相对比较稳定，选择的救援中心均为11、12和13，得到目标函数收敛于1.017 5，对应最优的时间为214 min，最低成本为25 145元.当迭代次数增加时，目标函数值是收敛的.对应的配送中心选址和车辆分配结果为:救援中心11、12 和13被启用，使用3辆车进行运输，其中车辆3分配给救援中心11，车辆1分配给救援中心12，车辆2分配给救援中心13.需求点的服务顺序和配送路径分别为：车辆1的路径为12-7-4-6-11；车辆2的路径为13-3-8-10-13；车辆3的路径为11-5-1-2-9-11.

目标函数收敛速度较快，在100代时可求得最优解，满足模型的快速求解要求.如果模型中置信水平发生改变，经济成本和配送时间也会发生改变，其中经济成本随置信水平增大而增大，总的配送时间随置信水平增大而减少.这是因为置信水平增大，则应急救援中对车辆容量以及救援中心容量的约束更加严格，因此选中的救援中心数量随之增多，且启用的车辆数也随之增多，导致应急救援的经济成本增大；同时，救援中心以及车辆数增加，会使得需求点的需求能够得到快速的响应，从而缩短应急时间.所以在应急物资配送优化问题中，要根据灾情和实际情况给出合适的置信水平，保证时效的同时降低经济成本.

4 结论与展望

考虑到自然灾害造成的不确定性，本研究认为需求点的需求量和救援车辆的行驶时间是不确定变量且其分布是正则的，以配送救援物资的总时间最少和配送系统总经济成本最小为目标，提出了不确定双目标机会约束LRP模型，以此对应急物流配送系统进行分析和决策.采用加权法和惩罚函数的思想对模型的目标进行处理，利用遗传算法得到模型的解，给出数值例子对模型的有效性进行验证，算例表明配送时间与置信水平成正相关，而成本与置信水平成负相关.因此，在决策中管理者必须根据实际情况给出合理的置信水平，以保证应急物资及时配送，并控制经济成本.

本研究并未考虑多种配送方式、需求为动态情形的配送以及多级配送中心的配送.在后续的研究中，考虑不确定因素影响，建立多级配送中心，多种车型以及多种运输方式联合的形式进行配送和动态需求下的多阶段的不确定配送模型，以期更快解决实际救援问题并完善不确定理论成果.此外，本研究利用已有的遗传算法进行求解，并未对算法进行改进，之后将算法也作为一个新方向进行研究.