Memorias adaptativas para el problema de ruteo de vehículos con múltiples viajes

Abstract

En este trabajo se estudia el Problema de Ruteo de Vehículos con Múltiples Viajes o Vehicle Routing Problem with Multiple Trips (VRPMT). En esta variante del problema de ruteo de vehículos, se dispone de una flota limitada y se supone que cada uno de ellos puede recorrer más de una ruta en el mismo período de planificación. Se busca obtener, además de un conjunto de rutas de costo mínimo para visitar a los clientes, una asignación de esas rutas a los vehículos. Existe un horizonte de tiempo prefijado que limita las posibles asignaciones. La inclusión de estas características, que en la mayor parte de los modelos clásicos no son tenidas en cuenta, hace que el VRPMT sea un problema de relevancia práctica. Además reviste un alto grado de complejidad, pues encontrar una solución factible es un problema NP-Completo. Su importancia práctica y su complejidad computacional son dos aspectos que motivan el estudio de esta variante del problema. Se propone un algoritmo de resolución basado en la técnica conocida como Adaptive Memory Procedure. Esta técnica consiste en utilizar una estructura de memoria para generar soluciones iniciales sobre las que se ejecuta una heurística de búsqueda local. Las soluciones obtenidas por dicha heurística se utilizan, a su vez, para modificar la informaciónn almacenada en la memoria. En este trabajo se utiliza un algoritmo de búsqueda local basado en la metaheurística Tabu Search. Se experimenta con dos estrategias para reducir el tamaño de las vecindades y el tiempo de ejecución. Los algoritmos fueron evaluados sobre un conjunto de instancias de prueba, obteniendo soluciones que pueden considerarse de buena calidad. En particular, se resolvieron instancias para las que los trabajos anteriores únicamente reportaban soluciones no factibles.