Problema del viajante de comercio: Su implementación mediante un algoritmo de ruteo dinámico y aplicación de optimización de colonia de hormigas

Abstract

El presente trabajo se basa en la experimentación empírica de meta-heurísticas empleadas en al ámbito de la Inteligencia Artificial del tipo de Colonia de Hormigas, para la resolución del problema del Viajante de Comercio (TSP) y en la implementación de algoritmos eficientes para la implementación de una aplicación que trabaje en la solución del mismo. Para la implementación de las distintas instancias empleadas de este problema se emplea un algoritmo que, a diferencia de los métodos tradicionales empleados, permite la fácil diagramación y modificación de escenarios (es decir, de los grafos del problema), aportando una escalabilidad tal que facilita el trabajo con escenarios de gran número de nodos (tanto más es su ventaja cuanto mayor sea el escenario). Este algoritmo además, se adapta perfectamente a los problemas de TSP asimétrico, lo cual será verificado durante las pruebas de este trabajo. Las mencionadas pruebas, además incluirán la verificación empírica de múltiples variables estocásticas que son el fundamento de estos métodos meta heurísticos. Finalmente se incluirá y probará una variante original del método AntSystem, que consiste en una inicialización sesgada de algunas variables del algoritmo.