改进NSGA-II算法求解多目标物流车辆路径优化问题

包贤哲 宋阿妮

(湖北工业大学电气与电子工程学院 湖北 武汉 430068)

0 引 言

近年来互联网电商平台兴起推动物流行业高速发展，快递分拨中心遍布城市乡村，但随着快递数量的增加、客户服务范围增大，逐渐出现配送快递效率不高、耗时太长、车辆配送路径不合理等问题，造成物流行业成本激增，客户服务质量下降，严重影响物流行业的发展。因此如何高效有序规划快递车辆行驶路径成为了物流行业领域研究的重点。

物流运输车辆路径规划问题本质上是一个带约束的NP难问题，随着对智能优化算法研究的深入，出现了许多解决该问题的方法，如郝群茹等[1]结合四种邻域变化规则改进禁忌搜索算法来求解车辆行驶路径；路径规划问题中改进禁忌搜索算法[2-3]的收敛速度较快且局部开发能力较强。黄戈文等[4]提出自适应遗传灰狼算法解决了带容量的车辆路径规划问题；Akpinar等[5]结合大领域搜索和蚁群优化算法研究路径规划问题；李凤坤[6]利用中位数层次分析法将多目标问题转化为单目标求解；范文兵等[7]结合爬山算法改进遗传算法，优化了其局部搜索能力；也有学者通过其他方式改进遗传算法[8-9]求解该问题并进行了验证。Akhand等[10]结合自适应扫描策略改进粒子群算法来优化路径；齐名军等[11]提出动态猴子跳跃机制改进粒子群算法提高算法收敛性并用物流实例验证了算法的有效性。Lai等[12]采用模拟退火算法以及TSA来降低使用车辆数和行驶成本；混合模拟退火算法[13-14]在路径规划问题上也有着不错的效果。Wang等[15]采用哈希函数加速禁忌状态来获得更好的优化方案；方文婷等[16]结合A*算法和蚁群算法克服算法前期收敛慢等问题，在物流配送问题上适应性较强。Mohammed等[17]则利用两阶段遗传算法寻找车辆最优路径。虽然现有研究针对这些问题提出了很多改进方案，但这些研究都只以最短路径为优化目标而忽略了运输过程中时间窗和成本的问题，这就导致方法的实际运用性不高，而考虑运输成本和时间窗的多目标优化问题更贴近实际情况，具有更高的研究价值。

国内外学者对多目标路径优化问题也做过许多研究如梅梦婷等[18]提出结合差分法的DE-NSGA算法考虑值班时间等因素，有效改善了路径寻优速度但收敛速度较慢。万逸飞等[19]提出协同非支配排序遗传算法求解机器人路径规划问题并用栅格法证明了算法的有效性但参数设置较为复杂，段征宇等[20]则在传统VRP模型的基础上,考虑路网交通状态的时变性和随机性，设计了一种带硬时间窗的随机时变车辆路径问题的非支配排序蚁群算法。改进的多目标优化算法虽然较传统单目标算法的实际应用性更高，但在车辆路径优化问题上仍然存在着参数设置复杂、收敛速度慢、容易陷入局部最优等问题，且大部分并未将时间窗和迟到惩罚成本等纳入模型。

针对这些问题提出一种改进的劣汰组NSGA-II算法(Elimination Group NSGA-II,EGNSGA-II)，该算法能够克服陷入局部最优的问题，且具有收敛速度快、参数设置简单、精确度高等优点。算法首先通过劣汰组策略将某些更接近最优Pareto前沿却因拥挤度排序被剔除的个体进行二次非支配排列，引入到最优Pareto前沿中提高算法的粒子多样性以扩大其搜索范围，再引入全局最优个体改进粒子进化公式，加快最优Pareto前沿收敛，提升收敛精度，并用ZDT1-ZDT4典型函数验证了算法改进的有效性。最后将算法应用于物流车辆路径规划实例，证明算法对于路径规划问题有良好的适应性，能够显著减少快递投放时间，提升物流行业运转效率增加企业收益。

1 模型建立

假设在某城市有一快递物流中心P，负责将快递送至本区域设置的n个快递点仓库N=(1,2,…,n)内，物流中心拥有M=(1,2,…,m)辆载货量为T、平均运输速度为v的运输车，快递点仓库i与快递点仓库j之间的距离为Rij，快递点仓库i的收货量为Pi，卸货时间为Hi，最佳卸货时间窗为t∈[Qi,Ei]，其中：Qi表示快递仓库i最早卸货时间，若运输车辆早于该时间到达，则需要等到时刻Qi再开始卸货；Ei则表示其最晚接受卸货时间，若货车到达时刻超过时间Ei会产生超时惩罚成本Tpub。车辆每次运输都从物流中心开始并最终回到物流中心。

快递点仓库所需货物只能由一辆运输车运输且只运输一次：

(1)

式中：Gij表示以快递点仓库为行、以运输车辆为列的矩阵中第i行第j列的数据，快递点仓库i货物由车辆j运输则Gij=1，否则Gij=0。

运输货物总量不得超过运输车的最大载重即：

(2)

式中：Tj表示第j辆运输车的最大载重，车辆j一共需要运送k个快递点的货物。

当运输车辆运输货物到达时刻晚于最晚接受卸货时间Ei时其超时惩罚成本为：

Tpub=α×(Dij-Ei)Dij>Ei,i∈[1,k]

(3)

式中：α为单位时间内超时成本系数；Dij表示第j辆运输车到达第i个快递点的时刻。

所有运输车辆将货物送到所需的总时间Sall为：

(4)

为了创造最大效益，可以确定目标函数为使得物流中心使用的运输总成本、运输总时间都最小即：

(5)

式中：Mkm表示车辆每公里的运输成本；q表示一共使用的派送车辆数。

2 算法设计

2.1 传统NSGA-II算法

对于多目标优化问题，人们常常无法评判解的好坏，而NSGA算法很好地解决了这个问题。NSGA-II算法是Deb等[21]在NSGA的基础上提出的，是一种基于Pareto最优解的多目标优化算法。相对于NSGA算法，其引入了快速非支配排序算法降低计算的复杂度，采用拥挤度比较同一等级个体的优劣，还加入了精英策略扩大了采样空间，在各方面性能上相较NSGA-I算法都有了显著提升。

2.1.1Pareto等级及支配关系

对于最小化的多目标优化问题，假定某个多目标优化问题共有n个目标分量,个体解Xm=(gm1(x),gm2(x),…,gmn(x))，任意给定两个多目标函数个体Xa、Xb。

(6)

若个体Xa、Xb满足式(6)，则Xa支配Xb，即Xb被Xa支配。对于某个体，如果不存在任何个体能支配它，则该个体被称作非支配解，在一个种群中相互比较，将所有非支配解找出，这些非支配解形成的解集Pareto等级定义为1，将非支配解剔除后，剩下的个体寻找所有非支配解Pareto等级定义为2，以此类推定义所有解的Pareto等级。以二维多目标优化问题为例，非支配排序结果如图1所示。

图1 双目标非支配排序Pareto等级图

2.1.2 拥挤度排序

为了使得在空间中得到分布更加均匀的个体，将某Pareto等级下的所有个体的每一个目标分量按大小进行排序，将排序后每个目标分量下的数值按照式(7)计算某个体的总体拥挤度

(7)

图2 双目标拥挤度示意图

2.1.3 精英保留策略

从所有Pareto等级的解中选择新的父代种群时遵循Pareto等级从小到大依次选择以保证个体的优质性，当Pareto等级i中的个体被全部选择，而剩余所需选择个体又小于Pareto等级i+1的个体总数时，依据拥挤度排序优先选择拥挤度更大的个体直至父代种群个体达到饱和。精英保留策略既能够保证个体优质性也能保证其均匀分布性。

2.1.4 编码交叉及多项式变异

父代种群确定后要进行编码交叉和多项式变异产生新子代个体，模拟交叉变异公式为：

(8)

式中：x1j(t)表示第t次迭代下个体1的第j维目标分量。

(9)

式中：δj为(0,1)内的随机数；λ为常系数可根据变异效果调整大小。

父代交叉变异产生的新子代个体与父代融合进行下一次的非支配排序直至到达最大迭代次数，此时输出Pareto等级为1的个体即为最优Pareto前沿。

2.2 劣汰策略NSAGA-II算法

2.2.1 劣汰组策略

NSGA-II在选择个体少于某Pareto等级下个体时会根据拥挤度值的大小选择其中较为分散的个体，但是这种选择策略也存在一定弊端如图3所示。图3中需要从Pareto等级1下的6个个体中选择5个个体，此时相比于4号、5号个体，3号个体离最优Pareto前沿较近，但由于拥挤度选择原则3号个体拥挤度最低被剔除，由于个体迭代变异是随机的，可能3号优质个体不会再出现，导致解的整体质量下降，收敛速度变慢。

图3 二维多目标个体选择示意图

为了解决此问题，设立劣汰组集合，将因为拥挤度排序被淘汰的个体放入劣汰组进行二次非支配排序，此时仍然不在最优前沿的个体被永久舍弃，当劣汰组的个体达到最大数量且全部处于最小Pareto等级下时劣汰组成熟，等待算法结束与最后一代种群合并再次进行非支配排序，最终得到最优Pareto前沿，该方法能够显著增加优质个体数量使算法更快收敛。

2.2.2 全局最优变异公式

多目标优化问题由于目标分量间无法比较优劣所以无法求取最优个体，但所有目标分量都向最小值方向优化，由此假设取所有目标分量和最小的个体为近似最优个体，据此改进个体更新公式：

(10)

2.2.3 环淘汰制

NSGA-II算法通过拥挤度排序一次性产生剩余所需子代个体数量以保证子代个体的均匀分布性，但此方式很容易因为某Pareto等级下的个体排列不均匀导致得到的个体分布性较差，如图4所示。

图4 Pareto等级2下个体分布图

根据图4，假设子代个体在选择完Pareto等级1的所有个体后还需要从Pareto等级2中选择3个个体，根据拥挤度排序方式，应该选择1号、2号、3号个体，但很明显选择1号、3号、5号个体其分布性更好，由此可见，传统拥挤度策略存在一定缺陷。

所以采用循环淘汰制方式，假设还需要从某Pareto等级下的k个个体中选择m个个体组成子代种群，先计算所有个体的拥挤度大小，将拥挤度最小的个体淘汰，再次进行拥挤度排序，继续淘汰拥挤度最小个体，循环k-m次，剩下的个体即为所需选择个体。这样的选择方式能够最大程度保证子代个体的均匀分布，加快算法的收敛速度。改进后的劣汰组NSGA-II算法流程如图5所示。

图5 劣汰组NSGA-II算法流程

3 仿真实验与分析

为了验证本文算法改进的有效性，选择传统NSGA-II算法、劣汰组策略NSGA-II算法、Deb等[22-23]提出的遵循NSGGA-II框架的基于参考点的NSGA-III算法来测试多目标函数的经典测试函数ZDT1-ZDT4，其优化结果如图6所示。

(a) ZDT1

(b) ZDT2

(c) ZDT3

(d) ZDT4图6 四种典型测试函数Pareto前沿图

由图6可知，在四个典型算例中，EGNSGA-II算法所得到的最优前沿面都要优于NSGA-II算法，在ZDT2-ZDT4三个函数中，EGNSGA-II算法的最优前沿也明显优于Deb等提出的基于参考点的NSGA-III算法，该测试证明了算法改进的有效性。

在S=100 km×100 km的范围里，存在一个物流中心P=(55,45),该物流中心拥有4辆不同型号的运输车即m=4，需要在一天内向周围存在的20个快递点仓库进行货物供给，车辆和快递点仓库的具体信息见表1和表2。

表1 运输车辆信息表

表2 快递点仓库信息表

续表2

根据表1、表2提供的数据，设初始父代种群个体数量N=500，劣汰组的个体数量为Nl=200，迭代最大次数tmax=200，目标分量n=2，用NSGA-III算法、多目标粒子群算法(MOPSO)、改进的NSGA-II算法、传统NSGA-II算法对该问题进行求解，得到的Pareto最优前沿如图7所示。

图7 四种算法的Pareto最优前沿

根据图7可以很明显地看出改进的劣汰组NSGA-II前沿面分布性更好，覆盖范围更大，能够得到更精确的结果。将算法最优前沿面所有点的目标函数值求和，选取求和后最小的数值作为适应度数值，可以得到四种算法的迭代过程如图8所示。

图8 四种算法迭代过程

可以看出，EGNSGA-II算法在27次左右就得到最优结果，相对于MOPSO、NSGA-II算法拥有更快的迭代速度以及更高的精度，算法性能对比提升显著。另一方面，在搜索前期NSGA-III算法与EGNSGA-II算法拥有着相似的收敛速度，但在收敛后期局部搜索过程中，EGNSGA-II算法的收敛速度更快且相对收敛精度更高。综合以上分析可以看出，EGNSGA-II算法在收敛速度和精度上都更加优秀，从而证明了该算法改进的有效性，对路径搜索问题的适应性较好。

因为时间数据差异并不大，而运输成本是影响企业效益的首要因素，所以在最优Pareto前沿选择最优解时将成本作为主要考虑的目标分量，得到最终的优化结果如表3所示。

表3 两种算法求解结果表

可以看出，在相同的配送时间下EGNSGA-II算法耗费的成本最低，改进后的算法能够有效帮助物流企业降低成本，在此方案下4辆运输车的行驶路线如图9所示。

图9 运输车路线规划

可以看出，四辆运输车的运输分配相对均匀，符合物流行业实际运输情况，算法对于该问题的适应性较好。

4 结 语

针对物流行业快递配送效率不高、车辆路径分配不合理等问题提出一种基于劣汰组策略的NSGA-II多目标优化算法，该算法采用劣汰组策略保留被拥挤度排序淘汰的优质个体，增加个体多样性扩大前期搜索范围，再将近似全局最优个体引入变异公式，平衡算法全局和局部的搜索能力，提高算法收敛精度和速度，再利用循环淘汰制策略增强子代个体的分布性。用典型的多目标测试函数对改进算法进行验证，证明了改进的有效性。最后通过物流运输实例证明该算法对物流车辆路径规划问题适应性很好，相对于传统NSGA-II算法性能上有较大提升。接下来会尝试将其他算法与改进后的NSGA-II算法进行有效融合进一步提升算法的各方面性能。