Metaheurísticas para el problema de ruteo de vehículos con ventanas de tiempo (VRP-TW)

Abstract

En este trabajo, se presentan 7 técnicas basadas en cuatro metaheurísticas y dos métodos exactos, las cuales son: Sistema de Hormigas (AS), Búsqueda Armónica (HS), Algoritmo Genético (GA), Búsqueda local iterada (ILS), Algoritmo primaldual (PDA) y Método dual simplex (DSM) para resolver el problema de ruteo de vehículos con ventanas de tiempo (VRP-TW), haciendo énfasis en los algoritmos híbridos entre estas técnicas, los cuales se denominan AS-GA, AS-HS, DSM-ASPDA, AS-ILS, donde a excepción de DSM-AS-PDA, las técnicas involucradas trabajan de manera entrelazada. Con el fin de analizar, comparar y caracterizar el comportamiento de las técnicas desarrolladas, estas se emplearon para resolver 12 instancias del VRP-TW. En AS-GA, se utiliza el GA para encontrar una mejor solución con la población generada por un ciclo de n hormigas dentro de AS, con la cual se actualiza el nivel de la matriz de feromona para el siguiente ciclo de hormigas. Con esto se logra guiar la construcción de una manera más eficaz, y el algoritmo genético ayuda a no converger de manera prematura, sino que debido a la codificación se diversifica el espacio de búsqueda. Dentro de AS-HS, la técnica HS sirve para guiar el comportamiento del AS a través de los cambios en la matriz de feromona, ya que se aprovecha la información de un número n de ejecuciones de la HS guardadas en la memoria armónica (HM). En el procedimiento propuesto se retoman las mejores soluciones para la actualización del nivel de la fermona. Por último, en DSM-AS-PDA se utiliza el optimizador denominado Gurobi ejecutando el método dual simplex para resolver dos relajaciones lineales del problema original. Con las soluciones regresadas por Gurobi se inicializa la matriz de nivel de fermona para AS y una vez que termina la ejecución de AS con base en la mejor solución entregada, se utiliza el algoritmo PDA para revisar si la solución encontrada es la óptima. Los resultados muestran que los algoritmos híbridos desarrollados poseen un comportamiento más robusto respecto a las técnicas reportadas en la literatura y a su vez, son capaces de generar mejores soluciones con un número menor de llamadas a la función objetivo en instancias grandes, utilizando menos recursos computacionales.

In this work, 7 techniques based on four metaheuristics and two exact methods are presented, which are: Ant System (AS), Harmonic Search (HS), Genetic Algorithm (GA), Iterated Local Search (ILS), Primal-Dual Algorithm (PDA) and Dual Simplex Method (DSM) to solve the vehicle routing problem with time windows (VRP-TW), emphasizing the hybrid algorithms between these techniques, which are called AS-GA, AS-HS and DSM-AS-PDA; where, with the exception of DSM-AS-PDA, these work in an interlaced way. In order to analyze and characterize the behavior of the developed techniques used a set of test instances for the VRP-TW. In AS-GA, the GA is used to find a better solution with the population generated by one cycle of n ants within AS, with which the level of the pheromone matrix for the next cycle of ants is updated.With this it is possible to guide the construction of a more effective way, and the GA helps to avoid the premature converge way, but due to the codification it diversifies the space of search. Within AS-HS, the HS technique is used to guide the behavior of AS through the changes in the pheromone matrix, since it takes advantage of the information of m executions of the HS stored in the harmonic memory (HM). In the proposed procedure, the best solutions for the updating of the pheromone level are taken up. Finally, in DSM-AS-PDA is used the optimizer called Gurobi executing the dual simplex method to solve two linear relaxations of the original problem. With the solutions returned by Gurobi the pheromone level for AS are initialized and once the execution of AS is terminated, based on the best solution delivered, the PDA is used to check if this solution is optimal. The results show that the hybrid algorithms developed have a more robust behavior than the techniques reported in the literature and, are able to generate better solutions with a smaller number of calls to the objective function in large instances using less computational resources.