Sublevel stope layout planning through a greedy heuristic approach based on dynamic programming

Sublevel stoping is a commonly used underground mining method in which the profit can be increased by optimizing the layout plan. The complexity of the sublevel stope layout problem is demonstrated by showing it is a special case of the independent set problem, which is NP-hard. A novel approach based on dynamic programming is proposed to solve the sublevel stope layout problem. This approach identifies the recurring subproblems and memoizes their results. Memoizing subproblems reduces the solution time by shifting the computational burden of recalculation to the computer memory. To solve larger problem instances, a greedy heuristic is introduced to further decrease the solution time and limit the memory usage. For smaller problem sizes, the heuristic can be lifted and the approach can be used as an exact method. A large case study is presented to demonstrate the performance of the approach. The results show that that the stope layout plan is generated fast and it captures the valuable regions of the orebody well. A second, smaller case study is presented to benchmark the introduced exact and heuristic approaches. The exact approach outperforms the heuristic approach only by 1% while the solution time is reduced by more than 99%.

Automated summary

The complexity of sublevel stope layout problem is shown to be a special case of the independent set problem, which is NP-hard. A new approach based on dynamic programming is proposed to efficiently solve the problem by memoizing subproblems and introducing a greedy heuristic method to further optimize solution time and memory usage. Results from case studies demonstrate the effectiveness of the approach in generating fast and accurate stope layout plans.