摘要：针对应急物流系统中选址-路径问题（LRP），建立了一个以最小化系统总耗时、总成本及最大化配送路线道路安全性的多目标优化模型，据此对应急物资供应点选择、配送中心选址及配送车辆路径安排进行决策。构造了带精英策略的快速非支配排序遗传算法（NSGAII）以求解多目标LRP模型，根据模型的特征，对算法的染色体编码、初始种群生成、交叉和变异方法进行了改进，并与变权多目标遗传算法进行对比研究。算例结果表明，改进的NSGAII可以更好地解决应急物流多目标LRP，求解出的帕累托最优解质量较高，算法具有较好的收敛性和运算效率。
关键词：应急物流；多目标优化；快速非支配排序遗传算法；选址-路径问题
DOI：10.13956/j.ss.1001-8409.2016.04.29
中图分类号：F252； TP182文献标识码：A 文章编号：1001-8409（2016）04-00135-05
Abstract：Regarding emergency logistics LocationRouting Problem （LRP）， a multiobjective optimization model is developed to decide supplier selection， emergency facility location and vehicle routing schedule. There are three objectives of the optimization model： minimizing the total operation time， minimizing the total cost， and maximizing the security of distribution routes. A modified Nondominated Sorting Genetic Algorithm II （NSGAII） is proposed， and according to the attributes of the model， the chromosome coding， initial population generating， crossover and mutation of original algorithm are modified. The modified NSGAII is compared with a variable weight multiobjective genetic algorithm. The results of a numerical example show that the modified NSGAII can resolve emergency logistics LRP more effectively， and have a good performance in the convergence and computational efficiency. The quality of the Pareto optimal solutions obtained by NSGAII is more optimal.
Key words：emergency logistics； multiobjective optimization； NSGAII； locationrouting problem
引言
应急物流系统主要需要解决应急设施选址及车辆路线安排两个关键问题，这两者之间并非相互独立，需要进行集成优化。时间效益和经济效益是应急物流系统追求的两大重要目标，此外，由于自然灾害具有较强的破坏性，还应考虑车辆配送路线的安全性。因此，研究应急物流系统中的多目标选址-路径问题（Location-Routing Problem， LRP）十分必要。文献[1-4]对应急物流系统中的单目标LRP进行了研究；文献[5-8]虽然研究了应急物流多目标LRP，但最后还是通过线性加权等方法将多目标转化为单目标进行求解；文献[9-10]采用epsilon约束法对应急物流系统中的多目标优化问题进行了研究。Chang提出一种基于贪婪搜索的多目标遗传算法，以解决灾后应急物流调度问题；Wang构建一个考虑时间、成本及可靠性的多目标应急物流LRP模型，并运用NSGA与NSDE两种多目标进化算法求解模型并进行对比[11-12]。
多目标进化算法种类较多，其中Deb提出的 NSGAII是目前应用最广且效率最高的多目标进化算法之一[13-15]。因此，本文针对应急物流系统中的LRP，建立以最小化系统总时间、总成本及最大化道路安全性为目标的优化模型，根据模型的特点构造NSGAII，对算法的染色体编码、初始种群生成、交叉和变异方法进行改进，并与变权多目标遗传算法进行对比研究。
1问题描述
本文所研究的应急物流LRP如图1所示，该网络由灾区外围的供应点、灾区附近的配送中心、灾区内部的受灾点以及它们之间的车辆路线组成。
图1应急物流LRP示意图
决策问题为：如何在设施容量和救援车辆能力限制的条件下，确定供应点、配送中心的数量和位置以及应急物资运输路径，且使应急物流系统耗费的总时间最少、总成本最小及路径安全性最大。
2模型构建
21符号说明
（1） 集合
S为供应点的集合；W为备选配送中心的集合；D为需求点的集合；N=S∪W∪D为所有节点的集合，i，j，l∈N，N1=W∪D；K为配送中心救援车辆的集合，k∈K；C为应急物资种类的集合，c∈C。
（2） 参数
SQci表示供应点i（i∈S）应急物资c的储备量；WQi表示备选配送中心i（i∈W）的最大处理能力；DQci为需求点i（i∈D）应急物资c的需求量；dij为点i到点j的距离；tij为救援车辆从点i到点j的行驶时间；cij表示从点i到点j单位车辆单位距离的运输成本；pij表示点i到点j实际道路的安全系数（i，j∈N1）；WFi表示启用备选配送中心i（i∈W）的固定费用；SFi表示启用供应点i（i∈S）的固定费用；MQ表示供应点运输车辆的最大容量；Qk表示配送中心配送车辆k的最大容量。 （3） 决策变量
xijk∈{0，1}，取1时表示车辆k从点i驶向点j，i，j∈N1，i≠j，k∈K，否则取0；yi∈{0，1}，取1时表示备选配送中心i（i∈W）被选中，否则取0；zi∈{0，1}，取1时表示供应点i（i∈S）被选中，否则取0；uij∈{0，1}，取1时表示选中的配送中心j（j∈W）被分配给选中的供应点i（i∈S），否则取0；gij∈{0，1}，取1时表示需求点j（j∈D）被分配给选中的配送中心i（i∈W），否则取0；fcij表示供应点i（i∈S）到配送中心j（j∈W）应急物资c运输量。
22模型构建
式（1）表示最小化应急物资配送的总时间；式（2）表示最小化应急物资配送的总成本；式（3）表示最大化应急物资配送的道路安全性；式（4）表示供应点的物资运出量不大于其储备量；式（5）表示配送中心应急物资接收量不大于其处理能力；式（6）表示配送中心的物资流量守恒；式（7）表示配送中心配送车辆的容量约束；式（8）表示所有需求点都要被服务到；式（9）表示当且仅当一条配送路线从配送中心j出发经过需求点l时，需求点l才能分配给配送中心j；式（10）表示路径连续性约束；式（11）表示子回路消除约束；式（12）～（14）表示配送中心的分配约束；式（15）～（17）表示配送车辆的分配约束；式（18）～（19）表示任意两个配送中心之间没有连接且不在同一车辆路径上；式（20）～（22）为决策变量的定义域约束。
3算法设计
31改进的NSGAII
Step1初始化种群规模Popsize、最大迭代次数Maxgen、交叉概率pc和变异概率pm，计数器gen=1。
Step2生成满足约束条件的个体Popsize个，计算个体的各目标函数值，并对个体进行非支配排序，生成父代种群。
Step3采用锦标赛选择、多点交叉、实值变异对父代种群进行遗传操作，生成临时种群。
Step4判断临时种群的个体是否满足约束条件，找出不满足约束条件的个体，产生等量的满足约束条件的个体替换，得到子代种群，并计算子代种群个体的各目标函数值。
Step5父、子代种群合并，进行非支配排序，将排名前Popsize的个体作为父代种群，gen=gen+1。
Step6如果gen≤Maxgen，转入step3，否则结束。
上述算法的关键操作如下：
（1） 染色体编码
染色体采用实值编码，每个染色体由3个子串组成：子串1的基因数量为N，对应每一个需求点，基因值为1到K（车辆编号）的随机整数，表示需求点由哪一辆车配送；子串2的基因数量为K，对应每一辆车，基因值为1到M（配送中心编号）的随机整数，表示车辆从哪个配送中心出发；子串3的基因数量为M，对应每个配送中心，基因值为1到S（供应点编号）的随机整数，表示配送中心分配给哪个供应点。
（2） 快速非支配排序及拥挤距离计算[13]
种群中的每个个体p都有两个参数Sp和np，Sp为种群中被个体p支配的个体集合，np为种群中支配个体p的个体数。快速非支配排序步骤：① 令i=1，Fi=，找出种群中所有np=0的个体，令prank=1，Fi=Fi∪{p}；② 令Q=，对Fi中的每个个体p，其支配的个体集合为Sp，对于Sp中的每个个体q，执行nq=nq-1，如果nq=0，则qrank=i+1，Q=Q∪{q}；③ 令i=i+1，Fi=Q，如果Fi≠，转入②，否则，算法结束。
拥挤距离计算方法为：对于每一个Fi中的个体，基于每一个目标函数m对其进行排序，I=sort（Fi，m）。令边界个体的拥挤距离为无穷，I（d1）=I（dn）=∞，对于k=2到（n-1）利用公式（23）进行计算。
I（dk）=I（dk）+I（k+1）・m-I（k-1）mfmaxm-fminm（23）
其中I（k）.m表示集合I中第k个个体的第m个目标函数值。通过计算，种群中的每个个体p都有非支配排序prank和拥挤距离pd两个属性，利用这两个属性可以区分种群中任意两个个体的支配和非支配关系。p支配q，当且仅当prankqd。
（3） 遗传操作
选择操作：根据快速非支配排序和拥挤距离的大小，用锦标赛法进行选择[13]。交叉和变异操作：运用英国德尔菲大学开发的遗传算法多点交叉算子，以促进算法对解空间的搜索，避免过早收敛现象产生。采用实值变异，并加入区域扫描器限制变异的范围，保证变异后的新个体不跳出解空间中对应的解。
32变权多目标遗传算法（MOGA）
Step1初始化种群规模Popsize、最大进化代数Maxgen、交叉概率pc和变异概率pm，计数器j=1。
Step2随机生成各目标函数的权重ωi，①令i=0，Ω=1；②i=i+1，ωi=rand*Ω（rand为服从0～1均匀分布的随机数），Ω=Ω-ωi；③如果i≠Nfobj（Nfobj为目标函数个数），转入②，否则ωi=Ω。
Step3种群初始化，生成满足约束条件的Popsize个个体，计算个体的适应度，并保留精英个体，令gen=1。
Step4采用轮盘赌选择、多点交叉、实值变异对父代种群进行遗传操作，生成临时种群。
Step5计算临时种群个体的适应度，找出不满足约束条件的个体，产生等量的满足约束条件的个体替换，并用精英个体代替最差个体，得到子代种群；保留这一代的精英个体，gen=gen+1。
Step6如果gen≤Maxgen，转入step4，否则j=j+1。
Step7如果j≤Popsize，转入step2，否则结束。 4算例分析
41数据选取
以成都市应急物流系统为例构建算例，成都市有35个应急避难所（编号1-35），4个配送中心（编号36-39），如图2所示。供应点所在地分别为西安、武汉、长沙、昆明（编号40-43）。 应急物资有3种类型，各避难所的需求量（件）为1～100的随机数。供应点与配送中心之间每辆车的运输成本均为500元/公里，配送中心与需求点之间每辆车的运输成本均为300元/公里。
表1给出应急配送中心的处理能力和启用成本。表2给出物资供应点的储备量和启用成本。供应点的车辆充足，且容量均为1500件。配送中心共拥有10辆配送车辆（编号1-10），其容量（件）由集合{700， 700， 700， 700， 800， 800， 800， 900，900， 900}给出。网络中各点之间的距离和车辆运行时间可由地理信息系统得出，受灾区域各点之间的道路安全系数为0～1的随机数。
42结果分析
采用MATLAB M语言分别编写了NSGAII和MOGA程序，在Inter Core i3 550 @ 320GHz CPU，400GB的计算机上对算例进行仿真。经过多次测试，确定最佳参数为： Popsize=200、Maxgen=1000、pc=09、pm=01。NSGAII和MOGA的帕累托最优解计算结果如图3所示，可以看出NSGAII求出的帕累托最优解的个数远大于MOGA，且MOGA大多数解都被NSGAII的解所支配。采用Collette.和Siarry P.提出的3个多目标算法评价指标对两个算法的性能进行比较，由表3可以看出NSGAII在各项指标上都优于MOGA [16]。
表4给出了NSGAII和MOGA总时间最短的最优解对应的应急物流方案，可以看出NSGAII最优解的道路安全性虽然比MOGA低了73%，但总时间和总成本却分别节约了146%和139%，且节约了2辆车的资源，程序耗时也仅为MOGA的101%。
表5给出NSGAII总时间最短（S1）、总成本最小（S2）及安全性最大（S3）的最优解，可以看出S1与S2是同一个最优解，这是由于影响时间和成本的关键因素都是距离，这2个目标之间不存在效益悖反。S3比S1和S2的道路安全性提高了455%，但时间和成本也相应增加了209%和203%，且多启用1辆配送车辆。
研究表明NSGAII与MOGA都能有效解决应急物流多目标LRP模型，但NSGAII的性能更加优越，具有较好的收敛性和运算效率，且能得出质量较好的帕累托最优解。
5结语
本文提出一个以系统总耗时及总成本最小、配送路线道路安全性最大为目标的LRP模型，并结合模型特点提出了改进的NSGAII及变权多目标遗传算法。算例分析表明，与变权多目标遗传算法相比，改进的NSGAII更能有效求解应急物流多目标LRP模型。本文研究的应急物流多目标LRP模型需求确定且运输方式单一，但自然灾害的突发性往往造成紧急救援阶段需求的不确定性，并可能采用多种运输方式，且灾后应急物流网络具有动态特征，因此需求不确定、多阶段及多式联运的LRP有待进一步研究。
参考文献：
[1]Afshar A， Haghani A. Modeling Integrated Supply Chain Logistics in Real-time Large-scale Disaster Relief Operations[J]. Socio-Economic Planning Sciences， 2012， 46（4）： 327-338.
[2]Yi W， Ozdamar L. A Dynamic Logistics Coordination Model for Evacuation and Support in Disaster Response Activities[J]. European Journal of Operational Research， 2007， 179（3）： 1177-1193.
[3]王绍仁， 马祖军. 震害紧急响应阶段应急物流系统中的LRP[J]. 系统工程理论与实践， 2011， 31（8）： 1497-1507.
[4]Ozdamar L， Demir O. A Hierarchical Clustering and Routing Procedure for Large Scale Disaster Relief Logistics Planning[J]. Transportation Research Part E： Logistics and Transportation Review， 2012， 48（3）： 591-602.
[5]Najafi M， Eshghi K， Dullaert W. A Multi-objective Robust Optimization Model for Logistics Planning in the Earthquake Response Phase[J]. Transportation Research Part E： Logistics and Transportation Review， 2013， 49（1）： 217-249.
[6]陈刚， 张锦， 付江月. 应急物资保障系统模糊多目标LARP研究[J]. 交通运输系统工程与信息， 2014， 14（4）：160-167.
[7]Barbarosoglu G， Ozdamar L， Cevik A. An Interactive Approach for Hierarchical Analysis of Helicopter Logistics in Disaster Relief[J]. European Journal of Operational Research， 2002， 140（1）： 118-133.
