A Path Search Algorithm for Optimizing Ultimate Limit of Open Pit Mines with Geomechanical Constraints

Abstract

In this study, a path search algorithm is introduced for exploring the ultimate pit limit using the Lerchs–Grossmann method. In an iteration of the algorithm, each vertex of the solution is randomly moved within a specified neighborhood. The vertices’ motion in such a neighborhood ensures that the formation of abnormal shapes is prevented. Since an open-pit design needs to address geomechanical concerns coincident with economic value maximization, the movements resulting in segments steeper than an allowable slope angle are discarded. For each valid vertex movement, the benefit of the resulted pit limit was calculated. The new position of the vertex is accepted according to a probabilistic regime in order to prevent the algorithm be trapped in a local maximum. Independence of the slope from the block size is one of the main advantages of the suggested algorithm. Hence, the algorithm provides a better mapping to the ore body and results in a higher benefit. The reason is the mobility of the path search algorithm and its high flexibility.

INTRODUCTION

Before the initiation of the extraction operation in open-pit mines, it is required to define the limit of the mine. The ultimate pit limit is a limit that its economical parameters such as the net present value, lifetime, profit, etc. be optimized. The best target function for optimization of the ultimate pit limit is the benefit. Knowing the ultimate pit limit is necessary for the determination of extractable reservoir, stripping ratio, production scheduling, the design of access routes, as well as the location of buildings, plants, and waste dams. Multiple parameters are involved in the determination of this limit. Therefore, using computers is inevitable to model interactions.

Many researchers have attempted to present various algorithms to design the ultimate pit limit. The main aim of all of these algorithms was exploring block sets, which resulted in maximized earnings by their extraction. The presented algorithms could be divided into the following three categories: mathematical (rigorous) algorithms [1–6], heuristic algorithms, and meta-heuristic algorithms [7–11].

The first category refers to algorithms that have mathematical proofs. These algorithms began with the graph theory and dynamic programming by Lerchs and Grossmann in 1965. The graph theory was encountered by difficulties such as spending a lot of time to acquire the response, needing advanced computers at the time of algorithm presentation, and un-considering the variable gradients of the mine during limit design.

The second category includes methods without mathematical proof of the derived response, and even it is probable that they are trapped by hasty convergence in a local maximum. However, more attention was paid to these methods due to the simplicity and lesser computations. The floating cone method is the simplest and fastest estimation algorithm for the ultimate pit limit that was presented by Pana et al. in 1965. In 2015, Adibi and Ataee-pour integrated the sustainable development principles in ultimate pit limit design [12].

The third category consists of those meta-heuristic algorithms which their most known one is the genetic algorithm. These methods are able to reach a desirable and acceptable solution in a short time. If even they cannot find the optimal solution, they present a response reasonably near to it.

The aim of the current study is to develop a novel hybrid method of determining the ultimate pit limit. A stochastic search algorithm, called path search algorithm, is introduced to explore the ultimate pit limit. Every stochastic search algorithm needs an initial solution at the starting point which is usually chosen randomly. In this study, the result of the Lerchs–Grossmann (LG) method is used as the initial guess for the pit limit. Hence, the suggested algorithm can be considered as an optimization for the Lerchs–Grossmann solution which removes the limitations of this algorithm.

1. LERCHS–GROSSMANN ALGORITHM

Lerchs and Grossmann presented an algorithm called graph theory for the problem of determination of the ultimate pit limit [5]. In this algorithm, the problem of finding the optimal limit converts to seek a sub-graph with the highest weight in which the limitations of extraction and the wall slope are considered.

The graph theory algorithm converts the three-dimensional grid of the block economic value (BEV) of the ore deposit to a directional graph. Every block of the grid is shown by a vertex and a weight equivalent to its net value. The vertices are connected to each other by arcs so that the connections directed from a given vertex towards the topography surfaces define a set of blocks that should be removed for the extraction of this vertex. Fig. 1 shows a direct graph used for a two-dimensional ore model in which the block dimensions are assumed to be the same. A set of vertices that can constitute an executable pit is called a closure. The value of every closure is equal to the total value of surrounded nodes (blocks). Therefore, this algorithm tries to explore the closure with the highest economic value by using a series of rules presented in [5].

Many attempts have been made to overcome the difficulties of incorporating variable slope angles within the Lerchs–Grossmann algorithm [1, 2, 13–16]. However, none provides adequate flexibility to deal with complex geology, and most are subject to block dimensions.

Fig. 1

Directional graph representing a two-dimensional cross-section of ore body [5]

Fig. 2

Enhancement of block model resolution by dividing every block into a number of sub-blocks

2. PATH SEARCH ALGORITHM FOR EXPLORING ULTIMATE PIT LIMIT

In this study, a stochastic search algorithm, called path search algorithm, is developed to locate the ultimate pit limit. Every stochastic search algorithm needs an initial solution at the starting point which is usually chosen randomly. Here, the result of the Lerchs–Grossmann method is used as the initial guess for the pit limit and is optimized iteration by iteration. First, the resolution of the block model is increased. For this purpose, every block is divided into a number of sub-blocks (Fig. 2).

If the number of sub-blocks of a block is equal to $n^{2}$, i.e., every side of the block in a two-dimensional section is divided into $n$ segments, the economic value of every sub-block is calculated by dividing the economic value of each block by $n^{2}$. The number $n$ is called the resolution enhancement coefficient. Similarly, the resolution of the ultimate pit limit obtained by the Lerchs–Grossmann method is also increased by adding some points between the vertices (Fig. 3). The higher the resolution at this stage, results in the greater the degree of freedom and flexibility of the algorithm.

The path search algorithm in each iteration, changes respectively the position of each vertex of the solution randomly repeatedly within a permissible neighborhood. Fig. 4 shows the movement space of each middle vertex, and Equation (1) presents the magnitude of allowable movement in the vertical direction:

$$ \Delta y = \Delta y_{\max } \alpha ^kM.$$

(1)

Where $\Delta y$ is the limit of the vertical movement; $\Delta y_{\max }$ is the maximum distance between the $i$th vertex and its pre and post vertices; $k$ is the number of algorithm iterations (changes between 1 and $n)$; $M$, $\alpha$ are the static and dynamic coefficients of vertical mobility that can change between 0 and 1, respectively. The greater the value of $M$ and $\alpha$, the higher the permissible vertical movement of the vertices. By decreasing these coefficients, the vertex mobility in the vertical direction decreases. The domain of horizontal mobility of the $i$th vertex in each iteration is between the primary position of this vertex and the position of the ($i+1$)-th vertex (Fig. 4).

Fig. 3

Increasing the resolution of ultimate pit limit obtained by Lerchs–Grossmann algorithm ($\blacksquare$) by adding vertices ($\circ$)

Fig. 4

Permissible motion range for the $i$-th vertex

An open-pit design needs to address geomechanical concerns coincident with economic value maximization. To accomplish this purpose, for random movement of a given vertex in its motion range, the slopes of the right and left segments leading to the vertex were first calculated ($\psi _R$, $\psi _L$ respectively). Let $\alpha$ be the geomechanically allowable segment slope angle. If the vertex movement results in ($\ - \beta \le \psi _R$, $\psi _L \le \beta$), the algorithm would proceed to the next step (i.e., benefit calculation for the new closure); otherwise, the movement is discarded and the algorithm goes to the next vertex.

It is worth mentioning that the first and last vertices have only the freedom to move horizontally in order that the achieved final limit forms a closed polygon (Fig. 5). The movement of the vertices in such a neighborhood ensures that convexity and awkward shapes would not be created in the ultimate pit limit. By the advancement of the algorithm iterations (i.e., increase of $k$) and getting closer to the optimum solution, the neighborhood for the vertex movement would become smaller according to (1), and hence the mobility of the algorithm would decrease.

For each valid vertex movement, the benefit of the new pit limit is calculated: $\Delta P = P_\mathrm{new} - P_\mathrm{current}$ ($P_\mathrm{new}$ is the value of the benefit for the new limit; $P_\mathrm{current}$ is the last accepted value of this parameter). The new position is accepted if it leads to higher benefit (at $\Delta P > 0$, $P_\mathrm{new} \to P_\mathrm{current}$). If $P_{rand} < \exp\,[(10\cdot \Delta P / P_\mathrm{current}/ \alpha ^k)]$, $P_\mathrm{new}\to P_\mathrm{current}$. The positions that lead to a smaller benefit could be accepted according to a probabilistic regime for random walking of the algorithm which prevents the algorithm to be trapped in a local maximum. For this purpose, a random probability $P_{rand}$ would be produced in such cases, and if it is smaller than the value of Boltzmann probability at that point, the new position would be accepted in spite of producing smaller benefit.

Fig. 5

Permissible motion range for the first and last vertices

Fig. 6

Results of searching columnar ore for ultimate pit limit: (a) pit limit obtained using the LG algorithm, benefit $P=986$ $US; (b) pit limit obtained using the path search algorithm, $\beta = 90^{\circ}$, $R=100$ %,$P=1373$ $US; (c) the same, $\beta = 65^{\circ}$,$R=68$ %, $P=1203$ $US; (d) algorithm convergence curve

As the value of $k$ increases, the chance of accepting positions of smaller benefit would decrease. After $n$ movements of one of the vertices, the algorithm goes to the next vertex. Upon completion of these steps for the final vertex of the pit limit, a sub-iteration is completed. After performing $n$ sub-iterations of the frequent, one iteration of the algorithm is completed. Then the next iteration begins, and the algorithm continues until the $n$iteration is completed.

For the evaluation of the performance of the suggested algorithm under various conditions, examples of a columnar ore deposit, and an irregular ore body with a random distribution of block economic value were investigated. Figures 6 and 7 compare the performance of the LG algorithm and the suggested algorithm with different values of $\alpha$ applied to the columnar ore and randomly distributed ore, respectively. The search algorithm parameters, obtained with trial and error, are represented in Table 1. The slope constraint causes some vertices to have no valid movement in an iteration. As a result, the slope-constrained $\beta = 65^{\circ}$ algorithm requires more iterations to converge compared to the unconstrained optimization $\beta = 90^{\circ}$. The parameter of $R$ specifies the ratio of valid vertex movements to the entire movement in percent. As can be seen in Figs. 6 and 7, the path search is able to optimize the Lerch–Grossman pit limit and leave behind the block size limitation. Therefore, it achieves better adaptation with the ore geometry and, as a result, leads to a higher benefit. The reason for this is the mobility of the algorithm and its high flexibility.

Fig. 7

Results of searching randomly distributed ore for ultimate pit limit: (a) pit limit obtained using the LG algorithm,$P=155$ $US; (b) pit limit obtained using the path search algorithm, $\beta = 90^{\circ}$, $R=100$ %,$P=209$ $US; (c) the same, $\beta = 65^{\circ}$,$R=76$ %, $P=189$ $US

Table 1. Path search algorithm parameters for determining ultimate pit limit

3. CASE STUDY

The performance of the suggested algorithm for designing the ultimate pit limit for a real case is examined. The Korkora iron ore mine is located 56 km north of Bijar in Kurdistan province (Iran). New exploratory boreholes were drilled in a grid of 50 m $\times$ 50 m in the mining area. The mine reserve was estimated to be 12.11 million tons of iron ore. According to economic investigations, the iron cutoff grade was 36.5 % [17].

The block model of the mine was built with block edges of 5 m. Below is the economic data related to Korkora mine [17]:

...

Mining cost per one ton of ore, $US	2.8175
Mining cost per one ton of waste rock, $US	2.4860
Mining cost per one ton of waste soil, $US	0.8130
Mineral processing cost per one ton of ore, $US	16.7300
Price of one ton of Fe concentrate with grade of 68 %, $US	51.3000
Mineral processing recovery, %	75
Mining recovery, %	95
Dilution, %	5

Block economic value (BEV) is determined as:

$$ BEV = T_0 GRS - T_0 C_s - T_0 C_p - TC_m$$

(2)

for blocks with a grade higher than the cutoff grade. Here,$T_0$ is the weight of ore in the block, t; $G$ is the grade of iron; $R$ is total ore recovery; $S$ is the price of iron, $US/t; $T$ is the total weight of block; $C_s$, $C_p$ are processing costs, $US/t; $C_m$ is the cost of block mining, $US/t. Then, we determined BEV for blocks with grade smaller than the cutoff grade: $BEV = - TC_m$.

The path search algorithm was applied using the parameters from Table 2. Figure 8 shows the results of searching Korkora mine for ultimate pit limit.

Table 2. Path search algorithm parameters in searching Korkora mine for ultimate pit limit

Fig. 8

Results of searching Korkora mine for ultimate pit limit: (a) pit limit obtained using the LG algorithm $P=2234$ $US; (b) pit limit obtained using the path search algorithm, $\beta = 90^{\circ}$,$R=100$ %, $P=2509$ $US; (c) the same, $\beta = 65^{\circ}$, $R=74$ %, $P=2395$ $US

CONCLUSIONS

The goal of this study was to develop a search algorithm for the ultimate pit limit, in such a manner that the slope is not fixed but restricted to a geomechanically allowable slope. For achieving this goal, a path search algorithm was developed in which the position of a pit limit vertices changes repeatedly in a specified neighborhood seeking a higher benefit and constrained to a maximum slope angle. Lerch–Grossman solution was used as the primary pit limit to reduce algorithm calculation load. In addition, the resolution of the block model was increased artificially for increasing the algorithm’s degree of freedom. The vertex movement in this algorithm was considered in such a manner that, it prevented unusual convex shapes of pit limit or geomechanically infeasible closures. Moreover, the solutions of smaller benefit could be accepted according to a probabilistic decision criterion to prevent the algorithm from being trapped in a local maximum. The results of the performance of this algorithm in different cases including columnar ore, randomly distributed ore, and a real massive iron ore showed that this algorithm is capable of finding the ultimate pit limit associated with more flexibility and as a result the larger benefit.

One of the advantages of the developed algorithm is to overpass the dependence of the minimum width of the pit floor to the block dimensions. In addition, the algorithm is able to reserve ramp locations within the pit shell by setting segment slope equal to zero in certain levels during the iterations. In other words, ramp locations would be considered as boundary conditions to the problem. Whereas, in the classic methods, the ramps are located after the solution is obtained. This would disturb the mine design and might impose additional costs due to the increase of the stripping ratio.

The development of the path search algorithm in the three-dimensional space could be considered as the topic of the next studies.