基于改进鲸鱼算法的黔北地区农产品配送问题研究

史文涛 周林荣

(遵义师范学院管理学院 贵州 遵义 563006)

0 引 言

作为全国脱贫攻坚的主战场，贵州省扶贫工作一定程度决定着全面建成小康社会的进展和成效[1]。近年来，贵州省狠抓电子商务迅速发展的机遇，结合自身生态环境和农业生产优势，探索实施了“电子商务+农产品”的扶贫模式，取得了良好成效。特别是黔北地区，农产品种类多、产量大，每年都有大批农产品销往全国，有效促进了群众增收。但随着农产品规模的持续增加，物流运输规模也飞速增长，企业物流费用大幅提升，严重影响了企业核心竞争力。

由实践可知，科学的配送方案有助于降低企业配送成本[2]。因此，学者们对物流配送问题进行了深入研究，提出了大量优化算法。文献[3-4]分别设计了求解带时间窗物流配送问题的遗传算法(GA)和粒子群算法(PSO)。结果表明，经过GA和PSO优化的配送方案，产生的运输成本更低。文献[5]提出了求解带能力约束物流配送问题的禁忌搜索算法，同样取得了较好效果。虽然现有智能算法能够对物流配送问题进行求解，但如何进一步提高算法性能、更大程度降低企业配送成本仍然是学者们关注的重要方向。

鲸鱼算法(WOA)是Mirjalili等模拟鲸鱼捕食机制于2016年提出的一种新型群体启发式智能算法，具有参数较少、原理简单等优点[6]，广泛应用于图形优化、连续函数求解、参数训练等领域。文献[7-8]通过WOA对预测网络参数进行了有效训练，文献[9]则根据多阈值图像分割的特点提出了一种改进WOA，但WOA同样存在容易早熟、稳定性不强等缺点，严重影响了问题求解的质量。

基于上述分析，本文主要对求解黔北地区农产品配送问题的改进WOA(IWOA)进行了研究。首先，对WOA编码和解码方式进行改进，并通过混沌方式生成初始种群。然后，分别引入反向学习、信息反馈和自适应权重等机制，进而提出IWOA。最后，采用黔北地区配送实例和国际标准算例进行仿真测试。实验结果表明，IWOA综合求解性能较好，有助于降低企业配送成本。

1 配送成本模型

1.1 问题描述

黔北地区农产品配送问题可以描述为[10]：某个位于黔北地区的配送中心需要对客户群体进行农产品配送，客户位置和需求量已知，要求在满足以下4个条件的前提下科学规划配送方案，使整体配送成本最小：(1)所有客户需求均被满足，且一个客户且只有一辆车进行服务；(2)配送车辆不能超载，且必须在客户规定时间进行配送，早于或者晚于客户规定时间均会产生惩罚成本；(3)配送车辆配送时按照相同速度匀速行驶；(4)配送中心拥有足够的同类型车辆。

1.2 成本分析

根据企业配送实际可知，农产品配送成本主要包括车辆运输成本、农产品货损成本和时间惩罚成本。

(1)车辆运输成本。车辆运输成本指运营成本和行驶成本，计算方式为：

(1)

(2)农产品货损成本。实际上，农产品容易受温度、时间的影响产生腐烂，进而产生货损成本。但由于生鲜农产品通常采用冷藏车进行配送，故可以忽略温度变化的因素，将货损成本表示为：

(2)

(3)时间惩罚成本。时间窗包括硬时间窗和软时间窗，前者不允许车辆在规定时间范围外配送，后者则允许车辆在规定时间范围外配送，但需要支付一定惩罚成本，且距离规定时间越久惩罚成本越高。根据企业实际情况，配送要求多为软时间窗，惩罚成本函数如下：

(3)

图1 时间窗惩罚成本示意图

1.3 模型构建

(4)

约束条件为：

(5)

(6)

(7)

(8)

(9)

(10)

式(5)表示车辆达到客户j的时间，设t0=0；式(6)和式(7)表示车辆从配送中心出发，配送完成后又返回配送中心；式(8)和式(9)表示每个客户且只有一辆车配送；式(10)表示配送车辆不能超载。

2 鲸鱼优化算法

2.1 包围猎物

WOA中，设定最优解为目标猎物，其他鲸鱼个体均通过目标猎物进行自我更新，对应公式为[6]：

D=|CX*(t)-X(t)|

(11)

X(t+1)=X*(t)-A·D

(12)

式中：D表示鲸鱼与猎物相隔距离；t表示当前迭代次数；X*(t)表示目标猎物位置；X(t)表示鲸鱼个体当前位置；A、C为系数向量。

A=2αr1-α

(13)

C=2r2

(14)

(15)

式中：r1和r2表示[0,1]之间的随机数；α表示收敛因子；T表示最大迭代次数。

2.2 气泡攻击

捕食时，鲸鱼会发出气泡包围猎物，并同步朝着猎物移动[9]。该过程主要包括收缩包围和螺旋更新2个机制，收缩包围如2.1节所述，螺旋更新鲸鱼个体位置的方法如下：

X(t+1)=Deblcos(2πl)+X*(t)

(16)

式中：b表示常数；l表示[-1,1]之间的随机数。

2.3 寻找猎物

经过包围和气泡攻击后，鲸鱼个体便可以对包围圈范围内的猎物进行搜索，公式为：

D=|CXrand(t)-X(t)|

(17)

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

(18)

式中：Xrand(t)表示随机选取的鲸鱼个体。当|A|≥1时，鲸鱼个体随机向远处搜索，寻找算法全局最优解；|A|<1时，鲸鱼个体向目标猎物处搜索，寻找算法局部最优解。

3 改进鲸鱼算法

3.1 编码与解码

对鲸鱼个体进行解码时，首先，比较各维向量大小，按从小到大的顺序获取各维向量在个体中的位置数值。例如，在个体[0.21,0.38,0.13,0.42,0.44,0.36]中，按照从小到大的顺序，0.36排列第3，则其位置数值为3。如图2所示，当位置数值大于客户数时，令对应数值为0，且当0相邻时，删除多余的0，即可得到配送方案。例如，上述个体[0.21,0.38,0.13,0.42,0.44,0.36]解码后为[2,0,1,0,3]，则表示该配送方案共需要3辆车，车辆1配送路径为0-2-0，车辆2配送路径为0-1-0，车辆3配送路径为0-3-0。

图2 鲸鱼个体解码示意图

3.2 混沌序列初始化

(19)

3.3 逐维小孔成像反向学习

WOA求解高维度问题时，鲸鱼个体各维度之间相互影响较大，容易导致算法陷入局部最优解。根据文献[12]可知，智能算法和反向学习有效结合，能够提高算法全局寻优能力。基于该思想，本文参考光学定律，提出一种逐维小孔成像反向学习策略，希望通过该策略降低鲸鱼个体不同维度的相互干扰，避免算法陷入局部最优解，具体原理如图3所示。

图3 逐维小孔成像示反向学习示意图

(20)

(21)

分析式(21)可知，与传统逐维反向学习策略不同，本文提出的逐维小孔成像反向学习策略通过改变接收屏和小孔屏的距离即可调整ξ取值，使得算法能够在更大范围内寻找优秀反向解，进而更大程度地提高个体质量和多样性，降低算法陷入局部最优解的可能性。当ξ=1时，可得：

(22)

即为一般反向学习策略。

在WOA的每次迭代中，都采用式(21)对最优鲸鱼个体进行位置筛选，某一维度的向量经过小孔成像反向学习后与其他维度的向量组成新个体，然后比较不同个体适应度值，进而确定最优个体。

3.4 信息反馈机制

WOA中，鲸鱼通过更新自身位置来靠近猎物，运动方式比较单一，一定程度上影响了算法收敛速度。对此，本文提出一种信息反馈机制，每次迭代中让最优和最差鲸鱼个体进行信息交流，引导距离猎物较远的个体迅速靠近猎物，进而加快算法收敛。具体公式如下：

(23)

式中:X*、X*分别表示当前种群最优和最差个体；ζ表示[0,1]之间均分分布的随机数。

3.5 非线性收敛因子和自适应权重策略

由文献[6]可知，WOA求解性能也受系数向量A的影响。分析式(13)，A的取值由收敛因子α决定，α随着算法进化逐步递减，且呈现线性趋势，这在一定程度上影响了算法求解性能。对此，本文提出一种收敛因子非线性变化策略，计算公式如下：

(24)

式中：μ表示控制常数，本文设置为2。由式(24)可知，收敛因子在保持递减趋势的情况下，在算法前期迭代中递减速率较慢，有效扩大了算法搜索空间；在算法后期迭代中递减速率较快，有助于加快算法收敛。

同时，为进一步平衡WOA全局寻优能力和局部搜索能力，本文提出一种自适应权重系数w：

(25)

用w改进鲸鱼个体更新公式：

X(t+1)=w(t)·X*(t)-A·D

(26)

X(t+1)=Deblcos(2πl)+(1-w(t))X*(t)

(27)

X(t+1)=w(t)Xrand(t)-A·D

(28)

由上述公式可知，惯性权重随着算法迭代次数增加而由大到小变化，较好地平衡算法全局和局部寻优能力。

3.6 适应度函数

为便于计算机编程计算，本文将式(10)融入到目标函数，得到算法适应度函数如下[13-15]：

(29)

3.7 算法步骤

IWOA求解农产品配送问题的步骤主要包括：

步骤1设置初始种群大小Num、最大迭代次数T等参数。

步骤4根据式(13)、式(14)和式(24)更新系数向量A，根据式(25)更新自适应权重因子w。

步骤5生成(0,1)之间的随机数rand。如果rand<0.5且|A|<1，则根据式(11)和式(26)更新鲸鱼个体；若rand<0.5且|A|≥1，则根据式(17)和式(28)更新鲸鱼个体；若rand≥0.5，则根据式(27)更新鲸鱼个体。

步骤6根据式(29)计算鲸鱼个体适应度值，选出当代种群最优个体X*和最差个体X*。

步骤8根据式(23)更新种群最差个体X*。

步骤9判断算法是否达到最大迭代次数。达到，则输出最优个体X*，即为最优调度方案；反之，则返回步骤4。

具体流程如图4所示。

图4 IWOA求解农产品配送问题示意图

4 仿真实验

为验证IWOA有效性，以黔北地区生鲜农产品配送实例和国际标准算例为测试数据，在Windows 7，Intel i5-6300HQ，4 GB内存环境下，用MATLAB R2016a平台编程仿真，对比分析WOA[6]、IWOA、GA[3]和PSO[4]的求解结果。

4.1 黔北地区配送实例

表1 配送网络参数表

利用WOA、IWOA、GA和PSO求解该实例，可得到对应最好配送方案和收敛情况，如图5和图6所示。可以看出，IWOA求得配送方案需要配送车辆3辆，最好配送成本最低，为1 317.33元，在21代左右收敛；GA需要配送车辆3辆，最好配送成本次之，为1 319.45元，在40代左右收敛；PSO需要配送车辆3辆，最好配送成本较高，为1 330.23元，在35代左右收敛。WOA需要配送车辆4辆，最好配送成本最高，为1 350.39元，在30代左右收敛。由此可见，IWOA全局寻优能力和收敛速度均为最优。

(a)IWOA

图6 各算法最好配送方案收敛情况

为进一步对比验证IWOA求解性能，分别采用上述算法对该实例进行60次求解，统计相关指标如图7和图8所示。分析可知，IWOA最好、最差以及平均配送成本最小，说明IWOA算法全局寻优能力最强，且算法最为稳定；WOA最好、最差和平均配送成本最大，说明WOA全局寻优能力最差，且算法不稳定。GA和PSO对应的最好、最差和平均配送成本处于IWOA和WOA之间，说明两个算法的全局寻优能力和稳定性居中，且GA优于PSO。同时，IWOA平均运行时间最短为7.2 s，WOA(8.2 s)和PSO(8.9 s)次之，GA最长为12.3 s，说明IWOA、WOA、PSO和GA收敛速度依次变慢。

图7 最好、最差配送成本对比示意图

图8 平均配送成本和运行时间对比示意图

4.2 国际标准算例

为验证IWOA求解大规模网络的性能，以C101、C201、R101、R201、RC108和RC208等6个客户规模为100的国际标准算例为测试集，分别采用上述算法进行60次仿真实验，统计算例已知最优解BK、求得最好解BC、平均解AC和平均运行时间AT如表2所示。

表2 国际标准算例仿真结果对比表

由表2可知，IWOA能够求得C101和C201算例的已知最优解，且对于R101、R201、RC108和RC208算例，IWOA求得最好解明显优于WOA、GA和PSO，说明IWOA全局寻优能力最强，求得各算例最好配送方案分别如图9、图10和表3所示。同时，IWOA求得各算例平均值和平均运行时间都优于其他算法，说明IWOA稳定性和收敛速度也是最优。这主要得益于混沌序列初始化增加初始鲸鱼种群多样性，逐维小孔成像反向学习降低最优鲸鱼个体不同维度的相互干扰，非线性收敛因子和自适应权重较好地平衡算法全局和局部寻优能力，进而提高算法综合求解性能。

图9 C101算例最好配送方案示意图

图10 C201算例最好配送方案示意图

表3 国际标准算例最好配送方案表

综上分析，IWOA求解性能明显优于WOA、GA和PSO，能够很好地适用于大规模农产品配送问题的求解。

5 结 语

本文主要对黔北地区农产品配送问题的求解算法进行研究。针对WOA容易早熟、收敛较慢等缺点，首先改进鲸鱼个体编码和解码方式，然后利用混沌方式生成初始种群，并引入反向学习、信息反馈和自适应权重等机制，提出IWOA。对黔北地区农产品配送实例和国际标准算例的仿真实验表明，与WOA、GA和PSO相比，IWOA能够更好地规划配送方案，有效降低企业配送成本。