Un método evolutivo de colonia de hormigas para la solución del problema de ruteo de vehículos con demandas estocásticas

Abstract

En el presente trabajo de investigación, se desarrolla un Método Evolutivo de Colonia de Hormigas (EACO) para resolver el Problema de Ruteo de Vehículos con Demandas Estocásticas (VRPSD) con reabastecimiento preventivo para el caso de un solo vehículo. El método propuesto se fundamenta principalmente en el algoritmo Sistema de Hormigas tradicional AS, desarrollado por Dorigo et al., en el año 1996. Además, se utiliza la mutación, un operador evolutivo, para ampliar la exploración de los agentes (hormigas artificiales) hacia nuevas zonas del espacio de búsqueda y, una heurística de búsqueda local, intercambio 2-Opt, con el fin de explotar las mejores soluciones. Para estudiar el efecto de la variación de los parámetros del algoritmo Evolutivo de Colonia de Hormigas en el valor de la función objetivo, y establecer la configuración que lleve a mejores soluciones del Problema de Ruteo de Vehículos con Demandas Estocásticas, se realizó un diseño experimental. Se utilizó un banco de pruebas previamente definido para evaluar la calidad de las soluciones obtenidas por el algoritmo EACO, las cuáles fueron comparadas con la metaheurística Sistema de Hormigas tradicional. Los resultados revelan que el método propuesto supera el rendimiento del algoritmo Sistema de hormigas tradicional en las ocho instancias comparadas. 1