Doctor en Sistemas de Ingeniería / Muchos problemas de decisión industriales o logísticos pueden ser vistos como problemas
de optimización y para muchos de ellos no es razonable ocupar datos deterministas. Como
veremos en este trabajo en el contexto de despachos de emergencia o de planificación de
seguridad, las condiciones reales son desconocidas y tomar decisiones sin considerar esta incertidumbre pueden llevar a resultados catastróficos. La teoría y la aplicación de optimización
bajo incertidumbre es un tema que ha generado un amplio área de investigación. Sin embargo,
aún existen grandes diferencias en complejidad entre optimización determinista y su
versión incierta. En esta tesis, se estudian varios problemas de optimización con aversión
al riesgo con un enfasis particular en el problema de camino más corto (RASP), problemas
estocásticos en redes en general y juegos de seguridad de Stackelberg.
Para obtener distribuciones de tiempos de viaje precisos sobre una red vial a partir de
datos GPS del sistema de tránsito, se presenta una revisión de los métodos existentes para
proyectar trayectorias GPS y se definen dos nuevos algoritmos: Uno que permite la proyección
de datos óptima con respecto a una medida de error convenientemente definida (MOE), y
un método heurístico rápido que permite proyectar grandes cantidades de datos de manera
contínua (MMH). Se presentan resultados computacionales en redes reales y generadas
de gran tamaño. Luego, se desarrollan algoritmos eficientes para problemas de ruteo con
aversión al riesgo utilizando métodos de Sample Average Approximation, técnicas de linealización y métodos de descomposición. Se estudian la medida de riesgo entrópica y el Conditional Value at Risk considerando correlaciones entre las variables aleatorias. Se presentan resultados computacionales prometedores en instancias generadas de tamaño mediano. Sin embargo, la naturaleza combinatorial de los problemas los vuelve rapidamente intratable a medida que el tamaño del problema crece. Para hacer frente a esta dificultad computacional, se presentan nuevas formulaciones para problemas en redes difíciles, que tienen un menor número de variables enteras. Estas formulaciones ayudan a derivar esquemas de brancheo que se aprovechan de la estructura especial de las formulaciones propuestas. Se muestra como aplicar estas ideas a los conjuntos de camino simple y de circuito hamiltoniano en redes generales, así como los conjuntos de camino simple y de corte en grafos dirigidos acíclicos (DAG). Este trabajo preliminar muestra ideas prometedoras para resolver problemas difíciles. Finalmente, se exploran las implicaciones de los métodos algortmicos y las formulaciones desarrolladas para resolver RASP en un área diferente. Se presentan nuevas formulaciones y enfoques de resolución para juegos de seguridad de Stackelberg cuando el defensor es averso al riesgo con respecto a la estrategia del atacante. Esto se puede resolver de manera polinomial cuando se enfrenta a un adversario y resolviendo un problema de optimización convexa en números enteros cuando el defensor enfrenta varios tipos de adversarios.
| Identifer | oai:union.ndltd.org:UCHILE/oai:repositorio.uchile.cl:2250/135193 |
| Date | January 2015 |
| Creators | Chicoisne, Renaud Pierre |
| Contributors | Ordoñez Pizarro, Fernando, Espinoza González, Daniel, Facultad de Ciencias Físicas y Matemáticas, Departamento de Ingeniería Industrial, Moreno Araya, Eduardo, Dessouky, Maged |
| Publisher | Universidad de Chile |
| Source Sets | Universidad de Chile |
| Language | English |
| Detected Language | Spanish |
| Type | Tesis |
| Rights | Atribución-NoComercial-SinDerivadas 3.0 Chile, http://creativecommons.org/licenses/by-nc-nd/3.0/cl/ |
Page generated in 0.0016 seconds