混合变异自适应樽海鞘算法的甩挂运输多目标调度优化

摘  要： 建立一种考虑时间窗的甩挂运输多目标调度模型，提出一种改进樽海鞘算法的求解策略。通过引入混合变异算子，改进樽海鞘算法领导者位置易陷入局部最优的问题，增加种群多样性；通过引入动态惯性权重策略，使追随者在迭代后期减小搜索步长，提高算法收敛精度。实验结果表明，该改进的樽海鞘算法具有较高的全局搜索能力，能有效得出甩挂运输多目标问题最优解，相关研究结论能够为大型企业运输提供决策支持。

关键词： 樽海鞘算法； 甩挂运输； 混合变异策略； 动态惯性权重优化算法

中图分类号：TP18          文献标识码：A     文章编号：1006-8228（2023）04-53-05

Abstract： A multi-objective scheduling model of the tractor and semi-trailer transportation considering the time window is established， and a solution strategy of the improved salp swarm algorithm is proposed. By introducing a hybrid mutation operator， the problem that the leader position of the algorithm is easy to fall into local optimum is improved， and the population diversity is increased. By introducing the dynamic inertia weight strategy， the search step size of the followers is reduced in the late iteration， and the convergence accuracy of the algorithm is improved. The experimental results show that the improved salp swarm algorithm has the high global search ability， and can effectively obtain the optimal solution of tractor and semi-trailer transportation multi-objective problem. The relevant research conclusions can provide decision-making support for large-scale enterprise transportation.

Key words： salp swarm algorithm; tractor and semi-trailer transportation; hybrid mutation strategy; dynamic inertia weight optimization algorithm

0 引言

甩掛运输是指牵引车将集装箱甩在指定的地点后，执行其他运输任务的物流模式。其优点是可以实现运输和装卸同时进行，相对于传统运输模式，甩挂运输能较好地解决一些企业车辆等待装卸时间长、车辆利用率低、在途车辆多、环境破坏严重等问题。

目前国内外研究的甩挂运输问题主要基于五类单一经典模型，使用挂车数量最少，运输成本最少，二氧化碳排放量最少，客户满意度较高，交通拥堵情况少。杨珍花等[1]构建混合整数规划模型，设计多阶段动态优化算法求解甩挂运输成本最小问题。成耀荣等[2]以吨公里 CO2排放量为目标函数，构建了考虑碳排放的大型制造企业内牵引车优化调度模型。Zhang R等[3]提出多挂车模型，提出了一种回溯自适应阈值接受算法来解决该问题。目前有关文献中很少有研究多目标的甩挂运输调度优化模型，而实际中，能源消耗、运输成本、客户满意度等因素之间相互影响，需考虑综合因素的共同影响。本文在已有研究的基础上，综合环境和经济效益因素，在考虑时间窗的情况下，以碳排放量最少和运输成本最少为双重目标，构建考虑碳排放与运输成本的甩挂运输带时间窗的车辆调度问题模型，寻找最优配送路径，从而降低能耗，实现企业经济效益。

针对该问题，提出一种混合变异的自适应樽海鞘算法的甩挂运输调度策略。樽海鞘算法有过早收敛、容易陷入局部最优等缺点。国内外众多学者对樽海鞘算法进行改进，如Wang等[4]提出一种基于单纯形法的随机变异改进樽海鞘算法，提高算法局部搜索能力。Sayed等[5]提出混沌樽海鞘算法，采用十种不同的混沌方案，提高结果精度和收敛速度。这些改进策略在不同程度上提升了樽海鞘算法的寻优能力，但该算法的性能仍有较大的提升空间。本文提出一种引入混合变异算子与动态惯性权重的策略来改进樽海鞘算法，最后将改进樽海鞘算法求解甩挂运输多目标模型。

1 多目标甩挂运输调度模型

在满足时间窗等约束条件下，牵引车需将重挂车从装货节点拖带到卸货点，使得完成运输任务的总成本与碳排放最小。为了便于描述，本文做出以下合理假设：

一辆牵引车只拖带一辆挂车。牵引车和挂车的甩挂操作只能在装卸货点完成。牵引车最初停放在中心节点，完成任务后返回中心节点。每一个运输任务都可用一辆挂车完成装货任务。

本文用有向图V网络来定义甩挂的运输网络。N表示所有的运输节点合集，E表示第i个节点到第j个节点之间运输路径的集合。K为牵引车集合，M为任务集合，Oi为任务i的起点，Di为任务i的终点，[ωpq]为车辆行驶耗费的可变成本。[α]为燃油二氧化碳排放系数，Qr是任务顺序为r的运输量，dij是第i个节点到第j个节点之间的距离，c是每公里燃油消耗量。决策变量定义如下：

[ykij=1，牵引车连续执行任务i和任务j0，其他]

[xki=1，牵引车执行任务i0，其他]

考虑运输成本和碳排放的多目标函数与考虑时间窗的约束条件的具体模型如下：

⑴ 目标函数

⑵ 约束函数

时间窗约束⑶⑷表示牵引车到达节点的时间不能早于该节点的最早到达时间，不能晚于该节点最迟到达时间。约束⑸一辆牵引车只能访问一次运输任务。

2 改进的樽海鞘算法

2.1 基本樽海鞘算法

樽海鞘有一种称为樽海鞘链的群体行为，这种行为可以帮助他们快速地寻觅食物[6]。S.Mirjalili等[6]以数学模型模拟了樽海鞘链，并应用于求解优化问题。

樽海鞘链分为两组，第一组是领导者，第二组是追随者，链的前面的鞘被称为领导者，后面的鞘被称为追随者[6]。在优化问题中，樽海鞘可以看作是候选解，海洋可以看作是搜索空间，食物的浓度可以看作最优目标函数，排在第一位置的个体可看作全局最优解。领导者和追随者位置更新公式如下：

[x1j]是第一个领导者鞘的第j维位置，[Fj]是第j维的食物源，第j维搜索的上边界和下边界分别是[ubj]和[lbj]，[c2]和[c3]是在0到1之间取的随机数以保持搜索空间。[c1]是重要的参数，用来平衡开发和勘探能力。公式如下：

t和tmax是当前迭代次数和最大迭代次数。领导者位置更新完成后，更新追随者位置。公式如下：

2.2 樽海鞘算法的改进策略

在标准樽海鞘算法中，算法在迭代过程中，会随着迭代次数的增加，链中领导者位置的多样性降低，从而使其陷入局部最优。高斯变异、柯西变异、莱维变异已被证实可以增强元启发式算法的全局搜索能力。因此，提出一种混合高斯变异、柯西变异、莱维变异算子策略，在每次迭代开始时，对樽海鞘领导者的位置进行混合变异，集成三种变异算子的优势，使各变异算子以各自不同的概率作用于种群中的不同个体[7]。

混合变异的思想如下：算法初始时，高斯变异、柯西变异、莱维变异三种算子的选择概率设置为0.3，0.3，0.4。因为莱维变异比高斯变异和柯西变异有更大的灵活性，所以初始设置的选择概率较大。当变异发生后，比较适应度函数值，如果当前适应度函数值优于变异前的适应度函数值，该个体所使用的变异算子的概率就要相应地增加[7]。每一次迭代都需要根据动态计算得到的变异算子的概率来确定将要使用的变异算子类型。

引入高斯变异机制的领导者位置更新公式：

其中，[gaussion0，1]为标准高斯分布。

引入柯西变异机制的领导者位置更新公式：

引入莱维变异机制的领导者位置更新公式：

在追随者位置更新公式中引入动态惯性权重[8]，随迭代次数自适应递减的惯性权重表示了樽海鞘追随者受全局最优解影响程度的变化。在迭代前期，追随者受全局最优解影响较大，有较大的全局搜索步长，能够更快地找到全局最优区域，而在迭代后期，大部分樽海鞘已达到最优值，追随者受全局最优解影响较小，追随者可以在最优解附近深度探索，提高了算法的收敛精度。追随者自适应惯性权重更新公式如下：

[ω]是自适应惯性权重，[ωmax]和[ωmin]分别是惯性权重的最大值和最小值界限，[α]是15到30之间的随机数。

具体的改进樽海鞘算法的寻优流程如下：

步骤1 初始化设置，包括种群规模，最大迭代次数，外部档案大小，维度，上下边界值；

步骤2 计算樽海鞘个体的适应度值，根据适应度值确定非支配解；

步骤3 根据非支配解确定外部档案，如果外部档案已满，根据拥挤度计算来删除与添加非支配解；

步骤4 从外部档案中选择食物源；

步骤5 更新种群个体位置，按一定的概率选择一种变异策略领导者更新公式进行混合策略变异操作；

步骤6 如果变异后的适应度函数值更优，则增加该个体所使用的相应变异算子的概率，否则，减少该个体所使用的相应变异算子的概率；

步骤7 计算追随者的惯性权重值，并更新带有自适应惯性权重值的追随者位置；

步骤8 判断当前迭代次数是否达到当前设定的最大迭代次数，若是，则停止运行并输出最优解，此时食物源库中的个体即为所求最优解集，若否，则返回步骤2继续运行。

3 改进樽海鞘算法的收敛性与有效性分析

为验证本文提出的改进樽海鞘算法具有较强的搜索精度和优化能力。采用S.Mirjalili等的文献中的benchmark的单峰测试函数和多峰测试函数对改进算法的精度和收敛性进行验证分析。收敛曲线对比如图1所示。从基准测试函数的收敛曲线可看出，改进的樽海鞘算法收斂速度更快，有较好的寻优精度。从F2和F3函数收敛曲线可看出，原樽海鞘算法在迭代早期陷入局部最优解区域，有较低的收敛精度。

为进一步验证算法的精度性能，对每个标准测试函数运行30次，其结果表示如表1所示。平均值为精度平均值，标准差可反应算法的稳定性。对比表1中试验结果可得出，改进的KESSA算法的标准差要比SSA算法的小很多，说明改进算法有更好的稳定性，从最优值和平均值来看，改进算法的求解精度更高。由此得出，引进的混合变异自适应樽海鞘算法比原算法寻优能力更强。

4 改进樽海鞘算法在甩挂运输调度优化的应用

本文对成耀荣等[2]的甩挂运输数据进行改进并实验。以厂内棒材厂、成品库、热轧板厂、冷轧板、转炉厂等十个主要厂址为网络节点，编号为0的中心节点停放牵引车。网络的弧为运输道路。表2为网络节点坐标，表3为每日的运输量与运输时间窗数据。

合理的甩挂运输调度方案能减少吨公里二氧化碳的排放量、同时减少车辆运营成本，提高运输效率。本文提出的混合变异自适应樽海鞘算法，能有效求得最优配送路径，具有较高的收敛精度，很大程度上节省了配送成本。表4为最优的甩挂牵引车的调度方案。

5 结束语

本文考虑时间窗下的甩挂运输吨公里二氧化碳排放量和运输成本的多目标问题，建立甩挂运输车辆调度优化模型，提出一种改进的樽海鞘算法的求解策略，通过将算法种群的领导者位置进行混合变异，来提高算法全局搜索能力，增加种群多样性。在迭代后期，为避免追随者受全局影响而偏离最优解，在算法种群的追随者位置更新公式中引入动态惯性权重，从而提高算法的收敛精度。为测试算法性能，在基础数据集上验证算法的收敛性和有效性，实验结果表明，引入混合变异算子与动态惯性权重能够提高基本樽海鞘算法的求解和收敛速度。最后将改进的樽海鞘算法优化多目标甩挂运输模型，结果表明，改进的樽海鞘算法所得出的调度方案能有效降低运输成本，吨公里二氧化碳排放量，可提供给企业有效且合理的甩挂运输调度方案。

参考文献（References）：

[1] 杨珍花，王滋承，魏照坤，等.挂车装卸时间不确定的甩挂车辆动态调度优化[J].系统工程理论与实践，2021，41（5）：1081-1095

[2] 成耀荣，杨谦，郑国华.考虑碳排放的大型制造企业甩挂运输牵引车调度优化[J].吉林大学学报（工学版），2021，51（3）：893-899

[3] Zhang R， Wang D， Wang J. Multi-Trailer Drop-and-Pull Container Drayage Problem[J]. IEEE Transactions on Intelligent Transportation Systems， 2020（99）：1-13

[4] Wang D， Zhou Y， Jiang S， et al. A Simplex Method-Based Salp Swarm Algorithm for Numerical and Engineering Optimization[J]. Springer， Cham，2018

[5] Sayed G I， Khoriba G， Haggag M H. A novel chaotic salp swarm algorithm for global optimization and feature selection[J]. Applied Intelligence，2018

[6] Mirjalili S， Gandomi A H， Mirjalili S Z， et al. Salp swarm algorithm： a bio-inspired optimizer for engineering design problems[J]. Advances in Engineering Software， 2017：163-191

[7] 丁蕊.復杂高维多目标优化方法[M].北京：电子工业出版社，2020

[8] 周密，王潇棠，闫河，等.一种混沌映射动态惯性权重的樽海鞘群算法[J].小型微型计算机系统，2021：1-7

作者简介：马明明（1993-），男，河北省邢台市人，在职研究生，主要研究方向：计算机应用技术研究、物流系统优化研究。