基于智能优化算法的车辆路径问题的研究与应用

张亚龙 肖银宝

摘要：在电子商务蓬勃发展的大环境下，物流行业已经成为推动我国经济发展的重要力量，人们对物流配送的要求也越来越高，如何科学合理地规划配送车辆的路线，实现高效率、低成本是当前学者们研究的重点。物流配送遍及生产生活的方方面面，面对日益复杂的道路环境，随着信息化水平的提升，这使得用智能计算推动物流配送模式革新有着重要意义。本文通过科学合理的方法对复杂的车辆路径问题（VRP）的衍生问题，即带时间窗的车辆路径问题和同时取送货的车辆路径问题（VRPSPDTW）进行求解，主要通過对现有的鲸鱼优化算法进行研究，针对鲸鱼算法求解问题后期种群多样性缺失的问题，引入新的收敛因子、自适应权重和Metropolis准则对其进行补足，将其应用至实际问题中，验证其可行性。

关键词：智能计算；路径规划；鲸鱼算法；VRP

1概述

随着电子商务行业的强劲发展，物流行业逐渐成为推动我国经济发展的主要力量，物流配送的车辆路径问题，越来越得到有关学者的重视，车辆路径作为经典的组合优化问题一直是研究的热点与难点。随着信息技术的快速发展，计算机算力大幅提升，使得启发式算法求解车辆路径及其衍生问题更加科学合理。本文主要从车辆路径问题的发展现状，传统鲸鱼优化算法方案的优缺点，对其进行改进，来提高其运行效率。

2研究方案

WOA算法是一种群智能优化算法，灵感来自海洋中座头鲸独有的气泡网捕食方式。座头鲸发现猎物后，通过制作气泡网的方式，以形似螺旋的路径进行捕食，其具体行为包括包围捕食、螺旋更新位置及搜索猎物。鲸鱼种群捕食过程中，通过最佳个体的位置来进行位置更新，最终收敛域最优目标值附件，但经典的鲸鱼优化算法存在有收敛性慢，算法后期迭代缺乏种群多样性，易陷入局部最优。本文在基本的鲸鱼优化算法上加以改进，通过采用新的收缩因子方法，较好地调节了全局和局部的搜索能力。引入自适应权重策略很好地保持了种群的多样性，使算法的收敛性和搜索性提升。引入Metropolis准则，通过以一定的概率接受较差的点来提升全局寻优能力，避免了算法陷入局部最优解。

3传统鲸鱼优化算法的实现

车辆路径问题及其衍生问题一直是NPHard问题，其约束条件繁杂，在对其目标问题建模后，根据鲸鱼优化算法包括三种更新个体位置的方式，分别是气泡攻击、搜索捕食、包围猎物，对问题进行求解。

当鲸鱼在包围捕获猎物时，首先要确定猎物位置，但是猎物在搜索空间中的位置往往是不确定的。鲸鱼优化算法将猎物位置或者接近目标猎物的位置作为当前最优候选解，其他鲸鱼个体通过最优候选解来更新自身所在的位置。

鲸鱼优化算法个体更新位置方式如下：

设p为［0，1］之间的随机数，p是捕食机制概率，则：

若p0.5，则鲸鱼个体采用气泡攻击方式以螺旋式形式进行个体位置更新，即当前鲸鱼个体以螺旋式的方式向当前最佳鲸鱼个体靠近。

气泡攻击方式下的鲸鱼个体位置更新公式为：

Xi（t+1）=X（t）+Deblcos（2πl）（1）

D=X（t）－Xi（t）（2）

其中，Xi（t+1）表示下一代第i只鲸鱼的位置，X（t）表示当前时刻全局最优向量，即当前最优鲸鱼个体位置，b为常数，定义了对数螺旋的形状；l为［－1，1］的随机数。D=X（t）－Xi（t）表示为第i只鲸鱼个体的位置到当前最优鲸鱼个体位置的距离。

若p<0.5且A1，则鲸鱼个体采用搜索捕食方式进行个体位置更新，即鲸鱼个体可能不向最佳鲸鱼个体靠近，而是随机选择一只鲸鱼个体靠近。

搜索捕食方式下得鲸鱼个体位置更新公式为：

Xi（t+1）=Xrand（t）－A×D（3）

D=C×Xrand（t）－Xi（t）（4）

其中，假设在d维空间中，Xrand（t）表示为当前鲸鱼种群中随机一只鲸鱼个体的位置，D=C×Xrand（t）－Xi（t）表示为当前种群中第i只鲸鱼个体的位置到当前种群中随机一只鲸鱼位置的距离，A=2a×r1－a，C=2×r2，其中，r1，r2为［0，1］之间的随机数。

若p<0.5且A<1，则鲸鱼个体采用包围猎物的方式进行个体位置更新。

包围猎物方式下得鲸鱼个体位置更新公式为：

Xi（t+1）=X（t）－A×D（5）

D=C×X（t）－Xi（t）（6）

其中，D=C×X（t）－Xi（t）表示当前种群中第i只鲸鱼个体的位置到当前最优鲸鱼个体位置距离，A=2a×r1－a，C=2×r2，其中，r1，r2为［0，1］之间的随机数。

当鲸鱼算法访问完所有的客户，第一次迭代完成，每条鲸鱼均找到了对应的行驶路径，相当于车辆完成了一次运行，在达到最大迭代次数时，选取所有迭代次数中整体适应度值最小的鲸鱼所选的路径，作为全局最优路径，总路径最短的鲸鱼为全局最优解。

传统鲸鱼算法解决车辆路径问题时会有两个缺点：（1）根据鲸鱼优化算法三个位置更新公式，不难看出，位置更新是通过最优个体的位置变动来更新此时鲸鱼个体的位置，会造成种群多样性的丢失，对于大规模问题算法初期，解的搜索具有盲目性。（2）经典鲸鱼优化算法缺少扰动机制，存在算法后期收敛速度慢，易陷入局部最优等缺陷。

4对传统鲸鱼算法的改进

鲸鱼优化算法是元启发式群智能优化算法，虽然有良好的启发性，但存在着求解精度低、收敛速度慢、易陷入局部最优解的情况。针对以上几个缺陷做出以下改进：

（1）通过采用新的收缩因子方法，较好地调节了全局和局部的搜索能力。

（2）引入自适应权重策略很好地保持了种群的多样性，使算法的收敛性和搜索性提升。

（3）引入Metropolis准则，通过以一定的概率接受较差的点来提升全局寻优能力，避免了算法陷入局部最优解。

4.1采用新的收缩因子

传统的鲸鱼优化算法的收缩因子为线性收缩因子，a的值从2到0线性下降，其收敛速度较慢，导致搜索时间较长，降低了算法的效率，传统的搜索因子公式为：

a=2－2tItermax（7）

本文通过采用非线性收缩因子的方法，较好地调節了算法的全局和局部搜索能力，新的收缩因子公式如下：

a=2－2sinμtItermaxπ+φ（8）

其中Itermax是最大迭代次数，t为当前迭代次数，μ、φ是表达式的相关系数，为使收敛因子a满足从2至0递减，选取μ=1/2，φ=0；用新的收敛因子公式计算系数向量A，设r1，r2为［0，1］之间的随机数，则A=2a×r1－a，系数向量C=2×r2。

4.2引入自适应权重

通过鲸鱼算法的所搜机制可知，位置更新是通过最优个体的位置变动来更新此时鲸鱼个体的位置，会造成种群多样性的丢失，对于大规模问题算法初期，解的搜索具有盲目性。自适应权重ω的公式如下：

ω=1－etItermax－1/e－1（9）

其中Itermax是最大迭代次数，t为当前迭代次数。通过采用自适应权重策略很好地保持了种群的多样性，使算法的收敛性和搜索性提升。

4.3引入Metropolis准则

1953年，Metropolis提出重要性采样方法，即以概率来接受新状态，而不是使用完全确定的规则，称为Metropolis准则。

假设前一状态为X（n），系统受到一定扰动，状态变为X（n+1），相应地，系统能量由E（n）变为E（n+1），定义系统由X（n）变为X（n+1）的接收概率为P，则P的概率计算公式为：

P=1，E（n+1）<E（n）

exp（－En+1－E（n）T），x0（10）

当状态转移之后，如果能量减小了，那么这种转移就被接受了。如果能量增大了，就说明系统偏离全局最优位置更远了，此时算法不会立即将其抛弃，而是进行概率判断。首先在区间［0，1］产生一个均匀分布的随机数ε，如果ε<P，这种转移将被接受，否则拒绝转移，进入下一步，如此循环。

其核心思想是当能量增加时以一定概率接收，即陷入局部最优时有一定概率能跳出局部最优，其中以能量的变化量和T进行决定概率P的大小，所以P这个值是动态的。

经典鲸鱼优化算法缺少扰动机制，存在算法后期收敛速度慢、易陷入局部最优等缺陷。在更新鲸鱼种群中的鲸鱼个体后，根据Metropolis准则，以一定的概率接受劣质个体。概率公式计算如下：

P1=e－fXit+1－fXi（t）/fXi（t）T（11）

其中，T为当前迭代次数时的温度，初始迭代温度T0为100。fXi（t）为第i只鲸鱼当前迭代下的最优路径，fXi（t+1）是下一次迭代下第i只鲸鱼的最优路径。每次迭代后的降温公式为：T=αT，其中，α为降温速率，设定为0.99。

4.4算法流程

下图为改进的鲸鱼优化算法流程图，整个算法对问题的求解过程分为以下步骤：

Step1初始化鲸鱼算法的相关参数，包括种群规模N、当前迭代次数t、最大迭代次数Itermax、初始温度T0和降火速率系数α；

Step2构建解空间，根据适应度函数，计算鲸鱼种群中的每个鲸鱼个体的所在位置的适应度值，确定初始种群中个体的最优位置和种群全局最优位置，初始个体适应度值最小的对应最优位置，就是初始种群的全局最优位置；

Step3采用非线性的方法计算收缩因子a，计算并更新鲸鱼优化算法系数向量A，C；

Step4引入自适应权重ω，根据鲸鱼个体更新公式、更新鲸鱼种群中的所有鲸鱼个体的位置，得到每只鲸鱼的初始可行路径；

Step5位置更新结束后，使用Metropolis准则更新种群；

Step6对Metropolis准则进行降温，T=αT；

Step7判断是否达到种群最大迭代次数Itermax，如果达到最大迭代次数，输出最优鲸鱼个体位置，得到最优鲸鱼个体的可行路径，计算结束，否则转到Step3，重复执行Step3至Step6，达到最大迭代次数时，输出求解结果。

5分析总结

本课题主要是应用鲸鱼优化算法，通过对其改进以便更好加快算法的收敛速度和求解精度，以此来更好地满足实际应用对效率和准确性的需求。

虽然创造性地从收缩因子方面及引入自适应权重和Metropolis准则来改进鲸鱼算法，但是仅从鲸鱼种群多样性和扰动机制上考虑是不够的，在未来的研究中还需要进一步加深。

主要创新点：

（1）通过对传统鲸鱼算法的改进，提高其搜索性能，增加其扰动机制，并采用Metropolis准则来增强其跳出局部最优的能力。

（2）优化参数的选择，提高其收敛性，提高算法运行效率，可更好地应用于复杂问题。

参考文献：

［1］唐彦，张进军.基于改进的鲸鱼优化算法的物流车辆配送路径规划［J］.陇东学院学报，2021，32（05）：610.

［2］庞燕，罗华丽，邢立宁，等.车辆路径优化问题及求解方法研究综述［J］.控制理论与应用，2019（10）：15731584.

［3］杨博，李昌华，李智杰，等.改进鲸鱼算法及其在路径规划的应用［J］.计算机测量与控制，2021，29（02）：187193+201.

［4］余贤星.一种改进的多领导鲸鱼优化算法［J］.软件工程，2022，25（11）：2834.

［5］杨柳，王颍超，侯汉坡.冷链低碳配送路径优化研究［J］.商业经济研究，2019（17）：104107.

［6］谢冲冲，李莹.基于改进算法的移动机器人路径规划［J］.重庆大学学报，2021，44（12）：140148.

［7］陈荣，王雯阳，卞东东.基于鲸鱼算法的循环取货路径优化研究［J］.物流科技，2021，44（10）：2832.

［8］崔东文.鲸鱼优化算法在水库优化调度中的应用［J］.水利水电科技进展，2017，37（03）：7276+94.

［9］高嘉，任亚明.基于模拟退火算法组合优化问题的求解［J］.企业科技与发展，2021（05）：6668.

［10］邓绍强，郭宗建，李芳，等.基于Metropolis准则的自适应模拟退火粒子群优化［J］.软件导刊，2022，21（06）：8591.

项目：本文受到广东高校重点领域专项新一代信息技术重点领域专项项目（2021ZDZX1019）的技术及经费支持

作者简介：张亚龙（1997—），男，汉族，河南洛阳人，硕士研究生在读，研究方向：智能优化算法及应用；肖银宝（1973—），男，汉族，云南昆明人，硕士，助理研究员，研究方向：科技管理及信息化。