一种适用于露天矿生产的局部分支启发式算法调度问题外文翻译资料

 2022-01-21 10:01

英语原文共 11 页,剩余内容已隐藏,支付完成后下载完整资料


O.R .的创新应用

一种适用于露天矿生产的局部分支启发式算法调度问题

Mehran Samavati a,lowast;, Daryl Essama, Micah Nehring b, Ruhul Sarker a

澳大利亚堪培拉新南威尔士大学工程与信息技术学院,澳大利亚布里斯班昆士兰大学机械与矿业工程学院

摘要

本文研究了著名的露天矿生产调度问题(opmpsp)。给定一个矿体离散化的块体模型,该问题寻求一个块体提取序列,使净现值(NPV)在几个周期内最大化。在实际应用中,块的数目可能很大,因此,这个问题很难解决。当ITN将最低资源需求表示为资源约束的下限时,这就更加具有挑战性。在本研究中,我们建议使用一种新的元启发式技术,即局部分支来处理opmpsp。为了加快搜索过程,我们将局部分支与一种新的自适应分支方案相结合,并开发了一种启发式算法,以快速生成一个起始可行解。尽管文献中很少考虑最低要求,但这种方法对于我们概念上生成的一系列数据集产生了接近最优的解。为了判断我们方法的性能,将结果与文献中的两种方法以及由混合整数线性规划(milp)求解器获得的结果进行比较。

1介绍

露天开采是先从地表开采有价值的物质,然后在市场上出售以获取利润的过程。采矿项目的经济可行性在很大程度上依赖于谨慎的管理。运筹学被广泛应用于决定如何完成提取过程以获得最大的利润。为了使物料提取的规划过程更易于操作,矿山规划者将矿体划分为一个个小立方体(但并不总是立方体)的块体。因此,块体模型是被离散成块体的矿体。虽然有许多模型可用,但3D固定块模型最受关注,因为它最适合计算机优化技术的应用(Caccetta amp; Hill, 2003)。

截止品位是指矿体内的物质含量不足以经济合理地进行开采的水平。含有高于截止品位的贵重矿物的砌块将被送往加工厂。所有其他区块将被送到一个垃圾场。这两种类型的块都安排在整个挖掘操作的生命周期中。该战略矿山计划的目标是在遵守各种操作限制的同时,最大化净现值(NPV)。在采矿作业规划中,一个主要问题是确定某个区块模型中区块开采的最优调度。这就产生了露天矿生产调度问题(opmpsp),其中目标是找出应该提取哪个块(如果有的话),在哪个时间段内,以获得最高的净现值。必须考虑几个操作限制同时使用运筹学技术解决opmpsp问题。例如,优先约束,即几何顺序约束,或墙坡约束,确保块体的挖掘不会向内塌陷。这意味着给定块在其上覆块之前不能被挖掘。

资源能力对从矿体中移出的物质数量和在轧机上加工的矿石(有价值的物质)数量施加限制。将项目的时间范围细分为时间段,每个时间段都有一定数量的资源加工和资源生产,分别称为最大加工能力和最大生产能力。

最低采矿和矿石加工要求是OPMPSP的其他限制。这些是重要的操作注意事项,主要与调度周期之间一致的可接受的设备利用率有关。在设定的时间表范围内,每个期间的最低采矿和加工率也允许适当分配与操作重型设备有关的其他资源,例如劳力和维修费。这确保了总体操作的可行性。

自20世纪60年代以来,许多研究人员一直致力于opmpsp的研究。早期的研究只集中于极限坑问题,这是只考虑优先约束的问题的简化版本(Underwood amp; Tolwinski, 1998)。OPMPSP的不同变体随后被表示为整数或混合整数线性规划(MILP)。相应的数学模型涉及二进制变量,这些变量决定给定块是否在某个时间段内被删除。在MILPs中,附加的连续变量表示在特定时间段内发送到特定目的地的每个块的数量。这些公式的约束取决于所假设的操作限制,从而形成调度问题的变体。为了使问题更易于解决,OPMPSP通常通过某些简化来解决,例如固定的截止等级和无库存。这个问题的简化版本被称为约束坑限问题(cpit),其中相应的公式涉及二元变量,目标是在优先约束、最大资源容量和最小资源需求的情况下使净现值最大化。模型将在第3节中详细解释。

尽管最低资源需求很重要,但它们会大大增加问题的复杂性。Cullenbine, Wood, and Newman(2011)通过实验分析了最小容量对CPIT复杂性的影响。他们发现,CPLEX可以在176秒内解决特定实例的最优性,而在考虑最小需求时,则需要3688秒。有许多原因使得最低要求使得问题更难解决。以下是其中一些:

首先,最大加工能力和生产能力在数学模型中通常表现为两个独立的容量(背包)约束。最低要求导致这些限制的下界,这可能与背包的上界冲突。例如,处理背包约束中的下界可能与提取容量的上界直接冲突。

其次,在只考虑上界的情况下,可将问题视为尽早提取高阶块(高值块),以使货币价值效应最小化。然而,当一个下界被整合时,需要一个前瞻性的方法来保持矿石材料的所有时期。

最后,在考虑最低要求时,某些用于问题的启发式方法和技术不能应用。例如,一些启发式方法可以通过首先解决最终的坑限问题,然后将解决该问题的过程中出现的那些块合并到求解算法中,从而减小模型A先验的大小。然而,在包含最低要求的模型中,这种尺寸减小是不可能的,因为加工的下限可能需要向工厂发送一个不经济的块,以保持实例的可行性。

尽管它们很重要,但最低的资源需求很少有研究涉及这个问题。最早的方法之一考虑到这些需求的是分支和Gaupp(2008)提出的cut (Bamp;C)算法。该算法使用了特殊的切割计划,这个计划是通过使用每个区块最早和最晚的可能提取时间而产生的。在应用Bamp;C算法之前,作者开发了一种变量约简技术来减少变量的数量。Gaupp还利用拉格朗日松弛来减少求解时间。尽管Bamp;C和拉格朗日松弛法得到的结果比直接解整个问题得到的结果要好得多,但是所处理的最大实例只有10,819个块和6个时间段。其他方法是Cullenbine et al.(2011)和Lambert and Newman(2014)的算法。前者将滑动时间窗启发式与拉格朗日松弛相结合求解CPIT,后者则利用滑动时间窗启发式为定制的拉格朗日松弛过程生成初始可行解。这两项研究在多达25620个街区和10个时间段的实例中都取得了良好的结果。Kumral(2012)也对7020个区块和5个周期进行了一个相对较小的案例研究。

因此,我们提出了一种新的有效的技术来处理更大的OPMPSP实例,同时包括最低要求和最大容量。我们的技术使用了Fischetti和Lodi(2003)提出的一种新的高级解决方案策略,称为局部分支。实际上,这种策略是一种混合的元启发式策略,它将混合整数规划(MIP)解决方案技术与典型的元启发式概念相结合,例如局部搜索、邻域定义以及增强和多样化机制。局部分支使用一个通用的MIP解算器来探索可行的子空间(邻域),该子空间是通过引入称为局部分支约束的线性不等式构造的。我们现在简单介绍一下这种技术。

我们首先考虑以下一般的0-1线性规划问题:

GP = max cT x

s.t. Ax = b

式子中, , 和,设为GP的可行解(称为参考解),n=1hellip;n, ,k为正整数。另外,让代表现有解决方案,bestlb=ct x∙是一个起始下限。当不等式时,可通过在一个分支(称为左分支)上取满足不等式的X的值来划分GP的可行域,在另一个分支(称为右分支)上取满足不等式的x的值。然后使用通用求解器对左分支生成的子问题进行优化,得到一个新的解X∙。设x=x,并将x(即通过局部分支获得的最佳溶液)设为x。在右分支的子问题中,通过将局部分支约束转换为来构造,如果ct xgt;bestlb,则x=x和bestlb=ct x。然后,迭代该过程,即在模型GP中添加局部分支约束.

据我们所知,还没有发表的研究利用局部分支来寻址OPMPSP。在我们的方法中,我们开发了一种新的自适应分支方案,并将其与局部分支相结合。这种策略使得局部分支非常快速和高效。我们还开发了一种新的启发式算法来寻找一种可行的解决方案来进一步加速该过程。

为了判断所提方法的效率,我们开发了一系列概念生成的数据集,并将用我们的方法求解这些数据集的结果与从Bamp;C和拉格朗日松弛等文献中获得的结果进行比较。与其他技术相比,该算法具有更好的性能。有趣的是,我们的方法处理了一个50,383块和10个时间段的实例,得到了一个接近最优的解决方案,而正如前面提到的,文献中解决的最大的实例只有25,620块和10个时间段。

本文的其余部分组织如下。在下一节中,我们将回顾相关文献并总结我们从事这项工作的动机。在第3节中,我们提出了本研究中所考虑的数学规划模型,并在下一节中解释我们的解决方案方法。第五节给出了实验结果。第六部分对本文的工作进行了总结,并对今后的研究提出了一些方向。

2文献综述

本节简要讨论OPMPSP的相关文献,以及局部分支过程。

2.1 OPMPSP

由于OPMPSP的大小在实际应用中不允许MIP求解器整体求解,文献中针对该问题的不同变体开发了各种聚合、松弛和启发式方法。其中一种方法是Ramazan(2007)的“基础树算法”,该算法考虑了固定的截止等级、最小的加工要求以及最大的加工和生产能力。本研究通过聚合块来减少变量的数量。Boland, Dumitrescu, Froyland和Gleixner(2009)研究了具有可变截止等级和最大资源容量的OPMPSP。它们使用聚合块来调度提取过程,而单个块用于处理决策。另一种算法是Jelvez, Morales, Nancel-Penard,Peypouquet, Reyes(2016)的“聚集与分离”启发式算法。尽管聚集技术大大缩短了溶解时间,但从采矿作业的角度来看,当涉及到年度矿石和/或废物生产、矿石平均品位等时,所获得的时间表实际上并不适用。Kawahata(2007)提出了聚合和拉格朗日松弛相结合的方法,以解决可变截止坡度和最大容量问题。

最近,一些研究人员把他们的努力集中在基于拓扑排序的启发式上。最有力的提出的启发式是著名的拓扑排序启发式,由Chicoisne, Espinoza, Goycoolea, Moreno, and Rubio(2012)和Moreno, Espinoza, and Goycoolea(2010)提出。Liu和Kozan(2016)的启发式也是基于拓扑序的方法的一个很好的例子。最近的这些研究对于下界为0的背包约束的CPIT得到了令人印象深刻的结果。

很少有研究使用元启发式来处理OPMPSP。最新和有效的元启发式是由Shishvan和Sattarvand(2015)开发的,它基于蚁群优化(ACO)。

同时还考虑了求解CPIT的LP松弛问题。Moreno等人的解决方法。(2010)和Bienstock和扎克伯格(2010)被认为是最有效地解决了CPIT的LP弛豫问题。有关解决方案方法的详细文献综述,请参考Gaupp(2008)和Espinoza、Goycoolea、Moreno和Newman(2013)。

2.2本地分支

本地分支技术最初由Fischetti和Lodi(2003)开发,旨在解决复杂和大型MIP问题。通过求解几个困难的MIP问题——网络设计、机组调度、铁路机组调度、嵌套、电信网络设计、批量确定、机车车辆和线路规划以及铁路线路规划,证明了该方法的有效性。Fischetti、Polo和Scantamburlo(2004)将局部分支与可变邻域搜索(VNS)结合起来,并将此方法应用于电信网络设计问题。Hansen、Mladenvic和Uro_evic(2006)描述了解决MIP问题的另一种VNS启发式方法。资源受限的项目调度问题也通过使用本地分支得到了解决。唯一的例子是Zhu、Bard和Yu(2006)将局部分支与特殊的变量约简方法相结合。Rodriguez-Martin和Salazar-Gonzalez(2010)证明了与解决网络设计问题的最佳相关启发式相比,局部分支具有优越性。

3数学公式

本研究中考虑的数学公式与opmpsp版本相关,该版本涉及预先确定的截止品位、最低采矿和加工要求以及最大容量限制。每个块只需要一个时间段来提取,由于实际的实现问题,不能部分删除。opmpsp的公式如下:

设置和参数

B ={1,hellip;,hellip;,B}块的集合

L ={1,hellip;,L}矿石块集

W ={1,hellip;,,W}一组废块

T ={1,hellip;,T}时间周期集

——b块的直接前辈集

——b座吨位

——最大开采能力(吨)

——最低开采量(吨)

——最大处理量(吨)

——最低加工要求(吨)

——从b块得到的净现值

决策变量

如果在时间段t内删除了块b,则为1;否则为0

数学模型

主题:

主题目标函数寻求NPV的最大化。

约束(2)确保在前一个块之前不提取任何块。

约束(3)保证在每个时间段内满足最小开采要求,不超过最大开采能力。

约束(4)对每个时间段中处理约束的下限和上限执行相同的任务。

约束(5)确保只在一个时间段内删除每个块(如果有的话)。

式(6)是一个二元约束。

4解决方案方法

在这一节中,我们提出了基于局部分支技术和一种新的自适应分支方案相结合的方法。在第一部分中,我们简要地描述了局部分支并解释了我们使用它的方式。在第二小节中,我们开发了一个自适应分支方案来与局部分支结合,在下面的小节中,我们将提出我们的方法。

最后,提出了一种启发式的生成启动算法解决此方法,以提高其效率。

为方便阅读,本节所使用的符号摘要如下:

符号

全文共21268字,剩余内容已隐藏,支付完成后下载完整资料


资料编号:[755]

原文和译文剩余内容已隐藏,您需要先支付 30元 才能查看原文和译文全部内容!立即支付

以上是毕业论文外文翻译,课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。