Algoritmos para la construcción de redes de caminos en minas a cielo abierto

Abstract

La planificación a largo plazo en minas a cielo abierto se compone de tres etapas: i) determinación de envolvente óptima, ii) secuenciamiento y diseño, y iii) plan de producción. La etapa ii) carece de herramientas matemáticas para optimizar el diseño, lo que la hace muy dependiente de la experiencia del ingeniero/a en planificación y muy demandante de tiempo, ya que requiere diseñar manualmente las fases y ubicar redes de caminos/rampas que conecten bancos con la infraestructura. En este trabajo se proponen dos algoritmos heurísticos que intentan guiar al ingeniero/a en planificación por dónde deberían construirse las rampas/caminos con tal de minimizar el costo de excavación y construcción. Para esto se modela el problema como buscar el Steiner Tree de costo mínimo en un grafo discreto, que conecta determinados nodos o terminales, siguiendo como ejemplo lo realizado en otras industrias, como la forestal. Luego, se revisan dos heurísticas clásicas para resolver este problema general, a saber, el Minimum Spanning Tree Heuristic (MSTH) y Shortest Path Heuristic (SPH), pero adaptándolas para que consideren la excavación de la topografía. Se programan los algoritmos en el lenguaje de programación Python, y se analiza la consistencia de estos con distintos casos de estudio. Se tomaron dos modelos de bloques públicos, el primero con cerca de 53,000 bloques, y el segundo con cerca de 270,000 bloques. En cada modelo se ejecutaron 3 experimentos cambiando el número y ubicación de los terminales a conectar. De esta manera, se contrastaron los dos algoritmos. En los 6 experimentos realizados el máximo tiempo de corrida fue menor a 30 min en una laptop personal. Las principales conclusiones obtenidas son: i) el algoritmo SPH tiende a entregar redes más económicas que el MSTH, lo que se fundamenta básicamente en la construcción de ambos algoritmos, siendo más general el SPH, ii) el algoritmo MSTH tiende a ser más rápido en encontrar una red factible que el SPH, nuevamente debido a que el algoritmo SPH puede requerir de más conexiones de las necesarias que el MSTH, y iii) el algoritmo SPH es más robusto que el MSTH, lo que posibilita que el SPH sea capaz de encontrar una red factible aun cuando el MSTH no la encuentra. Se espera que esta tesis sea el punto de partida para futuras investigaciones que aborden el problema de redes en minas a cielo abierto, con el fin de entregar una mejor guía al planificador.

The traditional long-term planning methodology in open-pit mines consists of three general stages: i) determination of the optimal envelope, ii) sequencing and design, and iii) production planning. Of these stages, only stage ii) lacks mathematical tools to assist in deciding the best design, making it a very time-consuming task and highly dependent on the planner's expertise. In this stage, the planner must manually design the phases and locate a network of paths/ramps connecting benches with relevant infrastructure. In this work, two heuristic algorithms are proposed to guide the planner on where ramps/paths should be constructed in order to minimize excavation and construction costs. For this purpose, the problem is modeled as searching for the minimum-cost Steiner Tree in a discrete graph, connecting certain nodes or terminals, following the example of other industries such as forestry. Then, two classical heuristics for solving this general problem are reviewed, namely, the Minimum Spanning Tree Heuristic (MSTH) and the Shortest Path Heuristic (SPH), but adapted to consider the excavation of the topography. The algorithms are programmed in the Python programming language, and their consistency is analyzed with different case studies. Two public block models were used, the former with approximately 53,000 blocks, and the latter with approximately 270,000 blocks. In each model, 3 experiments were conducted by changing the number and location of the terminals to be connected. Thus, the two algorithms were contrasted. In the 6 experiments conducted, the maximum runtime was less than 30 minutes on a personal laptop. The main conclusions obtained are: i) the SPH algorithm tends to deliver more economical networks than the MSTH, which is fundamentally based on the construction of both algorithms, with the SPH being more general, ii) the MSTH algorithm tends to be faster in finding a feasible network than the SPH, again because the SPH algorithm may require more connections than necessary compared to the MSTH, and iii) the SPH algorithm is more robust than the MSTH, allowing the SPH to find a feasible network even when the MSTH does not. It is expected that this thesis will be the starting point for future research addressing the network problem in open-pit mines, in order to provide better guidance to planners.