Aplicación del sistema de hormigas para el problema de enrutamiento de vehículos de suministros en desastres naturales

Abstract

El tiempo de respuesta y la eficiencia de los vehículos de suministros las primeras horas después de desastres naturales es un factor crítico de la mitigación de la crisis. Estas circunstancias son comúnmente modeladas como un problema de enrutamiento de vehículos con múltiples depósitos (MDVRP por sus siglas en ingles). Este problema consiste en un conjunto de puntos que deben recibir cierta cantidad de suministros, entregados a partir de un conjunto de depósitos y vehículos que deben comenzar y finalizar sus rutas en dichos depósitos, respetando limitaciones de tiempo y capacidad de los vehículos. Este trabajo propone un algoritmo de optimización por colonias de hormigas para encontrar soluciones al problema. El algoritmo construye soluciones inspirado en el comportamiento de las hormigas, las cuales utilizan feromonas para indicar a sus pares las mejores rutas que han encontrado. Esto se aplica en la construcción de soluciones, ponderando movimientos aleatorios con información histórica contenida en estas feromonas. Luego de dicha construcción, se aplican operadores de búsqueda local para mejorar las soluciones obtenidas, y luego se depositan mas feromonas para las hormigas de la iteración siguiente.