孙效玉¹, 邓鹏宏², 赵明³
1.东北大学 资源与土木工程学院, 辽宁 沈阳 110819;
2.鞍钢矿业公司 决策支持部, 辽宁 鞍山 114004;
3.中煤科工集团沈阳设计研究院有限公司 露天工程事业部, 辽宁 沈阳 110015
收稿日期: 2015-11-16
基金项目: 十二五国家科技支撑计划项目(2015BAB15B01);国家自然科学基金创新研究群体项目(71321001/01).
作者简介: 孙效玉(1963-), 男, 内蒙古赤峰人, 东北大学教授。

摘要: 针对数学优化方法在露天矿进度计划应用中存在的只对单一时段计划进行优化，或是对多时段计划进行分段优化，没有实现全时段整体优化的问题，在前后时段0-1整数规划和大小时段0-1整数规划两种模型分段优化的前期工作基础上，提出了露天矿整体优化的0-1整数规划模型，并针对计算速度慢的问题，提出了相应的改进措施.该模型既实现了多时段生产计划的整体优化，又解决了分段优化无解的隐患，还保证了速度和精度，不仅可实现用下层计划验证上层计划，而且可用于由下层计划导出上层计划，其实用性和通用性更好.
关键词：露天矿生产进度计划0-1整数规划线性规划整体优化多时段
Integrated Optimization Model of Multi-period Open-Pit Mine Production Scheduling
SUN Xiao-yu¹, DENG Peng-hong², ZHAO Ming³
1.School of Resources & Civil Engineering, Northeastern University, Shenyang 110819, China;
2.Resources Planning Management Department, Ansteel Mining Company, Anshan 114004, China;
3.Open-Pit Mine Engineering Business Unit, CCTEG Shenyang Engineering Company, Shenyang 110015, China
Corresponding author: SUN Xiao-yu, E-mail: sunxiaoyu@mail.neu.edu.cn
Abstract: To solve the integrative optimization of multi-period plans in the applications of open pit production only focused on single-period or multi-period optimization with mathematical optimization methods, a 0-1 integer programming model for the integrated optimization was proposed on the basis of previous works of 0-1 integer programming models for "before and after" periods and for "large and small" periods. The corresponding improvement measures were put forward for low computing speed. The model realizes the integrative optimization of multi-period plan, avoids the potential danger of no solution to the discrete optimization, and also guarantees the computational speed and accuracy. The model can be used to verify upper plan with lower plan and to derive upper plan from lower plan, and shows a better adaptability and versatility.
Key Words: open-pit mineproduction scheduling0-1 integer programminglinear programmingintegrative optimizationmulti-period
露天矿开采计划通常分为长期计划、中期计划、短期计划三个层次^[1].长期计划确定矿山企业5~10年的长期战略目标，中期计划确定1~3年的营运发展计划，短期计划确定更详细的1周至数月的开采顺序.上层计划对下层计划起约束作用，下层计划确保上层计划的实现.
由于采矿进度计划时空发展的复杂性，目前国内外生产计划编制普遍采用人机交互的计算机辅助设计方法，即计算机图形显示矿岩分布和当前开采状态，计划员根据经验圈定开采区域，计算机自动计算圈定区域的矿岩量及品位，Surpac，Datamine，3Dmine，Dimine等国内外众多采矿设计软件均采用此方法.这种方法费时费力，通常只能做出生产计划中的几个关键位置，难以实现上下层计划的有效验证.以这种方法确定的上层计划中的相邻两个工程位置为起终点，采用数学优化算法快速有效地细化成多个时段的下层开采计划，是验证上层计划时空发展可行性的有效途径；也可通过优化快速形成多个时段的下层计划，为上层计划编制提供参考依据.
国内外对数学优化方法应用于采矿计划的研究比较广泛.文献[2]对采矿进度计划的解决办法进行了很好综述；文献[3]提出了应用动态规划模型求解短期计划的启发式方法；文献[4]提出了用于解决短期计划问题的混合整数规划模型；文献[5]将储矿堆与配矿堆结合，建立了一个混合整数规划模型；文献[6]提出了求解长期计划的4种混合整数规划模型并进行了对比；文献[7]建立了混合整数规划模型，并通过松弛变量分级求解；文献[8]论述了分支求解0-1整数规划的策略；文献[9-11]对开采区域规整性、文献[12-14]对减少线性规划中的整数约束进行了系统研究，增强了露天矿生产计划的现实可行性.这些文献或是对单一时段进行优化，或是对多时段进行分段优化，没有实现多时段的一次性整体优化.
1 前期工作基础及存在问题分析1.1 露天矿时空发展要求露天矿分台阶、台阶分条带、条带分块段进行开采，其时空发展简化如图 1所示^[15-16].从设计角度讲，其时空发展应满足以下约束条件：
1)块段发展顺序：同条带前一块段采完，后一块段才能开采.
2)条带发展顺序：同台阶前一条带采完，后一条带才能开采.
3)台阶发展超前性：为保证矿山空间发展，上下相邻台阶之间的距离不小于最小平盘宽度.
4)台阶发展滞后性：为保证经济效益，避免超前剥离过量，上下相邻台阶之间的距离不超过一定的宽度.
5)分时段产量、质量要求：各时段必须完成相应的产量和质量要求.
图 1(Fig. 1)

图 1 露天矿时空发展顺序图Fig.1 Spatial-temporal scheme for open-pit mine

1.2 整数规划问题分析假设台阶从上到下顺序编号，条带按推进方向顺序编号，块段从条带的一端向另一端顺序编号.相关的参数及其符号如表 1所示.
表 1(Table 1)

表 1 参数定义表Table 1 Definition of parameters 符号 含义 单位 备注 I 台阶数 个 Ji i台阶的条带数 个 Kij i台阶j条带的块段数 个 (i, j, k) i台阶j条带k块段 Mijk (i, j, k)块的矿量 t或m3 Rijk (i, j, k)块的岩量 t或m3 B 矿质指标数 个 Aijkb (i, j, k)第b个矿质指标 T 划分的时段数 个 Mt1, Mt2 第t个时段计划 矿产量的下限、上限 t或m3 Rt1, Rt2 第t个时段计划 剥离量的下限、上限 t或m3 Abt1, Abt2 第t个时段第b个矿质 指标的下限、上限 n1 超前条带数 个 n2>n1 n2 滞后条带数 个

表 1 参数定义表 Table 1 Definition of parameters

显然，要解决的问题就是根据1.1矿山时空发展要求，确定各(i, j, k)块在哪个时段t(t=1~T)开采.从表面看，如果用变量X_{i, j, k}表示(i, j, k)在哪个时段开采，这似乎是一个简单的整数规划问题.
据此，根据1.1时空关系的约束条件1)~4)，可以列出以下不等式：

(1)

(2)

(3)

(4)

但无法用X_{i, j, k}列出第(5)项对应的约束条件.为此，引入变量X(t)_{i, j, k}，表示(i, j, k)是否在t时段开采，取值如下：

(5)

据此得产量约束方程：

(6)

(7)

同理还可得到质量约束、目标函数等.但用Lingo，Matlab，Eplex等多种软件均无法求解.经分析认为，这是由于变量X(t)_{i, j, k}的引入，使模型由线性变为非线性引起的.
1.3 前期工作回顾及存在问题分析为解决整数规划无解的问题，已先后建立了两个模型.
最开始采用文献[15]分时段求解的0-1整数规划模型：先求出第一个时段的开采计划，再求出第二个时段的开采计划，直到求出最后一个时段的开采计划.其存在的主要问题：有时会发生前面时段有解、后面时段无解的情况，需要反复调整，既费时费力，求解结果又不唯一.
然后采用文献[16]渐进细化的0-1整数规划模型，对文献[15]的计算顺序进行改进：将前后顺序改为类似折叠的大小顺序，先求大时段，再求小时段，直到最小时段(类似由年到半年、由半年到季、由季到月)，并且折叠后只计算前一半，后一半认为自然有解(如年计划只计算上半年而不计算下半年)，不仅提高了计算速度，而且不存在无解的问题.
文献[16]虽然解决了文献[15]后时段无解的问题，但也埋下了后一半没有优化甚至无解的隐患.同时两个模型都是分段进行优化，没有实现各时段的整体优化.
2 整体优化模型的建立2.1 总体思路前期工作的实践证明，应用目前软件采用非线性混合整数规划方法实现整体优化很困难，但由式(5)可以看出，即使决策变量采用整数，还是需要引入取值0或1的变量，体现出0-1变量解决此问题的方便性和有效性.既然文献[15-16]两个模型能够由0-1整数规划分时段求解，那么用0-1整数规划进行整体优化求解不失为一条有效的途径.
要进行0-1整体优化，必须将原来求(i, j, k)块在哪个时段t开采的问题，变为求(i, j, k)块在t时段是否开采的问题，即将原来求变量X_{i, j, k}=t的非线性整数规划问题，变为求X_{i, j, k}-t=0或1的0-1线性整数规划问题.因此需要对决策变量进行重新定义，进而列出模型.
2.2 变量和参数定义设决策变量X_{i, j, k, t}为0-1整数变量，表示(i, j, k)块在时段t(t=1~T)是否开采，开采等于1，不开采等于0(相当于式(5)中的X(t)_{i, j, k}，但取消X_{i, j, k}定义).同时保持表 1的参数定义不变.
设此决策变量后，目标函数和产量、质量等约束与式(6)、式(7)类似，但式(1)~式(4)需作较大改变.
2.3 目标函数目标函数依矿山的具体条件不同而各异.以伊敏露天矿实现最下2个采煤台阶开采量最大、从而尽快倒出内排空间为例^[15]，其目标函数为

(8)

2.4 约束条件1)块段发展顺序性约束：

(9)

其中τ表示时段.为实现从第一时段到时段τ的求和，又区别于t，所以加入τ，下同.
2)条带发展顺序性约束：

(10)

说明：因为式(9)已经约束了同一条带的前后块段开采顺序，所以式(10)只约束前条带的最后块段与后条带的第一块段，即可满足“前一条带采完，后一条带才能采”的限制条件，从而减少模型的复杂度，提高运算速度.下面式(11)、式(12)与此相同.
3)超前性约束：

(11)

4)滞后性约束：

(12)

5)产量约束：

(13)

(14)

6)质量约束：

(15)

(16)

7)重点工程约束：

(17)

式中：I_Q1, I_Q2为重点工程起止台阶号，τ₁, τ₂为重点工程起止时段，K_n¹, K_n²为重点工程量下限、上限.
8)开采时段约束：

(18)

此约束为本模型较文献[15-16]新增加的约束条件，表示每个块段(i, j, k)能并且只能在一个时段开采，从而保证∑各时段下层计划≡上层计划.如果改为≤1，则表示块段(i, j, k)可不开采(=0)，∑各时段下层计划≤上层计划，即完成但未必全等于上层计划.=1和≤1都可用于对上层计划进行细化，实现用下层计划验证上层计划；而≤1还可用于先作出多个时段的下层计划，为有效编制上层计划提供重要参考依据.
3 模型对比与改进完善3.1 模型对比文献[15]从前到后分时段求解，文献[16]从大到小分时段求解，本模型一次性求解各时段.
同文献[15-16]的模型相比，本文模型的决策变量增加了1个时段下标，使决策变量数成倍增加.以12 000块构成的年计划作出12个月的月计划为例，文献[15]要从前到后求解12次，变量数依次为12 000，11 000，…，1 000，总数78 000.文献[16]第一次计算12 000块，分成前8 000块和后4 000块，随后8 000，4 000，2 000各自计算1，3，6次，求解次数为11，变量总数44 000^[16].本模型求解次数为1，变量总数144 000.
文献[15-16]模型对不同时段进行多次运算，实现分段优化但没实现整体优化，且存在无解的隐患；本模型一次计算求解全部时段，实现整体优化，经多次运行还没发现无解情况, 实现了线性规划与采矿计划整体优化的完美结合.三种模型具体对比见表 2.
表 2(Table 2)

表 2 三种模型对比Table 2 Comparison among three models 项目 本文模型 文献[15] 模型 文献[16] 模型 本文模 型备注 变量维度 i, j, k, t i, j, k i, j, k 增加1 个下标 变量数 N×T N× (1+T)/2 约N× lnT 变量多 求解方式 一次性 整体求解 从前到后 分段求解 从大到小 分段求解 整体求解 求解次数 1 T T-1 次数少 计算速度 慢 慢 快 速度慢 有无解 有 有时无解 有但 埋藏隐患 有且最优 优化结果 整体最优 阶段优化 阶段优化 整体优化 注：N表示总块段数.

表 2 三种模型对比 Table 2 Comparison among three models

3.2 模型存在问题及改进方法本文模型存在的主要问题是由于增加了时间维度，导致变量数增加、运算速度慢，可通过减少时段、块段两种途径解决.
1)类似渐进细化的减少时段法：这种方法与文献[16]的渐进细化法的思路相同，但具体做法有较大差异.前者不限于两个时段(如可直接由年计划作季计划)，即使是制作两个时段也是两个时段同时优化；而后者必须分为两个时段，且只对前时段进行优化，对后时段既不求解，也不验证.
2)超级块方式的减少块段法：所谓“超级块”，就是对同一条带上的相邻块段进行组合.这种方法对三种模型都适用，但在本模型和文献[16]渐进细化法中更实用，因为大时段可以用大块、小时段用小块，并可逐级缩小，从而保证精度需要；而文献[15]前后时段法用大块则降低精度、用小块则达不到提速的目的.
显然，时段数较块段数对运算速度的影响更大，因此采用第一种方法更有效.同样以12 000块构成的年计划作出12个月计划为例，如果先作季计划，再作月计划，并且作季计划时采用2合1的超级块，则年计划分4个时段计算1次形成季计划、季计划分3个时段计算4次形成月计划.求解次数为5，第一次变量数为12 000/2×4=24 000，后4次变量数为3 000×3×4=36 000，变量总数为60 000，较一次性计算144 000减少很多，较文献[15]的78 000也少.如作季计划采用4合1的超级块，则变量总数为48 000，与文献[16]的44 000相差无几.
在文献[16]中程序的基础上，按本文模型进行了改进，并以4个时段为上限，结合超级块逐级进行整体优化，既实现整体优化，又保证运行速度和块段精度，达到了实用的目的.
4 结论1)建立的整体0-1整数线性规划模型可一次性求解各个时段的开采计划，并可实现整体最优.解决了分时段0-1整数规划模型要各个时段求解，分段达到优化、整体没有优化、且存在无解隐患的问题.
2)同分时段0-1整数规划相比，决策变量的下标增加了时段，造成决策变量成倍增加，计算速度显著降低，这是本模型存在的主要问题.
3)减少一次性计算的时段数，使用超级块减少块段数量，可有效提高计算速度，其中以减少时段数最佳.建议以4个时段为上限，结合超级块技术逐级进行整体优化，可达到事半功倍的效果.
4)本模型既可实现用下层验证上层计划，也可由下层计划推出上层计划，因此本模型的实用性更强.
参考文献

[1]	L'Heureux G, Gamache M, Soumis F. Mixed integer programming model for short term planning in open-pit mines[J].Mining Technology, 2013, 122(2) : 101–109.DOI:10.1179/1743286313Y.0000000037
[2]	Newman A M, Rubio E, Caro R, et al. A review of operations research in mine planning[J].Interfaces, 2010, 40(3) : 222–245.DOI:10.1287/inte.1090.0492
[3]	Lestage P, Mottola L, Scherrer R, et al.A computerized tool for short range production planning at Mount Wright[C]//Proceedings of International Symposium on the Application of Computers and Operations Research in the Mining Industries (APCOM XXIV).Montreal:Springer, 1993:67-74.
[4]	Smith M L. Optimizing short-term production schedules in surface mining:integrating mine modeling software with ANIPL/CPLEX[J].International Journal of Surface Mining, Reclamation, and Environment, 1998, 12(4) : 149–155.DOI:10.1080/09208118908944038
[5]	Eivazy H, Askari-Nasab H. A mixed integer linear programming model for short-term open pit mine production scheduling[J].Mining Technology, 2012, 121(2) : 97–108.DOI:10.1179/1743286312Y.0000000006
[6]	Askari-Nasab H, Pourrahimian Y, Ben-Awuhae E, et al. Mixed integer linear programming formulations for open pit production scheduling[J].Journal of Mining Science, 2011, 47(3) : 338–359.DOI:10.1134/S1062739147030117
[7]	Bolanda N, Dumitrescub I, Froylandb G, et al. LP-based disaggregation approaches to solving the open pit mining production scheduling problem with block processing selectivity[J].Computers & Operations Research, 2009, 36 : 1064–1089.
[8]	Caccetta L, Hill S P. An application of branch and cut to open pit mine scheduling[J].Journal of Global Optimization, 2003, 27 : 349–365.DOI:10.1023/A:1024835022186
[9]	李建祥, 王青. 多时段露天开采短期计划优化[J].金属矿山, 2001(4) : 1–4, 18. ( Li Jian-xiang, Wang Qing. Optimization of the short-term production scheduling of multi-period opencasting[J].Metal Mine, 2001(4) : 1–4, 18.)
[10]	李建祥, 吴会江, 唐立新. 考虑规整性的露天矿短期生产调度模型[J].系统工程理论与实践, 2005, 25(3) : 119–124. ( Li Jian-xiang, Wu Hui-jiang, Tang Li-xin. A model with regularity for open pit mine short term production scheduling[J].Systems Engineering-Theory & Practice, 2005, 25(3) : 119–124.)
[11]	李建祥, 吴会江. 基于距离的开采区域规整性测度及其几点性质[J].矿业研究与开发, 2005, 25(6) : 16–17, 66. ( Li Jian-xiang, Wu Hui-jiang. Distance-based regularity measure of mining area and its attributes[J].Mining Research and Development, 2005, 25(6) : 16–17, 66.)
[12]	Ramazan S, Dagdelen K, Johnson T B. Fundamental tree algorithm in optimizing production scheduling for open pit mine design[J].Mining Technology, 2005, 114(1) : 45–54.DOI:10.1179/037178405X44511
[13]	Ramazan S, Dimitrakopoulos R. Recent applications of operations research in open pit mining[J].Transactions of the Society for Mining, Metallurgy and Exploration, 2004, 316 : 73–78.
[14]	Ramazan S. The new fundamental tree algorithm for production scheduling of open pit mines[J].European Journal of Operational Research, 2007, 177 : 1153–1166.DOI:10.1016/j.ejor.2005.12.035
[15]	孙效玉, 张维国, 陈毓, 等. 根据露天矿长期计划自动形成短期计划的0-1整数规划方法[J].煤炭学报, 2012, 37(7) : 1139–1143. ( Sun Xiao-yu, Zhang Wei-guo, Chen Yu, et al. Automatic formation of short-term plan based on the long-term on open-pit mine using 0-1 integer programming[J].Journal of China Coal Society, 2012, 37(7) : 1139–1143.)
[16]	孙效玉, 张维国, 孙梦红. 自动优化露天矿短期进度计划的渐进细化法[J].东北大学学报(自然科学版), 2012, 33(5) : 735–738. ( Sun Xiao-yu, Zhang Wei-guo, Sun Meng-hong. Progressive thinning algorithm for automatic optimization of short-term scheduling of open-pit mine[J].Journal of Northeastern University (Natural Science), 2012, 33(5) : 735–738.)