基于GWO−NSGA−Ⅱ混合算法的露天矿低碳运输调度

文家燕， 闻海潮， 程洋， 罗绍猛， 何伟朝

（1. 广西科技大学 自动化学院，广西 柳州 545616；2. 柳州铁道职业技术学院 通信信号学院，广西 柳州 545616；3. 广西柳工机械股份有限公司，广西 柳州 545007）

0 引言

随着“双碳”政策的逐步实施，低碳化将成为露天矿开采的重要方向[1]。运输是露天矿开采重要环节之一，运输成本占矿石成本的30%～40%[2]。矿用自卸燃油卡车是我国露天矿主要运输工具，其运输途中碳排放量大、效率低，极大地增加了运输成本。与传统的燃油卡车相比，纯电动卡车可有效降低碳排放量及运输成本，但受充电限制及卡车运输排队影响，露天矿纯电动卡车运输调度仍需深入研究。

露天矿低碳运输调度问题可视为一个多目标函数最值优化问题。近年来，在自然界生物启发下，许多学者采用智能群搜索算法来解决露天矿卡车运输调度问题。苏楷等[3]以运输成本最小为目标函数，构建了露天矿运输调度数学模型，并利用自适应果蝇优化算法进行求解，有效降低了运输成本。程平等[4]采用非支配邻域免疫算法求解露天矿新能源卡车多目标优化调度模型，有效降低了电能消耗所引起的碳排放成本。此外，在求解露天矿卡车运输调度优化模型方面，还有粒子群算法[5]、模拟退火算法[6]、差分进化算法[7]、遗传算法[8]、蚁群算法[9]等。上述算法在一定程度上解决了露天矿运输调度问题，但存在全局寻优能力较差、待调节参数较多等问题。

非支配排序遗传算法（Non-dominated Sorting Genetic Algorithm−Ⅱ，NSGA−Ⅱ）[10]可有效解决多目标优化问题，且全局寻优能力较强。灰狼优化（Gray Wolf Optimization，GWO）算法[11]具有收敛性强、参数少、较易编程实现、局部搜索能力强等特点[12-13]。这2 种算法被应用于求解矿山卡车调度[14]、流水线车间调度[15]、函数优化[16-18]、车辆路径优化[19]和多输入多输出系统调度优化[20]等问题。但NSGA−II在求解有约束多目标问题时中后期容易收敛缓慢，GWO 算法种群的多样性在迭代进化过程中逐步降低，易陷入局部最优。因此，本文以纯电动卡车为研究对象，建立了运输成本最小、总排队时间最短和矿石品位偏差最小的多目标露天矿低碳运输调度优化模型；在NSGA−II 中后期引入GWO 算法来改善其收敛缓慢的问题，提出了一种GWO−NSGA−Ⅱ混合算法，并将其用于求解露天矿低碳运输调度优化模型。

1 露天矿低碳运输调度优化模型

1.1 目标函数

露天矿卡车调度是复杂的综合系统工程，在实际开采过程中往往是多个采矿场和破碎场间的协同作业。采矿场与破碎场之间的距离不同，则卡车运输作业时间不同，产生的碳排放和运输费用也不同。露天矿卡车作业调度涉及的优化目标包括运输时间最短、距离最短、设备利用率最高、运输成本最小等。为更好地反映实际状况，本文采用多目标优化卡车调度，以实际生产中企业重点关注的运输成本、总排队时间、矿石品位偏差为目标，构建露天矿低碳运输调度优化模型。

某露天矿实际开采过程中，有n个 采矿场Ai(i=1,2,···,n)、m个 破碎场 Bj(j=1,2,···,m)和k辆纯电动卡车，纯电动卡车在采矿场与破碎场之间往返作业，采矿场 Ai到 破碎场 Bj的距离为Di j。模型的各个优化目标用函数表示，纯电动卡车调度参数统称为S，构建的露天矿低碳运输调度优化模型的目标函数为

式中：F1(S)为 运输成本；F2(S)为 总排队时间；F3(S)为矿石品位偏差。

纯电动卡车所需的电能来自火力发电，因此在模型构建中增加了来自电能产生的碳排放成本，以更全面地考虑运输成本。碳排放成本以行驶距离作为指标进行计算。根据碳排放计算理论，卡车的碳排放成本为[21]

式中： η为单位电量火力发电占比；Cr1为 第r(r=1,2,···,k)辆 卡车单位碳排放的环境成本； λ为电能产生的碳排放系数；Xrij,Yr ji分别为第r辆卡车满载和空载次数； ρ1,ρ2分别为卡车重载和空载时的单位里程电能消耗量。

为了降低车辆碳排放的同时使企业收益最大，设运输成本最小为目标，综合考虑重载、空载成本，碳排放成本及人工成本，与燃油卡车相比，纯电动卡车后期保养费用低，不纳入成本计算。卡车运输成本为

式中：Cr2，Cr3分别为第r辆卡车作业时每度电的单位成本和人工费用；Tr为1 个班次内第r辆卡车运行时间。

实际工况中希望开采任务工期短，因此将时间成本作为单独目标进行优化可以有效避免不合理调度导致的卡车排队时间较长问题。总排队时间包含生产过程中的卡车充电时间、运行时间及维修等待时间，则有

式中：Tlimit为1 个班次时间，设定为8 h；T1rij为第r辆卡车满载运输时间；T0rij为第r辆卡车空载运输时间；Trrepair为第r辆卡车维修保养时间；Trvcharge为第r辆卡车在第v（v=1,2,···,z，z为充电桩数量）台充电桩充电时间。

矿石品位偏差为

式中：Wi为 第i个 采矿场的开采量；Wφ为目标品位矿石总量；Lr为第r辆卡车容量。

1.2 约束条件

卡车装载量应不小于破碎场的计划产量：

式中pj为第j个破碎场的计划产量。

卡车装载量应不大于破碎场的破碎量：

式中qj为 第j个破碎场的破碎量。

卡车装载量应不大于采矿场的开采量：

1 个班次内采矿场装车数量应小于采矿场最大装车数量：

式中bi为1 个班次内采矿场最大装车数量。

破碎场矿石品位误差应小于品位允许误差：

式中： φi为第i个 采矿场的矿石品位； φmin为最低矿石品位； ∆φ为品位允许误差。

1 个充电桩1 次只能给1 辆纯电动卡车充电，不能多个充电桩同时给1 辆卡车充电：

式中urv为 第r辆卡车在第v台充电桩上的状态，urv=1时 表示充电，urv=0时表示不充电。

卡车充电量应不大于充电站提供的最大电量：

式中：Emin为 卡车作业的最低电量；Emax为充电站提供的最大电量。

2 GWO−NSGA−Ⅱ混合算法

2.1 GWO 算法

GWO 算法是模拟自然界灰狼种群狩猎机制的群智能搜索算法。灰狼种群内社会阶层等级严格分明，自顶向下分为 α，β，δ，ω 4 个阶层。4 个阶层的灰狼猎食分工不同： α层为灰狼领导层，负责狼群所有事务； β层为灰狼管理层，负责辅佐 α层头狼领导和狩猎事务； δ层为灰狼普通层，负责执行 α,β层灰狼发出的狩猎指令； ω层为灰狼底层，听从 α，β，δ层灰狼的指令，朝狩猎最优方向移动。GWO 算法基本思想：首先，灰狼种群在追捕猎物过程中，根据猎物的味道等信息，头狼及管理层灰狼逐步确定猎物的方向，带领普通层及底层的灰狼接近猎物并建立狩猎包围圈；然后，底层灰狼根据 α，β，δ层灰狼的领导逐渐缩小包围圈；最后，狼群在头狼和管理层灰狼的组织下对猎物发动攻击，直至捕获到猎物为止。GWO 算法求解问题的步骤如下：

Step1：初始化算法参数（收敛因子、方位向量及参数向量），产生若干个体，设置最大迭代次数。

Step2：计算每个个体的适应度函数值。

Step3：比较个体的适应度函数值和方位向量的适应度函数值，确定当前最优搜索单元、次优搜索单元和第3 优搜索单元。

Step4：计算收敛因子、方位向量及参数向量的适应度函数值，更新当前最优搜索单元、次优搜索单元和第3 优搜索单元空间坐标。

Step5：计算最优搜索单元、次优搜索单元和第3 优搜索单元空间坐标的平均值，得到更新后当前每个个体位置。

Step6：若达到最大迭代次数，输出最优个体的适应度函数值，否则转到Step2。

2.2 NSGA−Ⅱ

NSGA−Ⅱ是一种带精英保留策略的多目标优化遗传算法，其核心为非支配排序、拥挤度距离计算和拥挤度比较算子。

NSGA−Ⅱ求解问题的一般步骤：首先初始化种群，判断是否生成第1 代子种群，未生成则采用非支配排序后通过选择、交叉、变异操作生成第1 代子种群；其次引入精英保留策略，合并父代与子代生成新种群，扩大下一代个体的筛选范围以增加种群解的多样性；然后对新的种群进行非支配排序，同时对非支配层中的个体遍历并进行拥挤度距离计算，根据非支配关系及个体的拥挤度选取合适的个体组成新的父代种群；最后通过选择、交叉、变异产生新的子代种群，并计算适应度函数值，直至满足结束条件，输出Pareto 最优解集。

2.3 混合算法

GWO 算法具备很强的搜索能力，但由于自身收敛性强，在多目标优化过程中会有很多Pareto 解丢失。NSGA−Ⅱ在运行后期容易陷入收敛缓慢，但NSGA−Ⅱ的精英保留策略和快速非支配排序具有多样性保持策略，能很好地解决GWO 算法后期Pareto 解丢失的问题。因此将2 种算法进行混合，通过GWO−NSGA−Ⅱ混合算法实现全局搜索和局部搜索的有效结合。GWO−NSGA−Ⅱ混合算法流程如图1所示。

图1 GWO−NSGA−Ⅱ混合算法流程Fig. 1 GWO−NSGA−Ⅱ hybrid algorithm flow

GWO−NSGA−Ⅱ混合算法实现步骤如下。

Step1：初始化种群，随机产生若干个个体，形成初始种群。

Step2：非支配排序后，通过NSGA−Ⅱ的选择、交叉、变异操作，基于GWO 算法的领导者围捕策略更新生成第1 代子代种群作为候选解集。

Step3：混合父代和子代种群，经染色体重组后判断是否生成新的父代种群，若是则执行Step5，否则执行Step4。

Step4：对混合的种群执行快速非支配排序和拥挤度距离计算，并根据设定值筛选合适的个体生成新父代种群。

Step5：计算当前种群中个体的适应度函数值，再次进行非支配排序和拥挤度距离计算。通过计算个体的非支配解和支配解数量，比较种群中所有个体，经过多次迭代后得到非劣解分层，并对不同的Pareto 前沿解集中任意个体的拥挤度距离进行计算，获得NSGA−Ⅱ的适应度函数值。然后使用GWO 算法的狩猎和攻击操作进行优化，基于 α,β,δ层灰狼的适应度函数值更新狼群方位，完成狩猎操作，通过收敛因子逐渐递减完成攻击操作，最终获得Pareto 前沿优化解。

Step6：判断当前迭代次数G是否小于最大迭代次数，若是则执行G=G+1并返回Step3，否则在所有Pareto 前沿解中筛选并输出最优解。

3 实验分析

3.1 GWO−NSGA−Ⅱ混合算法收敛性与稳定性分析

为了评估GWO−NSGA−Ⅱ混合算法收敛性与稳定性，在目标优化标准测试函数（ZDT1—ZDT4，ZDT6）上对GWO−NSGA−Ⅱ与实数编码NSGA−Ⅱ进行测试比较。测试函数具体公式见文献[22]。

测试参数设置参照文献[23]：测试函数种群规模大小均为300，最大迭代次数为200，Pareto 前沿解集大小为500。

收敛性指标为

式中：y为求出的Pareto 前沿解；P为求出的Pareto 前沿 解 集；x为 真 实 的Pareto 前 沿 解；P∗为 真 实 的Pareto 前沿解集；Ds(x,y)为求出的Pareto 前沿解与真实的Pareto 前沿解的欧氏距离。

稳定性指标为

式中：df为极端解集中边界解的欧氏距离；dl为非支配解集中边界解的欧氏距离；dε为最佳非支配解集中第ε（ ε =0，1，… ，N，N为最佳非支配解集中连续解的数量）个与第 ε +1个连续解间的欧氏距离；为dε的平均值。

为保证性能指标的稳定性，对每个标准测试函数连续运行30 次，并对性能指标求取平均值，测试结果见表1。可看出GWO−NSGA−Ⅱ在保证收敛性指标 γ稳定的情况下，稳定性指标 ∆有所提升，最高提升了26.03%。

表1 不同算法的标准测试函数测试结果对比Table 1 Comparison of standard test function test results of different algorithms

GWO−NSGA−Ⅱ混合算法对标准测试函数的测试 结 果 如 图2 所 示（f1(x),f2(x)为ZDT1—ZDT4 和ZDT6 的 目 标 函 数）。可 看 出GWO−NSGA−Ⅱ的Pareto 优化解分布均匀，可得到良好的分布前沿，说明该算法对于求解多目标有约束问题是有效的。

图2 GWO−NSGA−Ⅱ混合算法对标准测试函数的测试结果Fig. 2 Test results of GWO-NSGA-Ⅱ hybrid algorithm on standard test functions

3.2 露天矿运输调度实例分析

为验证GWO−NSGA−Ⅱ混合算法在实际场景中应用的有效性，以某露天矿某天的矿用纯电动卡车实际运输调度数据为例，将混合算法应用于求解露天矿低碳运输调度优化模型，并与NSGA−Ⅱ，GWO算法进行对比分析。

该露天矿有4 个破碎场，8 个采矿场，装载和卸载时间分别为4，2 min，采矿场至破碎场的距离见表2。根据露天矿的实际布置情况，充电站在距离破碎场约200 m 处，且每个充电站有4 台充电桩。该露天矿要求1 个班次（12 h）内破碎场的运输量为8 000 t。卡车的维护保养成本为1 元/km。卡车重载行驶和空载行驶的平均速度分别为20，35 km/h。

表2 采矿场至破碎场距离Table 2 Distance between mining site and crushing site

GWO−NSGA−Ⅱ 参数设置：搜索空间维度为20，初始种群大小为100，进化迭代次数为600，最大精英迭代次数为200，交叉概率和变异概率分别为0.1，0.5。GWO 算法参数设置参照文献[11]，NSGA−Ⅱ参数设置参照文献[14]。为降低算法在时间上的复杂度，本文将目标函数作为适应度函数，并使用Matlab 2019b 对露天矿低碳运输调度问题进行仿真求解，进化曲线如图3 所示。

从图3 可看出，与NSGA−Ⅱ和GWO 算法相比，GWO−NSGA−Ⅱ的寻优速度分别提高了48.7%和27.1%，寻优精度分别提高了17.1%和9.3%。GWO−NSGA−Ⅱ的进化曲线在100 次迭代之前变化迅速，在100 次迭代之后趋于平稳。这是由于GWO−NSGA−Ⅱ在初期继承了NSGA−Ⅱ较强的计算能力和全局搜索能力，使得种群快速收敛到全局最优附近；在中后期，GWO 算法的加入让种群能够快速集中到最优种群的周围，且减少Pareto 前沿解的丢失，降低了NSGA−Ⅱ中后期陷入收敛缓慢的概率，从而均衡了全局最优与局部最优。

图3 不同算法的进化曲线Fig. 3 Evolution curves of different algorithms

在实际运输调度中1 个班次需要40 辆纯电动卡车，根据式（2）、式（3），结合该露天矿具体参数可知，1 个班次作业调度实际运输距离为411.9 km，用电费用为889.704 元，碳排放费用为288.33 元，运输费用为1 178.034 元。分别基于NSGA−Ⅱ，GWO，GWO−NSGA−Ⅱ求解的露天矿低碳运输调度的用电费用、碳排放费用和运输费用（不含司机劳务费用）见表3。

表3 不同算法下露天矿低碳运输调度结果对比Table 3 Comparison of low-carbon transportation scheduling results in open-pit mine under different algorithms

从表3 可看出，与实际运输数据相比，在同一个班次内采用混合GWO−NSGA−Ⅱ混合算法求解，运输距离减少了97.086 km，纯电动卡车数量减少了10 辆，用电费用节省了209.706 元，碳排放费用节省了67.961 元，运输费用节省了277.665 元；而采用NSGA−Ⅱ和GWO 算法求解的运输费用仅分别节省了92.296 元和184.983 元。

为对比燃油卡车与纯电动卡车在GWO−NSGA−Ⅱ混合算法下的运输成本及碳排放量，以某公司同一型号不同版本的卡车作为研究对象进行实验。电动卡车型号为DW90A−EV，燃油卡车型号为DW90A，额定载质量均为58 t，在1 个班次运输距离和使用车辆数相同。在考虑发电厂电能产生的碳排放成本的条件下，燃油卡车与电动卡车用电费用、碳排放量和运输费用对比见表4。可看出采用GWO−NSGA−Ⅱ混合算法优化露天矿纯电动卡车运输调度，极大减少了碳排放量和运输费用。

表4 不同类型卡车露天矿运输调度结果对比Table 4 Comparison of transportation scheduling results in open-pit mine under different types of truck

4 结论

1） 考虑碳排放费用、维修费用及卡车保养费用，构建了以运输成本、总排队时间、矿石品位偏差为优化目标的露天矿低碳运输调度优化模型。

2） 针对NSGA−Ⅱ后期陷入收敛速度缓慢的缺点，在NSGA−Ⅱ搜索过程中融入GWO 算法，提出了GWO−NSGA−Ⅱ混合算法。该算法不仅能对解空间进行全面搜索，均衡全局寻优能力和局部寻优能力，而且收敛性及稳定性也显著提升。

3） 将GWO−NSGA−Ⅱ混合算法应用于求解实际露天矿运输调度优化模型，与NSGA−Ⅱ，GWO 算法相比，不仅提高了算法的收敛精度和速度，而且减少了卡车使用数量、运输距离和运输费用。与燃油卡车相比，纯电动卡车极大地降低了运输费用和碳排放量。