Heurística basada en predicción de demanda y generación de columnas para resolver el problema de ruteo dinámico de vehículos con ventanas de tiempo

Abstract

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.