Algoritmo para la sincronización del transporte principal en una operación minera de cobre

Abstract

Esta tesis describe un algoritmo desarrollado para sincronizar el desplazamiento de los trenes de la etapa de transporte principal en una operación minera de cobre, los que llevan mineral desde el interior de la mina hasta zonas de descarga sobre la superficie. La compañía es líder en el mercado del cobre, con ingresos anuales de 11.500 millones de dólares y además cuenta con la mina subterránea más grande del mundo, donde se producen 500 mil toneladas de cobre fino al año. En un turno normal un tren realiza aprox. 4 viajes de 1.500 toneladas. En total, por turno se mueven unas 50 mil toneladas, lo que equivale a 450 toneladas de cobre fino y a un ingreso de 3 millones de dólares. El principal desafío operacional de la mina se debe a que la red férrea posee un número bajo de rutas entre el interior de la mina y la zona de descarga, así que con frecuencia se obstruyen los 8 trenes que normalmente operan, haciendo compleja la tarea de coordinar su recorrido. El segmento de vía que más dificulta la operación es un túnel de 7 km. de vía única, tramo que toma 10 minutos atravesar y donde solo pueden circular trenes en un mismo sentido, de modo que si dos trenes lo quieren cruzar en dirección opuesta a la vez, uno de ellos debe esperar al menos 10 minutos, lo que genera congestión. El problema se divide en dos: establecer a cuál pique tiene que dirigirse cada tren en cada vuelta del turno y determinar cuál es el recorrido óptimo de los trenes en respuesta a esa asignación. Esta tesis se hace cargo solo del segundo, pues es el más complejo de resolver y el que más valor entrega debido a la serie de potenciales interferencias que se generan entre los trenes, donde se debe tomar una decisión en cada una de ellas. El algoritmo se basa en el método de árboles de decisión apoyado por una poda de ramas inspirada en Branch & Bound. Además, para aumentar el rendimiento se aplica una paralelización del problema en una cantidad n de threads que se ejecutan a la vez. El algoritmo analiza cerca de 2 millones de combinaciones por hora para sincronizar las rutas de los trenes, de manera que se obtengan soluciones donde se complete un mayor número de viajes dentro de cada turno en relación a lo que se logra en la realidad. Las combinaciones son construidas mediante un árbol binario, el que es recorrido de forma inteligente gracias a una poda que ayuda a identificar tempranamente las ramas que generan soluciones de alta y de baja calidad, eliminando tempranamente estas últimas. Se aplicó el algoritmo en dos instancias para evaluarlo. Primero se ejecutó usando los datos de un turno pasado, donde se logró una sincronización en la que se realizó dos vueltas más que en la realidad y luego se construyó un caso para comprobar si es factible completar el máximo teórico de 40 vueltas en un turno de 8 horas, lo que tuvo resultados positivos. En ambos casos se llegó en pocos minutos a muy buenas soluciones, cumpliendo con los objetivos por los cuáles el algoritmo fue desarrollado.