Un algoritmo híbrido para el problema de ruteo de vehículos con tiempos de viaje estocásticos y ventanas de tiempo suave

Abstract

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%.