Optimización de recorridos utilizando colonias de agentes cooperativos WRP-mTW Ant System

Abstract

En el presente trabajo abordamos la resolución del problema de Ruteo de Vehículos con múltiples Ventanas de Tiempo (VRP-mTW), utilizando el método de Ant System. Dicho problema consiste en un conjunto de clientes que presentan cierta disponibilidad horaria (ventanas de tiempo), y una demanda de bienes o servicios, que les debe ser entregada por un conjunto de vehículos desde un depósito central. El objetivo es encontrar un camino que visite cada cliente exactamente una vez, satisfaciendo su demanda, sin violar las restricciones de tiempo y capacidad, minimizando el costo de traslado. Ant System es un algoritmo de propósito general inspirado en el estudio del comportamiento de colonias de hormigas. Se basa en una búsqueda cooperativa que es aplicable a la solución de problemas de optimización combinatoria. En la investigación que hemos realizado en la literatura disponible para este método, no se encontró ninguna aplicación para la resolución del problema VRP-mTW. Hemos desarrollado un algoritmo Ant System mejorado, complementado con una post-optimización, que resuelve el problema mencionado, con resultados comparables con los mejores conocidos para el conjunto de casos de prueba comúnmente utilizado para testear este tipo de problemas (set de 56 problemas de Solomon).