0 引言

在露天矿生产中，运输过程会排放大量的碳，运输能耗约占露天矿总能耗的60%[1]，运输费用约占总生产费用的50%[2]。露天矿低碳运输调度优化成为促进露天矿高效生产、减少碳排放量和运输费用的关键环节。

露天矿低碳运输调度问题可看作是在满足露天矿生产的约束条件下，求解露天矿碳排费用和运输费用之和最小的多目标优化问题。近年来，许多学者采用仿生算法求解露天矿运输调度问题，如自适应果蝇优化算法(Adaptive Fruit Fly Optimization Algorithm，AFOA)[2]、基于差分的生物地理学算法[3]、粒子群算法[4]、模拟退火算法[5]、差分进化算法[6]、遗传算法(Genetic Algorithm，GA)[7]、蚁群算法[1，8]等。然而，上述算法存在全局寻优能力较差、需调节参数较多的问题。

灰狼优化(Grey Wolf Optimization，GWO)算法是一种通过模仿灰狼种群社会阶层和猎食过程而提出的仿生算法，该算法需要调节的参数较少、较易编程实现、全局寻优能力较强[9-10]，已被应用于求解流水线车间调度[11]、函数优化[12-13]、多层传感器训练[14]和电力系统优化[15]等问题。然而，随着GWO算法的迭代进化，灰狼种群的多样性逐步减少，算法陷入局部最优的概率增加，导致局部寻优能力减弱，难以均衡全局寻优能力和局部寻优能力。本文在GWO算法中引入迁移操作，并且根据不同的灰狼自适应调整其迁移概率，提出了一种改进的GWO(An Improved Grey Wolf Optimization，AGWO)算法，并将其应用于求解露天矿低碳运输调度问题。

1 露天矿低碳运输调度问题数学模型

在实际的露天矿生产过程中，多个采矿场往往同时开展采矿工作，然后将矿石分别运输至不同的破碎场进行破碎工作。各个采矿场到破碎场的运输距离不同，因此，运输过程产生的碳排费用和运输费用也会不同。露天矿低碳运输调度问题的本质是寻找碳排费用和运输费用之和的最小值。

(1) 碳排费用。卡车在第i(i=1，2，…，I，I为采矿场个数)个采矿场Mi和第j(j=1，2，…，J，J为破碎场个数)个破碎场Dj之间的运输过程中，需要从采矿场Mi满载至破碎场Dj，然后空载返回采矿场Mi。因此，碳排费用为

(1)

式中：B3为CO2的单位排放成本；γ为燃油转化为CO2的单位转化率；yij1为卡车空载时单位距离耗油量；yij2为卡车满载时单位距离耗油量；dij为采矿场Mi至破碎场Dj的距离；=1表示第k(k=1，2，…，K，K为卡车数量)辆卡车Sk从采矿场Mi至破碎场Dj，=0表示第k辆卡车Sk未从采矿场Mi至破碎场Dj。

(2) 运输费用。运输费用主要包括卡车的燃油费用和固定启用费用(即租赁费用)。卡车在采矿场Mi和破碎场Dj之间运输过程中，燃油费用为为每辆卡车的单位燃油成本)。卡车的固定启用费用与运输距离和装载量无关，卡车的固定启用费用为为每辆卡车的固定启用成本)。因此，运输费用为

(2)

露天矿低碳运输调度问题的数学模型为

(3)

式中：lk为第k辆卡车的装载量；Qi为采矿场Mi的开采量；Tj为破碎场Dj的破碎量；表示第k辆卡车Sk是否从采矿场Dj返回至破碎场Mi。

式(3)为目标函数，式(4)—式(9)为约束条件。式(4)和式(5)表示卡车装载量不应超过开采量和破碎量；式(6)表示每辆卡车最终必须返回至出发时的采矿场；式(7)表示运载卡车的数量应该在卡车总数之内；式(8)表示卡车不能从一个采矿场到另一个采矿场；式(9)表示变量约束。

2 算法原理

2.1 GWO算法

灰狼是以群居为主的食肉动物，种群内具有不同的社会阶层，从上至下依次分为α，β，δ，ω层。每个阶层的灰狼负责相应的猎食工作：α层为灰狼领导层，统管种群内各种事务；β层为灰狼管理层，辅佐α层规划猎食事务；δ层为灰狼普通层，负责遵守α，β层的指示；ω层为灰狼底层，负责听从α，β，δ层的命令[16-17]。

GWO算法的基本思想：灰狼种群在追捕猎物过程中，灰狼首先根据猎物的味道等信息逐步地接近猎物，构建包围圈；然后，其他灰狼在α，β，δ层灰狼的带领下，逐渐缩小包围圈；最后，灰狼种群有组织地对猎物发动攻击，直至捕获到猎物[18-19]。GWO算法求解问题的一般步骤：① 初始化算法参数和种群方位；② 计算适应度函数值；③ 灰狼种群进行包围操作；④ 灰狼种群进行狩猎操作；⑤ 灰狼种群进行攻击操作；⑥ 当满足终止准则，输出结果。

2.2 AGWO算法

在GWO算法中，灰狼种群根据当前最优灰狼的方位更新方位。然而，随着迭代次数的增加，大部分灰狼种群逐步聚集在当前最优灰狼附近，若当前最优灰狼的方位不是全局最优，则易陷入局部最优，无法快速寻找到全局最优。因此引入迁移操作构成AGWO算法，赋予灰狼自适应的迁移概率，由迁移操作重新生成的灰狼能更靠近全局最优，改善种群的多样性，降低陷入局部最优的概率，促使快速收敛至全局最优。AGWO算法求解问题的步骤如下。

(1) 初始化算法参数和种群方位。假定Xh=(Xh1,Xh2,…,XhL)为第h(h=1，2，…，N，N为灰狼种群大小)个灰狼的方位。初始化方位信息时，第h个灰狼的第d(d=1，2，…，L，L为搜索空间维度)维方位为

Xhd=Xmind+(Xmaxd-Xmind)rand()

(10)

式中：Xmind，Xmaxd分别为第h个灰狼的第d维方位的最小值、最大值；rand()为区间[0，1]的随机数。

(2) 计算适应度函数值。适应度函数值反映了灰狼寻找最优的能力，通常由目标函数转换而来。适应度函数值较低则说明该灰狼所在方位较好。AGWO算法在迭代进化时，适应度函数值较低的灰狼方位被保留，同时带领适应度函数值较高的灰狼逐步地靠近猎物。

(3) 包围操作。猎食开始时，灰狼种群先构建包围圈，接着逐步包围猎物。包围操作如下：

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

(11)

X(t+1)=Xp(t)-AD

(12)

A=2arand()-a

(13)

C=2rand()

(14)

式中：D为灰狼与猎物的距离向量；C为摆动因子向量；Xp(t)为第t代猎物的方位向量；X(t)，X(t+1)分别为第t，t+1代灰狼的方位向量；A为参数向量；a为收敛因子，a从2线性递减至0，表示灰狼种群逐渐缩小包围圈。

(4) 狩猎操作。基于α，β，δ层灰狼的适应度函数值，灰狼种群更新方位：

Dα=|C1Xα-Xp|

(15)

Dβ=|C2Xβ-Xp|

(16)

Dδ=|C3Xδ-Xp|

(17)

X1=Xα-A1Dα

(18)

X2=Xβ-A2Dβ

(19)

X3=Xδ-A3Dδ

(20)

X(t+1)=(X1+X2+X3)/3

(21)

式中：Dα，Dβ，Dδ分别为α，β，δ层灰狼与猎物的距离向量；C1，C2，C3分别为α，β，δ层灰狼的摆动因子向量；Xα，Xβ，Xδ分别为α，β，δ层灰狼的方位向量；Xp为猎物的方位向量；X1，X2，X3分别为α，β，δ层灰狼更新后的方位向量；A1，A2，A3分别为α，β，δ层灰狼的参数向量。

(5) 攻击操作。攻击操作主要通过收敛因子a逐渐递减完成。根据式(13)可知，随着算法的迭代进化，a线性递减为0，A逐渐递减为0，灰狼种群方位逐渐接近猎物方位。当灰狼种群与猎物方位相同时，表示灰狼成功捕获猎物，完成攻击操作。

(6) 迁移操作。每个灰狼生成一个 [0，1]的随机数，若该随机数小于迁移概率，则对该灰狼进行迁移操作；否则转至步骤(7)。

Pmh=Pm1(fmin+fh)/(fmax-fmin)

(22)

式中：Pmh为第h个灰狼的迁移概率；Pm1为标准迁移概率；fmin，fmax分别为适应度函数的最小值、最大值；fh为第h个灰狼的适应度函数值。

将迁移操作融入GWO算法，并且根据灰狼的适应度函数值动态地修正其迁移概率。一方面，对于较优灰狼(适应度函数值较低)，较小的Pmj可以保留较优灰狼的方位，避免算法错过全局最优，提升了全局寻优能力。另一方面，对于较差灰狼(适应度函数值较高)，较大的Pmj确保了较差灰狼可以被重新分配，分配后的灰狼可位于全局最优的周围，丰富了灰狼种群的多样性，加强了算法局部寻优能力，能快速地寻找到全局最优。

(7) 终止准则。当AGWO算法迭代至指定的进化代数，输出结果；否则转至步骤(2)。

3 仿真分析

为验证AGWO的有效性，以某露天矿实际运输调度数据为例，将AGWO应用于求解露天矿低碳运输调度问题，与AFOA，GWO，GA进行比较分析。

该露天矿包含10个采矿场和5个破碎场，采矿场至破碎场的距离见表1。卡车数量K=40辆；每辆卡车的装载量lk=40 t；卡车空载时单位距离油耗量yij1=0.08 L/(km·t)；卡车满载时单位距离油耗量yij2=0.22 L/(km·t)；燃油转化为CO2的单位转化率γ=2.65 kg/L；CO2的单位排放成本B3=0.25元/kg；每辆卡车的固定启用成本B1=20元/辆；每辆卡车的单位燃油成本B2=7.99元/L。

AGWO和GWO相关参数：搜索空间维度L=20，灰狼种群大小N=100，进化代数G=100。AGWO中的标准迁移概率Pm1=0.25。AFOA和GA参数设置分别与文献[2]和文献[7]中相同。为减少算法的时间复杂度，本文将露天矿运输调度的目标函数作为适应度函数。采用Matlab仿真露天矿低碳运输调度问题的求解。

AGWO，AFOA，GWO，GA的进化曲线如图1所示，可看出AGWO的寻优精度和寻优速度均优于其他算法。这是由于AGWO在初期继承了GWO较强的全局寻优能力，可以较快地聚集到全局最优附近；在后期灰狼种群逐渐集中在最优灰狼周围，此时迁移操作和自适应的迁移概率能够保留较优灰狼方位，重新分配较差的灰狼到新方位，从而降低了AGWO陷入局部最优的概率。

露天矿在实际运输中需要36辆卡车。根据式(1)—式(3)，结合表1和露天矿运输相关参数可知，露天矿的实际运输距离为1 882.227 km，运输费用为5 271.698元，碳排费用为374.093元，综合费用为5 645.791元。分别基于AGWO，AFOA，GWO，GA的露天矿低碳运输调度的碳排费用和运输费用见表2。可看出与实际运输数据相比，采用AGWO求解的运输距离减少了492.086 km，卡车数量减少了10辆，运输费用节省了1 419.531元，碳排费用节省了97.802元，综合费用节省了1 517.333元，采用AFOA，GWO，GA求解的综合费用分别节省了967.972，598.695，427.970元。由此可见，采用AGWO优化露天矿运输调度可有效提高运输效率，减少碳排费用和运输费用。

4 结语

AGWO算法在GWO算法的基础上引入迁移操作，并且根据灰狼的适应度函数值自适应调整灰狼的迁移概率，提升了算法局部寻优能力，促使算法能够较快寻找到全局最优，均衡了全局寻优能力和局部寻优能力；将AGWO算法用于求解露天矿低碳运输调度问题，提高了寻优精度与寻优速度，有效提高了运输效率，减少了碳排费用和运输费用。

参考文献（References）：

[1] 顾清华,张媛,卢才武,等.低碳限制下综合成本最小的露天矿卡车运输优化研究[J].金属矿山,2019(8):157-161.

GU Qinghua,ZHANG Yuan,LU Caiwu,et al.Truck transportation optimization research under the constraints of low carbon with the lowest comprehensive cost in open-pit mine[J].Metal Mine,2019(8):157-161.

[2] 苏楷,门飞.露天矿运输调度问题求解的自适应果蝇优化算法[J].金属矿山,2017(11):172-176.

SU Kai,MEN Fei.Adaptive fruit fly optimization algorithm for solving open-pit hauling dispatching optimization problem[J].Metal Mine,2017(11):172-176.

[3] 王桃,江松,卢才武.露天矿运输调度优化的生物地理学改进算法[J].金属矿山,2016(9):161-164.

WANG Tao,JIANG Song,LU Caiwu.Improved biogeography optimization algorithm method for open-pit hauling dispatching[J].Metal Mine,2016(9):161-164.

[4] 李勇,胡乃联,李国清.基于改进粒子群算法的露天矿运输调度优化[J].中国矿业,2013,22(4):98-101.

LI Yong,HU Nailian,LI Guoqing.Open-pit hauling dispatching optimization based on improved PSO algorithm[J].China Mining Magazine,2013,22(4):98-101.

[5] 彭程,薛伟宁,黄轶.露天矿运输问题的模拟退火优化[J].中国矿业,2018,27(4):138-141.

PENG Cheng,XUE Weining,HUANG Yi.Simulated annealing algorithm for the open-pit mine transportation problem[J].China Mining Magazine,2018,27(4):138-141.

[6] 彭程,隋晓梅,王辉俊.用于求解露天矿运输问题的改进差分进化算法[J].工矿自动化,2018,44(4):104-108.

PENG Cheng,SUI Xiaomei,WANG Huijun.Improved differential evolution algorithm for solving open-pit mine transportation problem[J].Industry and Mine Automation,2018,44(4):104-108.

[7] 鞠兴军,李林,刘光伟.基于遗传算法的神经网络在露天矿卡车调度系统中的应用研究[J].露天采矿技术,2009(6):31-33.

JU Xingjun,LI Lin,LIU Guangwei.Application research on truck dispatching system based on neural network of genetic algorithm in surface mine[J].Opencast Mining Technology,2009(6):31-33.

[8] 刘浩洋.基于改进蚁群算法的露天矿卡车优化调度研究[D].西安:西安建筑科技大学,2013.

LIU Haoyang.Strip mine truck optimization scheduling research based on improved ant colony algorithm[D].Xi'an:Xi'an University of Architecture and Technology,2013.

[9] MIRJALILI S,MIRJALILI S M,LEWIS A.Grey wolf optimizer[J].Advances in Engineering Software,2014,69:46-61.

[10] SAREMI S,MIRJALILI S Z,MIRJALILI S M.Evolutionary population dynamics and grey wolf optimizer[J].Neural Computing and Applications,2015,26(5):1257-1263.

[11] 吕新桥,廖天龙.基于灰狼优化算法的置换流水线车间调度[J].武汉理工大学学报,2015,37(5):111-116.

LYU Xinqiao,LIAO Tianlong.Permutation flow-shop scheduling based on the grey wolf optimizer[J].Journal of Wuhan University of Technology,2015,37(5):111-116.

[12] 王敏,唐明珠.一种新型非线性收敛因子的灰狼优化算法[J].计算机应用研究,2016,33(12):3648-3653.

WANG Min,TANG Mingzhu.Novel grey wolf optimization algorithm based on nonlinear convergence factor[J].Application Research of Computers,2016,33(12):3648-3653.

[13] 龙文,赵东泉,徐松金.求解约束优化问题的改进灰狼优化算法[J].计算机应用,2015,35(9):2590-2595.

LONG Wen,ZHAO Dongquan,XU Songjin.Improved grey wolf optimization algorithm for constrained optimization problem[J].Journal of Computer Applications,2015,35(9):2590-2595.

[14] MIRJALILI S.How effective is the grey wolf optimizer in training multi-layer perceptrons[J].Applied Intelligence,2015,43(1):150-161.

[15] EI-GAAFARY A A M,MOHAMED Y S,HEMEIDA A M,et al.Grey wolf optimization for multi input multi output system[J].Universal Journal of Communications and Networks,2015,3(1):1-6．

[16] 郭振洲,刘然,拱长青,等.基于灰狼算法的改进研究[J].计算机应用研究,2017,34(12):3603-3606.

GUO Zhenzhou,LIU Ran,GONG Changqing,et al.Study on improvement of gray wolf algorithm[J].Application Research of Computers,2017,34(12):3603-3606.

[17] 龙文,蔡绍洪,焦建军,等.求解高维优化问题的混合灰狼优化算法[J].控制与决策,2016,31(11):1991-1997.

LONG Wen,CAI Shaohong,JIAO Jianjun,et al.Hybrid grey wolf optimization algorithm for high-dimensional optimization[J].Control and Decision,2016,31(11):1991-1997.

[18] 徐达宇,LIU Renping.基于改进自组织临界优化的元启发式灰狼优化算法[J].计算机应用,2016,36(6):1588-1593.

XU Dayu,LIU Renping.Improved self-organized criticality optimized gray wolf optimizer metaheuristic algorithm[J].Journal of Computer Applications,2016,36(6):1588-1593.

[19] 姚远远,叶春明,杨枫.TFT-LCD模块组装调度问题的改进灰狼优化算法[J].小型微型计算机系统,2018,39(10):2146-2153.

YAO Yuanyuan,YE Chunming,YANG Feng.Improved grey wolf optimizer for the TFT-LCD module assembly scheduling problem[J].Journal of Chinese Computer Systems,2018,39(10):2146-2153.

Improved gray wolf optimization algorithm for solving low-carbon transportation scheduling problem in open-pit mines

MEN Fei, JIANG Xin

(School of Computer and Software Engineering, Pingdingshan Polytenchnic College,Pingdingshan 467000, China)

Abstract:In order to solve the problem of low-carbon transportation scheduling in open-pit mines, the mathematical model is established by taking the mining volume, crushing volume of crushing stations and the number of trucks as constraints and taking the minimum sum of carbon emission cost and transportation cost as the objective function. An improved gray wolf optimization algorithm is proposed for the problem that gray wolf optimization algorithm is easy to fall into local optimum when it is used to solve the low-carbon transportation scheduling problem of open-pit mines. The algorithm introduces migration operation in the gray wolf optimization algorithm and dynamically modifies the migration probability of the gray wolf optimization algorithm according to its fitness function value. It is beneficial to go beyond the local optimum and obtain the global optimum faster so as to effectively balance the global optimization ability and local optimization ability. Experimental results show that the algorithm has higher optimization accuracy and faster optimization speed. By applying this algorithm to optimize low-carbon transportation scheduling in open-pit mines, transportation efficiency has been improved and carbon emissions and transportation costs have been reduced.

Key words:open-pit mine transportation; low-carbon; transportation scheduling; gray wolf optimization algorithm; migration operation

中图分类号：TD57

文献标志码：A