Método de solución para problema de rutas de vehículos dinámico y centrado en el cliente

Ponente(s): Mayra Alejandra Luna Peña, Francisco R. Angel Bello Acosta, Ada M. Ávarez Socarrás, Irma D. García Calvillo
El problema de rutas de vehículos clásico consiste en diseñar las rutas que deben seguir un conjunto de vehículos de capacidad conocida de forma tal que se satisfagan las demandas de un conjunto de clientes dispersos en un área geográfica determinada y que se obtenga el menor costo total para el recorrido de los vehículos. A diferencia del problema estático donde toda la información es conocida con antelación, nosotros en este trabajo estudiamos una variante dinámica y objetivo de minimizar la suma de los tiempos de espera de los clientes para recibir el servicio (objetivo centrado en el cliente). En los problemas dinámicos no toda la información es conocida al inicio del período de planeación por lo que debe ser actualizada a lo largo del día. En nuestro caso de estudio consideramos como fuente de variación la llegada de las solicitudes de servicio de los clientes a lo largo del periodo de planeación. Para dar solución al problema dinámico el horizonte de planeación es divido en periodos de tiempo, en cada período se deben agregar los clientes que llegaron en el período anterior y re-optimizar la solución. Diseñamos e implementamos un algoritmo metaheurístico basado en Búsquedas por Vecindades Variables (VNS por sus siglas en inglés). El desempeño del algoritmo fue evaluado utilizando instancias adaptadas de la literatura y se presenta una amplia experimentación computacional.