遗传算法在水泥矿山卡车运输调度系统中的应用

摘要

根据露天矿山运输调度系统的复杂性与非线性特性，建立了实时运输调度系统模型；运用遗传进化算法中的选择、交叉、变异、插入、迁移算子的寻优迭代计算，成功地解决了在开采工艺、产量、质量等多因素约束条件下的实时运输调度优化问题。并将其用于韶峰水泥原料矿山的生产运输调度系统，既降低了矿山运输成本，又协调了开采工艺、质量、产量之间的关系，取得了较好的效果。同时为矿山企业信息化建设和其他物流企业提供了重要的参考价值。

正文

《1 引言》

1 引言

水泥原料矿山是一个以采掘为中心, 以运输为纽带的大型生产系统。生产过程的组织、实施是通过采装、运输、破碎设备, 尤其是对运输设备的实时调配来完成的。车流调度是否合理, 将直接影响整个生产系统的生产效率和经济效益。卡车运输调度系统是一个涉及产量、质量、设备利用率及资源问题的多目标系统, 生产过程优化实际上是一个多目标优化问题, 因而需考虑到在市场需求、开采工艺、矿石质量、设备能力等约束条件下的卡车运输优化调度问题, 要用多目标规划求解。文献[1,2,3]提出了运用遗传算法求解多目标问题的新思路, 对卡车调度系统具有一定的参考价值。根据矿山开采规则及水泥原料矿石质量指标要求, 铲装设备的合理布局成为加大开采与生产, 节省生产成本的一个重要手段, 因为它既能牵制车辆, 又能实施均化生产。文献[4,5,6,7]论述了在质量约束条件下的矿石运输调度系统问题, 并取得了较好的效果, 但没有很好解决其在线优化问题, 文献[8,9,10,11,12,13]论述了用遗传算法解决了物流与运输调度的优化问题, 在此基础上, 采用并行遗传算法解决在资源约束条件下的运输优化调度问题, 进一步得到较好的在线运输调度控制效果。矿石品位在空间上分布不均匀, 勘探获得的矿石品位分布规律与矿石品位的实际分布规律仍有较大的差别, 因而在生产过程中利用勘探品位实施搭配的质量控制方案难以达到预期目的。为此, 在考虑生产调度成本最小化的同时, 还应从长远的观点出发, 对资源的科学规划、合理利用及环境、安全等提出综合考虑的要求。

《2 水泥原料矿山卡车运输调度系统建模》

2 水泥原料矿山卡车运输调度系统建模

《2.1卡车运输调度系统的现场参数设置》

2.1卡车运输调度系统的现场参数设置

现以湖南韶峰集团水泥原料矿山为例, 建立露天矿山卡车运输调度系统模型。该矿山自开采到现在, 已经形成了汽车运输开拓系统和汽车箕斗车联合开拓系统。矿山采用自上而下水平分台阶开采, 段高为15 m, 工作面平行走向布置, 垂直走向推进。根据水泥市场信息需求及公司生产能力, 经预测需生产碎石1.95 Mt, 本着矿山近期、中期、长期开采规划及矿山生产经济效益最大化原则, 为控制合理的平台下降速度, 实现均化开采, 改善矿山开采局面, 必须加强采准剥离工作, 加快向1 290 m以上水平的推进;以230 m平台为主要生产平台, 260 m平台、245 m平台为辅助生产平台, 275 m以上平台为调节生产平台, 均衡出矿;实施优化生产调度, 搞好矿产资源的综合利用, 合理搭配高低品位料, 保持矿量平衡;为进一步规范生产工艺管理, 其生产调度运输系统参数设置如下:

铲装点:290 m, 275 m, 260 m, 245 m, 230 m, 215 m平台等6个出矿点, n=6;

破碎站:一破碎站为湿法水泥线服务, 另一破碎站为干法水泥线服务, 合计为m=2。

6大铲装矿点到2大破碎站的运输距离:d_i1=[4.5 4.0 3.5 3.0 2.5 2.0]^T (km) , d_i2=[4.3 3.8 3.0 2.5 2.1 1.5]^T (km) ;

铲装点到破碎站的重车费用向量为c′_i1=[0.22 0.21 0.20 0.18 0.17 0.15]^T (元/t·km) ,

c′_i2=[0.21 0.20 0.19 0.17 0.16 0.13]^T (元/t·km) ;

铲装点到破碎站的空车费用向量为c″_i1=[0.115 0.101 0.096 1 0.091 2 0.089 9 0.087 9]^T (元/t·km) ;c_i2=[0.113 0.099 9 0.095 1 0.090 2 0.087 9 0.085 9]^T (元/t·km) ;

各平台铲装点的CaCO₃品位分别Ca=[53.07 53.05 52.66 52.33 52.16 51.95]^T (%) , 公司控制指标为Ca = 52.00%;

MgO品位分别为Mg=[1.27 1.27 1.30 1.32 1.34 1.35]^T (%) , 控制指标为Mg=1.20%。

为满足水泥市场生产需求, 经测算月生产需求量碎石量Q_gravel为17.5×10⁴ t, 为保证留有足够的爆落矿石储备量为铲破生产服务, 则各平台既要保持的足够的可采矿量, 又要保证一定的爆落储备矿量, 且爆落矿量必须大于生产需求量, 才能维持生产的均衡与流畅。根据该矿山生产实际, 设装载点爆落矿石总量Q_block每月约为20.5×10⁴ t, 各平台必须保持的可采矿量为80×10⁴ t。根据矿山近期、中期、长期规划, 每月各平台爆落矿量波动范围为q=[3.5～4.5 2.0～3.0 2.5～3.5 2.0～3.0 4.5～5.5 2.0～3.0]^T (×10⁴ t) 。

《2.2卡车运输调度系统建模》

2.2卡车运输调度系统建模

确定在满足卸载点需要的前提下使总费用最小。其数学模型如下:

设平台i (i=1, 2, …, n) , n=6, 送往破碎站j (j=1, …, m) , m=2的矿石量矩阵为

$(x_{i j}) = X = [\begin{array}{l} x_{11} x_{12} \\ x_{21} x_{22} \\ x_{31} x_{32} \\ x_{41} x_{42} \\ x_{51} x_{52} \\ x_{61} x_{62} \end{array}]; (1)$ $(x_{i j}) = X = [\begin{array}{l} x_{11} x_{12} \\ x_{21} x_{22} \\ x_{31} x_{32} \\ x_{41} x_{42} \\ x_{51} x_{52} \\ x_{61} x_{62} \end{array}]; (1)$

假设车况相同, 即各车从破碎站到各平台的空车费用与重车费用消耗基本一致。则卡车调度系统费用最小的主函数为

$\min f (X) = \min \sum_{i = 1}^{n} \sum_{j = 1}^{m} a_{i j} x_{i j}, n = 6, m = 2 (2)$ $\min f (X) = \min \sum_{i = 1}^{n} \sum_{j = 1}^{m} a_{i j} x_{i j}, n = 6, m = 2 (2)$

a_ij=c_ijd_ij, (a₁₁=c₁₁d₁₁, a₂₁=c₂₁d₂₁, …, a₆₁=c₆₁d₆₁, a₁₂=c₁₂d₁₂, a₂₂=c₂₂d₂₂, …, a₆₂=c₆₂d₆₂)

c= (c_ij) =c′+c″= (c′_ij) + (c″_ij)

其中c_ij代表铲破间距的重车费用c′ (元/t·km) 与空车费用c″ (元/t·km) 之和, d_ij代表铲破间距离的运输距离, a_ij代表铲破间距离的运输费用 (元/t·km) ;

根据开采条件、产量条件、质量条件, 其约束方程为

$\begin{array}{l} g_{1} (X) = (\sum_{i = 1}^{6} x_{i 1} C a_{i} / \sum_{i = 1}^{6} x_{i 1}) - C a \geq 0 (3) \\ g_{2} (X) = (\sum_{i = 1}^{6} x_{i 2} C a_{i} / \sum_{i = 1}^{6} x_{i 2}) - C a \geq 0 (4) \\ g_{3} (X) = Μ g - (\sum_{i = 1}^{6} x_{i 1} Μ g_{i} / \sum_{i = 1}^{6} x_{i 1}) \geq 0 (5) \\ g_{4} (X) = Μ g - (\sum_{i = 1}^{6} x_{i 2} Μ g_{i} / \sum_{i = 1}^{6} x_{i 2}) \geq 0 (6) \\ g_{5} (X) = \sum_{j = 1}^{2} \sum_{i = 1}^{6} x_{i j} - Q_{g r a v e l} \geq 0 (7) \\ g_{6} (X) = Q_{b l o c k} - \sum_{j = 1}^{2} \sum_{i = 1}^{6} x_{i j} \geq 0 (8) \end{array}$ $\begin{array}{l} g_{1} (X) = (\sum_{i = 1}^{6} x_{i 1} C a_{i} / \sum_{i = 1}^{6} x_{i 1}) - C a \geq 0 (3) \\ g_{2} (X) = (\sum_{i = 1}^{6} x_{i 2} C a_{i} / \sum_{i = 1}^{6} x_{i 2}) - C a \geq 0 (4) \\ g_{3} (X) = Μ g - (\sum_{i = 1}^{6} x_{i 1} Μ g_{i} / \sum_{i = 1}^{6} x_{i 1}) \geq 0 (5) \\ g_{4} (X) = Μ g - (\sum_{i = 1}^{6} x_{i 2} Μ g_{i} / \sum_{i = 1}^{6} x_{i 2}) \geq 0 (6) \\ g_{5} (X) = \sum_{j = 1}^{2} \sum_{i = 1}^{6} x_{i j} - Q_{g r a v e l} \geq 0 (7) \\ g_{6} (X) = Q_{b l o c k} - \sum_{j = 1}^{2} \sum_{i = 1}^{6} x_{i j} \geq 0 (8) \end{array}$

《3 矿山运输调度系统 (TSS) 的智能优化设计与实现》

3 矿山运输调度系统 (TSS) 的智能优化设计与实现

《3.1遗传进化算法的实施步骤》

3.1遗传进化算法的实施步骤

复杂非线性系统建模因涉及的参数较多, 需对其进行全局求解。经典的优化算法易陷入局部最优点, 难以解决其全局优化问题。遗传进化算法根据生物进化原理, 基于群体寻优策略, 经过选择、交叉、变异、插入、迁移算子的迭代计算, 可求得最优解。由于目前采用的进化计算工具箱 (geatbx) 与遗传算法工具箱 (gaot) 中各有相应的遗传进化操作算子程序文件, 可根据各自的优点将其融合组装成新的工具箱, 装载入MATLAB平台中。并借助于MATLAB平台调用其工具箱中相应的程序文件, 来解决符合卡车调度系统的实时优化与实现问题。即根据运输调度系统模型中的参变量的历史数据设置相应的参数范围, 并借助遗传进化算法中实数编码方案进行随机编码, 经过选择、交叉、变异、插入、迁移算子的迭代计算求解。遗传进化算法求解步骤如下。

Step 1 建立调度系统模型主目标函数

ObjVal = f (Chrom) ;

Step 2 采用实数编码, 划分子代种群与子代数目, 生成初始种群

Chrom = crtrp (SUBPOP*NIND, FieldDR) ;

Step 3 设计适应度函数

fitness = objVal = f (Chrom) ;

Step 4 进行选择、交叉、变异, 优化种群个体

//从种群中选择个体

SelCh = select (SEL_-F, Chrom, FitnV, GGAP, SUBPOP) ;

//重新组合选择的个体

SelCh=recombin (XOV_-F, SelCh, XOVR, SUBPOP) ;

//变异

SelCh = mutate (MUT_-F, SelCh, FieldDR, [MUTR], SUBPOP) ;

Step 5 引入插入策略和迁移策略, 进行迭代计算, 求出最优解

//插入个体

[Chrom, ObjVal] = reins (Chrom, SelCh, SUBPOP, [1 INSR], ObjV, ObjVOff) ;

//迁移个体

[Chrom, ObjVal] = migrate (Chrom, SUBPOP, [MIGR, 1, 0], ObjV) 。

《3.2基于遗传进化算法的卡车运输调度系统的优化实现》

3.2基于遗传进化算法的卡车运输调度系统的优化实现

根据卡车运输调度系统费用最小目标主函数和约束条件方程构造惩罚函数, 选择惩罚因子, 介入遗传进化算法的选择机制, 确定其适应度函数, 化有约束为无约束方程, 即可确定其适应度函数方程为

$\begin{array}{l} Ο b j V a l = F (X) = \\ f (X) + {\begin{matrix} 0 & 若 X 可行 ‚ \\ \sum_{i = 1}^{6} r_{i} \cdot g_{i} (X) & 其他 \end{matrix} (9) \end{array}$ $\begin{array}{l} Ο b j V a l = F (X) = \\ f (X) + {\begin{matrix} 0 & 若 X 可行 ‚ \\ \sum_{i = 1}^{6} r_{i} \cdot g_{i} (X) & 其他 \end{matrix} (9) \end{array}$

式中

${\begin{matrix} 0 & 若 X 可行 ‚ \\ \sum_{i = 1}^{6} r_{i} \cdot g_{i} (X) & 其他 \end{matrix}$ ${\begin{matrix} 0 & 若 X 可行 ‚ \\ \sum_{i = 1}^{6} r_{i} \cdot g_{i} (X) & 其他 \end{matrix}$

为惩罚项, r_i (i = 1, 2, …, 6) 为惩罚系数。

利用并行遗传算法 (PGA) 的原理, 对参数变量实施实数编码, 选择合理的遗传操作算子、种群数及子种群的个体数和合适的插入率和迁移率, 经过多次迭代计算可求解最优解。

其算法操作参数设置如下:代间隔 (即每代产生多少个新个体) GGAP = 0.8, 插入率 (即插入多少个子代) INSR = 0.9, 交叉率XOVR = 1, 选择压力SP = 2, 变异率MUTR = 0.01, 子代之间的迁移率MIGR = 0.2, 迁移的子代数目MIGGEN = 20, 惩罚系数r_i (i = 1, 2, …, 6) = [-0.3, -0.8, -0.1, -0.9, -0.1, -0.8]。

经过群体迭代求解, 运行100次后, 其铲装点与破碎点的运输生产量及其总体运输成本费用趋于最优解 (分别见图1、图2、图3) 。程序最后运行结果得出最佳卡车运输调度方案, 卡车最优运输调度生产向量为

$(x_{i j}) = X = [\begin{array}{l} 1.400 0 2.100 0 \\ 0.800 0 1.200 0 \\ 1.000 0 1.500 0 \\ 0.800 0 1.200 0 \\ 1.800 0 2.700 0 \\ 0.800 0 1.200 0 \end{array}] (\times 10^{4} t) ‚$ $(x_{i j}) = X = [\begin{array}{l} 1.400 0 2.100 0 \\ 0.800 0 1.200 0 \\ 1.000 0 1.500 0 \\ 0.800 0 1.200 0 \\ 1.800 0 2.700 0 \\ 0.800 0 1.200 0 \end{array}] (\times 10^{4} t) ‚$

此时卡车运输调度系统最小成本费用为ObjV = 11.349 5元/t·km。

《4 结语》

4 结语

通过把并行遗传算法理论引入到矿山运输调度系统中, 解决了诸如产量约束、质量约束、设备约束条件下的运输调度系统的在线优化问题, 为降低矿山运输成本, 提高经济效益具重要的指导作用, 同时为其他物流运输企业实现企业效益最大化提供了重要的参考价值。

《图1》

图1 铲装点至破碎站1的最优运输产量图

Fig.1 Chart of optimal production from each shoveling station to first crashing station

《图2》

图2 铲装点至破碎站2的最优运输产量图

Fig.2 Chart of optimal production from each shoveling station to second crashing station

《图3》

图3 运输调度系统的适应度 (成本费用) 选择图

Fig.3 Chart of fitness selecting (cost) review

展示更多