Complete stochastic forestry planning problem using progressive hedging algorithm

Abstract

El trabajo desarrollado en esta tesis se enmarca dentro del área de investigación de operaciones, en el campo de la optimización estocástica para un problema de planificación forestal, el cual se modela como un problema lineal de carácter mixto. El problema de planificación forestal abordado en esta tesis consiste en la maximización del valor presente del plan de explotación táctico de un conjunto de 17 bosques sujeto a incertidumbres internas (rendimiento de los diversos predios) y externas (precio de los productos y cantidad demandada de estos), incertidumbres que se representan a través de árboles de escenarios. Dentro de las principales decisiones a realizar se encuentra la construcción y/o mejora de caminos de la red interna junto a la cantidad de cada predio que será cosechada, almacenada y vendida durante cada periodo. Llevar a cabo la resolución de este tipo de problemas estocásticos bajo las técnicas de optimización tradicionales se vuelve inabordable en la medida que el tamaño de la instancia aumenta, lo que justifica la utilización de un algoritmo adecuado para alcanzar resultados en tiempos razonables. La metodología de resolución utilizada se basa en el algoritmo de descomposición por escenarios Progressive Hedging (PH) sobre el cuál se realizan una serie de ajustes según las características del problema con tal de obtener mejores rendimientos. Junto a esto, se realizan una serie de comparaciones de diversas implementaciones del mismo algoritmo con respecto a técnicas de optimización tradicionales, determinando y analizando las ventajas que ofrece PH para el problema en estudio. Se implementa una metodología de generación de árboles de escenarios basada en un modelo matemático robusto, utilizando como punto de partida un proceso estocástico para representar el movimiento de las variables aleatorias, lo que permite obtener soluciones rigurosas y de calidad. Se lleva a cabo un estudio detallado respecto a técnicas de reducción de escenarios, así como del desarrollo de una metodología de simulación que permite comparar de forma cuantitativa el rendimiento de modelos estocásticos y determinísticos, permitiendo estimar el número suficiente de escenarios que logran representar de buena manera la realidad, manteniéndose óptimo el trade-off entre calidad de solución y tiempos de cómputo involucrados. Los resultados concluyen que la utilización del algoritmo PH bajo las configuraciones y ajustes realizados ofrece rendimientos superiores a las técnicas de optimización clásicas y tradicionales para problemas estocásticos de gran escala, con la posibilidad de explotar de gran manera su implementación en paralelo, obteniéndose así rendimientos superiores en la medida que se cuente con mayores recursos computacionales. Se determinan los mejores métodos para llevar a cabo la reducción del número de escenarios de la instancia original, permitiendo así el manejo abordable de instancias que inicialmente se presentan complejas. Finalmente, la aplicación de la metodología de comparación de rendimiento entre modelos determinísticos y estocásticos fue satisfactoria, determinándose un rango para el número suficiente de escenarios a utilizar dentro del modelo en estudio de tal forma de alcanzar un punto óptimo entre calidad de la solución y el rendimiento computacional del modelo.