自Lerchs和Grossmann的开创性论文“露天矿的最佳设计” [1]于1965年发表以来，人们一直致力于开发可比的地下矿井设计算法。本文讨论了造成这种情况的原因，探讨了为什么Lerchs-Grossmann算法和较新的伪流变体不直接适合于该任务，并概述了一些已提出的启发式方法的功能和不足。

       强大的数学编程求解器的可用性现已使产生采场设计成为可能，该采场设计与Lerchs-Grossmann算法为露天矿产生的采场设计意义相同。通过使用MICROMINE的新型Stope Optimizer分析的示例示例，本文着手比较启发式算法和求解器的性能，包括所产生的解决方案的质量和产生它们所需的计算资源。最后讨论了每种方法的比较优势以及未来研究和开发的潜在成果。
 

背景

露天矿设计的最终坑定

       在露天矿的长期规划和设计中，最终矿坑确定的目标是确定在给定的倾斜角度下可产生最高利润的矿坑轮廓。通常，此分析是在矿场的离散模型上进行的，该模型是三维块模型，其中为每个块分配了一个值，该值表示在提取，加工和出售该块后所包含的材料的值。托马斯[3]和许多其他作者回顾了确定最终坑轮廓的方法和假设。

       实际上，大多数用于确定露天矿场最终形状的算法都是通过从矿床的三维块模型中提取一组重叠的块“锥”来进行操作的。对于模型中的每个块，定义一个提取锥以指定必须删除才能访问该块的块。每个抽气锥的尺寸由其所应用的块的深度以及该位置允许的最大倾斜角确定。

       各种算法产生的解决方案的质量取决于它们处理不存在重复计数或遗漏而允许多个重叠圆锥效应的挑战的能力。

       对于每个块只需要删除一组单独的预定义块的要求，再加上以递归方式强制执行这些依赖关系的自由，而不必担心遇到块之间相互依赖的循环，从而简化了所需算法的复杂性。可以将适当的依赖关系递归应用于模型中的任何“可访问”块（即可以从表面到达而不会违反坡度限制的块），并确保生成可行的凹坑。从其他合适的区块重复此过程将产生更多可行的凹坑。由于不要求这些可行凹坑不重叠，并且多个可行凹坑的相交点始终是一个可行凹坑本身，因此优化算法的作用被简化为从可生成的所有可行凹坑确定最大可能值来自合适的源块。

       如今，为此目的，在商用软件包中最常用的算法是Lerchs-Grossmann 3D图论算法[1]，伪流算法（Hochbaum [6]）及其变体。这些算法可以产生可证明是最佳（“严格”）问题的解决方案，但要遵守任何所述简化假设。

       最近的创新使用数学编程求解器解决了矿山设计和调度的周期性问题，从而同时导出了设计和调度。

地下矿山设计的采场优化

       同样使用沉积物的三维块模型，采场优化的目标是确定采场的最佳配置，对于给定的一组采场尺寸和形状，采场的最佳收益。

       然而，直到1990年代中期，有关确定地下矿山的最佳设计的论文（Alford [2]，Thomas和Earl [4]）才开始出现。大多数已发布的采场优化算法都是“启发式”算法，因为它们缺乏对其最优性的数学证明，可能仅能找到近似解。其中许多具有容易发现的局限性（Sandanayake [9]，Nhleko等人[10]），并且没有人声称能够针对矿山规划中通常遇到的问题的规模提供最佳解决方案。

       Alford等人[7]提出了采场优化问题的几种新公式，这些公式已经证明具有最优性，并已成功应用于研究中。但是，随后发表的对该作品的引用很少，这表明它现在可能受到商业协议的保护。

       与最终坑的确定相反，由于要在潜在采场中为每个块移除的块集合还可以包括任意方向上的相邻块（不仅限于上述方向，反之亦然），因此尝试在同一方向上递归应用依赖项这种方式将很快退化为在依赖关系所指向的方向上将所有块提取到模型的边界。尽管仍然可以从一组依赖关系中在每个块周围生成可行的停靠点，但是该算法除了确定最佳的源块集合之外，还必须确定在每个块周围的停靠点的最佳位置。根据要求，可能还需要确保所生成的采场不重叠，并最大程度地减少支柱破坏。表1总结了最终矿坑确定与采场优化之间的重要区别。

表1.最终坑确定与采场优化

       因此，以通常用于坑优化的形式，Lerchs-Grossmann 3D图论算法和较新的伪流变体都不直接适合于采场优化。

严格解决方案的好处

启发式可能会遇到以下一种或多种缺陷：

1，可能难以量化解与数学最优值的接近程度。

2.解决方案的质量可能取决于问题的结构和/或所提供数据的配置。

3.在早期处理中做出的决定可能会影响以后做出的选择，从而损害了满足后续约束的能力。如果未结合某种形式的自我校正或探索替代决策路径的能力，则可能会导致与数学最优值产生重大偏差，并且在极端情况下，可能会导致启发式方法将问题视为不可行。

       每种启发式方法都可能以不同的方式受到问题的不同方面的影响。

       当进行敏感性分析以评估对设计参数的更改（例如，坡度限制，采场尺寸或坡度截止）的影响时，启发式的这些特征是非常不可取的，因为无法确定方案之间的变化是否是由变化引起的。设计参数或来自启发式方法的缺陷。严格的算法不会受到这些问题的困扰，并且在给定足够的处理时间的情况下，始终可以依靠它为不同的设计参数集产生数学上最佳的解决方案。结果，方案之间的任何变化都可以仅归因于那些参数的变化。

       Whittle编程公司的3D和4D软件产​​品的成功是建立在Lerchs和Grossmann [1]为他们的算法提供的数学证明的基础上的，这些产品为开放式银行的可行性研究和敏感性分析工具设定了标准。过去30年的矿井规划。

采场优化的启发式

已发布和/或商业化用于从三维块模型中确定最佳采场轮廓的试探法包括表2中列出的试探法。

表2.按年份的3D采场优化启发式

       Alford [2]描述了Floating Stope算法，并讨论了其局限性。 Thomas和Earl [4]总结了其算法的功能并说明了潜在的应用，而Alford等[7]提供了有关其操作的更多详细信息。 Ataee-Pour [5]描述了最大值邻域方法，该方法似乎基于与Floating Stope算法中“内部”包络相似的概念。这些算法生成可能会重叠的采场轮廓集。

       Topal和Sens [8]和Sandanayake [9]的后续算法包括所生成的采场不能重叠的限制。包括此限制或对生成的采场之间的支柱的任何要求，都要求算法意识到早期决策的潜力，以折衷后续决策可用的选项。 Sandanayake [9]通过探索更多的解决方案空间来解决这个问题。但是，成功取决于组合爆炸的影响。

       这些启发式算法的工作原理和局限性的更多详细信息，请参见Sandanayake [9]和Nhleko等[10]。
 

数学编程

       数学编程问题涉及目标函数的优化，该目标函数取决于一组可能有界和/或受约束的决策变量和固定参数。

       在这种情况下，术语“数学编程求解器”（“ solver”）是指可以使用任何类型的数学编程来优化支持的通用目标函数的计算机软件。著名的商业数学编程求解器包括CPLEX，Gurobi，LINDO和MATLAB。

       在过去的20年中，随着求解器性能和功能的显着且持续的提高，以及台式计算机处理能力的相应提高，现在可以将这些工具应用于尺寸和尺寸问题。在矿山规划中通常会遇到的问题。

用于采场优化的新数学编程模型

       MICROMINE已成功实现了用于采场优化的新数学编程模型。这些模型已针对不同类型的求解器进行了公式化设计并进行了测试，并且可以从模块模型生成三维采场轮廓，对于特定的设计参数，该轮廓被证明是最优的。

采场设计参数。新模型在块模型中的多个区域中支持以下采场设计参数：

   ◦轴的尺寸和方向可以使采场最小化；

   ◦是否可以将多个最小停止点重叠以形成更大的形状；

   ◦最小采场的最大轴向增长；

   ◦停止之间所需的支柱尺寸；

   ◦必须在其上锚定了采场的中心线，平面或数字地形模型；

   ◦应该限制/排除停靠站的区域；和

   ◦矿井优化中使用的所有相关经济参数。

结果产生。新的Stope Optimiser的输出包括：

   ◦停止构成最佳解决方案的线框和/或块的坐标；

   ◦采掘场的嵌套分组，以帮助进行阶段规划和开发规划；和

   ◦全套报告，可方便后处理和分析所有输入参数，阻止处理结果以及生成的采场。

应用程序。结合使用适当的设计参数组合和适当的经济参数，可以分析各种方案和挖掘方法，包括：

   ◦通过分段露天开采，挖矿和充填开采，收缩开采，大孔开采，垂直火山口撤退，机房和柱子开采，地下崩落或块状崩落来确定可开采的资源区域；

   ◦使用标准的矿井优化方法和现金流折现分析，可以优化地下采矿作业的 规模和分级；

   ◦在最小采矿量的情况下，确定有利可图的采矿的最佳外围；

   ◦在最小采矿宽度的情况下，确定露天开采台的最佳挖掘线；

   ◦规划地下通道的位置；和

   ◦识别用于环设计的矿石和废物封套。

结果验证

       开发任何新算法的挑战之一是建立并验证其解决方案的质量。尽管求解器生成的解证明是最优的，但仍然有必要验证所提出的模型的公式满足任何适用的约束并产生预期的结果。至少，这意味着使用其他方法不可能产生优异的结果。

       验证工作包括开发了几种新的启发式算法，以进行采场优化，以测试数学编程模型的解决方案性能。相反，它也提供了评估启发式方法性能的机会。

样本问题

       为了方便将来的研究人员进行独立分析，在MineLib的数据集上测试了新的数学编程模型和启发式方法[11]。

       表3中显示了所选数据集的摘要，其中包含用于优化的值的来源字段的名称。为帮助识别value字段，其中包含ID = 0的块的值。通过根据需要对所有块的优化值进行调整，确保了负值的代表性数量。

表3.采场优化测试的样本问题

为了便于将结果与最佳启发式方法的结果进行比较，允许在模型中按要求放置和重叠采场，并且不需要设置支柱。测试了以下采场尺寸：

   •3 x 2 x 4矿块

   •5 x 4 x 6矿块

   •6 x 9 x 4矿块

       结果总结在表4中。求解器生成的最佳解决方案的值记录在“最佳求解器值”中。

       作为其操作的组成部分，求解器确定并维持可以满足设计参数的提取总值的上限。这在“ Solver Bound”中有所报道。求解器产生的解决方案的质量（“解决方案质量–求解器”）和最佳启发式方法（“解决方案质量–最佳启发式”）以该界限的百分比表示，值为100％表示求解器能够验证是否找到了最佳解决方案。为了方便起见，某些求解程序运行被提前终止。

表4.示例问题的采场优化结果

       表5包含为SM2生成的5 x 4 x 6和6 x 9 x 4采场线框的图像，这些线框覆盖在可盈利的区块上。 这些图像确认了这些停放点可以按需跨越获利的区块，而由于这些块的分配方式，与6 x 9 x 4个停靠点相比，5 x 4 x 6个停靠点能够更有选择性地做到这一点。 这反映在较低的总价值上。

表5. SM2的采场优化结果（示例问题2）

观察与结论

       不出所料，每种模型的最佳值都随最小采场中的块数增加而降低。这是由于在较大的采掘场遇到废物块的可能性增加，从而使这些采伐场的价值降低，也不太可能被包括在内，从而降低了总价值。

       如果允许采场重叠，并且不需要柱撑，那么最好的试探法就能够产生接近于所有测试示例的数学最佳值的值。

       随着沉积变异性或最小采场中块数的增加，求解器将更加难以确定提取总值的准确范围，这增加了找到最佳值所需的时间。但是，在所有测试的示例中，这并没有影响最佳启发式方法的相对解决方案性能，而这种方法明显需要较少的处理时间。

       随着对非重叠采场或采场之间的支柱的要求，问题的复杂性不断增加，从启发式方法在合理的时间范围内获得接近最佳的解决方案变得更加困难。随着求解器解决方案现在可用作基准，未来的工作将致力于解决这些挑战并进一步缩短解决方案时间。

       新的数学编程模型接受许多常见的采场设计参数，并生成可证明是最佳的采场布局。结合对多种要素和处理方法，稀释，回收率以及收入和成本调整因素的支持，该软件为矿井优化从业人员无缝过渡到采场优化世界。

参考文献

1.Lerchs，H.，Grossmann，L .：露天矿的最佳设计。在：交易，加拿大矿业和冶金学院，卷。 LXVIII，第17-24页（1965）。

2.Alford，C.，《地下矿山设计的优化》。载于：APCOM XXV会议录，1995年《计算机和运筹学在矿业中的应用》，第213-218页。澳大利亚布里斯班的澳大利亚矿业冶金学院（1995年）。

3.Thomas，G.S.，矿井优化和矿山生产计划-未来之路。在：Ramani，R.V.，（ed。）Proceedings APCOM XXVI 1996 Computers and Operations Research in Mineral Industry中的应用，第221-228页。采矿，冶金和勘探协会。美国宾夕法尼亚州立大学（1996）。

4，Thomas，G.S.，Earl，A .：第二代采场优化工具在地下边界品位分析中的应用。在：战略性地雷规划第三次两年期会议，Whittle Programming Pty Ltd，西澳大利亚州珀斯（1997）。

5，Ataee-Pour，M .：优化采场边界的启发式算法。博士学位论文。澳大利亚卧龙岗大学工程学院（2000年）。

6，Hochbaum，D.S .:一种新旧算法，用于闭合图中的最小切割和最大流量，30周年特别论文，网络：网络，第37（4）卷，171-193页（2001）

7.Alford，C.，巴西，M.，Lee D .：地下采矿的优化。在：自然资源运筹学手册，卷。 99，第561-577页。 Springer US（2007）。

8.Topal，E.，Sens，J .：一种用于采场边界优化的新算法。煤炭科学与工程学报，第一卷。参见，例如，J.Med.Chem.16，No.2，pp 113-119（2010）。

9，Sandanyake，D.S.S .:基于启发式方法的地下采矿的采场边界优化。博士学位论文。科廷大学，西澳矿业学院（2014）

10.Nhleko，A.，Tholana，T.，Neingo，P .:地下采场边界优化算法综述。在：资源政策。 https://doi.org/10.1016/j.resourcpol.2017.12.004

11.Espinoza，D.，Goycoolea，M.，Moreno，E.，Newman，A。：MineLib：露天矿开采问题图书馆。在：运筹学年鉴，卷。 206，第1期，第93-114页（2013年7月）。另外：http://mansci-web.uai.cl/minelib，上次访问时间为2019/05/14。

12，Alford Mining Systems：Mineable Shape Optimizer，http://alfordminingsystems.com/?page_id=74，上次访问时间为2019/06/07。