文章编号：1004-0609(2016)-01-0173-07

基于混合整数规划法的采场回采顺序优化分析

王李管^{1, 2}，任助理^{1, 2}，潘传鹏^{1, 2}，陈  鑫^{1, 2}

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

2. 中南大学 数字矿山研究中心，长沙 410083)

摘  要：针对地下矿山传统编制生产计划时存在的随意性大、效率低、不能编制出最优生产计划的弊端，提出运用混合整数规划法解决采场回采顺序优化问题的方法。对无底柱分段崩落法的采场回采顺序进行科学系统的分析，以计划周期内贴现值最大化为目标函数，综合考虑逻辑、设备数量、空间顺序等约束条件，构建采场回采顺序优化的混合整数规划模型；在MATLAB环境下采用YALMIP编写模型语言并调用CPLEX求解器进行求解，进而得到采场回采顺序的最优布置方案。结果表明：此方法科学可行，克服传统手工方法编制生产计划的弊端，实现资源合理高效开采，对指导矿山的实际生产有重要的意义。

关键词：无底柱分段崩落法；采场回采顺序；混合整数规划；生产计划

中图分类号：TD853　　     文献标志码：A

安全高效的生产是矿山企业生存需要解决的重大难题。为使企业生产经营合理运行，矿山管理者必须从多个角度对企业运行做出合理的规划安排，其中编制生产计划是核心决策任务。采场是地下矿山生产的最基本单元，大部分采矿方法涉及到的生产工序活动(如中深孔、出矿、充填等)都以采场为单元体进行承载，因此，确定采场回采顺序是地下矿山生产计划编制的前提。

采场回采顺序的确定是一个复杂的过程，自20世纪60年代初人们主要从现代数学和计算机模拟技术两个方向对其进行研究^[1]，RIBEIRO^[2]运用动态规划优化无底柱分段崩落法矿山回采顺序，贾明涛^[3]基于计算机过程模拟技术和排队论优化冬瓜山铜矿深井回采方案。近年来，人们又引入了人工智能、不确定决策等方法：周科平等^[4]运用遗传算法和数值分析法优化回采顺序，实现三山岛金矿矿体开采的稳定性；云庆夏等^[5]应用遗传算法确定采场开采时间；KUMRAL^[6]采用模拟退火算法解决澳大利亚西部铁矿的生产计划编制问题。采场回采顺序优化问题已引起众多学者的广泛关注，因此，有必要对其进行研究。

采场回采顺序传统上是以采场的矿石品位、矿石量为基础，依靠矿山工作者的经验进行确定，缺乏科学系统的定量分析，不能保证开采全局最优。混合整数规划理论的提出为确定采场回采顺序提供了一种很好的解决途径，目前在诸多国家以不同采矿方法开采矿山中得到了显著应用^[7]。REHMAN等^[8]用该法求解巴基斯坦某空场法石灰石矿的采场开采顺序，以最低生产成本实现矿量与质量稳定。YASHAR等^[9]和CARLYLE^[10]分别用该法解决了澳大利亚某自然崩落法矿山和美国Stillwater分段崩落法铂钯地下金属矿的采场回采顺序优化问题，实现净现值最大化。O’SULLIVAN^[11-12]对爱尔兰利希恩铅锌矿基于混合整数优化法的启发式方法，优化采场回采顺序，实现贴现值最大化。针对无底柱分段崩落法的矿山，MARTINEZ等^[13]根据瑞典基律纳铁矿的生产约束以实际开采量和需求量之间的偏差量最小为目标函数，实现了回采方案最优化。尽管，混合整数规划法在国外应用广泛，但国内矿山的回采单元划分类型、采场尺寸及生产约束条件与国外矿山差别较大，因此将这些模型直接应用于国内地下矿山，具有很大局限性。2007年以来，为解决混合整数规划模型求解速率慢、求解质量低的问题，学者们引入了最早开始、最迟开始算法^[14]、聚类分析^[15]、拉格朗日松弛法^[16]等，但这些算法对程序运行环境苛刻，对计算机软硬件要求较高，不具备普遍适用性。

针对上述问题，本文作者运用混合整数规划法，

选取目标函数及有关约束条件，构建适用于国内无底柱分段崩落法矿山的采场回采顺序优化模型，很适合解决以传统经验布置回采顺序不科学问题。因此，在矿山的生产实践中有着更大的适用空间和应用价值。

1  采场回采顺序优化的混合整数规划模型设计

1.1  混合整数规划理论

混合整数规划(MIP)是涉及到整数或离散变量的一类数学规划问题^[17]。作为优化理论的一个重要分支有普遍的实用价值，已渗透到工商企业管理、工程技术、科学研究、金融工程、语言学及社会科学等领域中，常见应用如对大规模生产的设计规划问题、设备的使用规划、设计流程问题等，这都属于MIP问题的范畴，模型的标准形式为

               (1)

式中：Z为最大或最小目标函数；x_j为决策变量；a_ij、b_i、c_j分别为所解决问题的相关系数；i、j、k为所解问题的变量索引；m、n为索引的取值范围。

1.2  混合整数规划模型构建

结合无底柱分段崩落法矿山的实际情况，运用上述理论依据，选择合适的目标函数、约束条件及决策变量建立数学模型来解决地下金属矿山生产计划中回采顺序优化问题。

设地下金属矿山有V个分段，划分为A个采场，在计划周期T内决定A个采场何时开始，则设其采场回采顺序优化的决策变量为

。

无底柱分段崩落法的特点是在矿体内一般以15 m×15 m的网度开掘回采巷道，并在其中打上向扇形深孔落矿，随着矿石放出，崩落的围岩充满采空区。为了保证整个回采过程的安全高效，必须考虑到空间的约束关系(见图1)：水平方向上限制采场b开采的采场a、c未开采时，采场b不可开采；垂直方向上限制采场d开采的采场b未完成50%时，采场d不可生产。

图1  采场空间约束关系

Fig. 1  Space constraints of stopes

由于各采场地质品位及开采条件的差异，根据矿山企业生产需求(品位偏差最小、金属量或贴现值最大)，选取计划周期内的贴现值最大为目标函数，综合考虑时间、设备数量、空间顺序等约束条件建立混合整数规划模型如下：

1) 贴现值反应了矿山投资风险的影响和假设企业再投资时资本回收的情况，能帮助矿山企业决策，因此，选择计划周期内贴现值最大为目标函数。该目标函数实现贴现值最大化的同时也能实现金属量最大。

           (2)

式中：A为采场a集合；T为月期t和t′集合；d_a为采场a持续生产时间，月；g_a为采场a地质品位；r为矿山的折现率，其取值区间一般为8%~10%；γ为设备生产能力，万t/月·台，y_at为决策变量。

2) 同分段生产设备数量约束，即同分段每个时期生产设备在采场进行回采作业时，其生产设备数不得超过矿山实际生产规定设备数，以使回采工作安全有效地顺利进行。

            (3)

式中：L_vt为分段v内t时期能同时生产的最多设备数；V为分段v集合；A_v为分段v内采场的集合。

3) 全矿生产设备数量约束，即矿山各个分段同时期进行生产的设备数量总和不超过矿山实际规定的设备数量。

                 (4)

式中：L_t为t时期能同时生产的最多设备数。

4) 保持采场回采稳定的水平空间约束，根据无底柱分段崩落法的回采特点，在每个时期水平方向上同分段限制采场a开采的采场a′未完成时，采场a不能开始生产。

       (5)

式中：A_al为限制a采场开采的水平方向上的采场a′集合。

5) 保持采场空间稳定的垂直约束，即垂直方向上分段限制采场a开采的采场a″未完成50%时，采场a不能开始生产。

    (6)

式中：A_av为限制a采场开采的垂直方向上的采场a″集合。

6) 为避免矿山设备频繁移动，考虑生产设备调度约束。对第一分段、第一二分段、第一二三分段，t时期生产采场数之和不大于t-1时期生产采场数之和。

(7)

7) 逻辑约束，a采场在计划月期内只能开采一次。

                          (8)

8) 限定决策变量为非负数，二元变量。

                      (9)

1.3  混合整数规划模型求解

目前混合整数规划模型求解常采用分支界定算法，这种方法灵活且便于计算机求解，它的基本思想分3个关键步骤：分支、定界和剪枝，算法实现的流程^[18]如下(见图2)。

Step 1(初始化)：取初始的超矩形集合M={H}，原问题的初始下界为μ=min{μ(H)}，上界为r←min{f(x):x∈Q}，Q表示原问题所有可行解的集合，找一个当前最优解x^r∈argminr，置k=1；

Step 2(终止规则)：若r=μ，则输出原问题的全局最优解；否则，转Step 2；

Step 3(选择规则)：在M中选择超矩形H^k，其中H^k是μ对应的超矩形，即μ=μ(H^k)，使M=M/H^k；

Step 4(部分规则)：沿着超矩形H^k的最长边进行二倍分剖分，所得到的子超矩形记为R，让M=M∪R；

Step 5(剪枝规则)：让M=M{H:μ(H)≥r，H∈M}；

Step 6(定界规则)：定上界r=min{f(x):x∈Q}，定

下界；

Step 7：置k=k+1，转Step 2。

图2  模型的算法流程

Fig. 2  Model of arithmetic flow

2  应用实例

2.1  矿山简况

河北某铁矿矿体全部埋藏在河床之下，矿区平均标高280 m左右，矿体埋深134 m至679 m，埋藏标高为+142 m~-463 m，属大中型矿床。该矿设计规模为年生产铁矿石180万t，采用竖井开拓，利用无底柱分段崩落法进行开采。

该矿2014年末的采矿现状为：采矿作业位于-140 m、-155 m两个分段，正在回采的采场有9个，备用采场2个，铁矿石217万t/a，原矿入选品位40.06%，回采率81.13%，贫化率16.05%。年生产铁精矿120万t，铁精矿品位66.50%，综合金属回收率92.11%。矿山采用6台TORO400E电动铲运机回采，5台生产，1台备用，设备生产能力3.0~3.1万t每月。

采场回采顺序的优化模型以该矿-140 m、-155 m、-170 m水平采场为对象，共计30个采场，编制3年(2015~2017)的中长期生产计划。

2.2  基础数据准备

根据现有矿山的数据，周期集合T=[1，2，3，…，35，36]；分段集合V=[1，2，3]；采场集合A=[1，2，3，…，29，30]，其中1~6元素表示-140 m分段中的6个采场，7~17元素表示-155 m分段中的11个采场，18~30元素表示-170 m分段中的13个采场，即分段

采场集合；设备生产能

力γ为3.1万t每月每台；分段v内t时期能同时生产的最多设备数为3台，即L_vt=3；全矿t时期能同时生产的最多设备数为5台，即L_t=5；采场开采与否的决策变量y_at为采场数为30、周期数为36的矩阵，

，其中x的取值分别为二元变量0和1。

根据该矿的地质资料，利用DIMINE三维矿业软件进行储量估算，采场地质品位=[0.4751, 0.4585, 0.4536, 0.3472, 0.4577, 0.3762, 0.4906, 0.4823, 0.4333, 0.398, 0.4611, 0.4669, 0.4017, 0.3673, 0.3663, 0.3778, 0.3043, 0.3231, 0.4539, 0.4067, 0.434, 0.3269, 0.3183, 0.5025, 0.4703, 0.4074, 0.4321, 0.3825, 0.3907]。

采场持续开采时间d_a为采出矿量除以设备生产能力，由于编排中长期计划时考虑以月单位，最终对数据处理采用的是取整，但不会出现大的排产偏差情况，=[1, 7, 5, 7, 8, 10, 3, 7, 13, 12, 14, 19, 13, 10, 9, 3, 7, 10, 10, 8, 18, 10, 6, 5, 11, 11, 19, 10, 9, 14]。

通过三维矿业软件DIMINE^[19]进行空间信息搜索，假如该采场受其他采场的约束则标记为1，否则为0。利用30行×30列的矩阵A_al、A_av描述采场与采场之间的水平空间和垂直空间关系：

，，其中α、β的值分别取0或1。

2.3  模型求解

针对该矿山实际数据，利用YALMIP语言编写采场回采顺序优化的混合整数规划模型，在MATLAB中调用CPLEX采用分支定界算法进行快速求解。程序运行环境为MATLAB2014a，CPLEX Optimization Studio(64bit)12.5.1，Windows7操作系统，4G内存。该模型在44.813秒之内输出结果y_at(见表1)，求解目标函数的最大贴现值为5.1098×10⁵t。

根据模型求解的最优解，即可对矿山采场回采顺序进行优化配置，得到最优采场回采顺序方案，编制出采场网络计划图(见图3)，直观体现了采场回采的先后顺序与逐年矿石产量。

2.4  结果分析

1) 算法效率分析

在模型构建过程中，巧妙运用采场持续时间这一参数，间接减少了模型的变量数目，使模型的求解时间大大减少，整个求解过程的总时间仅为44.813 s，较以往模型求解速率得到很大提升，具体的求解时间分析如表2所列。

表1  y_at的求解结果

Table 1  Calculated results of y_at

图3  采场网络计划图

Fig. 3  Network-planning diagram of stopes

表2  模型求解时间分析

Table 2  Analyzing length of solving time

2) 金属量分析

在生产过程中金属量是矿山决策的重要参数，决定着矿山能否持续的生产和盈利，因此主要通过比较金属量来判断采场回采顺序优化的优劣，该铁矿实际需求产出金属量6.2万t每月。为深入研究混合整数规划法优化采场回采顺序的情况，将混合整数规划方法与传统方法进行对比分析(见图4和5)。

从图4可以看出：在2015年与2016年混合整数规划法编制的生产计划采出的金属量是高于传统方法的，2017年的采出金属量虽然没有比传统方法更高，但3年内总体上保证了富矿优先开采，实现了贴现值最大的生产目标。由图5可知：全生命周期内混合整数规划回采的金属量较传统方法更高，实现了矿山企业金属量最大化的目标，满足矿山的生产需求。因此，采用混合整数规划法优化无底柱分段崩落法矿山的采场回采顺序是成功的。

图4  采出金属量对比分析

Fig. 4  Contrast analysis of metal quantity

图5  金属量分布情况

Fig. 5  Distribution of mental production

3  结论

1) 通过对我国无底柱分段崩落法矿山的回采特点和混合整数规划法的研究，建立采场回采顺序优化的混合整数规划模型。经实例验证，该模型对于求解无底柱分段崩落法矿山的采场回采顺序是非常适用的，得出采场最优回采顺序优化方案，从而使得地下矿山回采顺序的优化从传统的定性分析上升到定量分析与数学优化的阶段，克服传统编排的弊端。

2) 在构建采场回采顺序的混合整数规划模型时，考虑矿山投资风险的影响和企业再投资时回收资本的情况，选择贴现值最大为目标函数，保证富矿优先开采的同时也满足金属量最大化的需求。考虑水平和竖直的空间顺序约束和设备约束，保证生产安全和避免设备的频繁上下移动，以符合矿山的生产实际。

3) 模型通过巧妙运用采场持续时间来减少变量个数，在1 min内得出最优结果，既体现了模型构建的优越性，也说明了模型求解速率较快。

REFERENCES

[1] 李英龙, 童光煦. 矿山生产计划编制方法的发展概况[J]. 金属矿山, 1994, 23(12): 11-16.

LI Ying-long, TONG Guang-xu. Survey of the development of mine production plan scheduling[J]. Metal Mine, 1994, 23(12): 11-16.

[2] RIBEIRO L T. Dynamic programming applied to the mining sequence optimization in a sublevel stoping exploitation[C]//JOHNSON T B, BARNES R J. Proceedings of the 17th APCOM Symposium. New York: American Institute of Mining, Metallurgical, and Petroleum Engineers, 1982: 494-499.

[3] 贾明涛. 基于过程模拟的回采方案优化技术及其在深井开采中的应用[D]. 长沙: 中南大学, 2007.

JIA Ming-tao. The modem metal mine mining scheme optimizing design methods based on the computer process simulation of the mining process[D]. Changsha: Central South University, 2007.

[4] 周科平, 古德生. 遗传算法优化地下矿山开采顺序的应用研究[J]. 中国矿业, 2001, 10(5): 52-56.

ZHOU Ke-ping, GU De-sheng. Optimization of stoping sequence in underground mine by using genetic algorithm method[J]. China Mining Magazine, 2001, 10(5): 52-56.

[5] 云庆夏, 高文炜, 陈永锋, 卢才武. 优化地下采掘进度计划的进化算法[J]. 金属矿山, 2002, 31(4): 11-13.

YUN Qing-xia, GAO Wen-yi, CHEN Yong-feng, LU Cai-wu. Evolutionary algorithm for optimizing the underground mining scheduling[J]. Metal Mine, 2002, 31(4): 11-13.

[6] KUMRAL M. Multi-period mine planning with multi-process routes[J]. International Journal of Mining Science and Technology, 2013, 23(3): 317-321.

[7] NEWMAN A M, RUBIO E, CARO R, WEINTRAUB A, EUREK K. A review of operations research in mine planning[J]. Interfaces, 2010, 40(3): 222-245.

[8] REHMAN S U, ASAD M W A. A mixed-integer linear programming model for short-range production scheduling of cement quarry operations[J]. Asia-Pacific Journal of Operational Research, 2010, 27(3):315-333.

[9] YASHAR P, HOOMAN A, DWAYNE D T. A multi-step approach for block-cave production scheduling optimization[J]. International Journal of Mining Science and Technology, 2013, 23(5):739-750.

[10] CARLYLE W M. Underground planning at Stillwater mining company[J]. Interfaces, 2001, 31(4): 50-60.

[11] O’SULLIVAN D, NEWMAN A. Optimization-based heuristics for underground mine scheduling[J]. European Journal of Operational Research, 2015, 241(1): 248-259.

[12] O’SULLIVAN D, NEWMAN A. Extraction and backfill scheduling in a complex underground mine[J]. Interfaces, 2014, 44(2): 204-221.

[13] MARTINEZ M A, NEWMAN A M. A solution approach for optimizing long- and short-term production scheduling at LKAB’s Kiruna mine[J]. European Journal of Operational Research, 2011, 211(1): 184-197.

[14] TOPAL E. Early start and late start algorithms to improve the solution time for long-term underground mine production scheduling[J]. The Journal of the Southern African Institute of Mining and Metallurgy, 2008, 108(2): 99-107.

[15] WEINTRAUB A, PEREIRA M, SCHULTZ X. A priori and a posteriori aggregation procedures to reduce model size in MIP mine planning models[J]. Electronic Notes in Discrete Mathematics, 2008, 30: 297-302.

[16] CARVALLO F. Lagrangian relaxation decomposes a stochastic mining problem[J]. European Journal of Operational Research, 2009, 203(3): 211-226

[17] 张明佳. 混合整数规划方法的工程应用研究[D]. 武汉:华中科技大学, 2005.

ZHANG Ming-jia. Research on the application of mixed integer programming in engineering[D]. Wuhan: Huazhong University of Science and Technology, 2005.

[18] 马艳利. 混合整数非线性规划问题的分支定界算法研究[D]. 宁夏: 宁夏大学计算工程, 2014.

MA Yan-li. Branch and bound algorithm of mixed integer nonlinear programing problem[D]. Ningxia: Ningxia University, 2014.

[19] 胡柳青, 王李管, 毕 林. 地下矿山生产计划3D可视化编制技术[J]. 煤炭学报, 2007(9): 930-933.

HU Liu-qing, WANG Li-guan, BI Lin. 3D visualization system based production plan scheduling of underground mine[J]. Journal of China Coal Society, 2007(9): 930-933.

Optimization analysis of stope mining sequence based on mixed integer programming

WANG Li-guan^{1, 2}, REN Zhu-li^{1, 2}, PAN Chuan-peng^{1, 2}, CHEN Xin^{1, 2}

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

2. Center of Digital Mine Research, Central South University, Changsha 410083, China)

Abstract: The traditional analysis process of production schedule is random, inefficient, and the optimal production scheduling can not be arranged. The mixed integer programming method was proposed to solve the stope mining sequence optimization problem. The amount of machinery and equipment, vertical and horizontal mine-sequencing were taken as constraints, the net present value (NPV) was used as objective function of mathematical programming model, the stope mining sequence optimization model was scenically analyzed and built based on mixed integer programming method. It was solved with CPLEX, MATLAB and YALMIP for a certain Chinese iron mine. Finally, the optimal arrangement scheme of stope mining sequence was obtained. The results show that this model is scientific and feasible, and the production schedule saves costs compared to schedules manually by meeting desired production quantities more closely and reducing employee time spent on preparing schedules. It has an important significance to guide the actual production of the mine.

Key words: sublevel caving method; mining sequence optimization; mixed integer programming; production scheduling

Foundation item: Project (2011AA060407) supported by the National High Technology Research and Development Program of China

Received date: 2015-05-06; Accepted data: 2015-09-08

Corresponding author: WANG Li-guan; Tel：+86-13808478410，E-mail: liguan_wang@163.com

(编辑  王  超)

基金项目：国家高技术研究发展计划项目(2011AA060407)

收稿日期：2015-05-06；修订日期：2015-09-08

通信作者：王李管，教授，博士；电话：13808478410；E-mail：liguan_wang@163.com