New Tabu Algorithm for Positioning Mining Drillholes with Blocks Uncertainty

Abstract

This paper proposes a new approach to the mining exploration drillholes positioning problem (DPP) that incorporates both geostatistical and optimization techniques. A metaheuristic was developed to solve the DPP taking into account an uncertainty index that quantifies the reliability of the current interpretation of the mineral deposit. The uncertainty index was calculated from multiple deposit realizations obtained by truncated Gaussian simulations conditional to the available drillholes samplings. A linear programming model was defined to select the subset of future drillholes that maximizes coverage of the uncertainty. A Tabu Search algorithm was developed to solve large instances of this set partitioning problem. The proposed Tabu Search algorithm is shown to provide good quality solutions approaching 95% of the optimal solution in a reasonable computing time, allowing close to optimal coverage of uncertainty for a fixed investment in drilling.

Introduction

In mining exploration, the drillhole positioning problem (DPP) emerges from the need to accurately plan future definition drillholes whose objective is to improve the current knowledge on an underground mineral deposit. The solution to this problem requires tools from geostatistics to model our current (lack of) knowledge of the deposit and from optimization to optimally select future drillholes such as to maximize knowledge of the deposit.

The classical geostatistical approach consists mainly in subdividing an exploration field into blocks that are classified according to their estimated mineral content and estimation accuracy. Future drillholes are planned with some amount of subjectivity by placing new drillholes next to the blocks of interest, targeting areas with moderate or low confidence blocks (indicated or inferred resources). This approach does not necessarily ensure a cost effective drilling campaign. The same unique drillhole may simultaneously cover different categories of blocks (and blocks already covered by other planned drillholes), so that it is hard to assess its real value. New drilling campaigns will not necessarily bring additional interesting information if not planned methodically using a holistic approach. Furthermore, uncertainty of the blocks or uncertainty on the mineral envelope (surface) needs to be methodically quantified using a reliable measure and a more rational approach. Dimitrakopoulos (1998) proposed an uncertainty evaluation based on the generation of equiprobable mineral deposits using conditional simulations. However, this approach was not used for future drillholes selection. Some authors proposed several approaches related to surface uncertainty on mesh grids (Surazhsky et al. 2003; Fuhrmann et al. 2010) but few are actually applicable to mineral deposits where forms and surfaces are often not smooth and irregular, with unexpected or unknown topology. Several approaches propose the kriging variance as an indicator of block uncertainty, and thus a criterion for drillhole targeting (Saikia and Sarkar 2006; Soltani-Mohammadi et al. 2012). However, the kriging variance is only dependent on the spatial configuration distance between blocks and existing drillholes—and not on the actual sampling results observed (Yamamoto 2000). Yamamoto et al. (2014) proposed a method to reduce geological uncertainty in a 3D block model using resampling and post-processing of the block model. Although this method can improve the accuracy of the geological interpretation, it is still limited to the amount of current samplings and does not address the question of optimal location of future drillholes. Soltani-Mohammadi and Safa (2018) proposes an uncertainty index combining kriging variance and average estimation variance at local sampled blocks; this is still subject to the limitations of kriging variance as an uncertainty index.

In our approach, a block can be either barren or mineralized, the state of each block being known with confidence level that is function of available drillholes in the block neighborhood. A different formulation of block uncertainty is proposed, which is based on the probability of the block being mineralized and calculated using geostatistical simulations, similar to Dimitrakopoulos (1998).

The optimization approach usually aims at selecting the best subset of possible drillholes that maximizes spatial coverage of the blocks (i.e., overall proximity between drillholes and blocks) using several optimization techniques such as genetic algorithms (Soltani et al. 2011), simulated annealing (Soltani-Mohammadi et al. 2012; Pinheiro et al. 2017), Tabu Search (Bilal et al. 2013) or particle swarm optimization (Ding et al. 2014; Soltani-Mohammadi et al. 2016). In most of these approaches, the blocks are not differentiated in terms of potential content and the current available information is most of the time ignored or unused.

Saikia and Sarkar (2006) in an application for a coal mine exploration proposed an optimization algorithm to minimize the total kriging variance by increasing/reducing the number of drillholes and the distance between the drillholes. A limitation of this approach (beside using the kriging variance as an uncertainty criteria as discussed earlier) is that it considers only vertical and even spaced drillholes. Soltani et al. (2011) used a metaheuristic (genetic algorithm) to find the position and length of a predefined number of drillholes. In this approach, information from existing samplings is not taken into account and there are other limitations such as the verticality of the drillholes and their predefined quantity. Soltani and Hezarkhani (2013) later completed this approach with drillhole inclination capability, but the number of drillholes was still predefined. Bilal et al. (2013) reformulated the DPP as a set covering optimization problem and proposed a Tabu Search metaheuristic that searches the best subset of drillholes (from several collar points with various dip angles and lengths) that maximizes the block coverage. This approach was comprehensive from an optimization perspective; however, the existing information from earlier samplings was not fully taken into account. Only the proximity of the closest drillhole was used to measure coverage, ignoring joint collaborative information provided by sets of close drillholes possibly just slightly further from the uncovered block.

Recent research has started to combine geostatistical simulations and optimization algorithms to plan new drillholes ; however, most methods are limited to vertical drillholes or do not consider the commonly adopted fan drilling in advanced exploratory phase where several drilling orientations are adopted from a single drill position. Ding et al. (2014) applied a modified particle swarm optimization algorithm along with a quality map representing production potential to find additional oil wells placement, but that approach is once again only applicable to vertical boreholes. Morshedy and Memarian (2015) tackled the vertical drillhole placement limitation by proposing a method that aims at identifying the best potential drillholes with dip angles using concentric cones around several potential collar points. However, the objective function used was based on kriging variance, which as an uncertainty criterion does not take full advantage of existing sampling results. Soltani-Mohammadi et al. (2016) used indicator kriging to produce a probabilistic index map that was used to define an objective function for the DPP optimization part done using simulated annealing and particle swarm algorithms. However, they considered only vertical drillholes with predefined depth. Pinheiro et al. (2017) used several realizations of geostatistical simulations, the Turning Band Method (TBM) algorithm, to define an uncertainty variable (local variance of simulated values or average width of simulated values 95% probability intervals). An optimization metaheuristic (simulated annealing) is then applied to select the number and the location of the future drillholes, which are represented by vertically aligned points. The same limitation (vertical drillholes) is found in Soltani-Mohammadi and Safa (2018), where an astute approach is proposed to decrease the calculation time by prioritizing uncertain blocks and particle swarm optimization algorithm is used to determine the location of additional drillholes.

The geostatistical methodology proposed in this research is similar to the approach in Pinheiro et al. (2017); however, the optimization problem is formulated differently (defined here as a partial set covering problem) allowing for a more precise definition of drillholes, taking into account several orientations from different drilling positions. The optimization approach proposed in this research is based on Bilal et al. (2013). A new uncertainty index is calculated using geostatistical methods (TBM simulations). This index permits to discriminate the blocks. More specifically, the uncertainty index assigned to each block was computed using a series of deposit realizations conditional to the available drillholes samplings, as in Dimitrakopoulos (1998). Blocks appearing always in the simulated deposit or always out of the simulated deposits receive a low uncertainty index value. Deposit realizations were obtained using a truncated Gaussian simulation method (Armstrong et al. 2011). The optimization process, which consists of solving a linear program, selects a subset of drillholes maximizing uncertainty coverage. A Tabu Search algorithm is finally proposed to solve heuristically large instances of this optimization problem.

Methodology

Definition of the Uncertainty Index

The first step consists in calculating, for each block, an uncertainty index representative of the current level of confidence we have on the nature of a block. This is done using geostatistical simulation.

Let us consider an existing (yet unidentified) mineral deposit in an exploration field. The field is subdivided into a set U of n three-dimensional blocks $(n=|U|)$. Let x be a variable identifying each block. Similar to Wellmann et al. (2010), we define I(x) as the deposit indicator function at block x, also called geological facies. We assume, for simplicity, that each block can only be fully inside ($I(x)=1$) or outside ($I(x)=0$) the deposit.

A subset $\Omega$ ($\Omega \subset U$) of m blocks are already sampled by existing drillholes ($m=|\Omega |$). The value of I(x) is known for each of these sampled blocks ($x \in \Omega$) and unknown for all the other blocks. For simplicity, we designate blocks belonging to the sampling group $\Omega$ by the variable $x^*$ ($x^*\equiv x \in \Omega$). Given the current information from the sampled blocks in $\Omega$, we seek the likelihood of each other block x to be in the deposit. Let p(x) denote the probability $p(x)=P(I(x)=1)$. For sampled blocks $x^*$ ($x \in \Omega$), $p(x^*)=1$ if block $x^*$ is in the deposit, and $p(x^*)=0$ otherwise. The variable p(x) is initially unknown for all the non sampled blocks $x \notin \Omega$.

p(x) is the expectation that a certain block x is in the deposit or not. The confidence in the state of block x is strong for blocks having high p(x) values (close to 100%) or low p(x) values (close to 0%). Inversely, the confidence is minimal for blocks with average p(x) values (close to 50%) as each facies is then equally likely. We can expect that a block close to a sampled block will be similar. However, the prediction is difficult when a block is far from any existing drillhole or close to two dissimilar blocks (inside and outside the deposit).

We can define p(x) as the success probability of a Bernoulli trial. The variance of the Bernoulli random variable is $u(x)=p(x)[1-p(x)]$. Note that u(x) is maximal for $p(x)=0.5$ and minimal for $p(x)=0$ or $p(x)=1$. We use u(x) as the uncertainty index. The goal is to assess u(x) for all blocks based on the knowledge we have on the current sampled blocks.

The proposed method to calculate u(x), $\forall x \in U$, consists in simulating many realizations of the deposit displaying the same facies as the real deposit in sampled blocks. For each unsampled block, the proportion of realizations showing deposit facies will be used as an estimate of p(x) from which u(x) can be computed. Among the numerous methods that can be used to simulate spatial binary field, we choose the truncated Gaussian approach (Armstrong et al. 2011) for its efficiency and simplicity. The method requires to define a latent Gaussian variable that, upon truncation, recovers the observed facies at sampled points. It involves the following four main steps, which are detailed in subsequent subsections:

• Select a variogram model for the latent Gaussian variable that is representative of the spatial continuity of the facies indicator variable $I(x^*)$ of already sampled blocks, based on existing drillholes.

• Simulate using a Gibbs sampling algorithm the latent Gaussian variables at sampled blocks. One different set is produced for each realization.

• For each set of latent Gaussian values in sampled blocks, generate one conditional realization at all unsampled blocks. Each conditional realization is a plausible interpretation of the deposit compliant with the observed facies at sampled blocks and the variogram model of the latent Gaussian. This is achieved using TBM simulations (Chilès and Delfiner 2012).

• For each block $x \in U$, calculate p(x) and u(x) as the mean and variance of the facies simulated for block x in the different realizations.

Selection of the Latent Gaussian’s Variogram Model

A variogram noted $\gamma (h)$ is a function that characterizes the spatial correlation between random variables separated by distance vector h. There are many different theoretical variogram models described in the literature : spherical, cubic, exponential, etc. (Chilès and Delfiner 2012). For simulation purposes, we have to select and use a theoretical variogram model $\gamma _{th}(h)$ that best fits the experimental indicator variogram of the facies observed in sampled blocks.

First, we calculate an experimental variogram $\gamma _{\exp }(h)$ from the observed facies in sampled blocks:

$$\begin{aligned} \gamma _{\exp }(h)=\frac{1}{2|N(h)|} \sum _{\forall (x_i,x_j)\in N(h)}[I(x_i)-I(x_j)]^2 \end{aligned}$$

(1)

where h is the separation vector, N(h) is the set of pairs of blocks separated by vector h, |N(h)| is the cardinality of the set.

The stationary latent Gaussian variable has unit variance and covariance $\rho (h)$. A threshold c is applied to define the deposit facies. Given $E[I(x)]=p$ one finds $c=F^{-1}(p)$ where $F^{-1}$ is the Gaussian inverse-cdf, p is the proportion of blocks in deposit, $1-p$ is the proportion of barren blocks. Then, the theoretical facies indicator variogram is given by Chilès and Delfiner (2012):

$$\begin{aligned} \gamma _{ {Ind}}(h)=p(1-p) - \frac{1}{2\pi } \int _{0}^{\rho (h)}\exp \left( -\frac{c^2}{1+u}\right) \frac{1}{\sqrt{1-u^2}}{\mathrm{{d}}}u \end{aligned}$$

(2)

The model type and parameters of p(h) are selected such that $\gamma _{ {Ind}}(h)$ is as close as possible to $\gamma _{\exp }(h)$. For this, a least square criterion can be used.

Gibbs Sampling of Gaussian Values at Sampled Blocks

The Gibbs sampling algorithm is a Markov Chain Monte Carlo algorithm. Let $Z^t(x^*)=[Z^t(x_1^*), Z^t(x_2^*) \cdots Z^t(x_m^*)]$ be a Markov chain representing the Gaussian values assigned to sampled blocks at iteration t of the Gibbs sampling. We start with $Z^0(x^*)$ by assigning a random Gaussian value to each block that respects the threshold corresponding to the blocks facies:

$$\begin{aligned} \forall x\in \Omega (\equiv \forall x^*) \left\{ \begin{array}{lc} I(x^*)=1 \Leftrightarrow Z^0(x^*) \in ]-\infty ,c]\\ I(x^*)=0 \Leftrightarrow Z^0(x^*)\in ]c,+\infty [ \end{array}\right. \end{aligned}$$

(3)

The Gibbs sampling consists, for each block, to draw a value from its conditional distribution. As soon as a new value is obtained, it replaces the old one and the new value is used to estimate the conditional distribution of the next block. An iteration is completed when all blocks have been visited once.

Because the field is truncated Gaussian, the conditional distributions are also truncated Gaussian. An easy way to sample from a truncated Gaussian distribution is to proceed by acceptance/rejection (Freulon and de Fouquet 1993). We compute the Gaussian conditional distribution by simple kriging and draw a value from this distribution. If the Gaussian value falls in the right interval for the observed facies, it is accepted, otherwise we keep the old value. In either case we proceed to the next block.

$$\begin{aligned} \begin{aligned}&{\mathbf{Gibbs\,sampling\,algorithm }}\\&1: Z^0(x^*)=[Z^0(x_1^*),Z^0(x_2^*)\cdots Z^0(x_m^*)]\, {\text {(Initial\, random \,drawing)}}\\&2: t=1 \cdots T\\&\qquad 2.1: {\text { Define\, a\, random \,order \,to \,visit \,the }}\,{m}\,{\text { known \,blocks}}\\&\qquad 2.2: k=1 \cdots m\\&\qquad \quad \quad {\textit{Value}} = {\textit{RandomDrawing}}()\sim N(Z_{kr}^*,\sigma _{kr}^{2}),\\&\qquad \qquad {\text {If }}[({\textit{Value}} \le c){\text { and }}I(x_k^*)=1] {\text { or }}[({\textit{Value}} > c){\text { and }}I(x_k^*)=0]\\&\qquad \qquad \quad \quad Yes: Z^t(x_k^* )={\textit{Value}}\\&\qquad \qquad \quad \quad No: Z^t(x_k^* )=Z^{t-1}(x_k^* )\\&3: {\text {Return }} Z^T(x^*) \end{aligned} \end{aligned}$$

where $Z_{kr}^*$ and $\sigma _{kr}^{2}$ are the simple kriging prediction and associated kriging variance at $x_{k}^*$.

Many iterations may be required before convergence to the desired joint distribution (histogram and variogram) is reached. The Gibbs sampling is stopped when a preselected maximum number of iterations is reached. The Gibbs sampling process goes through a burn-in phase when the values are gradually matching the assigned variogram model, as shown by Cuba et al. (2012). Once the burn-in phase is finished, the process enters a stochastic phase or random phase, during which there is no substantial improvement in the resulting joint distribution (in terms of matching the desired distribution). The process should always have enough iterations to ensure that the burn-in phase is finished.

Several authors such as Chen et al. (2004), Lyster and Deutsch (2008) and Reza Najafi and Moradkhani (2013) have attempted to find generalized stopping criteria to the Gibbs sampling process. Most were unsuccessful or at best only useful in their specific context. Onibon et al. (2004) concluded that the issue with many stopping criteria or techniques is that they are not reliable and are costly in computational time. Similar to Emery (2007), we monitored the convergence by following the evolution of the resulting histograms and variograms after each iteration. The selected number of iterations was chosen large enough to ensure that the burn-in phase has ended.

The whole Gibbs sampling process is repeated r times starting from different sets of initial values ($\{Z_1^0,\cdots Z_r^0 \}$) to obtain as many independent chains ($Z_1^{T} \cdots Z_r^{T}$) of $m=|\Omega |$ Gaussian values that are consistent with the assigned theoretical variogram model. Each independent final chains serve as conditioning input for one realization of the facies field providing r conditional realizations.

Simulation of Facies at Each Block

Having a set of Gaussian values for the sampled blocks, the next step consists in performing a geostatistical simulation of facies for each block in the field. There are several simulation methods applicable to Gaussian fields such as the LU Decomposition, the Sequential Gaussian Simulation (SGS) method, the Fast Fourier Transform (FFT) method and the Turning Band Method (TBM). The TBM is used in this application because of its low algorithmic complexity (O(n)) and its applicability on very large grids. A detailed description of the TBM can be found in Chilès and Delfiner (2012) and Emery (2006). The TBM creates a Gaussian random field with the desired covariance $C_3(h)$ in $R^3$ by simulating a process in $R^1$, along lines, with covariance $C_1(h)$ as given by Chilès and Delfiner (2012):

$$\begin{aligned} C_1(h)=\frac{{\mathrm{{d}}}}{{\mathrm{{d}}}h}[h C_3(h)] \end{aligned}$$

(4)

The Gaussian value simulated at block $x\in U$ is:

$$\begin{aligned} Z^{{ {unc}}}(x)=\frac{1}{|S|^{1/2}}\int _{S}Y(<x,v>) \mathrm{{d}}v \end{aligned}$$

(5)

where |S| is the surface of the unit sphere S and $Y(<x,v>)$ is the simulated value on line v at position $<x,v>$ corresponding to the projection of coordinate vector x on line v.

In practice, the integral is replaced by a summation over a sufficiently large number k of almost equally spread lines ensuring good coverage of the sphere.

$$\begin{aligned} Z^{{ {unc}}}(x)=\frac{1}{\sqrt{k}}\sum _{i=1}^{k}Y(<x,v_i>) \end{aligned}$$

(6)

The simulated Gaussian field (${Z^{{ {unc}}}(x) | x \in U}$) needs to be conditioned to Gaussian values $Z^T(x^*)$ obtained at sampled blocks in Gibbs sampling step. This is done using the method of post-conditioning by simple kriging (Chilès and Delfiner 2012):

$$\begin{aligned} Z^{{ {con}}}(x)=Z^{{ {unc}}}(x)+\left( Z^T_{kr}(x)-Z^{{ {unc}}}_{kr}(x)\right) ,\quad \forall x\in U \end{aligned}$$

(7)

where $Z^{{ {con}}}(x)$ is the Gaussian conditioned value at block x, $Z^T_{kr}(x)$ is the kriging prediction at block x using Gibbs values at sampled blocks ($Z^T(x^*)$) and $Z^{{ {unc}}}_{kr}(x)$ is the kriging prediction at block x using unconditional simulated values also at sampled blocks ($Z^{{ {unc}}}_{kr}(x)$). Notice that for sampled blocks $x^*$ this ensures $Z^{{ {con}}}(x^*)=Z^T(x^*)$.

The whole process (turning bands simulation + conditioning) is repeated r times, using each one of the r independent Gibbs chains as conditioning values. The conditioned Gaussian values ($Z_i^{{ {con}}}(x)$) are then converted back into simulated conditioned facies ($I_i^{{ {sim}}}(x)\in \{0,1\}$) using the same threshold c as in Eq. 3.

At the end of this step, each one of the r independent chains of conditioning Gaussian values leads to a different set of simulated blocks facies that forms a mineral deposit or realization. All the different realizations are possible interpretations of the real mineral deposit based on the sampled drillholes.

Calculation of the Blocks’ Uncertainty Index

For each block x, we now have r independent shots at a facies F(x) with only two possible outcomes: 1 (inside deposit) or 0 (outside deposit), as in a binomial process. We can now evaluate the probability p(x) of block x as the average value of the predicted value for block x in the realizations:

$$\begin{aligned} p(x)= P(I(x)=1)=\sum _{i=1}^{r}\frac{I_i^{{ {sim}}}(x)}{r},\forall x\in U \end{aligned}$$

(8)

For sampled blocks $x^*$, the facies probability is either 100% ($I(x^*)=1$) or 0% ($F(x^*)=0$) because $I_i^{{ {sim}}}(x^*)=I(x^*)$. The uncertainty index u(x) can be calculated as the variance of the binomial process:

$$\begin{aligned} u(x)={ {Var}}(I(x))=p(x)[1-p(x)] \end{aligned}$$

(9)

This index spans from 0.0 (p(x) = 100% or 0%) to 0.25 (p(x) = 50%). Each block of the field has an assigned uncertainty index. The index can be used to select future drillholes by favoring drillholes covering the zones with highest uncertainty index.

Optimization for Future Drillholes Selection

In this second part, an optimization model is proposed for selection of future drillholes. The optimization problem is formulated as an integer linear problem whose objective is to maximize coverage of the blocks’ uncertainty index. The rationale behind that approach is that from an exploration perspective, drilling in areas with high uncertainty would bring valuable information on the mineral deposit and reduce total uncertainty. A Tabu Search algorithm is proposed for large instances of this optimization problem for which an exact solution is hard to find.

The proposed approach is built on Bilal et al. (2013), who formulated the DPP as a partial set covering problem (with the objective of maximizing blocks coverage). The improvement in the current approach is that each block is now assigned a different weight (the uncertainty index) in the objective function that accounts for the information provided by all boreholes.

Definitions and Decision Variables

• Let ${\textit{UI}}_i$ designates the uncertainty index for block i (u(i)) as calculated in the first part of this work (calculation of the uncertainty index).

• The set of n blocks is still designated by U.

• Let $\Psi$ designates the set of all possible individual drillholes. We consider a finite number of $q=|\Psi |$ possible drillholes. Drillholes are defined by a collar point (position of the drilling machine) and a terminal point or terminal block. According to this definition, drillholes having the same collar point and orientation but only different length (or depth) are identified as different drillholes.

• A solution S is a subset of $\Psi$ and |S| designates the number of drillholes within the solution S.

• A block i is considered covered by a drillhole j if it is located within a certain distance (range) of the drillhole. The coverage index $cvr_j^i$ is defined as:

  $$\begin{aligned} {\textit{cvr}}_j^i=\left\{ \begin{array}{lc} {\text {1\quad if\, block\, }}\,i\,{\text { is\, covered \,by \,drillhole }} j\, ({\text {distance}}\,(i,j)\le {\text {range}})\\ {\text {0\quad otherwise}} \end{array}\right. \end{aligned}$$

• The block-drillhole coverage matrix $C=[{\textit{cvr}}_j^i|i\in U$ and $j\in \Psi ]$ is an input of this optimization problem.

• A block i is considered covered in a solution S when it is covered by at least one drillhole $j\in S$. We denote ${\textit{DH}}_i$ the subset of drillholes that covers block i:

  $$\begin{aligned} {\textit{DH}}_i=\{j\in \Psi |{\textit{cvr}}_j^i=1\} \end{aligned}$$

• $X_i$ is the decision variable associated with the coverage of block i, defined as:

  $$\begin{aligned} X_i=\left\{ \begin{array}{lc} {\text {1\quad if \,block\, }}i\,{\text { is\, covered \,by \,at \,least \,one \,drillhole \,of \,a \,solution }}S:\\ \quad \Rightarrow \sum _{j\in S} {\textit{cvr}}_j^i\ge 1\\ {\text {0\quad otherwise}} \end{array}\right. \end{aligned}$$

• $Y_j$ is the decision variable associated with the selection of a drillhole j, defined as:

  $$\begin{aligned} Y_j=\left\{ \begin{array}{lc} {\text {1\quad if\, }}j{\text { belongs \,to \,the \,current \,solution }}S\Rightarrow j\in S\\ {\text {0\quad otherwise}} \end{array}\right. \end{aligned}$$

• We denote ${\textit{BL}}_j$ the subset of blocks covered by drillhole j:

  $$\begin{aligned} {\textit{BL}}_j=\{i\in U|{\textit{cvr}}_j^i=1\} \end{aligned}$$

• $\hat{c}_j$ is the cost of drillhole j. As with the set of potential drillholes, the drillholes cost array $\hat{c}=[\hat{c}_j |j\in \Psi ]$ is an input to the optimization problem.

• $\hat{C}_{\max }$ is the maximal total drilling cost allowed (when applicable). A solution is considered acceptable if it satisfies the maximal cost constraint: $\sum _{j\in S}{\hat{c}_j} \le \hat{C}_{\max }$.

Linear Programming Model

The optimization problem can be formulated as an integer linear program that selects the subset of drillholes that maximizes coverage of the uncertainty index, for a given cost constraint (maximal drilling cost $\hat{C}_{\max }$):

$$\begin{aligned} \begin{array}{ll} {\displaystyle {\max \sum _{i\in U}} {\textit{UI}}_i X_i}&{}\\ {\text {Subject\, to:}}&{}\\ \displaystyle {\sum _{j\in \Psi }} \hat{c}_j Y_j \le \hat{C}_{\max } &{}\\ \displaystyle {\sum _{i\in {\textit{BL}}_j}} X_i \ge |{\textit{BL}}_j| Y_j, &{}\quad \forall j \in \Psi \\ \displaystyle {\sum _{j\in {\textit{DH}}_i}} Y_j \ge X_i, &{}\quad \forall i \in U\\ \quad X_i \in {0,1} &{}\quad \forall i \in U\\ \quad Y_j \in {0,1} &{}\quad \forall j \in \Psi \\ \end{array} \end{aligned}$$

(10)

The first constraint is the budget constraint. The second set of constraints ensures that if a drillhole j is selected, then all the blocks in ${\textit{BL}}_j$ are covered. The third set of constraints ensures that if a block i is covered, then at least one drillhole in ${\textit{DH}}_i$ is selected.

We can also define an alternative problem where the goal is to minimize the total drilling costs for a defined level $\alpha$ of uncertainty coverage (for example, we would like to cover $\alpha =90\%$ of the current uncertainty). This problem can be formulated as:

$$\begin{aligned} \begin{array}{ll} {\displaystyle {\min \sum _{j\in \Psi }} \hat{c}_j\times Y_i}&{}\\ {\text {Subject\, to:}}&{}\\ \displaystyle {\sum _{i\in U}} {\textit{UI}}_i X_i \ge \alpha \displaystyle {\sum _{i\in U}} {\textit{UI}}_i&{}\\ \displaystyle {\sum _{i\in {\textit{BL}}_j}} X_i \ge |{\textit{BL}}_j| Y_j,&{}\quad \forall j \in \Psi \\ \displaystyle {\sum _{j\in {\textit{DH}}_i}} Y_j \ge X_i, &{}\quad \forall i \in U\\ \quad X_i \in {0,1} &{}\quad \forall i \in U\\ \quad Y_j \in {0,1} &{}\quad \forall j \in \Psi \\ \end{array} \end{aligned}$$

(11)

Tabu Search Algorithm

Large instances of such integer problem are difficult to solve. In a similar research, Bilal (2014) has shown that the CPLEX solver was unable to find an optimal solution after several computing days for a problem with 20,000 blocks. Metaheuristics are then used to find good quality solutions for such problems. The method proposed in this research is a Tabu Search algorithm which explores solutions of a neighborhood while keeping a record (Tabu list) of explored solutions characteristics (drillholes). As demonstrated in further examples, this algorithm provides good quality solutions comparable to the optimal solution for a reasonable computing time.

In this algorithm, a solution S represents a subset of drillholes. The neighborhood of a solution S, noted N(S), is a set of solutions having similar characteristics with S. For each solution S, we define three types of neighborhood sets as shown in Figure 1:

• $N(S)^+$: A solution $S'$ is considered in the neighborhood of the current solution S, if $S'$ has the same drillholes as those in S plus a single additional drillhole. Thus, a solution S has at most $|\Psi |-|S|$neighbors+ in set $N(S)^+$:

  $N(S)^+: = {S'\in \Psi : |S'\cap S|=|S'|-1 }$

• $N(S)^-$: A solution $S'$ is considered in the neighborhood of the current solution S, if $S'$ has the same drillholes as those in S excluding a single drillhole in S. Thus, a solution S has at most |S| neighbors− in set $N(S)^-$:

  $N(S)^- = {S'\in \Psi : S'\in S {\text { and }} |S'\cap S|=|S|-1}$

  Let us notice that: $S'\in N(S)^- \Leftrightarrow S\in N(S')^+$

• $N(S)^*$: A solution $S'$ is considered in the neighborhood $N(S)^*$ of a current solution S, if S and $S'$ has the same number of drillholes and $|S|-1$ common drillholes (S and $S'$ differ by only one drillhole). Thus, a solution S has at most $|S|\times (|\Psi |-|S|)$neighbors$^*$ in set $N(S)^*$:

  $$\begin{aligned} N(S)^*: = {S'\in \Psi : |S'|=|S| \quad {\text { and }}\quad |S\cap S'|=|S|-1 } \end{aligned}$$

A drillhole is considered nearby another one if they have the same collar point and nearby terminal blocks. In order to reduce the number of neighboring solutions to explore starting from a current acceptable solution S, the considered neighbors⁺ and neighbors^* are limited to acceptable neighboring solutions that differ from S by a nearby drillhole.

Figure 1

Types of solution’s neighborhood

For each acceptable solution explored, a score is calculated as the evaluation of the objective function for this solution (total uncertainty that is covered by the solution’s drillholes). The Tabu Search process (Fig. 2) explores the domain of solutions by going from solution to neighbor solution, choosing at each step the local optimum as the current solution (neighbor with the best score to cost ratio, when comparing all types of neighborhood).

At first, only $neighbors^+$ and $neighbors^*$ are considered in the neighborhood search. When the algorithm can no longer find better solution than the current solution in the $neighborhood^{+/*}$, it considers removing drillholes from the current solution. A score to cost ratio is then used as selection criteria in order to ensure that solution with fewer drillholes ($neighbor^-$) are considered. The Tabu algorithm can thus remove ineffective drillholes from a current solution and later add more interesting drillholes.

A drillhole added or extracted when passing from the current solution to the overall best neighboring solution is registered in a Tabu list for a certain number of iterations t (actually the length of the Tabu list). At any time, the overall best solution evaluated is recorded.

An acceptable initial solution can be generated by a simple greedy algorithm, which consists of randomly selecting and adding drillholes (maybe from a predefined list of best single drillholes) until the maximum drilling cost is almost reached and it is no longer possible to add a drillhole to that initial solution. When the Tabu Search algorithm is stuck (i.e., no new best solutions after a certain number of iterations), a temporary violation of the maximal cost constraint can be allowed for a certain number of iterations in order to change some of the current solution features. During this violation time, overall best solutions are not recorded if they are not acceptable solutions.

Figure 2

Diagram of the Tabu process

The Tabu algorithm presented provides good solutions to the optimization problem. We can compare its predictions with optimal solutions for some examples of average-sized problems using test cases.

Application on Test Cases

The whole process (uncertainty index calculation and drillhole optimization) was tested on two synthetic test cases: a two-dimensional and a three-dimensional example.

Test Case 1: A Two-dimensional Example

Let us consider the mineral deposit presented in Figure 3a (generated by random unconditioned geostatistical simulation). The field was subdivided into a $300\times 200$ grid (60,000 blocks). Existing drillholes were presented in continuous lines, and results of sampled blocks are shown in Figure 3b: solid color line for inside-deposit facies blocks ($I(x^*)=1$), and pattern line for outside-deposit facies blocks ($I(x^*)=0$). A total of 1117 blocks were sampled by the existing drillholes.

Figure 3

Example of a 2D mineral deposit in a $300\times 200$ field with existing drillholes

Calculation of the Uncertainty Index

The omnidirectional experimental variogram $\gamma _{\exp }(h)$ was calculated from those samplings and presented in Figure 4a (in red dots). The theoretical model selected for the Gaussian variable is an isotropic (omnidirectional) Cubic model with a range of 75.0 distance units presented in Figure 4b. An isotropic model was selected for simplification purposes (meaning that the variability is considered the same in every direction). The induced categorical variable model $\gamma _{ {Ind}}(h)$ and its adjustment to the experimental variogram is shown in Figure 4a.

Figure 4

Variogram model selection

An omnidirectional variogram was assumed in the current test case for simplification. It should be noted that the method can be generalized to anisotropic deposits also. First, let us notice that the geostatistical process (Gibbs sampling and Turning Bands simulation) can be applied using anisotropic variograms. In addition, the approach could be applied to elongated deposits using isotropic variograms when working with parallel cross-sections (as usually done in exploration). Finally, using the two-dimensional example, if one contracts/dilate the vertical coordinates say by factor b, then the variogram would be anisotropic and the blocks would also be contracted/dilated by the same factor.

We can now encode the categorical facies values for sampled blocs $I(x^*)$ into Gaussian values $Z(x^*)\sim N(\mu ,\sigma ^2)$, using the Gibbs sampling and the theoretical model selected as target variogram. The Gibbs sampling process was applied 100 times to obtain 100 independent sets of Gaussian values. Figure 5 shows an example of the resulting variograms of the final Gaussian values for one of the $r=100$ independent repetitions. The average variogram (in heavy line) shows a good fitting to the target variogram (dash line). This test case with 1117 initial values required 30,000 iterations to make sure the burn-in phase has passed.

Figure 5

Variograms produced during the gibbs sampling process

Once the 100 independent sets of Gaussian values are obtained, they can be used as conditioning values to generate 100 simulations of Gaussian values for the complete field using the Turning Bands Algorithm. The Gaussian values were then coded into facies values, producing as many realizations of the mineral deposit. Figure 6 presents three different independent realizations simulated for the current test case with the TBM. We can notice that although different, each one of those realizations is consistent with the initial sampling results shown in Figure 3.

Figure 6

Example of independent realizations generated with the Turning band simulation

The 100 independent realizations were used to calculate the facies probability and uncertainty index for each block, illustrated in Figure 7. Figure 7a shows the facies probability for each block with the values ranging from 0.0 to 1.0 (color scale on the left). We can distinguish areas where no mineral deposit is expected from areas likely to contain some mineral deposit, given the current information provided through existing drillholes. Figure 7b shows the uncertainty index with values ranging from 0 to 0.25 (color scale on the left). Blocks nearby existing drillholes are more certain whereas, generally, blocks far from existing drillholes or blocks that are close to the deposit boundary, tend to be the most uncertain. The total block uncertainty is 8017.7.

Figure 7

Facies probability and uncertainty index

Figure 7d shows the average simulated deposit (average of 100 simulations rounded to 0 or 1) and compares it to the original mineral deposit in Figure 7c. The total facies error (blocks with the wrong interpreted facies) for the average deposit is 3785 (among 60,000), representing 93.7% of correct block interpretation.

Figure 8 compares two realizations generated using different theoretical variogram models as target: spherical and cubic models, both with range of 75.0. Both models provide similar fits to the experimental indicator variogram; however, the realization with the spherical model differs in texture from the original mineral deposit and appears unrealistically irregular from a geological standpoint.

Figure 8

Comparison of realizations generated with different theoretical variogram models

Optimization for Future Drillholes Selection

Once the uncertainty index value for each block of the field is calculated, the optimization problem for selection of future drillholes can be formulated and solved. Figure 9 presents the universe of all possible drillholes considered with three collar points, forming a total of 1800 possible drillholes. For simplification purpose, it was assumed that a drillhole individual cost is proportional to its length. It was also assumed that each drillhole has a coverage radius of 10.0 distance units. We want to find the best subset of future drillholes for a total drilling costs of 1000.0 (in distance units), based on the criteria of covering the maximum uncertainty.

Figure 9

Uncertainty map and potential future drillholes

The initial number of blocks is 60,000. In order to reduce the number of blocks and thus the number of variables of the problem (to allow optimal resolution), we can aggregate the blocks in the original uncertainty index map. In this example, $300\times 200$ original blocks have been aggregated into $75\times 50$ larger blocks with uncertainty indexes corresponding to the sum of the $4\times 4$ initial blocks. The results are shown in Figure 10, both images are similar (with lower resolution in the second one), but the number of blocks has been reduced to 3750. We have to be cautious with such a reduction: we can reasonably assume that a good solution for the reduced problem will be a good solution for the original set, only if the final aggregated image is similar to the original one.

Figure 10

Blocks aggregation for variables reduction

We can now solve the optimization problem illustrated in Figure 10 with the GUROBI solver. The optimal solution was found within 989.0 s of computing time on a 1.70 GHz Intel Core i5 processor. The optimal solution found is presented in Figure 11. This optimal solution has a total drilling cost of 999.8 and a coverage score of 3317.3 (total uncertainty covered by selected drillholes), which represents the highest achievable uncertainty coverage for a drill cost of 1000.0.

Figure 11

Optimal solution found for test Case 1 with a maximum cost of 1000.0

In the current test case, the number of collar points was fixed to three for simplification. It should be noted that the proposed optimization model can be generalized to larger number of collar points, but at the cost of larger computation time (the number of potential drillholes directly affects the computation time). A potential drillhole is defined here as the association of a collar point and an endpoint (Fig. 9). One can increase the number of collar point while keeping the computation time constant by simply reducing the number of endpoints.

It should also be noted that the drillhole positioning problem can be solved successively in an iterative fashion, considering at each step the remaining drilling budget. Such approach would require to rerun the geostatistical process after each step (addition of a new drillhole) in order to have an updated uncertainty map, and ten solve a new optimization problem with the remaining drilling budget.

Finally, in the current test case, a drilling budget of 1000.0 was considered, which seemed sufficient to target most of the uncertainty in the field (see Fig. 11). Let us examine the impact of reducing the total maximal drilling cost. Figure 12 presents the optimal drillholes (exact solution) found with different drilling budgets of 500.0, 700.0 and 1000.0 (default value). The total uncertainty covered was 1820.7 with a maximum drilling budget of 500.0 (a reduction of 45.1% from the total coverage of the 1000.0 budget solution). The total uncertainty covered with the 700.0 budget solution was 2470.9 (a reduction of 25.5% from the 1000.0 budget solution). For this example, all three solutions have similar valuable (in terms of coverage) drillholes. As the budget increases, the model is adding new drillholes while only slightly modifying existing best drillholes, which suggest a smooth solution space for this example at those level of budget.

Figure 12

Optimal solution with different total drilling cost for test Case 1

Optimization Using the Tabu Search Algorithm

The problem is now solved using the Tabu Search algorithm proposed in “Tabu Search Algorithm” section for 20,000 iterations. An empirical and usually recommended value of $t\approx \sqrt{n}$ is used for the length of the Tabu list (Gendreau et al. 1994). The best Tabu Search solution is presented and compared to the optimal solution in Figure 13.

Figure 13

Tabu Search solution and optimal solution for test Case 1

The best Tabu Search solution has a cost of 996.4 and a coverage score of 3310.7 (i.e., 0.2% gap from the optimal coverage score of 3317.3). The drillholes selected in the Tabu Search algorithm are also very similar to the optimal solution (actually the Tabu Search found 5 out of the 7 drillholes from the optimal solution, and suggested 2 other drillholes very close to the remaining 2). The best Tabu solution was found after 10,913 iterations (a computing time of 381.64 s on the same 1.70 GHz Intel Core i5 processor). Results evolution of the Tabu Search algorithm is presented in Figure 14. The Tabu Search algorithm found a solution at 2.4% gap from the optimal solution after only 2124 iterations or 87.1 s of computing time (compared to 989.0 s for the optimal solution).

Figure 14

Evolution of the Tabu Search results

We can now assess the impact on residual total uncertainty of actually realizing the optimal set of drillholes or the set of drillholes from the best Tabu Search solution (Fig. 15). This was done by adding the suggested new drillholes to the existing ones and recomputing the uncertainty index as previously using geostatistical simulation. In Figure 15a, the overall uncertainty is reduced from 8017.7 to 2621.9 (a total reduction of 67.3%). The accuracy of the simulated deposit has also improved (Fig. 15d), with a total facies error of 1292, representing an accuracy of 97.8%. Very similar results were obtained with the best Tabu Search solution (shown in Fig. 15c and d) with a new overall uncertainty of 2622.6% and 97.9% accuracy.

Figure 15

Facies prediction and uncertainty with the optimal set of drillholes

The Tabu Search algorithm has provided a solution that is very close to the optimal one. Using a Tabu Search algorithm also enable the identification of different good quality solutions revealing several interesting configurations of future drillholes with high uncertainty coverage. In contrast, the optimal solving provides a single solution that may not always be the most practical one. Most importantly, the Tabu Search algorithm is less limited in terms of problem size (number of discretization blocks), only the number of drillholes matters.

The optimization model presented in this research considers a binary coverage indicator $cvr_j^i$ (block i is either entirely covered by a drillhole j—i being within a certain distance from j- or not covered). This assumption simplifies the model by limiting the number of coverage/selection constraints linking the blocks coverage variables $X_i$ to the drillholes selection variables $Y_j$ (total of $n+m$ constraints, n being the number of blocks and m the number of drillholes). However, this assumption also prompts the usage of a coverage radius parameter or range, which is set at 10.0 distance units in the current test case. Figure 16 compares the optimal solutions (exact solver) found for different coverage distances (range) of 5.0, 10.0 (default value) and 15.0 units. The 15.0 range solution is closer to the 10.0 range solution: the most valuable drillholes in terms of coverage in both solution are very similar, the solutions differing only on the few short lateral drillholes. Four out of 7 drillholes from the 5.0 range solution (the most valuable in terms of coverage) are similar to drillholes in the 10.0 range solution. Furthermore, the overall uncertainty is reduced to 2785.7 when realizing the drillholes from the 15.0 range solution (a 68.0% reduction). This reduction is comparable to the 67.3% uncertainty reduction obtained with the 10.0 range solution, which means that both solutions have a similar quality. The total reduction when using drillholes from the 5.0 range solution is 58.8%. Within a certain realistic threshold, the value of the coverage distance parameter would have little impact on the optimization solution. Nevertheless, careful consideration should be given in the selection of a realistic value for that parameter.

Figure 16

Optimal solution with various coverage distances

Test Case 2: A Three-dimensional Example

The proposed method also works for three-dimensional mineral deposits. Let us consider the mineral deposit in a $60\times 48\times 24$ grid (69,120 blocks) as presented in two views in Figure 17. This mineral deposit was also generated using unconditioned geostatistical simulation. The existing drillholes are shown in red (vertical drillholes were considered in this example for simplification only).

Figure 17

Mineral deposit and existing drillholes (test Case 2)

The sampling results from existing drillholes are presented in Figure 18. A total of 672 blocks were sampled by these drillholes (on a total of 69,120 blocks).

Figure 18

Initial drillholes samplings results

Calculation of the Uncertainty Index

Figure 19 shows the omnidirectional experimental variogram (in dots) calculated from the samplings results. The theoretical variogram model selected for the Gaussian variable is an isotropic cubic model with a range of 20.0 units. The induced categorical model is presented by the continuous line. Its fitting to the experimental variogram is acceptable.

Figure 19

Experimental and induced indicator variograms for test Case 2

Figure 20 presents the average simulated mineral deposit (average of 100 simulations rounded to 0 or 1) in View G, which can be compared to the original mineral deposit in View F. The total facies error is 5987; thus, the deposit representation is 91.3% accurate. Some part of the original deposit is missing in the simulated deposit at the top left (View E). However, the uncertainty is higher at this location, which imply that future drillholes will target this area. View H show the blocks uncertainty index with values varying from 0.01 to 0.25. To facilitate the visualization, blocks with uncertainty below 0.01 (i.e., 4% of max. uncertainty) were not represented.

Figure 20

Simulated mineral deposit and uncertainty index for test Case 2

Optimization for Future Drillholes Selection

For this case, we consider a set of potential vertical drillholes that are evenly spaced and follow a rectangular pattern. Each drillhole position (collar point) has six different possible depths (4.0, 8.0, 12.0, 16.0, 20.0 or 24.0), for a total of 1710 potential drillholes, position and depth combined. We would like to know which subset of drillholes to select for a maximal drilling cost of 200.0 (distance units) and assuming a coverage radius of 5.0 (distance units).

The optimal solution found for this problem is presented in Figure 21 (View C1, green lines). The optimal solution was found in 180.0 s of CPU time on a 1.70 GHz Intel Core i5 processor using the GUROBI solver. This solution has a cost of 200.0 and a total coverage score of 2153.3 (total uncertainty covered).

The Tabu Search algorithm applied to this problem for a maximum of 20,000 iterations, provided the best solution presented in Figure 21 (View D1). The best Tabu Search solution has a cost of 200 for a maximum coverage of 2120.9 (a 1.5% gap from the optimal coverage score) and was found after 6509 iterations (4825.3 s on a 1.70 GHz Intel Core i5 processor). This solution is very similar to the optimal solution (Fig. 21, View C1). Actually, six drillholes were exactly the same. The total blocks covered by both solutions are also very similar (Fig. 21, Views D2 and C2). The Tabu Search algorithm found a solution at a 2.2% gap from the optimal solution after only 730 iterations or 691.1 s of computing time.

Figure 21

Optimal solution and Tabu Search solution for test Case 2

Conclusion

A new approach for the DPP in mineral exploration context is proposed in this paper: an optimization model for maximization of the coverage of a new block uncertainty index, which is calculated using a set of conditioned Gaussian realizations. The uncertainty index is higher in undrilled areas or in blocks close to deposit boundary. Future drillholes are selected by solving the optimization model. A Tabu Search algorithm has been shown to produce results comparable to optimal solutions for medium-size instances of the DPP problem.