Genetic algorithm framework for stochastic open pit mining optimization problems

Abstract

Genetic algorithm (GA) is a metaheuristic evolution algorithm that has been applied in the area of combinatorial optimization problems. One of these areas of optimization is mine production scheduling. Mine production scheduling is the process of determining the sequence of block extractions over a period of time that will yield the maximum net present value (NPV) for the mining operation subject to a set of constraints. The block extraction sequence needs to occur under certain resource constraints, which presents an NP-hard problem. NP-hard problems are computationally intractable and complex to solve for large- scale problems using exact mathematical models such as Mixed Integer Linear Programming (MILP) and Stochastic Mixed Integer Linear Programming (SMILP). In the mining production scheduling problem, the conventional approach is to use a single interpolated orebody model as the basis for production scheduling. This approach, however, does not consider grade uncertainties. These uncertainties have a significant impact on the NPV and can only be accounted for when modelled as part of the optimization problem. However, modeling these as part of the optimization problem increases the complexities associated with the production scheduling. In this research, a metaheuristic optimization framework based on GA was designed and implemented to solve the NP-hard large-scale open pit production scheduling (OPPS) problem. The problem definition and the resource constraints were formulated and optimized using a specially designed mining-specific GA. A multiple chromosome encoding technique was used in the GA to handle partial block processing to obtain a near-optimal solution. Two case studies from an oil sands dataset were presented in this research. A stochastic formulation (SGA) of the OPPS problem to incorporate grade uncertainty based on equally probable orebody realizations was considered and optimized with the GA framework. A deterministic approach (DGA) to the OPPS problem that did not consider grade variability was also presented. The NPV and computational time from the DGA scenario were compared to a MILP model solved with CPLEX and the SGA scenario was compared to a SMILP model solved with CPLEX as a means to validate and analyze the GA results. There was a 53.6% improvement in the computational time for the DGA compared to the MILP model with CPLEX in Case Study 1. However, the NPV was within 5.1% of the MILP model with CPLEX. The SGA model for Case Study 1 generated an NPV within 5.3% of the NPV of the SMILP model with CPLEX. Conversely, the result of the SGA model was generated in a computational time that was 75.2% better than the SMILP model with CPLEX. For Case Study 2, whereas the MILP model generated NPV of $10,175 M at a gap of 10% after 226 hours, the DGA model generated NPV of $9,142 M at 12.9% gap after 1.3 hours. Additionally, while the SMILP model was at a gap of 101% after 28 days, the SGA model generated NPV of $10,045 M at 10.6% gap after 1.5 hours.