Algorithms for optimum design and planning of open-pit mines.

A graph theory oriented algorithm for optimal ultimate pit limit design is developed. Mathematical proofs of optimality and convergence are given. The algorithm works on a 3-D block mine model and formulates the model into a directed graph consisting many trees. The vertices in the graph are identified with the blocks in the model and the imposed arcs in the graph represent pit slope constraints. The formation of each directed tree is based more on the ore-waste support concept than geometric constraints alone. The algorithm efficiently handles the joint support and re-allocation problems. The theoretical proof shows that the new algorithm is consistently faster than the well known Lerchs-Grossmann's (LG) algorithm, which is the only algorithm developed in the past one-quarter century capable of producing a true optimum pit limit. The case study results show that the new algorithm is able to generate the optimal ultimate pit limit for a model with 80 columns x 80 rows x 40 levels on an IBM PC AT 80286 microcomputer in 115 minutes. The indirect comparison was made between the results of the new algorithm and the results obtained by P. Huttagosol (1988, 1989) using the LG algorithm. P. Huttagosol optimized a smaller mine model than the one optimized by the new algorithm in 535 minutes of VAX8600 CPU time. The comparison between 535 minutes of VAX8600 CPU time for a smaller model with 115 minutes PC AT processing time for a bigger model clearly indicates that the new algorithm is significantly faster than the LG algorithm. This study also investigates both proposed mathematical optimization approaches and the popular trial and error "pushback" approach to long range mine planning. Both the theoretical analysis and numerical examples demonstrate it is impossible to obtain the optimal solution to mine production scheduling by the approach combining the Lagrangian relaxation with the ultimate pit limit algorithm. The non-convergence due to redundant optimal solutions and the non-convergence due to the requirement of advanced stripping are identified with the proposed approach. The investigation clarifies the long-time misunderstood concept and proves the impossibility of such a research direction itself. Finally, some problem solving techniques which play important roles in the computerized mine planning and grade control are developed and discussed. Specifically, they are: (1) point-in-polygon algorithm, (2) polygon area algorithm, (3) polygon clipping algorithm, (4) blast hole data collection, validation and database maintenance, and (5) the interactive graphics ore-waste delineation