No description available.

No description available.

Magíster en Ciencias de la Ingeniería, Mención Transporte / Ingeniero Civil Matemático / El objetivo de esta tesis es formular un modelo que integre el Pickup and Delivery Problem (PDP) y la localización óptima de los depots de distribución, el cual llamaremos Problema de Localización y Ruteo con Pickup and Delivery (PLRPDP). Este problema se plantea y tiene una gran variedad de aplicaciones en la industria, como por ejemplo en el courier, en el transporte de pasajeros, o en el transporte de alimentos perecibles, y por lo tanto es de suma importancia cuando existe un sistema de alta demanda con diferentes opciones en relación a la ubicación de los depots. Para modelar este problema se propone un esquema de generación de columnas, donde el problema maestro resultante es similar al del modelo propuesto por Berger et al. (2007), pero en este caso, el subproblema es un PDP. Para resolver este subproblema y poder generar columnas factibles para el problema maestro, se propone un algoritmo de label-setting, que resuelve el problema de camino más corto, con restricciones de Pickup and Delivery y ventanas de tiempo. Además se propone un conjunto de heurísticas para acelerar este proceso. Para validar el modelo, se hace una implementación del esquema de generación de columnas, el cual se prueba en diferentes instancias, algunas ya existentes en la literatura actual, como también desarrolladas en este trabajo. Destacando dentro de estas últimas, las instancias clusterizadas y las de tipo corredor, las cuales por su geometría especial hacen que la localización de los depots sea de suma importancia. También se hace un análisis detallado de como los costos de apertura de los depots inciden en la solución óptima. Finalmente se presentan resultados del rendimiento de nuestra implementación para cada una de las instancias.

El trabajo se ha desarrollado en la Compañía de Petróleos de Chile COPEC S.A., empresa dedicada exclusivamente a la distribución de combustible, la cual en el año 2008 creó un servicio exclusivo para pequeños clientes industriales. Aunque ha existido un aumento en los niveles de venta a través de los años, en la actualidad éste no opera de manera eficiente, generando pérdidas de hasta 3 horas diarias por camión, sólo por encontrarse distante el lugar de carguío de los clientes. Totalizando 247,5 hrs mensuales entre los 5 vehículos que operan, lo que se estima en un costo de MM$4,1. Como objetivo principal se ha planteado determinar las ubicaciones óptimas para establecer centros de carguío, considerando la demanda proyectada, distancia al cliente y los costos de implementación, utilizando la red existente de Estaciones de Servicio que en la actualidad alcanzan las 176 para la Región Metropolitana. Además, estimar la demanda futura de combustible, ítem que ha sido resuelto utilizando el modelo de suavización Holt-Winters, permitiendo calcular el crecimiento del consumo para los siguientes 4 años. La situación descrita se ha planteado como un problema de programación entera mixta (MIP), en el que el modelo minimiza el costo de habilitar Estaciones de Servicio, agregar nuevos estanques y del transporte del combustible, sub-dividiendo en dos tramos distintos este último, el realizado por medio de camiones tradicionales (33 m3) entre la planta de almacenamiento y el centro de despacho y el segundo, entre el centro de despacho y el cliente final, utilizando camiones de 5 m3, los cuales poseen un costo unitario $/(Litro*Kilómetro) superior al promedio. Las principales restricciones del problema radican en la capacidad limitada de las E/S, debido a que conservan el negocio de la distribución a vehículos menores, limitación que se suple con un aumento en la frecuencia de recarga desde la planta de almacenamiento y/o un eventual aumento en la capacidad instalada, por medio de un estanque adicional. Los 1048 clientes industriales analizados se han agrupado en 35 zonas de 5 km2, lo que permite reducir considerablemente el tamaño del problema. Las dos inversiones: habilitación de la E/S e instalación de estanque promedian un costo de MM$9,2 y MM$12,5 respectivamente. La propuesta se ha enfocado en el sector nororiente de la Región Metropolitana, ya que en él se genera un 37,5% de las ventas con tan solo un 12% del total de comunas. Bajo este escenario el modelo resuelve utilizar 3 Estaciones de Servicio y agregar 1 estanque adicional, los que deben estar operativos antes del primer trimestre de proyección. Esta solución disminuye en un 65% el costo respecto a continuar con el modelo actual, desde MM$427,5 a MM$149,6, incrementando en igual proporción los ingresos brutos, desde MM$362,7 a MM$671,5 en todo el período de análisis. Además, la propuesta reduce en un 76% la distancia promedio entre los clientes y los centros de carguío, lo que significa bajar de 21,9 a 5,6 kms. la distancia que percibe el cliente final.

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.

No description available.

La programación de las actividades quirúrgicas en un centro médico es un proceso muy complejo. La elección de los horarios y la asignación de recursos impactan directamente en el número de pacientes tratados y en el nivel de rendimiento del sistema. Las complicaciones de la asignación surgen del gran número de consideraciones que se deben tener cuando se realiza la programación. Un aspecto importante a considerar en la programación de pabellones es la prioridad relativa de los pacientes, la que se basa en criterios de tiempos de espera y categorización biomédica del diagnóstico. El objetivo principal de este proyecto es desarrollar y comparar modelos de optimización que permitan la programación de intervenciones quirúrgicas electivas en pabellones durante intervalos de tiempo específicos. El proyecto pretende obtener una optimización en el uso del recurso pabellón, reducción de los tiempos de espera de los pacientes y hacer un uso eficiente de los recursos humanos necesarios. En este trabajo se desarrollaron cuatro modelos que permiten la asignación de pacientes a pabellones y horarios específicos: dos de ellos basados en programación matemática entera, uno en algoritmos del tipo Backtracking y un modelo mixto. Los modelos desarrollados se estudiaron bajo distintos escenarios, basados en información real de hospitales públicos de Chile. Los modelos se evaluaron en función del tiempo de ejecución y la calidad del resultado. Para determinar la calidad del resultado, se midió la utilización del recurso pabellón de la solución entregada y el respeto de la prioridad relativa de los pacientes que son asignados. Las pruebas realizadas permiten concluir que la elección del modelo, entre los modelos desarrollados, depende fuertemente de las características de los escenarios. En escenarios reales, es posible, mediante la utilización de estos modelos obtener mejoras entre un 10% y un 15% del tiempo total disponible en pabellón, comparado con los métodos manuales utilizados actualmente.

Magíster en Gestión de Operaciones / Cada día Santiago de Chile se convierte en una ciudad con más habitantes y, consecuentemente, con un mayor número de vehículos. El Cuerpo de Bomberos de Santiago (CBS) se le presenta, entonces, un gran desafío, pues debe atender a una emergencia en poco tiempo y al mismo tiempo lidiar con calles y avenidas congestionadas. El Departamento de Ingeniería Industrial de la Universidad de Chile (DII), ha desarrollado herramientas que apuntan a encontrar rutas óptimas para llegar a una emergencia con el fin de ayudar en su labor a CBS. Sin embargo, estas aplicaciones, hasta el momento, no utilizan criterios que incluyan la distribución de probabilidad de estos tiempos, lo que podría ayudar a tomar mejores decisiones. Usando datos del sistema de transporte urbano de Santiago, Transantiago, se busca estudiar la distribución de los tiempos de viaje por arcos de un grafo que representa esta ciudad. Se propone una metodología que abarca desde el manejo de estos datos, hasta un modelo que permite estimar distribuciones. Inicialmente, se sugiere un modelo de datos con sus índices. Luego, se da paso a la descripción de métodos para la identificación de rutas seguidas por los distintos servicios. Haciendo uso de algoritmos de proyección y Cadenas de Markov, se logran procesar más de 5300 arcos, los que posteriormente, se utilizan para proyectar tiempos de viaje y velocidades. Con los datos procesados, estas variables aleatorias se estudian en su distribución de probabilidad, comportamiento a lo largo de un camino y criterios de ajuste. Los tiempos de viaje muestran ser una variable aleatoria de distribución Lognormal para una gran cantidad de arcos. Los resultados obtenidos, además, permiten encontrar un perfil para los arcos que presentan un mejor ajuste, tanto por sus características espaciales como temporales. Junto con ello, se resuelve si estos tiempos son independientes o no. Finalmente, en base a los resultados se establece que es importante incluir la correlación entre los tiempos de viaje. Se estudia la suma de tiempos en caminos arbitrarios, comparándola con datos reales. Los resultados permiten validar el modelo propuesto, e identificar qué método para la suma de variables es mejor. Finalmente se analizan distribuciones para bloques de horarios, concluyendo que los tiempos de viaje es mejor tratarlos de la forma más desagregada posible. Para trabajos futuros se recomienda analizar mezclas de Lognormales para los tiempos de viaje y estudiar la distribución Burr como una alternativa.

Magíster en Ciencias de la Ingeniería, Mención Eléctrica / En esta Tesis se presentan estrategias de Control Adaptable por Modelo de Referencia de orden entero y de orden fraccionario, aplicados a los Reguladores Automáticos de Voltaje utilizados en sistemas eléctricos de potencia. El documento se enfoca en la sintonización de las ganancias y órdenes de derivación de las leyes ajuste de ambos esquemas de control, asociados a la minimización de funciones objetivo no lineales y de alta dimensionalidad, mediante el uso de tres técnicas a mencionar; Programación Cuadrática Secuencial, Optimización por Enjambre de Partículas y Algoritmos Genéticos. Se estudian dos modelos comúnmente usados en el estudio de Reguladores Automáticos de Voltaje, que son los que se reportan en la literatura técnica. Estos modelos establecen los tres casos de estudio analizados en este documento. Finalmente, con el objetivo de analizar las ventajas y desventajas del controlador adaptable por modelo de referencia se realizan comparaciones con los resultados encontrados en la literatura, en particular con la técnica de control PID de orden entero y de orden fraccionario. Por otro lado, también se realizan comparaciones entre algoritmos de optimización para demostrar, mediante algunos índices de rendimiento, que los controladores de orden fraccionario con parámetros optimizados por la técnica de Optimización por Enjambre de Partículas, entrega mejores resultados en términos de robustez frente a variaciones paramétricas del modelo de la planta y mejoras en relación a la velocidad de convergencia de las señales a los valores de referencia del sistema de potencia.

Magíster en Gestión de Operaciones / Las agencias de seguridad alrededor del mundo enfrentan el reto de proteger objetivos sensibles, tales como aeropuertos, puertos u otras infraestructuras críticas. Para ello, toman acciones preventivas y asignan recursos de defensa a patrullar un objetivo. El problema es que, por lo general, los recursos a su disposición son limitados y la cantidad de objetivos a defender puede llegar a ser muy grande, por lo que la labor de asignación de recursos puede llegar a ser muy compleja y costosa en términos computacionales. Para enfrentar este problema, un enfoque es utilizar técnicas de teoría de juegos para captar el razonamiento entre el defensor y los atacantes o criminales, específicamente se usan los Juegos de Seguridad de Stackelberg, ó SSG por sus siglas en inglés. Los SSGs son parte esencial de varias aplicaciones actualmente en uso por diversas agencias de seguridad en Estados Unidos y su éxito ha generado que el interés por estos aumente, por lo que muchos autores han dado diversas contribuciones sobre este tema. Sin embargo, uno de los puntos que aún es un tema abierto de estudio es la escalabilidad de las formulaciones, ya que los modelos existentes tienen un bajo desempeño cuando el número de tipos de atacantes es grande, lo que resulta inadecuado para problemas complejos del mundo real. Una instancia cualquiera de SSG tiene muchas posibles formulaciones, este trabajo de tesis estudia tres: (SSMG), (DOBSS-SSG) y (MIP-SSG). Estas formulaciones son equivalentes entre sí, que tienen diferencias en términos de tamaño y fortaleza, lo que hace que no sea evidente cúal es la de mejor desempeño, pero todas resuelven el problema, en ámbitos con múltiples tipos de atacantes, aprovechando la estructura propia de los juegos de seguridad donde la utilidad de los jugadores depende solamente de si el objetivo atacado esta protegido o no, logrando de esta manera una representación compacta y acelerando los tiempos de ejecución. Este trabajo describe y analiza cada una de estas formulaciones comparándolas tanto desde el punto de vista de modelación como computacional. En el aspecto de modelación se muestra el efecto de incorporar una representación logarítmica de las las variables enteras y el efecto de restringir el espacio de soluciones. En el aspecto computacional, el enfoque esta en el rendimiento, en términos del tiempo de ejecución requerido para hallar una solución, sobre un conjunto amplio de instancias, poniendo énfasis en escalar tanto el número de tipos de atacantes como el número de objetivos a defender. Se compara las formulaciones entre sí y se detalla las ventajas de estas sobre las formulaciones presentes en la literatura.