Un algoritmo memético para el problema de rutas de vehículos con restricción de capacidad

Abstract

RESUMEN: Un problema central en el ámbito del transporte y la logística es encontrar rutas de mínimo coste bajo ciertas restricciones. En los últimos años, este tipo de problemas ha captado la atención de los investigadores en ciencias de la computación por dos razones. La primera de ellas es la gran cantidad de aplicaciones en la vida real que tienen este tipo de problemas, que van desde la distribución de puntos de recarga para vehículos eléctricos hasta el reparto de paquetes usando camiones y drones. La segunda razón es que este tipo de problemas pertenecen a la clase de complejidad NP-Hard. Dado que únicamente es posible resolver este tipo de problemas de forma exacta en tiempo exponencial, nuestro objetivo es encontrar un algoritmo aproximado que obtenga soluciones cercanas al óptimo en tiempo razonable. En este trabajo, desarrollaremos un algoritmo memético competitivo para el “Problema de rutas de vehículos con capacidad” (CVRP). Este algoritmo combina un algoritmo genético con una búsqueda local, denominada búsqueda tabú granular, e incorpora dos heurísticos voraces para proporcionar semillas a la población inicial. Además, utiliza varios mecanismos de control de diversidad. Se ha evaluado la calidad del algoritmo desarrollado a través de la ejecución de instancias de uso común en la literatura, para las cuales se han obtenido soluciones cercanas al óptimo. Por otro lado, se ha realizado un estudio de sinergia entre las distintas componentes que constituyen el algoritmo memético para comprobar si su rendimiento es mayor de forma conjunta que por separado.

ABSTRACT: One of the central problems in the area of transportation and logistics is to find minimum cost routes under certain restrictions. In recent years this kind of problems has caught the attention of computer science researchers for two reasons. The first one is the huge number of real life applications that have this kind of problems, ranging from the distribution of charging points for electric vehicles to the delivery of packages using trucks and drones. The second reason is that this kind of problems belongs to the complexity class NP-Hard. Since solving this kind of problems using exact methods is only possible in exponential time, our goal is to obtain an approximate algorithm that yields solutions close to the optimum within reasonable time. In this work, we develop a competitive memetic algorithm for the “Capacitated vehicle routing problem” (CVRP). This algorithm combines a genetic algorithm with a local search, called granular tabu search, and uses two greedy heuristic algorithms to seed the initial population. In addition, it incorporates several diversity-control mechanisms. The quality of the developed algorithm has been evaluated using commonly used benchmarks, obtaining in most of the cases solutions close to the optimum. Besides, a synergy studied has been carried out to discover the interactions among the di↵erent components of the memetic algorithm.