基于遗传算法的多车型露天矿卡车调度模型研究

王金亮

（中铁十一局集团有限公司）

近年来，随着物流运输科技的飞速发展，采矿业如何通过降低运输成本提高生产效益成为学者普遍关注的焦点。目前，国内外针对露天矿卡车调度的研究主要集中在运输费用、运输台班生产作业时间、非生产时间等方面。以运输环节为例，在露天矿生产过程中，运输费用占整个矿山生产费用的50%以上。因此，有必要对露天矿卡车调度问题进行研究，进一步完善调度系统，减少运输成本。

露天矿卡车调度问题是一类复杂的优化问题，按卡车车型分为单车型调度问题和多车型调度问题。过去的几十年里，国内外学者对单车型露天矿卡车调度问题进行了大量的研究。而对于多车型调度问题的研究仅仅停留在物流配送领域，涉及露天矿卡车调度的多车型问题很少。王旭［1］、刘波［2］、魏明［3］、SarangKulkarni［4］针对单车型调度问题进行了研究，并给出求解此类问题的量子遗传算法、混合遗传算法、离散粒子群算法、两阶段启发式算法。为了解决露天矿卡车调度问题，许茂增等［5］在一般模型的基础上进一步细化了运输费用的组成，将卡车折旧、卡车轮胎磨损以及司机工资等费用考虑在内，建立了综合成本最小化的调度模型。此外，霍晓宇等［6］以卡车总运营成本最小为目标建立调度模型，并采用自适应变异粒子群算法对模型进行求解。曹庆奎等［7］以最小化系统总成本为目标，建立了带时间窗约束的车辆调度模型，并提出求解该问题的模拟植物生长算法。考虑到卡车运输量和车辆利用率对运输效率的影响作用，蹇洁等［8］建立了卡车油耗成本和固定用车成本综合最小化的调度模型，并根据问题的特点设计了1 种云自适应遗传算法。Chang Y 等［9］考虑不同的运输收入及最优解的2 个性质和2 个上界，构建了混合整数规划模型，并提出了1 种具有2 种改进策略的启发式算法，实现了露天矿卡车优化调度。S R Patterson 等［10］为最大限度地减少满足生产要求所需的设备数，以最小化卡车和电铲的能耗为目标，提出了1 种混合整数线性规划（MILP）调度模型，并开发了1种构造性算法和禁忌搜索方案，实现了露天矿卡车的节能调度。上述学者都是研究单车型露天矿卡车调度问题，而实际矿山生产中，运输卡车车型并非只有1种。因此，本项目在上述研究的基础上提出了露天矿多车型卡车调度模型。此外，虽然目前已有学者对多车型卡车调度问题进行研究，但该类研究大多停留在一般物流配送问题上。葛显龙［11］在分析不同车型调度问题的基础上，对具有动态需求的多车型调度问题进行了研究，并利用云模型对遗传算法进行了改进，设计了1种云自适应遗传算法对调度模型进行求解。之后，葛显龙等［12］考虑车辆运输的固定成本和油耗成本，以总运输成本最小化为目标建立了多车型车辆调度模型，最后采用量子遗传算法对该问题进行解决。国外对该问题的研究大多停留在最短配送路径研究方面，如Salhi［13］对多车场多车调度问题进行了研究，设计了1种改进的遗传算法用于求解最佳的运输路径。此后，Comaniciu［14］基于模拟退火算法求解了多车场多车型最短配送路径问题。A Ceder［15］针对多车型车辆调度问题开发了一种结合偶数车头和均匀载荷概念构建时间表的方法，并将该问题转化为具有NP 复杂度级别的成本流网络问题。Stephan Hassold［16］针对多车型车辆调度问题（MVT-VSP）提出了基于多组帕累托最优时间表的最小成本网络流量模型，结果表明使用帕累托有效时间表作为输入，可以将调度成本降低15%以上。Subramanian［17］提出自适应记忆规划求解多车型车辆调度问题。Artur［18］采用禁忌搜索算法研究了多车型车辆调度问题。

目前物流企业针对配送问题提出了一些解决多车场多车型调度问题的解决办法，但基本都是由TSP问题引申出的遍历问题，这些方法往往由于适应范围太广，针对性不强。而露天矿卡车调度问题不同于传统的TSP问题，该问题属于兼顾配矿与调度的非遍历调度问题，故此类办法在露天矿卡车调度问题中往往无法使用。因此，本研究在现有单车型露天矿卡车调度和多车型物流配送问题研究的基础上，综合考虑露天矿运输卡车载质量以及运输过程中的空载费用、重载费用等影响因素，以最小化运输成本为目标建立多车型露天矿卡车调度模型，以实现调度卡车的优化配置。

1 露天矿卡车调度模型

1.1 问题描述

考虑多种车型卡车组合运输的露天矿卡车调度问题可描述为设E={ }F,D为1 个代表装载点、卸载点和点间距离的道路网络图，其中F={1,2,…M;1,2,…N} 为节点集，D={dij},i,j∈F,i≠j为边集。1 队载质量不同的卡车从车库出发，行驶到装载点，满载矿石至卸载点，卡车往返直至满足1 个班次内卸载点产量需求。考虑卡车数量的限制和运输任务的要求，1 辆卡车可以为多个卸载点服务。铲点产量和卸载点需求量已知。问题的目标是确定1 套卡车调度方案，满足产量及品位等要求，且运输总成本最小。

1.2 模型假设

运输过程中卡车以恒速行驶，假设如下。

（1）电铲和卡车在1 个班次内可以不停地工作，不会出现机器故障等突发事件。

（2）1个班次内卸点、铲点的位置固定。

（3）卡车路线不固定，当其在1 条路线上完成任务之后可以到其他路线上去帮助其他卡车运输。

（4）卡车仅从车库出发和返回1 次，且不同型号卡车空载、重载单位费用相同。

（5）1个铲位只安排1台电铲，同一时间该铲位只能有1 辆卡车装车，前1 辆车开走后才允许后1 辆车装车，当某个铲位的矿石量低于卡车载质量时，由载质量小的卡车运输。

1.3 符号变量说明

露天矿卡车调度模型研究是一类大型复杂问题，其涉及约束众多，模型建立时需考虑参数较多，为便于模型的建立与理解，现对各参数作以下说明，具体见表1。

1.4 目标函数

在满足约束条件的情况下，取总运输费用最小的解。总运输费用包括卡车从车库O到铲点i、从卸点j到铲点i和从卸点j返回车库O的空运费用以及卡车从铲点i到卸点j的重运费用。目标函数如下。

1.5 约束条件分析

（1）道路通行能力约束。1 个电铲不能同时为2辆卡车提供服务，因此，1 条路线上能同时运行的卡车数有限，在卡车不等待的前提下，1 条线路上可同时运行的最大卡车数为Zij=[ ]tij÷p，其中[ ]表示向下取整。

按第1 趟卡车装车来计算，1 个班次内该线路某型号卡车最大运行次数为

2 遗传算法设计

遗传算法是模拟生物在自然界中的遗传和进化过程而开发的1 种全局优化自适应随机搜索算法。遗传算法由于全局搜索能力强、鲁棒性好，而且适应于并行处理，所以被广泛应用于求解车辆调度问题、运输问题及供应链网络设计问题等。

2.1 染色体的编码与解码

用遗传算法求解多车型露天矿卡车调度问题时，确定染色体的编码方法是一项非常关键的工作，它直接决定算法实现的难易程度和性能的优劣。本研究采用对运输车次数按照x11,x12,…x1n,x21,x22,…,xm1,xm2,…xmn直接进行实数编码的方式，对于1 个包含M个铲位，N个卸点，V种车型，每种车型包含S辆卡车的露天矿卡车调度问题，染色体编码就是M×N个非负整数0 到max的一个随机排列，其长度为S×V×M×N。每个基因对应一个非负整数，基因值表示运输次数。这种编码和解码方法是随机产生1个1到V的整数表示调用哪种车型；然后随机产生1 个1 到S的整数表示调用哪辆车，按照卡车具体分配给哪个铲位，将该卡车写入该铲位对应解的编码中，重复以上操作，直至所有路线卡车分配完毕，得到1个完整的配送方案。

例如，1 个调度中心有3 种卡车车型（编号为Ⅰ、Ⅱ、Ⅲ），每种车型均有2辆相同的卡车（编号为1，2），需要为3 个铲位、2 个卸点服务。假设根据铲位最大矿石量和卡车最小载质量算得仅1 辆卡车参与运输时的最大运输次数为8，设染色体的编码为，通 过 如下解码过程可以得到上述染色体对应的1 个可行解（即配送方案）。

表示路线（1，1）安排Ⅰ型1 号卡车运输3 次，Ⅰ型2 号卡车运输0 次，Ⅱ型1 号卡车运输1 次，Ⅱ型2号卡车运输2 次，Ⅲ型1 号卡车运输0 次，Ⅲ型2 号卡车运输2次；重复以上步骤直到安排完所有路线的配送计划，可得到1个完整的调度方案。各铲位服务卡车均从车库出发，最后回到原车库。容易看出这种编码和解码方式在交叉、变异过程中极易跳出可行解的范围（例如交叉后车次数远大于8）。因此在第1次编码的基础上进行二次编码，这里可以采用四位二进制编码。例如路线（1，1）的运输方案为301202，其二进制编码为。

2.2 初始种群的确定

随机产生1 个由N个染色体组成的初始种群，对其进行解码操作可得到每个个体对应的车辆调度方案。

2.3 适应度函数

本研究选取目标函数作为适应度函数去评价车辆调度问题中可行解的优劣。

2.4 精英选择

从每一代种群中选择一定数量的适应度最好的个体直接进入下一代，并参与下一代种群适应度的比较及交叉和变异操作。精英选择不仅可以保证优秀个体不会在进化过程中丢失，加速算法收敛，而且可以保证下一代种群中的最优个体不会比上一代差，使得进化曲线保持单调下降趋势。

2.5 交叉操作

设交叉概率为Pc，首先在上一代种群中随机选取2 个个体作为父代，然后生成1 个介于（0，1）的随机数P，如果P＞Pc，则2 个父代不进行交叉，因而不产生新个体，如果P＜Pc，则随机确定1个交叉点再进行交叉操作。

设父代染色体A1的1个基因组为，B1的1个基因组为，则按照如下步骤进行交叉操作。

Step 1：随机产生1 到3 之间的1 个随机整数组，长度为6，表示基因的交叉点，如122321。

Step 2：将染色体B1中的6 组基因分别从第2、3、3、4、3、2 个基因开始的所有基因依次加到A1染色体的前面，同时将染色体A1中从第2、3、3、4、3、2个基因开始的所有基因依次加到染色体B1的前面，得到A1=，B1=。

Step 3：A1、B1中每组只保留前4 位自然数，得到新的染色体A1′，A2′=。

与传统方法相比，这种交叉操作能够避免交叉后由于基因长度的增加而产生的跳出解空间的现象。

2.6 变异操作

本研究采用的变异方法为多点变异，设种群的变异概率为PM，首先生成1 个介于（0，1）之间的随机数P1，如果P1＞PM则染色体不发生变异，因而不产生新个体；如果P1≤PM，则染色体发生变异。这里采用六点反转变异，首先随机产生整数1 到4 的1 个长度为6 的随机排列，序列数代表基因位数，将排列中整数对应的染色体基因做0-1互换即可。

如父代染色体为A1′=，则按如下规则进行变异操作：首先给出整数1～4 的1 个随机排列，如232141，然后将染色体各组基因的第2、3、2、1、4 及第1 个基因做0-1 互换，则得到1 个新的染色体A1"=。

2.7 生成新种群

在遗传算法中，新个体来源于精英选择、交叉和变异3 种操作，假设通过上述3 种途径得到的种群大小为N′，如果N′＞N，则按照适应度由小到大的顺序选取前N个个体组成新种群，如果N′＜N，则再随机生成(N-N′)个个体加入新种群，保持新种群与上一代种群大小相同，既可以避免因为种群规模越来越大而增加交叉和变异的难度，也可以防止因为种群规模越来越小而使算法趋于早熟［16］。

3 模型应用

3.1 基本数据

以国内某露天矿生产调度为例对所建模型进行求解。采场内共有5 个装载点，3 个卸载点，各铲位均分布1台电铲，车库有3种车型，每个车型有2辆卡车，不同车型车辆的载货量如表2所示。各个铲点和卸点位置如图1 所示，在1 h 内，卸载点的产量要求：矿石漏1 600 t，倒装场Ⅰ为1 850 t，倒装场Ⅱ为1 513 t。根据统计数据，得知电铲的平均装车时间约为5.5 min，卡车的平均卸载时间约为3.5 min。铲点到卸点及车库到铲点、卸点的距离如表3 所示，假设矿石品位要求为29.5%±1%，各铲位矿石储量以及矿石的平均铁含量如表4 所示。所用卡车平均时速32 km/h，3 种车型卡车的空车单位运输成本均为10 元，重车单位运输成本分别为15、20、30元。在1 h内，主要生产计划目标是利用现有卡车，根据生产计划要求和卡车数量，规划出1 h 内所要出动卡车的台数、型号、每条路线卡车运行次数，并安排其运输路线，即生产调度方案。

3.2 结果分析

设种群规模为150，交叉率为0.9，变异率为0.05，最大迭代次数为500，ε=0.01。采用MATLAB 编程实现上述算法，得到最优调度方案，如表5所示。Ⅰ型1号卡车分别在路线（1，3）、（2，1）、（3，1）、（3，2）、（4，2）、（4，3）、（5，3）上运输3 次、2 次、6 次、4 次、3 次、8次、2 次；Ⅰ型2 号卡车分别在路线（1，2）、（2，2）、（3，1）、（3，2）、（4，1）、（5，3）上运输4 次、5 次、2 次、2 次、6次、5 次；Ⅱ型1 号卡车分别在路线（1，2）、（2，1）、（2，2）、（3，1）、（4，2）、（4，3）上运输6 次、3 次、3 次、5 次、4次、4 次；Ⅱ型2 号卡车分别在路线（1，2）、（2，2）、（3，2）、（4，1）上运输5次、7次、5次、6次；Ⅲ型1号卡车分别在路线（1，3）、（2，2）、（3，1）、（3，2）、（4，1）上运输6次、3次、4次、1次、2次；Ⅲ型2号卡车分别在路线（1，2）、（4，1）、（4，3）、（5，3）上运输4 次、6 次、5 次、3 次；总运输成本为1409 元，相比单车型卡车运输分别节约11.2%、9.7%、6.2%。最优解收敛情况见图2。

4 结论

（1）针对露天矿卡车调度问题，采用整数规划方法，建立了以最小运输成本为目标的卡车调度模型，实现了卡车运输费用最小化。该模型考虑了卡车多车型调度问题，与传统单车型卡车调度模型相比，多车型卡车配合调度减少了因非满载而造成的资源浪费，节约运输费用，同时也更加贴近矿山生产实际。

（2）提出了1种全新的染色体二次编码和解码方法，一定程度上减小了染色体编码的复杂度，对于求解大规模问题，可有效降低计算时间和对电脑内存的要求。最后，通过仿真计算实现了多车型露天矿卡车调度问题的求解，结果表明，本研究选用的算法及遗传操作策略对于多车型露天矿卡车调度问题的求解具有良好的适应性。