Magíster en Ingeniería con Tecnología de Información / En industrias altamente competitivas como las líneas aéreas, la estrategia de relación estrecha con el cliente y el modelo de negocio, asociado a determinar demanda y segmentarla de modo de poder determinar la oferta (cuándo y cómo vender) de aviones por asientos para una determinada ruta, hace la diferencia en el negocio aéreo. Para esto existe una técnica llamada Revenue Management, que permite a las empresas generar rentabilidad en el corto y largo plazo. El rediseño de procesos se basa en la metodología de diseño, a partir de patrones de procesos, que es detallada desde la arquitectura de procesos hasta el diseño del apoyo computacional y lógicas de negocio requeridos para implementarlo. Además, se realizó una prueba de concepto para el proceso de Pronóstico y Optimización de vuelos, donde se corroboró la desactualización del modelo y se redujo el porcentaje de falla, llegando a un 7%, mediante una calibración de los datos históricos y cargando near real time , los cambios en reservas sobre el modelo. Finalmente, la experiencia de esta prueba de concepto es generalizada en la construcción de un Framework, desarrollado para cualquier empresa que utilice modelos predictivos y desee actualizarlos en el tiempo. En términos de la justificación económica del proyecto, se podrá ver que es alta, ya que los beneficios que otorga a la compañía por cada unidad del porcentaje de error que se disminuyan y las nuevas oportunidad que genera a las áreas de ventas, se espera que sean del orden de los 2 millones de usd. Haciendo muy rentable el proyecto, pagándose en el mes 8 de proyecto.

El tema principal de esta memoria es el estudio del problema de planificación minera, junto con el análisis detallado de un nuevo algoritmo propuesto en la literatura para resolverlo. El problema de planificación minera consiste en determinar la secuencia de extracción de una mina a tajo abierto. Para esto, típicamente se modela la mina como un conjunto de bloques y se diseña un calendario tentativo de su extracción. En la industria minera se resuelve este problema siguiendo una serie de pasos consecutivos que terminan por entregar una planificación. Por otro lado, existen distintos modelos de optimización que han sido propuestos para resolver este problema, pero debido a que las instancias son de gran tamaño, obtener soluciones requiere de técnicas y algoritmos más elaborados. Una instancia típica posee millones de variables y millones de restricciones. Por estas razones resulta ser un problema desafiante y con una aplicación muy importante, para el cual distintos tipos de descomposiciones han sido propuestas para resolverlo, junto con pre-procesos, heurísticas o versiones simplificadas de manera de hacer el problema más manejable. Todas estas técnicas pueden resolver problemas del orden de 200.000 bloques, lo cual es bueno, pero está lejos de poder resolver problemas reales. Recientemente, Chicoisne et. al. (Operations Research, 2012) desarrollaron un algoritmo eficiente capaz de resolver instancias con millones de bloques, pero en una versión simplificada del problema. Y por otro lado, Bienstock y Zuckerberg (Optimization Online, 2009) propusieron otro algoritmo, el cual es capaz de resolver eficientemente instancias de millones de bloques y bajo ningún supuesto importante. Este último resulta ser un algoritmo muy ingenioso y será el foco principal de este trabajo estudiarlo. En el desarrollo de este trabajo se estudió principalmente el problema de planificación minera, junto con la implementación del algoritmo de Bienstock y Zuckerberg. Además, usando algunas técnicas originales y otras técnicas clásicas, se diseñaron una serie de mejoras al algoritmo que lo hacen más eficiente, aprovechando la estructura del problema de planificación minera. Se verá que estas modificaciones producen mejoras significativas en el tiempo necesario para resolver las instancias disponibles. Y por último, y como un inicio para trabajo futuro, se propone una generalización del algoritmo a un contexto más amplio. Esta generalización se implementó para un nuevo modelo de Optimización Robusta propuesto en este trabajo para el mismo problema de minería, de esta forma dando un primer paso a una nueva manera de considerar incertidumbre en este problema.

Magíster en Gestión de Operaciones / Ingeniero Civil Matemático / En general, un problema de decisión min f(x) s.a. x en F0 está sometido a una gran cantidad de factores que pueden provocar incertidumbre respecto a la delidad de los valores de los datos que de finen F0, causando que la respuesta de este no sea del todo con fiable. Existen diversos métodos para hacerse cargo de la incerteza en los datos, como el Análisis de Escenarios, la Optimización Estocástica y la Simulación, entre otras. Si el decidor es adverso al riesgo, por ejemplo en situaciones donde las decisiones son poco frecuentes o bien las consecuencias de una mala decisión ponen en riesgo la vida de personas, la Optimización Robusta, es la estrategia que le permite ser en extremo conservador, buscando soluciones óptimas que sean factibles bajo cualquier escenario posible de datos. Lamentablemente un algoritmo robusto puede consumir vastos recursos computacionales. Resulta interesante ser capaz de predecir cuánto se arriesga (en términos de la función objetivo), al utilizar una solución económica que ignora la incertidumbre en vez de una costosa solución robusta, o dicho de otra forma, cuánto cuesta una solución conservadora en relación al problema con datos estimados (fácil de resolver). Es posible acotar este valor , en términos de la sensibilidad estructural del problema, una característica intrínseca de la modelación, y el nivel de incertiza que al que estan sometidos los datos, de la siguiente forma: D <= (2/k+1) (max f(x) - min f(x)) Donde k es una medida llamada Margen de Factibilidad propuesta por Ben-Tal y Nemirovski, en situaciones donde la variabilidad de los datos puede ser modelada a través de un conjunto de incerteza U poliedral. Ellos presentan una cota superior para D y en este trabajo se construye un modelo linearizado para computar una estimación simpli cada de esta cota para problemas lineales con incertidumbre en la matriz de restricciones de desigualdad, descrita a través de un conjunto poliedral. Se aplicó este modelo a 16 problemas de la librería NETLib, asumiendo perturbaciones independientes de los parámetros considerados como inciertos. La estimación implementada consiguió buenas cotas ajustadas: Para un nivel de incerteza del 1% las cotas fueron, salvo por dos ocasiones, a lo más 6 veces el valor a estimar y en general el error de la estimación no supero el 8% del valor óptimo nominal. En estos problemas se pudo observar que el error en la cota estimada es proporcional al nivel de incerteza, de comprobarse esta idea, se presentaría una ventaja signi cativa al momento de estudiar el impacto sobre problemas con nivel de incerteza desconocido.

Magíster en Gestión de Operaciones / Ingeniero Civil Industrial / En el presente trabajo se considera el problema de asignación de asientos para diversas clases de clientes en una red de Aerolíneas, más conocido en inglés como Network Revenue Management. Usando la metodología de programación dinámica, se busca maximizar el beneficio esperado sujeto a restricciones de tiempo y capacidad de los aviones en la red. Uno de los problemas que enfrentan las aerolíneas al momento de vender vuelos interconectados en una red es qué precio fijar para cada clase de cliente de tal forma de no dejar potenciales compradores fuera al fijar precios altos, ni perder potenciales ingresos con precios bajos. Para gestionar la demanda a través del tiempo, las aerolíneas utilizan políticas de control de asientos como Booking Limits, Protection Levels o Bid Prices, cuya solución se obtiene de resolver problemas de optimización dinámicos o estáticos. Esta tesis aborda este problema cuando la demanda está sujeta a incertidumbre. Bajo este escenario el problema es altamente riesgoso, pues los costos de operación son elevados y el producto que se ofrece es perecible, es decir, los asientos libres no se pueden inventariar lo que genera pérdidas. Para enfrentar esto se propone resolver usando optimización aversa al riesgo más conocida como optimización robusta. El enfoque de optimización robusta es optimizar contra el peor de los casos que pudiera surgir debido a la incertidumbre en la demanda, encontrando políticas de control en la capacidad de los aviones relativamente insensibles a variaciones en la estimación de demanda. La formulación robusta intenta mitigar el impacto de los errores en la estimación de probabilidades de transición mediante la elección de una política óptima maximin, donde la minimización es sobre un conjunto de probabilidades de transición y el objetivo es escoger una política que maximice los beneficios esperados sobre este conjunto. Los experimentos que se realizaron muestran que cuando el riesgo supera cierto umbral, el modelo robusto captura de forma más eficiente el riesgo y obtiene resultados esperados mejores que los modelos tradicionales.

No description available.

Magíster en Gestión de Operaciones / Ingeniero Civil Matemático / En la actualidad, el flete marítimo es una actividad fuertemente ligada al desarrollo comercial entre distintos agentes alrededor del mundo. Permite, entre otras cosas, la expansión hacia nichos y mercados que de otra forma serían imposibles de alcanzar y con costos menores en relación a otros medios de transporte. El uso de contenedores, y por ende la logística de ellos, es clave en este aspecto, pues son el elemento básico de esta industria. Consideramos el caso de Compañía Sudamericana de Vapores (CSAV), empresa de transporte marítimo que posee puntos de operación en diversas zonas geográficas del planeta. En cada uno de éstos, la compañía mantiene un stock de contenedores vacíos de distinto tipo con la finalidad de suplir la demanda por ellos. Cuando un cliente solicita un contenedor, este es llenado con la carga y transportado en una nave hacia otra localidad, donde se desembarca y es devuelto vacío a la compañía. Si bien casi siempre los contenedores son retornados a manos de la empresa, esto no siempre ocurre en el lugar o momento indicado, creando situaciones de exceso de ellos en algunas zonas y falta en otras, efecto denominado desbalance comercial. Por esto, la compañía realiza movimientos de reposición de manera de distribuir eficientemente los contenedores entre sus puntos de operación. Dado que la demanda tiene un elemento de incertidumbre importante, es necesario el desarrollo de una planificación de inventario y resposicionamiento que considere este factor. En este trabajo extendemos algunos aspectos del sistema de apoyo a las decisiones que CSAV ha implementado recientemente. Como primer paso, proponemos una formulación alternativa para el problema básico de movimiento de contenedores, el cual reduce en forma sustancial los tiempos de ejecución en relación a la formulación usual. Luego derivamos modelos robustos ante demanda, retorno y tiempos de viaje inciertos. Finalmente proponemos un modelo robusto ajustable para la relajación lineal del problema con demanda y retorno inciertos. Los experimentos numéricos indican que esta última metodología disminuye el costo nominal de las soluciones robustas, lo que es apoyado mediante simulaciones en distintas instancias.