Desarrollo y aplicación del algoritmo de Optimización basado en Colonia de Hormigas (ACO) para la resolución del Problema del Viajante Asimétrico (ATSP)

Abstract

Los algoritmos evolutivos, concretamente los basados en Colonia de Hormigas, ACO, están cobrando cada vez más importancia en el campo de la metaheurística, así como su aplicación para la resolución de problemas de optimización combinatoria. Uno de los problemas más comunes y difíciles de resolver que se clasifica como NP-duro, es el Problema del Viajante, TSP. El interés en el estudio de las técnicas metaheurísticas para la resolución de este problema radica, principalmente, en el gran número de aplicaciones prácticas en las que se encuentra. El presente documento recoge, explícitamente, el desarrollo y aplicación de un algoritmo ACO para la resolución del problema del viajante asimétrico, ATSP, cuyo fin es encontrar una solución que, satisfaciendo las condiciones iniciales del problema, proporcione una ruta o circuito cerrado cuya longitud sea la mínima. Para ello, se realizarán una serie de pruebas, a través de las cuales se obtendrán resultados que, posteriormente, se evaluarán y valorarán mediante el uso de técnicas estadísticas adecuadas.