基于鲸鱼算法的循环取货路径优化研究

陈荣 王雯阳 卞东东

摘  要：针对汽车零部件入场物流循环取货路径优化的问题，考虑车载容量和时间窗等约束条件，构建最小化物流成本的数学模型。首先，在鲸鱼优化算法的基础上引入自适应权重，提升算法寻优速度;其次，利用变螺旋方式更新位置，提高算法全局搜索能力;最后结合模拟退火算法，改善算法的早熟现象有助于实现全局最优。通过A企业入场物流数据进行仿真实验，改进后的算法不仅减少了车辆数目还降低了总物流成本，可知改进后的鲸鱼算法求解路径问题时可以提供更优化的方案。

关键词：车载容量;软时间窗;路径优化;改进鲸鱼算法

中图分类号：U116.2    文献标识码：A

Abstract： Aiming at the problem of the optimization of the entry logistics cycle pick-up route for automobile parts， a mathematical model was built to minimize the logistics cost considering the constraints of vehicle capacity and time window. Firstly， introduce adaptive weights on the basis of the whale optimization algorithm to improve the algorithm optimization speed. Secondly， use the variable spiral method to update the position and improve the algorithm's global search ability. Finally， combined with the simulated annealing algorithm， improving the premature phenomenon of the algorithm is helpful to achieve globally optimal. Through the simulation experiment of A enterprise's entry logistics data， the improved algorithm not only reduces the number of vehicles but also reduces the total logistics cost. It can be seen that the improved whale optimization algorithm can provide a more optimal solution when solving the routing problem.

Key words： vehicle capacity; soft time window; path optimization; improved whale algorithm

0  引  言

近年来，随着全球汽车制造企业的快速发展，汽车零部件入场物流逐渐成为汽车制造企业降本增效的重要环节。借鉴国内外先进汽车制造企业的经验，通过循环取货的方式可以有效地降低零部件入场物流的费用。现如今国内外学者对于循环取货的路线设计优化主要侧重于研究带有车载容量限制的车辆路径问题以及考虑时间窗的车辆路径优化问题，而本文综合考虑车载容量和时间窗约束，使问题更贴近实际。

车辆路径问题（VRP）最早由Dantizg于1959年提出，其基础是考虑车载容量的车辆路径问题（CVRP）;黄戈文等[1]针对CVRP，通过灰狼空间整数编码以及先路由后分组的策略对灰狼优化算法进行优化并求解问题。Xiao-Fang Ji等[2]设计了一种自适应猫群优化（ACSO）的新型混合算法解决货物取货中的车辆路径问题。考虑时间窗的车辆路径优化问题（VRPTW）是在傳统的车辆路径问题上增加了时间窗约束，孙沪增等[3]利用改进的蚁群算法进行求解VRPTW，并通过GIS物流取货实例进行验证;文展等[4]提出一种改进的基于集合的粒子群优化算法求解VRPTW。李珺等[5]提出细菌觅食优化算法与大邻域搜索算法相结合的混合算法求解VRPTW;魏小迪等[6]针对花朵授粉算法的局限性进行改进求解VRPTW;Shuai Zhang等[7]设计了一种基于模糊仿真方法的ALNS算法对VRPTW进行求解。

随着群智能优化算法的发展，越来越多的算法被用来解决复杂的优化问题。例如2016年Mirjalili等[8]提出的鲸鱼优化算法（WOA），它已被用于优化各个领域。刘磊等[9]提出引入最优邻域扰动策略提高鲸鱼优化算法处理最优问题时的全局搜索能力;蔡雨岑等[10]针对地面无人车路径规划的问题，利用和声搜索策略和动态平衡策略相结合的平衡鲸鱼优化算法进行求解。然而目前文献中未发现将鲸鱼优化算法用于循环取货车辆路径优化问题中，因此本文采用控制参数少且易于实现的鲸鱼优化算法进行求解。

1  问题描述

已知在一个循环取货物流系统中，零部件制造商作为供应方，A汽车制造企业作为零部件需求方，A企业委托第三方物流中心C公司进行零部件的取货。在循环取货流程中，第三方物流中心按照零部件需求订单派遣车辆装载空器具从物流中心出发，按照规定的时间窗、路线和需求订单，前往各个零部件供应商取货，到达供应商处后合理的安排空器具的卸载与零部件的装载，完成取货任务后返回物流中心。

2  数学建模

2.1  基本假設

本文针对循环取货的数学模型，提出如下假设：

（1）物流中心与各个供应商的距离已知，且各个供应商之间的距离已知;

（2）各个供应商的待取零部件体积均不超过车辆的最大装载能力;

（3）车辆的固定成本已知，运输成本与行驶距离成正比;

（4）不管车辆故障、交通堵塞、天气等不可控因素，所有车辆都保持匀速行驶。

2.2  参数设置和符号说明

其中：基于软时间窗定义时间惩罚函数ct的具体表达式如下：

ct=

ca-t表示车辆早于供应商时间窗要求的罚款成本，ct-b表示车辆晚于供应商时间窗要求的罚款成本，在供应商规定时间窗内服务惩罚成本为零。

2.3  数学模型

基于上述分析，本文的数学模型描述如下：

MinW=xf+xdC+cmaxa-t， 0+cmaxt-b， 0                （1）

s.t.

x=y， ？坌j∈V， ？坌k∈K                                                （2）

x=y， ？坌i∈V， ？坌k∈K                                                （3）

x≤S-1， ？坌k∈K， S≥2                                         （4）

x=x， ？坌k∈K                                                    （5）

yq≤Q， ？坌k∈K                                                      （6）

t+u+t≤t+M1-x， ？坌i， j∈V， ？坌k∈K                                  （7）

Q， q， u>0， i∈V， k∈K                                                  （8）

约束条件：

目标函数式（1）表示最小化循环取货的物流成本，第一项表示车辆的固定启动成本，第二项表示车辆的运输成本，第三项表示取货车辆违反供应商时间窗要求的惩罚成本;式（2）表示在一次循环取货中，车辆k最多只能从某取货点发出一次;式（3）表示在一次循环取货中，车辆k最多只能到达某取货点一次;式（4）表示子回路消除约束，该约束保证了两个供应商之间只有一條路径;式（5）闭环约束：表示所有的车辆都是从物流中心发出，完成任务后再回到物流中心;式（6）车载容量约束：指每辆车的载货量不超过车辆的最大装载容量;式（7）时间窗约束：表示车辆从上一个供应商取货到访问下一个供应商需满足的时间约束;式（8）变量的非负约束。

3  改进的WOA算法设计

3.1  WOA算法基本原理

WOA是2016年由Mirjalili提出的一种基于座头鲸鱼群体狩猎行为的新型群智能优化算法。该算法通过对鲸鱼的随机搜索，气泡网攻击以及包围捕食等行为进行优化搜索，从而找到问题的最优解。

3.2  WOA的改进

3.2.1  变螺旋更新位置

WOA中，鲸鱼进行螺旋气泡网捕食时通过参数b控制螺旋形状，该参数设置为常数时会导致鲸鱼移动位置的方式比较单一。因此将该参数设置为随着迭代次数变化的变量，从而动态调整鲸鱼进行气泡网捕食时的螺旋形状。则变螺旋更新位置的公式如下：

Xj+1=wj·j+·e·cos2πl                                   （9）

其中：b=e。

3.2.2  结合模拟退火算法

模拟退火阶段重新定义一个新的初始种群，用于调整种群鲸鱼个体的位置。该阶段接受较差解的概率设置为：

p=exp

其中：fX是新种群中第s个鲸鱼个体的适应度值，fX-fX是新旧鲸鱼个体的适应度差值，概率p通过该差值进行调整。

3.3  改进WOA算法的求解步骤

（1）初始化算法参数：鲸鱼初始种群的规模N，问题维数dim及最大迭代次数T。

（2）随机生成鲸鱼的初始种群，计算种群的适应度值并记录最优个体X，计算模拟退火的初始温度t。

（3）计算并更新参数：a、C、A、l、p。

（4）若p<0.5且>1，则种群内鲸鱼个体按照公式j+1=wj·j-×更新当前位置，否则（即≤1）鲸鱼个体根据公式j+1=wj·-·更新位置;若p≥0.5，则种群内个体依据公式（9）调整当前位置。

（5）进入到模拟退火阶段，重新定义一个新的鲸鱼群体，随机初始化新鲸鱼群体的个体位置，计算群体的适应度值。

（6）计算并比较更新后的新旧种群的适应度值。若新种群个体适应值优于原种群则进行替代操作;如果新种群个体适应度值比原种群低，则利用概率p判断是否接受新种群中的鲸鱼位置。

（7）退火操作：t=0.99*t。

（8）记录最优的鲸鱼位置X以及适应度值，若j

（9）输出全局最优个体X以及适应度值。

4  实例分析

4.1  实例数据

已知在A汽车制造企业循环取货过程中，第三方物流中心C公司派遣的是飞翼式卡车，该车型的最大装载容量为61m3，平均速度为50km/h。其中该卡车的固定成本为300元/辆，卡车的单位时间运输成本为10元/km，提前和延迟到达供应商处的惩罚成本分别为20元/h和每小时30元/h。各供应商的基本信息如表2所示，各个供应商之间的距离如表3所示。

4.2  实验结果分析

针对上述实例使用基本的WOA算法和改进的WOA算法进行求解，实验结果如图1和图2所示。

基本WOA算法求解的结果如表4所示。

改进的WOA算法求解的结果如表5所示。

通过结果对比发现，改进的WOA算法不仅减少了物流中心派遣车辆的数目，使原来9辆车减少到7辆车，载货率还由原来的65%提升到84%，提高了19%，行驶总距离由2 367km变为1 889km，减少了20%，物流总成本由3 581元降为2 896元，优化了19%。由此可以看出，改进的WOA算法在合理规划循环取货路径以及优化物流成本方面表现出明显优势。

5  结束语

针对汽车零部件入场物流中循环取货路径优化问题，本文以A企业的汽车零部件入场物流的实际情况为例。以最小化入场物流的总物流费用为目标，考虑车载容量和供应商的时间窗等因素，建立单目标数学模型。将WOA算法运用到模型中，首先使用变螺旋更新位置的方式使算法寻优方式多样化，其次结合模拟退火算法使算法跳出局部最优解。通过A企业的实际数据验证，改进后的WOA算法可以为循环取货提供更优化的路径规划方案，从而更节约物流成本。

参考文献：

[1] 黄戈文，蔡延光，戚远航，等. 自适应遗传灰狼优化算法求解带容量约束的车辆路径问题[J]. 电子学报，2019，47（12）：2602

-2610.

[2]  Xiao-Fang Ji， Jeng-Shyang Pan， Shu-Chuan Chu， et al. Adaptive Cat Swarm Optimization Algorithm and Its Applications in Vehicle Routing Problems[J]. Mathematical Problems in Engineering， 2020，15（26）：1-14.

[3] 孫沪增，李章维，秦子豪，等. 带时间窗车辆路径规划算法研究与实现[J]. 小型微型计算机系统，2020，41（5）：972-978.

[4] 文展，唐康健，李文藻. 一种改进粒子群优化算法在车辆路径问题的应用研究[J]. 重庆邮电大学学报（自然科学版），2020，32（5）：891-897.

[5] 李珺，郝丽艳，何奕涛，等. 改进细菌觅食算法求解带时间窗的车辆路径优化问题[J]. 计算机工程，2020，59（26）：5-8.

[6] 魏小迪，郑洪清. 求解带时间窗车辆路径问题的改进离散花朵授粉算法[J]. 数学的实践与认识，2020，50（2）：193-200.

[7]  Shuai Zhang， Mingzhou Chen， Wenyu Zhang， et al. Fuzzy optimization model for electric vehicle routing problem with time windows and recharging stations[J]. Expert Systems With Applications， 2020，145：113-123.

[8]  Seyedali Mirjalili， Andrew Lewis. The Whale Optimization Algorithm[J]. Advances in Engineering Software， 2016，16（8）：35-95.

[9] 刘磊，白克强，但志宏，等. 一种全局搜索策略的鲸鱼优化算法[J]. 小型微型计算机系统，2020，41（9）：1820-1825.

[10] 蔡雨岑，杜鹏桢. 基于平衡鲸鱼优化算法的无人车路径规划[J]. 控制与决策，2020，16（4）：1-9.