Un algoritmo híbrido para el problema de ruteo de vehículos con tiempos de viaje estocásticos y ventanas de tiempo suave - Oviedo Reyes, Diana Marcela; Valdivieso Gomez, Karol Melissa (Universidad Industrial de Santander, 2016)
En esta investigación se implementó un algoritmo híbrido de PSO para resolver el problema de ruteo de vehículos con tiempos de viaje estocásticos y ventanas de tiempo suave. El híbrido se formó a partir de cuatro metaheurísticas que enfocan sus esfuerzos en diferentes puntos críticos de la optimización para entregar en conjunto soluciones de alta calidad. MPNS-GRASP es la primera metaheurística, la cual hace uso de procedimientos voraces y aleatorios para generar soluciones iniciales; estas soluciones pasan a ser mejoradas en una segunda etapa a través de la metaheurística Expanding Neighborhood Search quien pretende eliminar arcos de gran longitud mediante el uso del intercambio 2-opt enmarcado en la estrategia de búsqueda local por círculos restringidos. Finalmente, Path Relinking, actúa como agente de post optimización, encontrando las mejores soluciones a través de la exploración de caminos entre soluciones elites. La optimización por enjambre de partículas (PSO) actúa como algoritmo central y se encarga de la convergencia del problema a una respuesta cercana a la óptima. El algoritmo es probado en 18 problemas de las instancias de Solomon, reconocidas en la literatura como banco de prueba para el VRP con ventanas de tiempo. Los resultados obtenidos presentan variaciones con respecto a las mejores soluciones conocidas en la literatura que oscilan entre el 0% (alcanzando la mejor solución conocida en la literatura) y un 23%.
Vehicle Routing Problem, Stochastic Travel Times, Particle Swarm Optimization, Mpns-Grasp, Ens, Path Relinking.
Keywords: Problema De Ruteo De Vehículos; Tiempos De Viaje Estocásticos; Optimización Por Enjambre De Partículas; Mpns-Grasp; Ens; Path Relinking.; In this work; a hybrid particle swarm optimization (PSO) algorithm was implemented to solve the vehicle routing problem with stochastic travel times and soft time windows. The algorithm was formed based on four metaheuristic techniques that focus their solving effort on different critical points of the optimization. Firstly; Multiple Phase Neighborhood Search - Greedy Randomized Adaptative Search Procedure (MPNS-GRASP) arrange an initial set of solutions by using random and greedy procedures. Secondly; Expanding Neighborhood is based on a method called circle restricted local search moves (CRLSM); this strategy restricts the search into circles around the candidate for deletion edges. Finally; Path Relinking acts as a post optimization agent and tries to find the best solutions by means of path exploring inside the elite group of solutions. PSO is the core of the algorithm and is responsible for the convergence of the problem. This study tests the algorithm in 18 problems in the well-known data sets given by Solomon; which are recognized as a test bench for the Vehicle Routing Problem (VRP) with time windows. The final results are in the range of 0% (reaching the best solution given by the literature) and 23%.