IMPLEMENTACIÓN DE METAHEURÍSTICAS PARA LA RESOLUCIÓN DEL PROBLEMA DE RUTEO DE VEHÍCULOS CON CAPACIDAD LIMITADA Y VENTANAS DE TIEMPO

Abstract

El presente trabajo muestra tres soluciones algorítmicas para Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) el cual corresponde a un problema NP-hard con un enfoque multi-objetivo que busca la optimización del tiempo/distancia total de las rutas (D), la cantidad de vehículos (K) y balancear el tiempo/distancia de las rutas (RB). Se trabajó con el Solomon’s Benchmark para CVRPTW de 25, 50 y 100 clientes. Las técnicas implementadas corresponden a metaheurísticas poblacionales basadas en la naturaleza: un Algoritmo Inmune Artificial de Selección Clonal (AIS), un Sistema de Colonia de Hormigas con Búsqueda Local (ANT) y un híbrido de ambas (ALL). Se utilizó ParamILS para sintonizar los parámetros asociados a cada algoritmo y para potenciar su desempeño. De esto se desprende que en comparación AIS tiene un buen desempeño en instancias pequeñas de 25 y 50 clientes pero al aumentar a 100 clientes no logra obtener soluciones al nivel de otras técnicas. Por último los resultados de ANT son buenos y se mantienen estables para todotipo de instancias comparativamente aunque no es el mejor. Por otro lado la versión híbrida ALL logra malos resultados en instancias pequeñas pero en 100 clientes logra superar en casi todas las ejecuciones a las otras versiones principalmente en el objetivo D. Además se calculó el aporte en hipervolumen de cada frente agregado para comparar desempeño de las técnicas entre sí en términos de calidad general de los resultados para todas las instancias.

This work present three diferent algorithm for solutions the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) which corresponds to an NP-hard problem with a multi-objective approach that seeks the optimization of the time/distance of the routes (D), the number of vehicles (K) and routes balance (RB). The Solomon Benchmark for CVRPTW of 25, 50 and 100 clients was used for evaluation. The implemented techniques correspond to population-based nature inspired metaheuristics: a Clonal Selection Artificial Immune System (AIS), an Ant Colony System with Local Search (ANT) and a hybrid of both (ALL). ParamILS was used to tune the parameters associated to each algorithm toenhance them. AIS shows a good performance in small instances of 25 and 50 clients, but its performance deteriorates as number of clients increases. On the other hand, the results of ANT are good and permanent for all types of instances comparatively but not the best. Finally the hybrid version ALL achieved poor results in small instances but in 100 clients managed to surpass in almost all the executions the other versions, mainly in the objective D. In addition, we use hypervolumen of each front to compare the performance among of the techniques in terms of overall quality of results for all instances.