基于改进的鲸鱼优化算法的物流车辆配送路径规划

2021-10-15张进军

陇东学院学报 2021年5期

唐彦，张进军

(安徽警官职业学院，安徽合肥 230001)

带容量约束的车辆路径问题(Capacitated Vehicle Routing Problem，CVRP)的主要特征是车辆有最大容量限制、各客户需求点有货物配送需求，该问题是一种典型的NP-Hard组合优化问题[1]。传统算法很难求解CVRP问题，近年来很多研究人员将群智能算法应用于CVRP问题求解。文献2将混合变邻域生物共栖搜索算法应用于CVRP问题求解[2]。文献3将多种群人工蜂群算法用来求解带重新路由策略的CVRP问题[3]。文献4提出了一种基于改进的粒子群优化算法的车辆路径优化方法[4]。

鲸鱼优化算法[5](Whale Optimization Algorithm，WOA)具有控制参数少、收敛速度快和计算简单等优点，是一种模仿座头鲸捕食行为而衍生出的新型群体智能搜索算法。该算法已在机器学习、函数寻优、数据挖掘、电力调度、控制器设计调优等方面得到广泛应用[6-7]。目前应用鲸鱼优化算法求解CVRP的文献较少，因此本文提出一种基于改进的鲸鱼优化算法的物流配送车辆路径优化方法。研究结果表明，与WOA、PSO和GA相比，改进鲸鱼优化算法可以有效降低物流配送成本和减少配送距离，为车辆路径规划提供了新的方法。

1 改进的WOA算法

在标准的WOA算法中，座头鲸包括包围猎物、狩猎行为和随机搜索猎物等3种行为，每一只座头鲸的位置为一个可行解。

1.1 包围猎物

座头鲸发现猎物后能够快速包围式(1)所示的所发现的猎物并更新位置：

(1)

(2)

式(2)中，M为最大迭代次数；a和r为随机数，a∈[2,0]，r∈[0,1]。

1.2 狩猎行为

座头鲸狩猎采用如式(3)所示的螺旋运动方式：

(3)

式(3)中，l∈[-1,1]的随机数；b为螺旋形状的常数。

在座头鲸的狩猎行为中，鲸鱼位置更新的过程中将以50%的概率包围如式(4)所示的猎物或进行螺旋式狩猎：

(4)

1.3 随机搜索猎物

当A>1或A<-1时，鲸鱼群体离猎物远去，随机搜索更为合适的猎物，数学模型为式(5)所示：

D=|C·Xrand(t)-X|，X(t+1)=Xrand-A·D

(5)

式(5)中，Xrand为随机选择的鲸鱼位置。

针对鲸鱼算法容易陷入局部最优和“早熟”问题，将非线性收敛因子引入标准WOA算法，提出一种改进的鲸鱼优化算法(Improved Whale Optimization Algorithm，IWOA)，其改进策略为：

收敛因子a数值大小直接影响WOA算法的搜索能力和寻优能力。在基本WOA算法中，收敛因子a搜索前期较大，后期较小，导致其后期容易陷入局部最优，本文为解决该问题，提出一种随迭代次数非线性变化的收敛因子，其更新公式为式(6)：

(6)

式(6)中，astart和aend分别为a的初始值和终止值；μ为调节系数，文中取μ=25。

2 物流车辆配送路径规划

车辆配送路径规划问题可表述为[8-9]：假设配送中心配备有K辆物流运输车，车辆载重容量为qk(k=1,2,3,…,K)，配送需求点有L个，第i个需求点的需求量为gi(max(gi)≤max(qi))，完成需求点任务i货物装载或卸货的时间为Ti，其中任务i必须在时间段[ETi,LTi]内完成。ETi、LTi分别为任务i的最早开始时间和最迟开始时间。若配送车辆早于ETi到达需求点，则配送车辆等待；否则，任务将被延迟。车辆物流配送示意图如图1所示。

图1 车辆物流配送示意图

根据问题描述将货物需求点编号为1,2,3，…,L，物流配送中心编号为0，任务和配送中心编号为i=(0,1,2,3,…L)，则决策变量为[10]：

(7)

(8)

综合所述，物流车辆配送路径数学规划模型为：

(9)

(10)

(11)

(12)

式(9)～(12)中，si为配送车辆到达需求点i的时间；cij为需求点i到需求点j的运输成本；pE、pL分别为配送车辆提前到达需求点i的或者滞后到达需求点i的单位时间内的等待成本以及惩罚成本。该数学模型中每个需求点均有车辆配送，且每个需求点只能由一辆物流配送车辆配送；与此同时，同一配送路径上的需求点的需求量之和应小于等于物流配送车辆的最大载重。

为实现物流配送车辆路径的最优规划，解决该问题的关键是构造合适的最佳鲸鱼位置表达方式。参考文献11-12构造一个2L维空间对应L个需求点任务的物流配送车辆路径规划问题，保证需求点任务为2维[11-12]。若需求点任务为7，配送车辆为3，需求点任务编号为[1 2 3 4 5 6 7]。此时最佳鲸鱼位置向量X如图2所示，其中最佳鲸鱼位置对应物流配送车辆的编号和行驶路径。

图2 车辆和路径编号

由图2车辆和路径编号可知，最佳鲸鱼位置对应的物流车辆配送路径为：(1)车辆1∶0→1→0；(2)车辆2∶0→4→5→3→2→0；(3)车辆3∶0→7→6→0。

基于IWOA的车辆配送物流路径优化算法步骤具体描述如下：

Step1：设定IWOA算法参数：种群规模N、最大迭代次数Maxgen、当前迭代次数t以及螺旋形状常数b，并且随机初始化鲸鱼群体初始位置Xi(i=1,2,…,n)；

Step2：按式(13)计算每个鲸鱼个体的适应度，并对适应度进行排序，找到适应度最小时所对应的鲸鱼个体即最佳鲸鱼个体X*并保存；

(13)

Step3：如果t≤Maxgen，则更新参数a、A、C、l和p；

Step4：当p<0.5时，如果|A|<1，按式(1)更新当前鲸鱼个体的空间位置；当|A|≥1时，则随机选择鲸鱼个体位置Xrand，并且按式(5)更新当前鲸鱼个体的空间位置；

Step5：当p≥0.5时，按式(4)更新当前鲸鱼个体的空间位置；

Step6：限制和修正鲸鱼个体搜索空间；

Step7：按式(13)计算每个鲸鱼个体的适应度，并对适应度进行排序，找到适应度最小时所对应的鲸鱼个体即最佳鲸鱼个体X*并保存；

Step8：判断算法终止条件：如果t≥Maxgen，则转到步骤Step9；反之，重复步骤Step3～Step7；

Step9：输出最优鲸鱼个体的空间位置X*及其适应度，即输出车辆物流配送路径。

3 仿真试验与结果分析

为了验证IWOA进行物流配送车辆路径规划的有效性和可靠性，选择参考文献13中实例为研究对象[13]，各需求点的坐标位置以及用户需求和中心仓库数据信息如表1和表2所示。

表1 配送中心和需求点坐标

表2 配送中心和用户需求

将IWOA和WOA、PSO、GA进行对比，不同算法参数设置如下：(1)WOA参数：种群规模N=50、最大迭代次数Maxgen=500。(2)粒子群算法(particle swarm optimization algorithm，PSO)：种群规模N=50、最大迭代次数Maxgen=500、学习因子c1=c2=2、惯性权重w=0.2。(3)遗传算法(genetic algorithm，GA)：种群大小N=50、最大迭代次数Maxgen=500交叉概率Pc=0.7和变异概率Pm=0.1，对比结果如图3～图7所示。

图3 IWOA配送路径图

图4 WOA配送路径图

图5 PSO配送路径图

图6 GA配送路径图

图7 寻优对比曲线

由表3可知，GA、PSO和GA进行物流车辆配送路径规划时，GA的平均行驶成本和行驶里程分别为603.0031元和139.5906km，PSO的平均行驶成本和行驶里程分别为565.8001元和138.9368km，WOA的平均行驶成本和行驶里程分别为359.3838元和130.2608km，而改进的IWOA的平均行驶成本和行驶里程分别为337.6755元和129.1333km。与WOA、PSO和GA相比，在行驶里程和平均行驶成本方面，IWOA进行车辆路径规划的成本最低且行驶里程最短。由图7寻优对比曲线可知，IWOA进行车辆路径规划寻优具有更快的收敛速度和更低的平均行驶成本。通过综合对比验证了IWOA进行物流车辆配送路径优化的有效性和可靠性。