Tutorial en Español

Por Jose Gregorio Freites | Publicación original en LinkedIn | 28 de Abril de 2018

Comparación Programación Pits Anidados Vs Programación Directa de Bloques

Investigadores del laboratorio de planificación minera Delphos publicaron un artículo que compara los resultados del enfoque tradicional de Pits Anidados con su algoritmo de Secueciamiento Directo de Bloques. El detalle del artículo técnico lo puede conseguir en la página de DELPHOS – Laboratorio de Planificación Minera.

Pits anidados

En 1965, Lerchs y Grossmann escribieron un artículo que describía un algoritmo tridimensional basado en la teoría de grafos, que podía aplicarse específicamente a la optimización de los diseños de mina a cielo abierto. En ese momento, la mayoría de las computadoras no podían realizar las grandes cantidades de cálculos iterativos requeridos por el método. También se describió un algoritmo 2-D que, aunque eficaz en secciones, perdió su calidad optimizada cuando se combinaron las secciones. El algoritmo 3-D, por lo tanto, sigue siendo la opción preferida. El gran logro de Lerchs y Grossmann (LG) fue formular este problema, irresoluble mediante programación lineal debido a los enormes requerimientos computacionales, como un problema de cierre máximo en la teoría de grafos.

Figura 1: Lerchs-Grossmann y el enfoque de teoría de grafos (Fuente: CIM Magazine – Febrero 2010)

Figura 1: Lerchs-Grossmann y el enfoque de teoría de grafos (Fuente: CIM Magazine – Febrero 2010)

Los pits anidados consisten en la definición de las fases de la explotación mediante análisis paramétrico. Esta técnica afecta el valor neto de cada bloque con un parámetro λ, de manera que variando éste convenientemente y aplicando el algoritmo de optimización, se obtienen contornos sucesivos de la fosa (fosas/pits incrementales), que serán la base de la planificación minera. El objetivo es que cada contorno delimitará una fosa con beneficio unitario mayor al que se generará posteriormente, así se minará sucesivamente material de mayor a menor valor unitario. Lerchs y Grossmann propusieron en su artículo en el año 1965 la variación del valor económico de cada bloque del modelo, de bi a (bi-λ) con λ≥0. Esto es equivalente a determinar el contorno de la fosa en el que el beneficio medio de los bloques es igual o mayor que λ.

La parametrización del Pit también se puede hacer al aplicar λ a los ingresos base (precio de venta – costos de venta). Por ejemplo, para un Revenue Factor λ = 0.9, se tiene: 0.9 * (precio de venta – costos de venta). El factor λ se puede aplicar al precio, al beneficio o al costo.

Figura 2: La parametrización (λ ) de los pits anidados se puede hacer en base a alguna de las siguientes opciones: precio, beneficio o costo minero

Jeff Whittle hizo accesible la optimización de pit basado en Lerchs -Grossmann

En 1986, el paquete de optimización Whittle 3-D para proyectos de minería a cielo abierto fue lanzado por Whittle Programming Ltd. Este paquete utilizó el algoritmo Lerchs-Grossmann por primera vez en una aplicación de software comercial y es una referencia en el mercado del software de planificación de minas.

Comentarios de Jeff Whitte (Fuente CIM):

Jeff Whittle estaba contratado por Newmont en Australia cuando se encontró con el trabajo de Lerchs-Grossman. "También leí un artículo en algún lugar que decía que a la industria minera le encantaría usar Lerchs-Grossman, pero que era 'demasiado difícil de programar' ”, escribió Whittle a la revista CIM recientemente.

A principios de los 70, Placer Dome había logrado hacerlo funcionar, pero era bien sabido en la industria que habían tenido grandes dificultades y les había costado un montón de dinero. La cifra citada fue aproximadamente de un cuarto de millón dólares. Eso fue de hecho una gran cantidad de dinero a principios de los años 70. Por supuesto, Placer Dome no permitió que nadie más lo usara.

"En 1980, tenía 18 años de experiencia en programación técnica, ¡y consideré 'demasiado difícil de programar' como un desafío personal!", Escribió Whittle.

El documento incluía un algoritmo de optimización 2D y 3D basado en la teoría de grafos, un campo de las matemáticas utilizado para representar una colección de objetos conectados.

"El algoritmo 3D fue bastante brillante y lógicamente muy complejo. ¡También la descripción fue algo escueta! Sin embargo, descubrí una forma de programarlo y me ofrecí a escribirlo para Newmont ", recordó Whittle. La compañía, sin embargo, no estaba preparada para correr el riesgo, por lo que la familia Whittle sí. El programa fue escrito durante un par de meses usando Fortran. Su esposa, Ruth, escribió el manual y asumió el marketing. "La primera ejecución con datos reales en Newmont tomó 160 horas en una mini computadora VAX".

Pasaron otros 12 meses antes de que hicieran su primera venta. Entonces Whittle dijo que las ventas comenzaron a cobrar impulso y que había vuelto al trabajo con la próxima versión del software. Finalmente, no había un banco en Australia que financiaría a un proyecto minero que no había utilizado el software de optimización para crear un plan de mina, según Roussos Dimitrakopolous, profesor de ingeniería minera de la Universidad McGill, que se especializa en la optimización de minas.

Programación directa de bloques

La programación de la producción de mina ha sido estudiada desde 1960 y ha evolucionado rápidamente con las capacidades de hardware y software. Johnson estableció el concepto de Programación Directa de Bloques.

Figura 3: Modelo de Johnson sobre la programación de la producción basado en programación lineal – Nace el concepto de programación directa de bloques.

Sin embargo, según los investigadores, el problema de la secuencia directa de bloques (OPBS – Open Pit Block Sequency) usando programación entera (IP-Integer Programming) o programación entera mixta (MILP – Mixed Integer Programming) es un problema tipo NP-Hard; ya que hasta ahora no ha sido posible optimizar el valor presente neto – VPN simultáneamente con múltiples períodos, mezclas (blending), múltiples procesos, múltiples minas, optimización del tenor de corte (cutoff grade optimization) y el manejo de stockpiles en una sola corrida (Global) a nivel de detalle de bloques en OPBS; en la actualidad, se recurre a ejecutar la optimización período por período (foward strategy) pero se obtiene una optimización con menor VPN en comparación con una ejecución de optimización Global con todos los períodos.

Otra estrategia es agrupar y optimizar en grupos de períodos de tiempo (A Sliding Time Window Heuristic) que es una mejor estrategia que el período a período y permite modelar el stockpile dentro de una función lineal. Para obtener una solución (no necesariamente el óptimo global), se emplean técnicas meta-heurísticas como algoritmo evolutivo (por ejemplo Maptek Evolution); no obstante, es necesario rebloquear cuando el modelo es muy grande o ejecutar la optimización período por período para reducir los tiempos de corrida a niveles aceptables. Por otra parte, XPAC Scheduling ha estado en el mercado desde hace algún tiempo y se basa en la aplicación de técnicas de programación entera mixta. Dentro de ésta revisión cabe mencionar el software DeepMine que utiliza programación dinámica y “ramificación y acotamiento” (approximate dynamic programming and a branch and bound strategy) y recientemente el lanzamiento del software SimSched DBS de MiningMath Associates que utiliza programación entera mixta con heurísticas propias para resolver problemas de planificación de minas con el nivel de detalle de bloques.

DELPHOS - Comparación entre programación directa de bloques y programación por pits anidados.

Fuente: http://delphoslab.cl/index.php/en/software/samples-demo/30-doppler-examples/63-doppler-nested-pits-v-s-direct-block-scheduling-3

Este es un ejemplo donde se compara la metodología tradicional de programación mediante pits anidados y la programación directa de bloques sobre un modelo de bloques específico.

Programación mediante pits anidados

La programación mediante pits anidados corresponde a utilizar el algoritmo de Lerchs y Grossmann (u otro) sobre una serie de valorizaciones del modelo de bloques, parametrizadas por un multiplicador del precio o "revenue factor". A partir de los pits anidados generados de esta forma, se seleccionan pushbacks o "candidatos a fase", que sirven de guía para el diseño, y a continuación, son programados para extracción en el tiempo.

Programación directa de bloques

La programación directa de bloques es un enfoque alternativo que pone énfasis en la temporalidad del problema y el costo de oportunidad, buscando resolver desde un principio el problema de en qué momento del tiempo es más conveniente extraer un bloque y cuál es la mejor decisión de procesamiento (incluyendo el escombro). Tradicionalmente, esta metodología se apoya en modelos de programación lineal de gran tamaño.

Resumen del ejercicio de DELPHOS

En el experimento planeado por DELPHOS, se compara la programación de la producción de una mina a cielo abierto mediante dos metodologías: utilizando pits anidados y a partir de ahí generando dos estrategias de extracción, pit por pit de manera incremental, conocida en la literatura como "Best Case" y otra estrategia que extrae banco a banco, conocida como "Worst Case".

En la Figura 4, se muestra la familia de pits anidados obtenida a partir de la elección de los revenue factors: Figura 4A muestra una vista isométrica de los pits anidados dentro de la envolvente económica, mientras que Figura 4B muestra una vista en sección. Cabe destacar que el primer pit es aquel que corresponde a un RF= 0,15

Figura 4: Pits anidados de la corrida. Fuente: DELPHOS

El escenario “Best Case”, es el algoritmo de planificación basado en la secuencia de pits anidados obtenida de la etapa de determinación de reservas, este método tiene la particularidad de considerar a cada pit anidado como una fase, es decir, consumirá las reservas de acuerdo a secuencia originalmente hallada: Se minan primero los niveles de una fase para luego pasar a la siguiente fase.

Figura 5: Escenario “Best Case” de la corrida (VPN = 1.372 MUSD). Fuente: DELPHOS

Por otro lado el Worst Case, representa una estrategia de consumo de reservas a banco completo, es decir, las reservas se consumirán a pit final banco a banco.

Figura 6: Escenario “Worst Case” de la corrida (VPN = 1.306 MUSD). Fuente: DELPHOS

Luego, la programación directa de bloques (Figura 7), se plantea el problema utilizando modelos de programación lineal y se utilizan diversas estrategias para resolverlo, en particular, en el ejemplo planteado por DELPHOS se emplean dos: utilizando una heurística por ventanas de tiempo, llamada STW, y otra, utilizando una heurística Toposort. En ambas estrategias, se imponen restricciones sobre los tonelajes extraídos. No se hacen consideraciones de diseño.

Figura 7: Programación Directa de Bloques basado en algoritmo Toposort (VPN = 1.390 MUSD). Fuente: DELPHOS

En los cuatro casos, se analizan sus geometrías de extracción, tonelajes de mineral y escombro, y valor descontado acumulado a lo largo de la vida del proyecto. En términos de valor, las estrategias de programación directa de bloques muestran el mejor desempeño.

Resultados (Fuente DELPHOS)

Considerando los resultados obtenidos por ambas heurísticas para la programación directa de bloques, se ve claramente que la heurística toposort programó la producción en 18 periodos, tal como se pidió, mientras que la heurística por ventanas acortó la vida de la mina a 17 años. Mirando los planes de producción, toposort pudo retrasar la entrada de escombro en los primeros periodos, clasificando como mineral todo el material extraído entre los periodos 1 y 4, además del 6, y desde ahí extrayendo de manera gradual el escombro hasta completar la capacidad de mina en los periodos finales. Por su parte, STW hace una extracción homogénea, saturando tanto las capacidades de mina y planta en la mayoría de los periodos (salvo 16 y 17). Por una parte, la característica "miope" de STW no le permite tomar decisiones mirando lo que podría hacer en periodos posteriores, tomando en cada periodo la mejor decisión posible. Por otra parte, toposort es capaz de tomar una decisión "global" a partir de la información obtenida de la solución continua del problema original, por lo que en cierto sentido toma una decisión más robusta, pues para decidir sobre un periodo particular, lo hace mirando qué pasará en periodos posteriores.

En términos de valor descontado acumulado (VAN), la estrategia TOPO muestra un VAN ínfimamente mayor al VAN de STW, de hecho, un 0,23% mayor.

VPN STW : 1.386 [MUSD]

VPN TOPO: 1.390 [MUSD]

En general, este tipo de estrategias no pueden asegurar encontrar una solución óptima al problema de programación, sin embargo, son una buena alternativa considerando que en problemas reales de gran tamaño (en cuanto a número de bloques, periodos y destinos) se hace no viable obtener la solución óptima por tratamiento directo del problema.

¿Qué es SimSched Direct Block Scheduler?

Es un software que cuenta con una tecnología innovadora para determinar la programación directa de bloques. El SimSched DBS busca maximizar el VPN (Valor Presente Neto) del proyecto, decidiendo cuáles bloques serán explotados, cuándo y cuál será el destino de cada uno, a partir de un modelo de bloques importado.

Es posible definir múltiples plantas de proceso, stockpiles y acopios de estéril, respetando sus respectivas capacidades. También es posible definir límites físicos o forzar la explotación en determinadas regiones, a partir de la importación de superficies.

La programación directa de bloques permite que una secuencia completa sea ejecutada directamente a partir del modelo de bloques, sin la necesidad de definir un pit final, pits anidados, pushbacks o expansiones, optimización de ley de corte y stockpiles, como una secuencia tradicional completa lo exige. SimSched DBS encontrará una secuencia de explotación que busca maximizar el VPN del proyecto, unificando todas las etapas citadas y optimizando todos los períodos simultáneamente. De esta forma, un profesional experimentado puede probar múltiples escenarios sólo modificando parámetros y adelantar otras etapas de su trabajo, mientras el SimSched DBS ejecuta toda la optimización.

Figura 8: Ancho mínimo de fosa, ancho mínimo de explotación y tasa de avance vertical.

Los planes mineros generados por la optimización respetan las principales restricciones geométricas, tales como ancho mínimo de fosa, ancho de explotación y avance vertical, las que pueden ser configuradas de acuerdo a la realidad del proyecto. Además de ésto, la tecnología del SimSched genera superficies sin errores geotécnicos. Los planes generados son cercanos a la realidad operacional de la mina, lo que implica menores cambios cuando se incluyen las rampas de acceso.

La versión actual del SimSched DBS se ajusta a cualquier proyecto de mina a cielo abierto que pueda ser modelado con bloques de dimensiones regulares. Si su proyecto posee múltiples tipos de roca por bloque, existen formas de manipular los inputs para tratar con esos casos. El SimSched es 100% basado en tecnología 64 bits y posee un algoritmo eficiente, capaz de manejar decenas de millones de bloques sin la necesidad de supercomputadores o de procesamiento en la nube.

SimSched DBS permite también que determinados sectores no sean minados (sean restringidos de la excavación), bien por razones ambientales o para proteger la ubicación de estructuras como planta de trituración, una estación de carga de mineral o una vía férrea; o forzar ciertas regiones por cuestiones estratégicas de la empresa.

¿Cuál es la principal diferencia entre las versiones SimSched PO y SimSched DBS?

La principal diferencia es que la versión DBS considera el impacto del dinero en el tiempo: el Valor Presente Neto (VPN) del proyecto es maximizado considerando una tasa de descuento a lo largo de los períodos.

La versión PO pretende maximizar el valor no-descontado del proyecto: el beneficio máximo irreal que el proyecto podría generar en caso que todo el material fuese explotado y procesado hoy, generando un pit optimizado que no necesariamente será la mejor solución, dadas las simplificaciones de ese modelo matemático.

El SimSched PO es una simplificación del algoritmo principal del SimSched DBS y seguirá recibiendo la mayoría de los nuevos desarrollos relativos al SimSched DBS, como restricciones de mezcla.

¿Implementa SimSched DBS el algoritmo Lerchs-Grossman?

No, SimSched DBS se basa en otro enfoque, no utiliza LG. SimSched DBS trabaja con algoritmo de programación entera mixta, superficies restringidas y heurísticas propias que maximiza el VPN; no requiere crear pits anidados o pushbacks basado en LG ... Lerchs-Grosmann fue un algoritmo brillante para su época. Los avances tecnológicos prueban que nuevas metodologías superan algunas barreras que el LG enfrenta. Cualquier software que tenga implementado el mismo modelo matemático de LG utilizará un algoritmo basado en flujo máximo (Max Flow), que puede ser ejecutado decenas o centenas de veces más rápido que LG. Sin embargo, tanto LG como Max Flow no poseen flexibilidad para incluir otras restricciones importantes, como un ancho mínimo de fondo de pit o mezclas.

La tecnología de programación directa de bloques de SimSched está disponible para su evaluación

El estudio de DELPHOS – Laboratorio de Planificación Minera utilizaron su software propietario; no obstante, usted puede solicitar una licencia de SimSched Direct Block Scheduler para que evalué usted mismo ésta tecnología y llegue a sus propias conclusiones.

Descargue el documento

Cursos Gratuitos y Base de Conocimiento

Acceda a nuestra sección de Cursos Gratuitos o a la Base de Conocimiento, donde encontrará información técnica relevante y videos técnicos.

Blog Cursos GeoMin

Suscríbase gratuitamente a nuestro blog, donde encontrará información técnica de interés.