基于改进蚁群算法的露天矿无人驾驶卡车智能调度

张 超，江 松

(1.洛阳栾川钼业集团股份有限公司矿山公司，河南栾川471500；2.西安建筑科技大学资源工程学院，陕西西安710055）

矿山智能开采是21世纪矿业发展的重要方向和前瞻性目标[1]。实现智能采矿是一个复杂的系统工程，面临许多科技难题，其中露天矿无人驾驶卡车智能调度问题更是被国内外学者广泛关注[2]。国内方面，李宏刚等[3]针对矿区生产、运输工作环境恶劣、安全事故频发、作业现场远离生活区导致目前面临人员流动性高、司机老龄化严重等现象，提出了一种矿用运输车辆无人驾驶感知控制方法；赵勇等[4]在建立露天矿卡车调度运输模型时考虑到车流规划目标流率饱和度，较快地实现了车流的转移；邢军等[5]给出了目标产量完成度和当前车流饱和度的准则，使卡车实时调度过程及结果更优；黄宝祥[6]通过对遗传算法杂交算子的改进，优化了矿山卡车多目标车流分配调度模型。国外方面，加拿大的森科尔能源公司从2019年开始部署超过150辆的露天矿无人卡车；Patterson等[7]考虑到装载和运输过程中由于设备闲置而产生的能源消耗问题，以能耗为目标建立了卡车调度运输模型；Sub等[8]将机器学习方法与大数据相结合预测露天矿卡车调度运输时的实时链路行程时间，并考虑气象特征对模型的影响。综上所述，目前关于露天矿卡车调度问题的研究，大部分是以路径最短或运费最少为目标建立优化模型，对露天矿无人卡车调度中的车流分配与传统人工卡车车流分配模型的不同之处考虑不足[9]。为合理调配露天矿无人驾驶卡车运输设备，实现新型露天矿矿山企业快速发展，解决无人驾驶卡车运输车流分配调度的需求，文中以综合成本最小为目标函数，构建露天矿无人驾驶卡车最优分配调度模型，采用改进的蚁群算法对模型求解，进而实现新型露天矿无人驾驶卡车的车流分配调度。

1 露天矿卡车调度问题

露天矿的开采是在有矿石资源的地表层利用先进技术及先进设备对地表下含有的矿石进行勘探及挖掘，并用卡车将开采的矿石、岩石运送到指定地点再进行一系列操作的过程。露天矿场景及运输模拟如图1。卡车的调度运输是露天矿开采的核心，调度运输消耗的能耗和产生的成本占整个生产过程的一半以上。因此，合理的调度运输对矿山的生产效益产生巨大影响。

图1 露天矿场景及运输模拟Fig.1 Open pit mine scene and transportation simulation

露天矿卡车调度运输前，要充分考察矿山的地理环境，全面考虑卡车、铲车、破碎站的位置及数量、每一过程具体如何开展及卡车不能出现扎堆与堵车等现象，当现场出现临时状况要能及时处理，提出合理的解决方案，且满足最初目标。目的是为完成一定任务时，所用的卡车、铲车等数量能够减少，减少无效工作时间，节省费用支出，提高工作效率。露天矿卡车调度系统包括最佳运输路线的确定、车流规划、实时调度等方面，每个方面对矿石开采过程起重要作用[10]。

1.1 最佳运输路线的确定

根据露天矿的现场地理环境，找出挖掘点与破碎站之间的最短路径，以往求解最佳运输路线常用的方法主要是以下几种。

Dijkstra法是以图论为基础，将露天矿中电铲、卡车、道路与道路之间的交叉点等表示成节点，每条运输路径可视为图上的一条弧线，每条路径的距离可视为权值，这样可把露天矿中形成的简易道路网转化成带权的有向图。假设露天矿运输网G=(N,E,W)，N 为运输网络图G 中节点的集合，E 为图G 中边的集合，W 为图G 的权，假设图G 中包含的各节点数为n，对于其他任何一个点p 和q(p,q=1,2,3,…,n,p ≠q)，则最短路径方程为

式中： dq为道路网中从第1个点到第q 个点距离最短的线路；wpq为道路网中从p 点到q 点的长度。

Floyd法解决小规模的露天矿最优问题时，利用动态规划的特点可快速找到最适合的运输路径。将露天矿装载点、卸载点及其他节点当作一个加权图中的各节点，节点与节点之间的连线赋予权值，其权值可用矩阵表示并求出每两个点之间的距离，即为矿山中各点之间的实际距离。选择距离最短的值存入矩阵A=[a(i,j)]n×n，按照已知条件将初始矩阵D(0)=A 反复迭代g 次，构造出矩阵D(n)，即为加权图的距离矩阵。用G′表示给定的加权图，i 与j 之间的距离用d 表示，即G′(i,j)=d，若在i 与j 之间插入一点k，则G′(i,j)=min[G′(i,j),G′(i,k)+G′(k,j)]。

1.2 车流规划

在满足矿山产量及卡车、铲车等设备的数量约束条件下，通常采用线性规划等方法对各装载点和卸载点之间的车流量进行合理分配，使各路径的车流运输达到最优。

1.3 实时调度

确定最短路径及车流规划后，采用合适的矿山实时调度准则对正在运行的设备和必须完成的作业给予合理的优化调度。若任务未完成，应将参与运输的卡车派到不需等待或等待车辆较少的铲位处，利用动态规划原则使即将行使的车辆行驶在车流量适中且运输距离最优的道路，提高作业效率。

2 露天矿无人驾驶卡车最优调度模型

文中针对矿石从出矿口到达处理点的一个调度运输，考虑矿山运输的特点及环保问题，综合考虑卡车在调度运输过程中的各项成本，以装载点的最大产量、卸载点的最大承载量、卡车装卸时间及品位要求等为约束条件，构建以总成本最小为优化目标的露天矿低碳调度模型。矿山中有m 个可装载卡车的点、n 个破碎站、k 辆车可参与运输，且每辆装载车的工作能力和每个破碎站的倾卸能力已知，制定一个可行的方案使能够参与工作的各机械设备在规定时间内完成计划任务，同时可使总费用达到最低。

2.1 运输成本

运输成本与运输距离有直接关系。用Dij表示卡车在装载点i 到破碎站j 之间的距离，Xrij表示第r 辆车从装载点i 运输矿石到破碎站j，Xrji表示第r 辆卡车卸载完矿石后从破碎站返回装载点，Cr1表示第r 辆卡车单位距离的重车运输费用，Cr2表示第r 辆卡车单位距离的空车运输费用，则卡车从装载点i 到破碎站j 的重车、空车运输成本费用C1，C2分别为

2.2 维修成本

卡车在运输过程中随时会出现故障问题，假设卡车维修费用与卡车运行路径长短有关，Dr表示第r 辆卡车运行路径的长度，Cr3表示第r 辆卡车单位距离的维修费用，则卡车运输过程中的维修费用C3如

2.3 油耗成本

假设卡车行驶路径不存在坡度，且卡车运输的油耗费用受车辆载重和行驶距离的影响。当卡车在i，j两点间运行时，假设卡车满载时单位距离油耗为yij1，空载时单位距离油耗为yij2，单位燃油成本为y，卡车满载质量为m1，空载质量为m2，则重车、空车下的油耗成本分别C4，C5为

2.4 碳排放成本

卡车在运输过程中排放的CO2是由油耗量间接转化而来的，可通过CO2的单位转换率δ 计算碳排放成本。CO2单位排放成本为c，卡车在i，j 两点间单位距离的CO2排放量为δyij1δyij2，则卡车在重车、空车下的碳排放成本C6，C7分别为

2.5 卡车固定成本

无论卡车运输距离如何变化，载重都不会影响卡车固定成本费用，平均分摊到每辆卡车上即为卡车固定启用成本，用b 表示，则矿山运输中卡车固定启用成本C8为

综上所述，露天矿无人驾驶卡车最优调度模型的目标函数为

3 蚁群算法的改进

3.1 算法基本原理

蚁群算法是通过自身释放的信息素来判断路径距离，初期蚂蚁在经过路径上的信息素含量较少，需很长时间积累才能增加路径上信息素的量，因此蚂蚁很难在短时间内找到合适路径，收敛到最优值的速度较慢[11]。当蚂蚁多次经过这条路径使信息素增多才能加快算法收敛于最优值。遗传算法开始时搜索范围较广，刚开始的种群较丰富，找到最优值的速度快，但遗传算法经过反复迭代，后期种群规模不再继续扩大，导致收敛速度明显减弱，且没有蚁群算法正反馈的优点，算法很难快速找到最优解，产生冗余现象。为解决以上问题，文中提出一种新的混合蚁群算法(ant colony genetic algorithm,ACGA)，用改进的混合算法求解低碳卡车调度问题。

3.1.1 编码方式与初始种群的产生

编码方式的选择会影响算法的优劣。文中对露天矿卡车低碳调度模型采用整数编码方式记录每条染色体点的顺序，即每辆卡车的运行路线。假设露天矿中有3个卸载点，卡车从0号铲装点运送矿石往1，2，3号卸载点；4，5，6，7，8 为路径交叉点编号，则[0，1，2，3，4，5，6，7，8，9，10]可表示一条染色体的顺序，[0，4，5，1，…，…，0，7，6，2，…，…，0，8，3]代表染色体对应的卡车运输路径，即有3辆卡车从0号装载点出发分别往卸载点1,2,3，随即产生3条运输路径0-4-5-1，0-7-6-2，0-8-3。

3.1.2 计算种群适应度

3.1.3 选择过程

在基本遗传算法中交叉率Pc和变异率Pm是固定值，算法在运行过程中没有发生大的变化，运行速度依然很慢，且易产生局部最优现象。为改变这一缺点，用适应度来计算Pc和Pm，使Pc和Pm成为动态的。交叉率Pc和变异率Pm的计算公式为：

式中：fmax-favg用来判断种群的多样性；f′≥favg用来判断个体与种群的离散程度；fmax为最大适应度值；favg为平均适应度值；f′为参与交叉两个个体中的较大适应度值；f 为变异个体的适应度值；Pcmax为最大交叉率；Pcmin为最小交叉率；Pmmax为最大变异率；Pmmin为最小变异率。

通过式(11)和(12)得到Pc和Pm后，需选择Pc和Pm值较大的个体进行交叉和变异，因此选取一个(0,1)之间的随机数u 与Pc和Pm比较，大于u 的个体才能进行下一步。

3.1.4 交叉过程

文中采用算术交叉的方法将寻优过程中表现良好的个体保留下来继续迭代，算数交叉公式为：

式中：X(i)，X(i+1)表示不同的个体；X′(i)，X′(i+1)表示交叉后产生的新个体；u 为（0,1）之间产生的随机数。

3.1.5 变异过程

基本遗传算法只对固定的字符变异，文中提出的混合蚁群算法对每次发生变异时的字符和位置都发生变化，使之产生多种新个体，种群更庞大，算法迭代寻优过程更顺利。此变异操作可表示为：利用已知的变异率乘以每个个体的字符长度，得到每个需变异个体的字符数，如

式中：gene(i)为第i 个个体需要变异的字符个数；d 为个体字符长度；Pm(i)为个体的变异率。根据需要变异的字符个数，可从个体的最后一位字符开始随机变异：Xn=X1+b+rand(a-b)，Xn为变异产生的最终个体，X1为不参与变异的个体，a 和b 分别为所求解中每个字符的最大值和最小值，rand()为(0,1)之间的随机函数。完成一轮交叉变异后对得到的所有解进行比较，采用轮盘赌的方式保留与初始种群个数相同的个体，可留下大部分较优解，增加解的多样性。

3.2 算法基本流程

混合蚁群算法流程图如图2。其中遗传算法主要步骤为如下1)～7)；蚁群算法主要步骤如下8)～12)。

1)设置参数，种群规模为N，最初迭代次数为0，最大迭代次数gmax；

2)染色体编码方式为整数编码；

3)计算种群适应度，定义种群适应度函数为综合成本的倒数；

4)依据适应度值计算Pc和Pm，选择Pc和Pm大的个体参与到下一步；

5)采用算数交叉方法选择优良性高的个体进行交叉操作；

6)采用随机变异字符数和位置的方法对新个体进行变异操作，并对新个体与父代个体进行比较，选择最优个体作为最终的子代个体；

7)使用比较策略判断遗传算法与蚁群算法的最佳切换时间，并对迭代次数进行比较，若g ＞gmax，则遗传算法结束，进入蚁群算法，否则继续步骤3)；

8)选用遗传算法运行结果中排名前20%的个体为蚁群算法中的初始值，并对算法的参数进行取值，蚂蚁个数为m′，初始迭代数设置为0，迭代最大次数设置为gmax；

10)当一只蚂蚁完成路径寻优后，将其放入禁忌表中，并对路径上的信息素进行局部更新；

11)当所有蚂蚁完成一次循环后，寻找到一条合适的运输路径，对所有可能经过路径的信息素进行更新，重复上述过程继续循环找寻最优解；

12)当g ＞gmax，循环结束，输出最优解，否则转步骤9)。

图2 混合蚁群算法流程图Fig.2 Flow chart of hybrid ant colony algorithm

4 实例应用

为解决露天矿卡车低碳调度运输问题，以河南省某露天矿为例进行求解，该矿采区有6个装载点、4 个卸载点、卡车20 辆。车队在一个班次内需完成4个卸载点的任务，如表1。破碎站处对矿石品位的约束范围为0.10%～0.13%。

4.1 装载点与卸载点的距离

矿山中装载点到卸载点的距离是通过经纬度获得的，通过GPS监测可得到各点之间卡车的运行轨迹，根据卡车在每时间段内运行的轨迹叠加计算装载点1与卸载点a之间的距离，据此得到其他点之间的距离，结果如表2。

表1 各卸载点任务量Tab.1 Tasks of each unloading point

表2 各点之间的距离，kmTab.2 Distance between points,km

4.2 铲位量与矿石品位

矿山中每处矿石的品位不同，且每个电铲的铲位量也有差异，表3为6处装载点矿石品位及电铲每次装载量。

4.3 现场设备作业参数

装车时间受电铲工作效率的影响，根据现场经验可知，装载点处电铲的装车时间为5 min，卸载点处卡车倾卸矿石所需时间为3 min，卡车在运输过程中始终保持匀速行驶，重车状态下卡车运行速度,空车状态下卡车运行速度。

4.4 作业费用

根据露天矿卡车低碳调度优化模型，文中实例模型参数设定为：卡车重载运输费用为60 元/km,空载运输费用为50 元/km，维修费用1.5 元/km，卡车空载单位距离油耗量为0.08 L·km-1·t-1，卡车重载单位距离油耗量0.22 L·km-1·t-1，卡车运输过程中燃油消耗转化为二氧化碳的单位转化率2.65 kg/L，单位距离消耗燃油成本7.99 元/L，卡车固定启用成本20 元/辆，CO2单位排放成本0.25 元/kg，卡车重车状态下的质量40 t，卡车空车状态下的质量12 t。

4.5 优化求解

采用MATLAB软件依据文中研究的内容对混合蚁群算法编程，对卡车低碳调度过程优化求解，得到6个装载点与4个卸载点形成的各条道路能同时运送矿石的卡车数目(如表4)，各线路卡车运行次数如表5。根据各条线路卡车的运行次数，调度方案中派车时只针对这些线路派车，结果如表6。

表3 各装载点的铲位量及品位Tab.3 Shovel position and grade of each loading point

表4 各条路径上能同时运行的卡车数，辆Tab.4 The number of trucks running simultaneously on each route

表5 各条路径卡车运行次数，次Tab.5 Truck operation times of each route

表6 最佳派车方案线路Tab.6 Route of the best vehicle dispatching scheme

由表6可知调度运输方案中14条路线的具体数据，依照此数据对矿区内卡车进行实时调度，使卡车按一定方式运输，卡车可在同一线路运输，依照先后次序并保证前一辆车与后一辆车间隔运输，不发生卡车等待情况。卡车也可完成自己路线的任务后到其他线路运输，但不能与其他线路的卡车运输发生冲突。这些线路卡车每班运行的各项成本如表7(以前5个路线为例)。由表7可知：1-c路线的距离比1-b，1-d的长，但1-c的总成本低于1-b，1-d，而1-d路线的距离小于1-c，但1-d的成本比1-c的高，说明装载点与卸载点之间运输距离不是决定运输成本的唯一因素；距离长的路段在一个班次内的维修成本、油耗成本、碳排放成本不一定比距离短的成本高，卡车运行速度一定时，维修成本、油耗成本、碳排放成本和固定成本除与运输距离有关外，还与每条路径的路况、运输趟数、使用卡车数有关。因此距离最短运输路径的维修成本、油耗和碳排放成本不一定最低，运输距离相差较大的卡车固定成本差距并不是最大的，若只从运输距离最短来衡量卡车运输过程中的成本，其运输方案不一定最优。

表7 各线路调度成本Tab.7 Dispatching cost of each line

为证明本文建立模型的优异之处，分别以卡车运输距离最短、油耗成本最小、碳排放成本最小和综合成本最小为目标，利用混合蚁群算法对其中一条路径5-d进行求解，得到相应目标下的最优调度方案的各项成本，对比结果见表8。由表8可知：以距离最短为优化目标时并未考虑油耗和碳排放量对成本的影响，导致其油耗和碳排放成本较高，因此总成本不是最优；以综合成本为优化目标时考虑的因素较全面，虽卡车运输距离不是最优，但在完成相同任务的前提下使用的卡车数最少，卡车得到了充分合理利用，减少了卡车的固定启用成本，同时维修、油耗和碳排放成本均较低，使综合成本最小。

表8 不同优化目标下最优调度方案对比Tab.8 Comparison of optimal scheduling schemes under different optimization objectives

4 结 论

建立综合成本最小的露天矿卡车最优调度优化模型，包括卡车在重车、空车状态下的运输费用、维修费用、卡车启用成本、油耗成本和碳排放成本。同时提出采用混合蚁群算法来优化总成本最小的露天矿卡车低碳调度问题。实例应用结果表明，卡车在运输过程中考虑不同因素作为目标函数得到的优化结果不同，以综合成本最小为优化目标消耗的能耗最少，产生的碳排放最少，降低了生产成本的目标。