多策略改进麻雀搜索算法的同时取送货车辆路径规划

肖 磊 （沈阳大学 机械工程学院，辽宁 沈阳 110003）

0 引 言

同时取送货车辆路径问题(Vehicle Routing Problem with Simultaneous Pick-up and Distribution, VRPSPD)是经典VRP的扩展，由Min H在研究图书馆书籍配送与回收问题时首次提出。VRPSPD作为传统逆向物流的拓展，将取货需求融入配送过程中，比单独进行配送或取货更能减少配送车辆数量，从而提高客户满意度和车辆装载率，降低不确定性成本，并实现物流资源的最大化利用。随着物流需求的增长，VRPSPD被视为一种更科学和合理的配送方式，并逐渐成为学术界的研究热点。

高振迪等[1]针对库存不平衡问题，提出了一种基于模糊客户需求的多商品多批次车辆路径规划模型，并采用改进禁忌搜索算法进行求解。孟姗姗等[2]提出了一种卡车与无人机相结合的配送模式，并采用改进模拟退火算法优化路径。王新杰等[3]研究了基于共享车辆与客户订单的多配送中心联合取送货车辆路径问题，并证明了大联盟配送方式具有稳定性和成本节省优势。解永亮等[4]针对多温区冷链物流配送问题，提出了混合蚁群算法的解决策略。张烜荧等[5]采用超启发式分布估计算法来解决带有软时间窗的物流取送货车辆配送问题。袁晓建等[6]通过在VRPSDP中引入时间窗，建立数学模型并设计了一种改进的量子算法对模型进行求解。

本文主要研究软时间窗约束下的取送货车辆路径规划，首先构建了整数规划模型以达到最低成本和最高客户满意度，然后采用改进麻雀搜索算法求解模型，并通过实例验证其优越性，最终得到了最优路径图。

1 问题描述及建模

1.1 问题描述

同时取送货车辆路径规划问题可描述为：一个配送中心为其所服务区域提供取送货服务，要求在满足客户需求的情况下完成服务后返回配送中心，配送车辆必须为所有客户点提供服务。本文建立了一个以最低总成本和最高客户满意度为目标的数学模型，涉及车辆运行成本、调用成本和时间窗惩罚成本，同时需满足客户约束条件与需求。模型中对变量的定义见表1。

本文现提出以下假设：设定单一配送中心；已知客户需求量且不超过车辆最大载重；车辆型号、载重能力和速度相同；已知客户地点与配送中心间距离；仅为每位客户服务一次；同车实现取送混合装载；不考虑天气因素。

1.2 数学建模

基于上述问题描述和变量的定义，构建双目标VRPSPD数学模型如下。

目标函数（1）—（3）分别为车辆运行成本、调用成本和时间惩罚成本；式（4）为最小总成本；式（5）为最小顾客不满意度。约束条件式（6）为每个客户节点被访问且仅被访问一次；式（7）—（8）为每辆车有且仅有配送一次；式（9）—（14）为车辆载重约束；式（15）—（16）为服务时间约束；式（17）为车辆行驶里程约束；式（18）为决策变量。

2 求解算法

2.1 麻雀搜索算法

麻雀搜索算法（Sparrow Search Algorithm, SSA）由Xue J K于2020年首次提出，此新型群体智能优化算法的灵感来自雀鸟的觅食与反捕食行为。SSA算法中有发现者、追随者和警戒者，分别按照各自规则进行位置更新，更新规则如下。

其中，t为当前迭代次数，T为最大迭代次数，Xij为第i个麻雀在j维中的位置信息。α∈（0，1]的随机数，R2∈[0，1]为预警值，ST∈[0.5，1]为安全值。Q为随机数，L是维数为1×d的矩阵，元素全为1。

其中，Xp为追随者的最佳位置，是全局最差位置，A+是一个随机赋值为1或-1的矩阵，其维度为1×d，且A+=AT（AAT）-1。

其中，为全局最优位置，β为步长控制参数，K∈[-1，1]的随机数，fi为麻雀个体的适应度值，fg和fw为最佳和最差的适应度值，ε是极小常数。

2.2 改进麻雀搜索算法

2.2.1 立方混沌映射

本文针对麻雀搜索算法初始化阶段存在的局部最优和收敛精度问题，采用混沌立方映射方法。这种方法利用混沌理念的偶然性和规则性特点，实现特定范围内的均匀分布，从而提高算法的稳定性和收敛精度。因混沌立方映射展现出优越的不可预见性和分布均衡性，所以本文采用混沌立方映射来优化麻雀搜索算法的初始阶段。

假设初始麻雀种群由n个d维个体组成，在d维空间中随机产生麻雀个体为Xi=（x1，x2，x3...，xd），即随机生成一个每维都在[-1，1]区间内的d维向量作为第一个个体。

其中，Xi表示麻雀实际个体的变量值；Xlb和Xub为解空间中每个个体在各维度上的上下边界。

2.2.2 精英反向学习策略

反向学习策略（Opposition-Based Learning, OBL）是计算智能领域的一种新兴策略，其通过寻找反向解并比较优劣，可提高群体多样性和解质量，避免局部最优。

精英反向学习策略（Elite Opposition-Based Learning, EOBL）针对反向学习策略在某些情况下无法更容易搜索到全局最优解的问题进行了改进，EOBL通过引入精英策略与精英个体进行反向学习，生成精英反向解，并选择优秀个体，以提高种群多样性，从而更有效地寻找全局最优解。

设Xi=（xi，1，xi，2，…，xi，d）为d维空间中的一个普通粒子，普通粒子的某个自身极值点为精英粒子，即精英反向解定义如下。

其中，Xij∈[aj，bj]，m是精英反向系数，为0-1间的随机数，[caj，cbj]为第j维搜索空间的动态边界，可通过下式计算得到：

当反向解处于边界之外，就需要进行越界处理，公式如下。

2.2.3 正余弦优化算法

正余弦优化算法(Sin Cos Algorithm，SCA)是由Mirjalili于2016年创立的新颖群体智能优化算法。此算法利用了正弦和余弦函数的振动特性来执行优化搜索，它的优点包括参数较少、结构简单以及算法收敛性能佳，公式如下。

其中，Xi为第i个待优化变量，Li和Ui分别为Xi的上界和下界。

SCA基于适应度函数计算每个个体的适应度值，并将最优个体记录为X*。在搜索过程中个体位置更新公式如下。

其中，为第t代种群中的第i个个体位置，为最优个体位置。a为大于1的常数，设a=2。t为当前迭代次数，tmax为最大迭代次数。r2∈（0，2π），r3∈（0，2），r4∈（0，1）。

2.2.4 ISSA 算法流程

本文提出的ISSA算法，采用立方映射混沌算子和反向选择策略进行种群初始化。通过精英反向学习策略增强多样性，结合正弦余弦算法优化追随者位置更新，并采用线性递减方法控制警戒者数量，以提高全局搜索能力、探索效率和收敛速度。警戒者数量的线性递减公式如下：

其中，Numb为现有的警戒者数目，t为当前的迭代次数，tmax为最大迭代次数，Numbint表示初始警戒者数量。

改进后麻雀算法的具体算法步骤如下。

Step1：初始化麻雀数量，定义相关参数；

Step2：利用立方混沌映射方法初始化种群；Step3：加入OBL提高种群的多样性，令t=1；

Step4：若算法没有达到最大迭代次数tmax，则计算个体适应度值，并记录最佳个体及其位置；

Step5：根据式（24）和（26）更新发现者的位置；

Step6：根据式（28）更新追随者的位置；

Step7：根据式（21）更新警戒者位置，根据式（30）在算法后期对警戒者数量进行控制；

Step8：进行动态边界控制，缩小搜索范围；

Step9：获取更新后的麻雀种群；

Step10：判断算法是否达到最大迭代次数tmax，若达到，则输出最优解，否则回到Step4。

ISSA流程图如图1所示。

3 仿真实验与结果分析

3.1 案例描述及实验参数设置

本文选取M物流企业作为实例，来检验所建立的路径规划模型和改进的麻雀搜索算法。M物流企业在某区域设有一个营业部，其作为配送中心服务于周边的揽投点，揽投点每日需要取送货服务。现选取M物流企业某一天的数据进行求解，表2展示了当天33个客户的具体相关信息。模型及配送车辆的相关参数设置见表3。

表2 配送中心及各客户点相关信息表

表3 模型及配送车辆的相关参数

本文使用ISSA、SSA、GA和WOA四种算法求解该实例，并使用MATLAB 2022b进行编程求解。实验参数设定：种群大小为50，最大迭代次数为100，麻雀种群的发现者比例为0.3，预警者比例为0.1，警戒阈值为0.7，GA的突变率为0.05，精英个体数为10，WOA的参数配置参考了文献[7]。实验进行了10次运算，选取总成本最小并且客户满意度最高的路径作为最优路径。

3.2 实验结果分析

基于上述信息，本次实验分别使用ISSA、SSA、GA、WOA算法求解同时取送货车辆路径规划问题。首先将配送中心与客户的地址坐标、需求量、客户时间窗和服务时间作为算法输入，然后将前文构建的总成本和客户满意度函数作为算法的适应度函数。同时，使用MATLAB进行编程计算，并对运行结果进行分析和比较。图2和图3展示了四种算法迭代优化收敛图和车辆最优行驶路径图，优化结果对比见表4。

图2 各算法迭代曲线图

图3 四种算法的最优路径规划图

表4 ISSA、SSA、GA 和WOA 算法的路径优化结果对比

由图2可知，ISSA算法的收敛曲线斜率最高，展现出优越的最优解逼近能力和多次跳出局部最优的特点。这主要得益于算法使用混沌映射和反向学习策略来获取初始种群分布，以降低优化过程的随机性，从而在早期获取良好的初始位置优势。ISSA算法在计算开始阶段生成的初始解可能性能较差，但随着迭代的进行，解会逐渐向最优解靠拢，并在第80代时产生最优解。ISSA算法在SSA算法的基础上，结合了立方混沌映射、精英反向学习策略和正余弦优化算法的优点，显示出更强的全局搜索能力和寻优能力。在解决复杂的同时取送货车辆路径问题时，ISSA算法相较于SSA、GA和WOA算法，展现出更佳的效果和实用性。

图3展示了ISSA、SSA、GA和WOA四种算法的配送路线图，从图中可以观察到，每条配送路径上的客户点分布呈现出相对分散的状态。ISSA算法的最优配送方案只需要3辆车，而其他三种算法的最优配送方案则需要4辆车。

由表4可知，采用ISSA算法进行配送所需的总成本最低，费用为11 038.101 3元，同时客户满意度最高，达到0.977 5，显著优于SSA、GA和WOA算法。这验证了本文针对标准麻雀优化算法所提出的改进策略是有效的。通过对时间窗和服务质量进行控制，不仅提高了客户满意度，也有助于企业维护客户关系，从而促进企业更好地发展。这也证实了本文提出的基于ISSA算法的同时取送货配送路径规划方法具有有效性和优势。

4 结 语

本文构建了带有软时间窗的同时取送货车辆路径规划问题模型，其优化目标为最小化总成本和最大化客户满意度。为提高算法效果，研究将立方混沌映射、精英反向学习策略和正余弦优化算法融入麻雀搜索算法中。针对M物流公司33个揽投点的实际需求，本文使用ISSA算法解决了问题。通过与SSA、GA和WOA等其他算法的比较发现，ISSA算法在配送总成本和客户满意度方面均优于其他三种算法，证实了ISSA算法解决同时取送货车辆路径规划问题的有效性和优势。本文预设所有的配送均能一次完成，然而在现实中，配送不成功也可能对总体成本产生影响，因此，未来的研究可以进一步探讨配送的失败率对整体配送成本的影响。