Magíster en Gestión de Operaciones / Ingeniera Civil Industrial / En el mundo actual la mayoría de los problemas logísticos son dinámicos; sin embargo, la investigación desarrollada hasta hoy se concentra principalmente en enfoques basados en adaptaciones de algoritmos estáticos. El vertiginoso avance de la tecnología ha incrementado significativamente las posibilidades de diseñar modelos de ruteo dinámico, lo que debe ser explotado para mejorar la eficiencia en problemas reales. En esta tesis se aborda el problema que enfrenta el Servicio Técnico de Xerox en Santiago, el cual es una aplicación real del Problema Dinámico de Ruteo de Vehículos con Ventanas de Tiempo. El objetivo es atender a los clientes con el menor retraso posible dentro de los límites factibles, minimizando a la vez los costos de trasporte. La complejidad de este problema radica principalmente en su naturaleza dinámica, ya que la información de las llamadas se conoce una vez que son recibidas durante el día, por lo que las rutas diseñadas deben ser modificadas para incorporar la nueva información cuando entran al sistema nuevos clientes. Para resolver este problema se desarrolló un algoritmo que utiliza la información histórica de las llamadas para definir Idle Points o puntos de espera, a los cuales acuden los vehículos desocupados para anticipar la demanda futura y minimizar los tiempos de respuesta. Además, se considera un sistema de puntuación según la intensidad de la demanda con el cual se premia la cobertura de las zonas con mayor intensidad de demanda y un esquema de Generación Dinámica de Columnas, en el se utilizan las rutas generadas anteriormente para diseñar nuevas columnas cada vez que surge una nueva solicitud de un cliente. El modelo fue implementado computacionalmente en C++ utilizando Ilog Cplex como motor de optimización, con el fin de realizar simulaciones con datos disponibles de la operación real y evaluar su desempeño en comparación a una versión dinámica de un algoritmo Greedy. Respecto a este benchmark se obtienen mejoras de 26% en los costos totales evaluando instancias que corresponden a 120 días de operación real de todos los meses del año. Además, se compara el modelo con dos versiones simplificadas para medir el impacto de incluir la información histórica y el covering en el modelamiento. Se observa que ambas componentes del modelo permiten disminuir los tiempos de espera de los clientes. Finalmente se comparan los resultados obtenidos con la operación manual de Xerox, obteniendo mejoras significativas en el nivel de servicio y una reducción de un 23% en el tamaño de flota requerido para la atención. Se concluye que el enfoque propuesto se adapta de manera satisfactoria a problemas dinámicos cuya prioridad es el nivel de servicio ofrecido a los clientes.

Magíster en Gestión de Operaciones. Ingeniero Civil Industrial / El desarrollo de nuevas tecnologías en los últimos años, ha permitido reducir de manera significativa los costos de los sistemas GPS y de envío de información; a la vez han existido mejoras en el rendimiento de los algoritmos de optimización y un aumento de la capacidad computacional. Estos tres factores han impulsado la investigación de problemas dinámicos, en los que una parte de la información se va revelando ha medida que transcurre el tiempo, y en particular en problemas complejos como el ruteo de vehículos. En esta tesis se diseñó, implementó y evaluó una solución para el Problema de Ruteo de Vehículos Dinámico con Ventas de Tiempo, la que está basada en el método de descomposición de generación de columnas, que emplea un algoritmo de programación dinámica adaptado especialmente para el subproblema enfrentado. El modelo ocupado en esta tesis está basado en el presentado por Weintraub et al. [1999],que considera en su función objetivo métricas tanto de calidad de servicio como costos operacionales, además una componente de cobertura, la que busca mantener una distribución espacial de los técnicos que permita una reacción temprana a la llegada de los nuevos clientes. Se incluyen también puntos de espera para los vehículos ociosos, al igual que en Briceño [2014], en zonas donde la aparición de nuevos clientes es más probable. Para evaluar la solución, se ocuparon dos casos de estudio que enfrentan problemas dinámicos desarrollados en la ciudad de Santiago. El primero corresponde al servicio técnico de reparaciones de la empresa multinacional Xerox, y el segundo al servicio de emergencias de reparaciones eléctricas de CAM; en ambos casos, el principal objetivo es brindar una alta calidad de servicio, lo que se traduce en bajos tiempos de retraso y espera a sus clientes, que generan en promedio 300 y 200 llamados diarios respectivamente. La implementación de la solución fue realizada en el lenguaje de programación Python ocupando Gurobi como motor de optimización. Cada instancia se compone de una semana real de operación, y fueron generadas a partir de las base de datos históricas de ambos casos. Los resultados muestran que los tiempos de resolución del algoritmo de programación dinámica propuesto, son significativamente menores que los requeridos para resolver el subproblema de generación de columnas directamente como problema de programación entera mixta. Se observa además que el rendimiento de la solución depende fuertemente de la relación entre el número de clientes y vehículos. En el Capítulo 5 de resultados, se analiza en detalle cómo las distintas características de cada instancia, además de las distintas configuraciones de parámetros afectan el rendimiento del algoritmo propuesto.

Magíster en Gestión de Operaciones / Ingeniero Civil Industrial / En la presente Tesis, se propone una metodología para enfrentar el Problema Dinámico de Ruteo de Técnicos con Ventanas de Tiempo. La naturaleza dinámica del problema está comprendida en los clientes que aparecen dinámicamente y deben ser asignados a la mejor ruta posible mediante algún criterio. La metodología propuesta puede ser resumida en tres pasos: - Usar información histórica para crear nodos ficticios, los que sirven como puntos de espera (y de covering) para los vehículos que han terminado sus tareas en agenda. - Resolver el problema de ruteo estático, que comprende los nodos reales y los puntos de espera, mediante Generación de Columnas. - Añadir las llamadas entrantes usando la heurística Generación de Columnas Dinámica. La Generación de Columnas Dinámica es una heurística que se basa en la propuesta de Chen, la cual genera nuevas columnas usando la información de los nuevos nodos junto con un subconjunto de las columnas generadas anteriormente en la resolución del problema estático. Mientras se generan nuevas columnas, estas pueden ser añadidas al conjunto total de columnas y resolver el nuevo problema de optimización. Esta heurística permite encontrar nuevas soluciones muy rápido, por lo cual corresponde a una buena opción para resolver problemas dinámicos donde las decisiones son tomadas en tiempo real. En cuanto a los resultados numéricos, el método propuesto (SCTTP-DCG), obtiene mejores resultados que la implementación dinámica más intuitiva realizable: el ruteo estático de nodos más la agregación Greedy de llamados dinámicos (TTP-Greedy). Por otra parte, el ruteo estático de nodos con la agregación de nodos dinámicos por medio de Generación de Columnas Dinámico (TTP-DCG) obtiene mejores resultados en comparación SCTTP-DCG. La explicación a este fenómeno tiene que ver con dos efectos: TTP-DCG gana las bondades de la inserción por medio de DCG y, además, ahorra en tiempos de desplazamiento pues no tiene que viajar a los nodos ficticios. Si bien era lógico que este fenómeno existiera, se esperaba que el SCTTP-DCG lograra recuperar los costos extra de transporte por medio de menor desplazamiento gracias a la buena ubicación frente a los llamados venideros.