一种新的用于编制露天矿生产计划开采模型

黄俊歆^{1, 2}，郭小先³，王李管¹，谭正华¹，毕林¹，李德⁴，陈建宏¹

(1. 中南大学 资源与安全工程学院，湖南 长沙，410083；

2. 湖南工学院 安全与环境工程系，湖南 衡阳，421001；

3. 西部矿业股份有限公司，青海 西宁，810001；

4. 玉溪矿业有限公司，云南 玉溪，653100)

摘要：用混合整数规划法求解露天矿生产计划编制问题(OMPSP)，其算法的时间复杂度为指数阶。提出一种基于成本流的露天矿开采锥模型(CFCM)。采用图论的方法将矿床块段模型抽象为节点的集合，用有向边表示成本流，将所有正价值节点与其开采锥内负价值节点相连形成初始CFCM。研究采用线性规划的方法对成本流进行合理分配而形成最终CFCM的方法，并应用于实际露天矿山的计划编制工程中。研究结果表明：CFCM能极大地减少用混合整数规划法求解OMPSP时的整数变量个数，适应于复杂的实际OMPSP，其计算结果与工程实际结果较吻合，为解决实际OMPSP提供了一种新的有效方法。

关键词：露天矿；块段模型；生产计划编制；线性规划；混合整数规划

中图分类号：TD 804         文献标志码：A         文章编号：1672-7207(2011)09-2819-06

A novel mining model for open-pit mine production scheduling

HUANG Jun-xin^{1, 2}, GUO Xiao-xian³, WANG Li-guan¹, TAN Zheng-hua¹,

 BI Lin¹, LI De⁴, CHEN Jian-hong¹

(1. School of Resources and Safety Engineering, Central South University, Changsha 410083, China;

2. Department of Safety and Environment Engineering, Hunan Institute of Technology, Hengyang 421001, China;

3. Western Mining Co. Ltd., Xining 810001, China;

4. Yuxi Mining Company, Yuxi 653100, China)

Abstract: The complexity of mixed integer programming method for solving open-pit mine production scheduling problems (OMPSP) was exponential complexity. The cost-flow based mining cone model (CFCM) was presented. The deposit block model was abstracted into the node collection by the method of graphic theory. Cost-flows were used to connect each positive-value node with the negative-value nodes in its excavation cone to form the initial CFCM, and the cost-flows were denoted by directed edges. Furthermore, the linear programming method which distributes the cost-flows to form the final CFCM was introduced. The algorithm based on CFCM was applied in an actual OMPSP. The results show that CFCM can greatly reduce the number of integral variables using mixed integer programming method to solve OMPSP, and it is adopted to all OMPSP in any complex geological conditions, calculation speed and accuracy. The algorithm based on CFCM provides a new and effective method for the actual OMPSP.

Key words: open-pit mine; block model; production scheduling; linear programming; mixed integer programming (MIP)

编制露天矿采掘进度计划的总目标是确定一个技术上可行且能够使总体经济效益最大化的矿岩采剥顺序。矿床开采的总体经济效益最大是指从动态经济观点出发，使矿床开采中实现的总净现值最大；技术上可行是指采掘进度计划必须满足一系列技术上的约束条件，主要包括：(1) 在每一个计划期内为选厂提供较为稳定的矿石量和入选品位；(2) 每一计划期的矿岩开采量应与可利用的采剥设备的生产能力相适应；(3) 各台阶水平的推进必须满足正常生产要求的时空发展关系，即最小工作平盘宽度、安全平台宽度、工作台阶的超前关系、采场延深与台阶水平推进的速度关系等^[1]。目前，国内编制露天矿采掘进度计划普遍采用手工方法，即使借助计算机，现在已有的辅助设计软件都只是提供模拟手工操作的方法，无法准确考虑上述技术约束条件，导致编制出来的露天矿采掘计划难以指导生产。国外发达国家通常利用计算机来解决露天矿生产计划编制问题(Open-pit mine production scheduling problems, OMPSP)。最初有研究者提出利用LG图论法^[2]或浮锥法^[3]通过调整价值模型分别进行计算，得出一系列嵌套分期境界作为各计划期的期末图，但这种方法无法满足采掘进度计划的技术约束条件，而且试算法调整价值模型的工作量非常大。随后又相继产生heuristics算法^[4]、Korobov算法^[5]、参数化算法^[6]、动态规划法^[7]、混合整数规划法^[8]，等等。其中：混合整数规划法能够充分考虑露天矿生产计划编制问题的一系列技术约束条件，该算法的时间复杂度为指数阶^[9]，因计算量太大，该方法仅在理论上可行，无法解决实际的大规模OMPSP。Natashia等^[10]针对OMPSP从优化线性规划问题求解算法的角度进行研究，有效地降低了其时间复杂度，但该方法实现难度非常大。在此，本文作者提出一种基于成本流的开采锥模型(CFCM)。采用图论的方法将正价值块与其开采锥内相关负价值块聚合，减少了混合整数规划模型中的变量个数，降低了计算复杂度，从而使解决实际的大规模OMPSP变成可能。此外，通过工程实例验证了该模型的有效性及可行性。

1  露天矿生产计划编制流程

将矿床划分为有限个尺寸相等的长方体(包括开采的矿石和剥离的废石)，每个块体形成的离散模型称为矿床块段模型。采用矿体解译、地质资料分析等方法，通过估值使块段模型中每一块的净价值变为已知，估值后的块段模型称为价值块段模型。露天矿境界优化流程图见图1。

图1  露天生产计划编制流程图

Fig.1  Flow chart of open-pit mine production scheduling

块段净价值是根据块中所含可利用矿物的品位、经营成本及产品价格计算的。由于矿床所含矿物的多样性及矿山企业经营体制和成本管理制度的差异，计算净价值时用到的参数并不固定。其净价值计算方法见图2。其中：每个块体的值表示开采该块体的净利润，剥离的废石为负值，V_ore=V_o-C_om-C_ot-C_or-C_p-C_s；V_waste=-C_wm-C_wt-C_wr。

图2  矿床价值模型净价值计算方法

Fig.2  Calculate method of deposit block model

2  CFCM模型的构建

实际的露天矿矿床块段模型的块数通常在10⁶数量级以上。构建混合整数规划计算模型时，为了充分考虑露天矿生产计划约束条件，必须为每一个块建立一个整数变量(0表示不开采，1表示开采)。这样一个大型的混合整数规划问题，对现有的计算机软、硬件技术来说是无法实现的。

2.1  基本原理

为便于叙述CFCM模型的基本原理，采用图3所示的简单二维块段模型进行阐述，以块段的中心点表示该块段(以下称节点)。

在满足工作帮坡角几何约束条件的前提下，只考虑开采矿床块段模型中某一正价值节点，该节点记为N_i，其净价值记为V_i，其上方所有必须先开采的负价值节点的净价值代数和即为开采正价值节点N_i所须承担的成本。节点N_i与其上方所有必须先开采的节点形成1个倒圆锥，称为正价值节点N_i的开采锥，记为C_i；开采锥C_i的顶点为N_i，正价值节点N_i与其开采锥内某负价值节点N_j之间以有向边相连，该有向边表示节点N_i与节点N_j之间的成本流，记为f_ij；该开采锥顶点N_i与锥内所有负价值节点的价值代数和称为开采锥的锥价值，记为V_ci。矿床块段模型中的所有正价值节点都与其开采锥内的负价值节点以有向边相连，在其底部加一源节点，记为S；在其顶部加一汇点，记为T。形成的有向图称为初始CFCM，如图3所示。

这样，矿床块段模型中每一正价值节点都与其上所有可能对其构成成本负担的负价值块以成本流连接，但节点作为模型中的最小单元，每一个负价值节点只可能对1个正价值节点构成成本负担。以此作为理论基础，采用线性规划方法对初始CFCM进行成本最优分配。构建混合整数规划计算模型时，其整数变量个数也从原来的矿床块段模型节点总数减少为其正价值节点数，极大地减少了整数变量个数，降低了计算复杂度。

2.1.1  构建线性规划模型目标函数

对于一个给定的矿床块段模型，在其最终开采境界内的所有负价值节点的价值代数总和为定值，即总开采成本为定值，则其成本流之和也为一定值，即∑f_ij为定值。

为力求早投产、快达产、缩短基建期、减少基建投资，应从最先能开采到正价值块处开始开采，从而达到尽快回收成本的目的。这样，就应该使成本流尽量地流向价值更大的开采锥。依据该原则构建如图3所示的线性规划模型。

图3  二维块段模型及初始CFCM模型

Fig.3  2D block model and initial CFCM model

图3所示为简单二维块段模型的CFCM模型初始图，为便于阐述，令工作帮坡角为45°。构建模型的具体步骤如下。

(1) 计算所有正价值块的C_V，C_Vr0c2=4-1-1-1- 2-2=-3，C_Vr1c3=5-2-2=1，C_Vr1c4=6-2-2-2=0、C_Vr1c5= 8-2-2-2=2。

(2) 为每个正价值节点按其C_V分配1个权值系数，记为C_e。将所有节点按其在块段模型中的层号从大到小排序(坐标系统如图4所示)，层号相同的按其C_V从大到小排序，权值系数C_e则按排好序的节点。其C_e则按该顺序从小到大分配，下一层的各正价值块的C_e则从上一层最大C_e开始分配。

(3) 构建目标函数。该线性规划模型的目标是使成本流尽量地流向价值更大的开采锥，因此，取上述分配了权值系数的表达式的最小值作为线性规划模型的目标函数，即

min{f_{N(r1,c5)N(r2,c4)}+f_{N(r1,c5)N(r2,c5)}+f_{N(r1,c5)N(r2,c6)}+

2[f_{N(r1,c3)N(r2,c3)}+f_{N(r1,c3)N(r2,c4)}]+3[f_{N(r1,c6)N(r2,c3)}+

f_{N(r1,c6)N(r2,c4)}+f_{N(r1,c6)N(r2,c5)}]+4[f_{N(r0,c2)N(r1,c1)}+f_{N(r0,c2)N(r1,c2)}+

f_{N(r0,c2)N(r2,c0)}+f_{N(r0,c2)N(r2,c3)}+f_{N(r0,c2)N(r2,c4)}]}

注：f_{N(r1,c5)N(r2,c5)}表示节点N(r1,c5)流向节点N(r2,c5)的成本流，其他项类同。

2.1.2  构建线性规划模型约束条件

由于成本流是从源点流出，流向汇点，根据图的性质，有：

(1) 中间任意节点流入的与流出的成本流代数和为0；对于正价值节点N_i，有：；对于负价值节点N_j，有：。

(2) 从源点流向正价值节点的成本流不大于该节点的价值，即：f_Si≤V_i；

(3) 从负价值节点流入汇点的成本流等于该节点的价值，即：。

其中：S表示源点；T表示汇点；i表示正价值节点；j表示负价值节点；n_i表示从正价值节点N_i引出的有向边条数；p_i表示指向负价值节点N_j的有向边条数。

因此，对于图3所示的简单块段模型，其线性规划模型约束条件如下：

f_SN(r0,c2)≤4；f_SN(r1,c3)≤5；f_SN(r1,c4)≤6；f_SN(r1,c5)≤4；f_N(r1,c1)T=1；f_N(r1,c2)T=1；f_N(r2,c0)T=1；f_N(r2,c3)T=2；f_N(r2,c4)T=2；f_N(r2,c5)T=2；f_N(r2,c6)T=2；

f _SN(r0,c2)–f _{N(r0,c2)N(r1,c1)}–f _{N(r0,c2)N(r1,c2)}–f _{N(r0,c2)N(r1,c3)} –

f _{N(r0,c2)N(r2,c0)} –f _{N(r0,c2)N(r2,c3)}–f _{N(r0,c2)N(r2,c4)}=0；

f _SN(r1,c3)–f _{N(r1,c3)N(r2,c3)}–f _{N(r1,c3)N(r2,c4)}=0；

f _SN(r1,c4)–f _{N(r1,c4)N(r2,c3)}–f _{N(r1,c4)N(r2,c4)}–f _{N(r1,c4)N(r2,c5)}=0；

f _SN(r1,c5)–f _{N(r1,c5)N(r2,c4)}–f _{N(r1,c5)N(r2,c5)}–f _{N(r1,c5)N(r2,c6)}=0。

2.2  算法描述

建立图4所示的坐标系统，XYZ坐标系为世界坐标系，其值为块段的真实坐标值；ijk坐标系为相对坐标系，其值为块段在矿床块段模型中的序号。

2.2.1  CFCM构建算法

第1步：形成初始图。遍历所有节点，当前节点记为N_i，若节点N_i为正价值节点，将节点N_i与其开采锥内所有负价值节点以有向边相连，正价值节点N_i与负价值节点N_j间的有向边记为f_ij。同时，将N_i存入正价值节点数组中。

图4  三维块段模型坐标系统

Fig.4  Coordinate system of 3D block model

第2步：计算锥价值。遍历所有正价值节点，当前节点记为N_i，节点N_i及所有与它以有向边相连的负价值节点的价值代数和即为节点N_i的锥价值。

第3步：赋权系数。将正价值节点数组中所有节点按其在块段模型中的层号从大到小排序，层号相同时按节点的锥价值从大到小排序。在排序后的数组中，第1个节点权系数C_e1为1，第2个节点权系数C_e2为2，依此类推，第n个节点权系数C_en为n。

第4步：建立线性规划模型。

第5步：求解线性规划问题，遍历结果中所有成本流，当前成本流记为f_ij。若f_ij为0，则将节点N_i与节点N_j之间的有向边删除。删除所有为0的成本流后形成新的CFCM，执行第2步；若无结果为0的成本流，则程序结束，得到最终CFCM。

2.2.2  线性规划模型算法的建立

第1步：构建目标函数。遍历所有正价值节点，共有m个正价值节点，当前节点记为N_i；其权系数为C_ei；N_i引出的成本流有n条，记为f₁~f_n。则目标函数为：。

第2步：构建约束条件。

(1) 遍历所有从源点S流出的成本流，共有x条，当前成本流记为f_Si，流向正价值节点N_i，N_i的价值为V_i。据此可以构建出x个约束条件：f_Si≤V_i；1≤i≤x

(2) 遍历所有流入汇点T的成本流，共有y条，当前成本流记为f_jT，从负价值点N_j流出，N_j的价值为V_j。据此可以构建出y个约束条件：f_Si=|V_j|；1≤j≤y

(3) 遍历所有正价值节点，共有z个正价值节点，当前节点记为N_i，流入该节点的成本流有u条，记为f_iI1~f_iIu；从该节点流出的成本流有v条，记为f_iO1~f_iOv；据此可以构建出z个约束条件：；1≤i≤z。

3  实例应用

3.1  三维地质模型的创建

基于CFCM的算法已用于DIMINE数字矿山系统中。以云南某矿为研究对象，用DIMINE创建了该矿的空间地质数据库、数字地形模型(Digital Terrain Model，DTM)^[9-11]、矿体模型、矿床品位块段模型，见图5，这些资料是该矿露天矿生产计划编制工作的基础。

图5  DTM、钻孔空间位置及主要矿体分布

Fig.5  DTM and drill spatial location and main orebodies distribution

矿体呈北西向北东呈波状缓倾斜，倾角为10°~ 25°，局部大于35°。地面标高1.21 km，矿体总体长2.00 km，宽100~670 m，埋深从地表到280 m标高，矿体厚度为2~50 m，平均品位约0.4%。矿体形态较复杂，呈多个不规则的透镜体或构造块体。同一矿体厚度与品位变化较大。

本次建立地质数据库包含钻孔486个，测斜数据2 246条，所有钻孔、槽探和坑探取样38 411个。矿床主要有Ⅰ号、Ⅱ号、Ⅲ号3个矿体，其中Ⅱ和Ⅲ号矿体储量大，为该矿区的主要矿体，块段模型创建中选择单元块长×宽×高为10 m×20 m×4 m。矿体分布情况及最终设计境界见图6。

图6  矿体分布情况及最终设计境界(即范围)

Fig.6  Ore bodies distribution and its final designed limit

3.2  露天矿生产计划编制参数选择

3.2.1  经济参数的选取

此次优化的参数主要来源于地质报告、选矿实验指标和根据目前开采技术条件下通过工程类比法选取出相关指标，本例以云南某露天矿的3 a采剥计划编制为例。其主要优化参数见表1。

3.2.2  优化参数的选取

在计划编制过程中，按照矿山的选厂处理能力等实际情况，确定6 000 t/d方案各年采矿量为：第1年75万t，第2年150万t，第3年以后按照198万t进行编排，直至减产结束。矿量容差为5%，各年品位及剥采比约束如表2所示。

3.3  结果分析

将上述参数输入DIMINE软件露天矿生产计划编制模块中。矿床块段模型XYZ 3个方向的块数为89×55×93，共455 235块；但其中正价值块数仅为75 315块。利用CFCM构建计算模型，采用混合整数规划法进行露天矿生产计划编制，其整数变量数从455 235个减少到75 315个，极大地减少了计算量。

表1  优化参数表

Table 1  Optimal parameters table

表2  优化参数表

Table 2  Optimal parameters table

经计算，得到各年度采剥块段集合。在该结果数据为指导的基础上进行生产计划设计，其设计结果见图7，采剥量见表3。

图7  露天矿生产计划设计结果

Fig.7  Design results of open pit mine production scheduling

表3  各年度采剥量

Table 3  Stripping quantity for each year

4  结论

(1) 针对采用混合整数规划法求解OMPSP时的高复杂度，提出了一种新的露天矿开采锥模型即CFCM。CFCM能够极大地减少采用混合整数规划法求解OMPSP时的整数变量个数，为解决OMPSP提供了一种新的有效方法。

(2) CFCM的不足之处在于其依赖于规则三维块段模型，块段的细分程度及各个方向的尺寸对工作帮坡角的精度影响很大。然而，混合整数规划算法为指数复杂度，块段划分过细将会导致计算量过大。如何构建一种不规则块段模型，通过调整不同台阶、不同工作地点的块段尺寸、形状、细分程度来更精确地模拟工作帮坡角、开采条带等，是未来露天矿开采锥模型构建技术的难点与发展方向。

参考文献：

[1] 王青. 采矿学[M]. 北京: 冶金工业出版社, 2007: 344-394.
WANG Qin. Mining science[M]. Beijing: Metallurgy Industry Press, 2007: 344-394.

[2] Lerchs H, Grossmann I F. Optimum design of open pit mines[J]. CIM Bull, 1965, 58(633): 47-54.

[3] Lemieux M. Moving cone optimizing algorithm[C]//Computer methods for the 80s in the Mineral Industry. New York, 1979: 329-345.

[4] Gershon M. Heuristic approaches for mine planning and production scheduling[J]. International Journal of Mining and Geological Engineering, 1987, 5(1): 1-13.

[5] Yegulalp T M, Arias J A. A fast algorithm to solve the ultimate pit limit problem[C]//Proc of 23rd Symposium on the Application of Computers and Operations Research in the Mineral Industries (APCOM). Colorado, 1992: 391-397.

[6] Dowd P A, Onur A H. Open-pit optimization. part 1: Optimal open-pit design[J]. International Journal of Rock Mechanics and Mining Sciences & Geomechanics Abstracts, 1994, 31(1): 95-104.

[7] Wilke F L, Wright E A. Determining the optimal ultimate pit design for hard rock open pit mines using dynamic programming[J]. Erzmetall, 1984, 37(3): 139-144.

[8] Caccetta L, Hill S P. An application of branch and cut to open pit mine scheduling[J]. Journal of Global Optimization, 2003, 27(2/3): 349-365.

[9] Natashia B, Irina D, Gary F, et al. LP-based disaggregation approaches to solving the open pit mining production scheduling problem with block processing selectivity[J]. Computers & Operations Research, 2007, 36(4): 1064-1089.

[10] 庞碧君. 线性规划与随机规划[M]. 郑州: 郑州大学出版社, 2009: 1-16.
PANG Bi-jun. Linear programming and stochastic programming[M]. Zhengzhou: Zhengzhou University Press, 2009: 1-16.

[11] 周智勇, 陈建宏, 杨立兵. 大型矿山地矿工程三维可视化模型的构建[J]. 中南大学学报: 自然科学版, 2008, 39(3): 423-428.
ZHOU Zhi-yong, CHEN Jian-hong, YANG Li-bing. 3D visualization modeling on geological and mining engineering in a large-sized mine[J]. Journal of Central South University: Science and Technology, 2008, 39(3): 423-428.

(编辑 陈灿华)

收稿日期：2010-09-13；修回日期：2010-12-19

基金项目：国家自然科学基金资助项目(50774092)

通信作者：黄俊歆(1982-)，男，湖南衡阳人，博士研究生，从事安全预警、采矿仿真及可视化技术研究；电话：0734-6666858；E-mail: amwwcwujqw@126.com