Algoritmo basado en generación de columnas para el problema de ruteo de vehículos dinámico

Abstract

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.