Advanced Ore Mine Optimisation under Uncertainty Using Evolution

Evolutionary algorithms provide great flexibility in dealing with a wide range of optimisation problems. This includes highly constrained problems as well as problems involving dynamic and/or stochastic components. Their wide applicability has made evolutionary computing techniques popular optimisation techniques in areas such as engineering, finance, and supply chain management [2].

The area of mining where the goal is to extract ore in a cost efficient way poses large scale optimisation problems, and evolutionary computation techniques have successfully been applied in this area [1, 19, 21, 6]. We consider the problem of mine planning and focus on uncertainties which highly impact the mine planning process. Mine planning is one of the key optimisation problems in mining and a wide range of approaches have been developed over the years. The classical article of Lerchs and Grossmann [11] introduced the basic problem formulation and provided a dynamic programming approach. Over the years, a wide range of mine planning approaches taking different characteristics of this important real-world optimisation problem into account have been studied in the literature. This includes integer programming approaches based on block scheduling [16, 12] and heuristic techniques that are able to deal with various characteristics such as uncertainties of the problem [5, 15, 10]. Different software products for carrying out mine planning and extraction sequences are available [13, 14].

We discuss the mine planning problem in the light of Maptek’s mine planning optimisation software Evolution [13] which builds on evolutionary computing techniques. Evolution is representative of a new breed of commercially available algorithmic approaches to mine planning. One of the key features that set it apart from similar market offerings are its ability to handle large, complex data sets. Algorithmic mine planning solutions are typically offered in two streams. The first being a linear programming approach that attempts to simplify complex models into linear relationships. The second utilise evolutionary algorithms, which can model non-linear relationships and arbitrarily complex constraints, where the results are considered near-optimal. Evolution is an example of the latter category, and is increasingly being used by large mining corporations globally for their life-of-mine extraction sequences.

We introduce and evaluate a new approach which allows the effect of uncertainties in the source geological data on which extraction sequences are based to be economically quantified. In mine planning the classical goal is to maximize net present value (NPV) over the life of the mine. This optimisation task involves deciding on whether to process given blocks of minerals based on the predicted amount of ore it contains. As the information on ore concentration can only be obtained by complex drilling processes the information about the grade of ore is highly uncertain for most of the material that needs to be considered. In our approach, uncertainty quantification is done by an ensemble of neural networks that predict the grade of ore in the different blocks that should be processed. We have integrated our approach into the latest software release of Evolution.

A crucial part when running the Evolution software is the staging of blocks. This process divides the mine planning task into different stages that are processed sequentially. Given that the number of blocks is very large, usually in the hundreds of thousands, the staging process enables an efficient optimisation process by constraining the time at which a block can be processed. On the other hand, the staging heavily influences the quality of the solution to be obtained overall and at different periods in the extraction sequence. We exemplify this by showing different staging setups and the resulting profits that are obtained in the periods of a mine plan. Furthermore, staging has the potential to deal with uncertainties as it is possible to combine certain and uncertain areas of the mine into a stage which can lead to a reduction in the overall uncertainty in critical time periods of the life of a mine. Our experimental investigations explore the uncertainty of typical mining schedules and compare the impact of different staging approaches on NPV and uncertainty in the different time periods of the life of a mine.

The paper is structured as follows. In Section 2 we define the problem and describe the mineral resource block model. Afterwards, we present Maptek’s Evolution software in Section 3 and introduce uncertainty qualification based on ensembles of neural networks in Section 4. In Section 5, we discuss the implications of staging on optimised solutions. We present our experimental results on uncertainty quantification and staging in Section 6. Finally, we discuss important open problems and research gaps, and finish with some concluding remarks.

The open-pit mine production scheduling problem, known as the open-pit mine block sequencing problem, is an important problem in open-pit mine planning as it determines the material that contributes to the sustainable utilization of mineral resources over the life of the mine [8]. The overall goal is to find an optimal extraction sequence maximizing net present value (NPV). Decisions on block scheduling in the open-pit mine production scheduling problem have to take into account several constraints [7, 8, 4]. The set of constraints includes amongst others blending constraints, stockpile related constraints, logistic constraints, mill feed and mill capacity, reserve constraints and slope constraints.

In the following, we describe a basic model of the open pit scheduling problem similar to the one given in [20] and it should be noted that the actual implementation might require the consideration of additional constraints and/or variations of the objective function. A block model is given by a set of blocks $B$ and a set of destinations $D$. Each block $i\in B$ has a certain number of parameters such as density, tonnage, ore grade, etc. These parameters permit to determine the economic value of every block $i\in B$ at a given time. We denote $T=\{1,\ldots,t_{\max}\}$ the set of time periods where $t_{\max}=|T|$ is the number of time periods. For each block $i\in B$ we assume a revenue of $r_{i}^{t}$ and a cost $c_{i}^{t}$ if block $i$ is sent at time $t$ for processing. On the other hand it encounters a mining cost $m_{i}^{t}$ if it is send to waste. In addition, the slope requirements for the set of blocks and other mining constraints are described by a set of precedence constraints $P$ as follows. The pair $(i,j)\in P$ describes a scenario where a block $i$ must be extracted by time $t$ if block $j$ needs to be extracted at time $t$. More precisely, $P$ is the set of precedence constraints, $i$ → $j$ if $(i,j)\in P$, block $i$ a has to be mined before block $j$.

The value $(r^{t}_{i}$ - $c^{t}_{i})$ is given for each block $i\in B$ at time $t\in T$ in the case if the block $i$ is sent to processing plant, and produces a cost $m^{t}_{i}$ if the block is sent to waste dump. We denote by $\tau_{i}$ the tonnage of block $i$. For each period $t$ maximum limits $M^{t}$ on the amount of material that can be mined are imposed. Similar, for each period $t$ the maximum processing capacity $P^{t}$ i.e., the amount of ore that is milled have to be met.

In our model we use two types of decision variables for each block $i\in B$ and time $t\in T$. The first type are the variables associated to the extraction for processing purposes for each block. A binary variable $x^{t}_{i}$ is one if block $i$ is extracted and processed in the period $t$ and zero otherwise. The second variable type describes the decision relating to the disposal of a block by sending it to the waste dump. The binary variable $w^{t}_{i}$ is one if block $i$ is extracted and sent to waste in the period $t$ and zero otherwise.

In this formulation, the objective function (1) seeks to maximise the net present value of the solution (NPV) based on the a given discount rate $d$. Constraints (2) ensures that is not possible to choose two different destinations for a block $i$ and that a block is only chosen at one point in time. Crucial constraints are the precedence constraints (3) which determine the extraction process of each block $i$ from surface down to the bottom of the ore deposit. In order to provide for access and the stability of the pit walls it is not possible to mine a given block in a given time in the case that blocks in a defined pattern above have not already been extracted. The the mining constraints (4) ensure that the total weight of blocks mined during each period do not exceed the available extraction equipment capacity i.e., the mining capacity. Similarly, the amount of material that can be processed in each period is restricted by the processing constraints (5).

The simplified mathematical model can be summarized as follows:

There can be a number of additional supporting constraints, such as policies around stockpiling and product blend. Stockpiling is the process of storing mined material that will eventually go through the processing plant, but is deferred for mill capacity or economic reasons. Product blend constraints are used to ensure processed material meets a minimum grade, and can result in the schedule reflecting simultaneous mining from different areas of the pit, or using lower grade material from stockpiles to achieve a target grade. These have not been reflected above as they are not always required.

Evolution is a suite of products offered by Maptek that provides scheduling engineers with tools to produce optimal extraction sequences constrained by many practical considerations. These products work together to collectively span multiple time horizons, ranging from:

• •

  life-of-mine: yearly scheduling showing returns for an entire mine’s life.

• •

  medium term: monthly scheduling used to optimise extraction sequence and equipment for a portion of the mine’s life.

• •

  short term: operational scheduling used to inform daily operations on required material volumes and grades, as well as assign given equipment to specific tasks.

For the purpose of our investigation, Maptek Evolution Strategy was used. Strategy is used for life-of-mine economic optimisation that aims to maximise net present value of the resource (NPV) by optimally ordering the stage/bench extraction sequence. It employs a dynamic cut-off grade policy for both the stockpiling and wasting of material.

Strategy’s only required input is a block model as described. Along with the block model, Strategy requires yearly mining capacities and yearly plant capacities, as well as costs for mining, processing and selling the target ore. The optimisation weighs the cost of mining against the value of the ore being sold, dynamically choosing on a per stage per bench basis when and how to best handle material to maximise economic returns.

Strategy employs evolutionary algorithms to perform this optimisation. A dynamic cut-off grade policy introduces non-linearity into the optimisation and evolutionary algorithms require no compromises to handle this. The algorithm has been shown to perform robustly in acceptable time frames on very large whole-of-mine sized resource models. Another strength of an evolutionary algorithm approach is that the best solution is available at any given point in the run time. This means that a solution can be inspected for a given computation budget and released as ’good enough’ without requiring guaranteed optimality.

Strategy is designed to always produce valid solutions. A valid solution adheres to precedence and capacity constraints. Mutation and crossover operators are designed to preserve these constraints so provided seed genomes produce sequences that exhibit them, then the evolutionary algorithm will preserve them during selection and generation. A feasible solution is not only valid, but also practical and economically viable to mine. This will typically require cash flows to remain positive after an initial start-up and with material movements aiming to consistently utilise mining equipment at or near full capacity.

A feasible solution isn’t always the solution with the highest NPV for the resource model. This is because not all economic considerations are captured in this value. For example, solutions with periods of negative cash flow may make financing the operation infeasible even if this is for the benefit of larger future profits in net present terms. In this situation a solution that evens out revenues in each period will be considered feasible compared with another that may have a higher NPV.

Staging - the assignment of stages to divide the block model into sequentially mined subsets of blocks - is required by Evolution. It is used extensively in traditional manual scheduling but is also a useful tool to preserve feasibility whilst optimising for NPV. Staging is a discrete process and has a non-linear effect on NPV. Variability in the assigned domain of blocks and the ore grade within them also has a non-linear effect on the NPV of a given extraction sequence and this aspect is now able to be explored in the software from the work presented here.

A mineral reserve block model is inherently uncertain because the estimations of ore grade in each block are derived from samples obtained by drilling into the rock and the spacing of drilling is typically much wider than the block resolution. Many interpolation methods exist for combining samples in the local neighbourhood of a block to estimate its grade value. Those with a basis in geological processes are favoured. These methods typically involve a categorisation of the rock mass into lithological domains. Such domains typically delineate separate mineralisation processes that have occurred under different physical conditions, such that the formation of ore and its concentration in one domain is considered independent to that in another. The domain classification then guides the choice of samples and the weight to give to them in a geostatistical interpolation method such as Kriging [9] or inverse distance weighted averaging [22] to derive an estimate of the grade for each block in the block model.

Quantifying the uncertainty of any estimation process involving domains is complicated to do analytically because complex 3D geometries are often involved with the interfaces between domains [3, 17]. Conditional simulation is a commonly used technique in geostatistics to quantify the geological uncertainty in a multi-domain reserve block model [18]. This method can be thought of as a sensitivity analysis of grade value estimations and their distribution throughout the model based on varying one or several of the parameters involved in one or several geostatistical interpolation methods. The range through which to vary the parameters and the methods to include in the simulation are all subject to qualitative choices and are difficult to approach for a novice in the field.

Here we employ a simpler technique to quantify the locations and ranges of uncertainty which has been introduced in [23]. The method produces data that is adequate to illustrate the economic sensitivity of different extraction sequences based on the spatially varying uncertainty that arises from a population of different interpolations of the input sample data. The method simultaneously allows variation in lithological domain boundaries and grade distributions within the domains to be explored. The approach in summary is to train a deep neural network to fit the input sample data in its three spatial dimensions, an arbitrary number of continuous dimensions corresponding to grades of elements of interest and a categorical dimension corresponding to the domain. The fit is performed from random starting weights and employs standard deep learning model fitting techniques based on gradient descent to minimise a differentiable error function until the goodness-of-fit is within a specified tolerance. By exploiting the property of such networks to converge on a set of weights from different random initialisations, we compute an ensemble of trained networks that statistically interpolate the input data equally well.

Maptek’s DomainMCF machine learning geological modelling software was used to produce an ensemble of ten models based on this technique. These models are then evaluated into each block in a block model to produce a population of grade and domain estimates for each block. These ensembles are the basis for quantifying the economic uncertainty of optimised extraction sequences.

Staging is an important component that serves as an input to Evolution. It divides the optimisation problem into stages that are processed sequentially. Staging is therefore a partitioning of the given set of blocks $B$ into stages $S_{1},\ldots,S_{k}$ where each block in stage $S_{i}$ is processed before each block in stage $P_{j}$ iff $i<j$. For the given partitioning $S_{i}\cap S_{j}=\emptyset$ iff $i\not=j$ and $\cup_{i=1}^{k}S_{i}=B$ is required. In practice, the requirement of processing a stage completely before starting the next one is not strict and there might be some time overlaps in processing different stages. Note that a trivial staging is obtained by using only one stage $S_{1}$ and setting $S_{1}=B$ which implies that all blocks belong to the same stage. The drawback of this is that all blocks have to be considered at the same time which does not break down the optimisation problem. Furthermore, benches are scheduled completely in a single stage and breaking benches down by dividing them into different stages can lead to better overall solutions.

Several methods have been proposed that do not use staging in mine optimisation and schedule blocks directly. These are collectively known as direct block scheduling methods. They remain an active area of research because they still have not solved the benefits afforded by staging methods around some aspects of practicality even though they may yield an extraction sequence of higher NPV. For example, staging methods inherently create a controlled number of active mining areas and so afford a direct means of localising where equipment needs to be and where it needs to go next on relatively long time frames. This enables roads to be constructed in time and without interfering with other passages, distances over which equipment needs to be moved to be minimised and other similarly advantageous considerations for practical mining. Direct block scheduling methods require explicit constraints to gain these advantages and without them will often result in extraction sequences that involve mining small pockets of material from impractically distant locations.

Staging helps to take a problem from hundreds of millions of variables into a few hundred that can be optimised with complex non-linear relationships. It introduces practical constraints on the order of blocks in a schedule. Strategy uses stages and considers combinations of stage and bench. A stage and bench combination is all the blocks that share the same stage and position on the Z axis (the bench). When considering what blocks to mine in each period, the optimisation process will sum the values of each block in a stage and bench and mine it in one large chunk. Without staging, Strategy would be forced to mine the entirety of each bench before moving on. This will result in significant mining of waste before any ore could be reached. In effect, staging allows high value ore to be targeted early on in the process, leaving the movement of waste from other stages to later in the process.

The creation of these stages are used as a loose guide for a logical mining sequence. Typically, stage $1$ will be mined before stage $2$, but there will be some overlap. As mining hits ore in stage $1$, the start of stage $2$ - which will often be removal of waste blocks to get to future ore blocks - would begin. This simultaneous mining of ore and waste in stages ensures a consistent positive cash flow. Through the process of staging, a number of practical mining rules are adhered to. There is an assumption that a completed stage design will follow some basic mining practices. These are - but not limited to - the rules outlined in Section 3 which Strategy uses to produce valid mining solutions.

Our approach on uncertainty quantification has been implemented into Evolution and is part of the latest software release. We now investigate the uncertainty of optimised solutions introduced by the neural network approach. We interpret the solutions obtained from a mine planning perspective in terms of economic risks associated with the obtained solutions. Furthermore, we investigate optimised solutions for different staging approaches and show that this leads to significantly different results.

We have presented an approach for visualizing and quantifying economic uncertainty in mine planning based on geological uncertainty derived from a neural network approach to obtain multiple interpolations of the same input data. The approach allows mine planners to consider the effects of what they do not know during crucial planning periods and possibly take manual steps to mitigate downside risk. We pointed out the impact of staging on solutions mine plans produced by Evolution. Our results were successful in showing how different staging mechanisms can effect NPV, as well as per-period uncertainty.

However, our results do not yet inform how an algorithm could be designed to assist with this. A manual approach to staging with the intent of spreading economic uncertainty over several periods as a way of mitigating its effect on feasibility is not conclusively beneficial. We maintain that this is a worthy goal of further research. Even if a staging approach is shown to reduce NPV, if it can conclusively and consistently be shown to mitigate the economic effects of geological uncertain using this problem model it will likely be an attractive alternative for mining operations and investors alike.

We now discuss important challenges when facing the optimisation of extraction sequences in the face of geological uncertainty in the context of using the Evolution Strategy software. We concentrate on the problem of staging. Because the optimiser used in Evolution depends on the given stage design, an important problem is to formulate a stage design that leads to a high quality schedule: in terms of maximising NPV, in terms of feasibility and now also in terms of economic mitigation of geological uncertainty. The overall goal - a remaining open problem - is to produce stage designs in an automated way that lead to feasible extraction sequences exhibiting high NPV compared with others and low economic uncertainty in critical periods of the mine plan.

From our tests we drew a number of insights. The first observation is that uncertainty in our setting can be split into two categories: domain uncertainty and grade uncertainty. Domain uncertainty typically manifests by a block switching domain between different members of the ensemble. This effect would appear to have little influence on economic uncertainty. The impact of uncertainty observed in our experimental results is primarily related to grade uncertainty. Uncertainty in ore grade around the cut-off grade has a considerable effect on NPV. Most mines are scheduled based on their minimum cut-off grade, meaning there are typically large reserves of ore at or near the cut-off grade. If this ore was to fluctuate in grade by even a fraction of a percent, it could then be classified as waste. The effect of this re-classification is non-linear and can result in tens of millions of dollars being lost in unprofitable mining. This suggests that uncertainty around ore near the cut-off grade has a considerable effect on NPV.

Lastly, our attempts to level out uncertainty showed that in order to level out highly uncertain high grade ore, it needs to be matched with an equal amount of highly certain, high grade ore. It could also be matched with a large deposit of highly certain low to medium grade ore. This suggests that it is not just grade, but also tonnage that needs to be considered when attempting to even out uncertainty across a schedule. Further work is required here.

It would be very valuable to design automated staging approaches that lead to a feasible extraction sequence with a high NPV while minimizing the risk associated with geological uncertainty. An avenue for future work is to take the quantified economic effect of uncertainty presented here into the fitness function used as part of the evolutionary algorithm optimiser in Strategy. It could do this by processing the full ensemble simultaneously. Additional constraints around the uncertainty for critical time periods could be introduced that prevent the mine plan from having a high uncertainty around low cash flow periods where an unexpected negative cash flow could financially jeopardise the operation.

Mine planning poses challenging and complex optimisation problems which involve high uncertainties due to the unknown grade of the ore that is mined. In this paper, we studied the uncertainty around Maptek’s mine planning software Evolution and provided a way to quantify uncertainty based on ensembles of neural networks. We have pointed out how this can be used to assess the risks associated with a given mine plan. Furthermore, we investigated the impact of staging which is provided as an input to the mine planning algorithm and have shown how staging can be used to influence the resulting solution in terms of NPV and uncertainty.

This research has been supported by the SA Government through the PRIF RCP Industry Consortium.