Solución al Problema del Agente Viajero usando un algoritmo de colonia de abejas - Villegas Flórez, Jairo Alberto; Agudelo Zapata, Ángel Augusto; Muñoz Guevara, John Andrés (Tecnura, 2025)
El Problema del Agente Viajero, o TSP por sus siglas en inglés (Travelman Salesman Problem), es un problema de optimización que consiste en hallar la ruta mínima para recorrer n ciudades, partiendo desde la ciudad de origen o nodo cero, visitando todas las ciudades y retornando nuevamente al punto o ciudad de origen. Este artículo expone una solución al problema utilizando la heurística exacta 2-opt, en combinación con una metaheurística de Colonia de Abejas, con el fin de obtener soluciones de buena calidad. Objetivo: usar la heurística 2-opt y la metaheurística algoritmo Colonia de Abejas para encontrar soluciones cercanas al óptimo, o incluso iguales, para el problema del agente viajero. Metodología: se emplearon las heurísticas MTZ y 2-opt para obtener soluciones iniciales de buena calidad, de tal forma que, al combinarlas con el algoritmo de Colonia de Abejas, estas pudieran mejorarse y tener valores cercanos o mejores que el óptimo reportado en la literatura. Resultados: Entre los resultados obtenidos para las instancias de TSPLIB, donde se agrupan casos conocidos como att48, berlin52, dantzig42, datasahara, oliver30, entre otras, la aplicación la metaheurística de colonia de abejas se llegó a resultados por encima del 10 por ciento del óptimo, valor que no era adecuado, posteriormente al combinarse con la heurística 2-opt se mejoró dicha solución alcanzándose valores cercanos al óptimo en instancias como oliver30, dantzig42 y datashara. Conclusiones: aunque el modelo MTZ es una heurística que, por su modelo matemático, ayuda a romper subtours y a encontrar buenas soluciones iniciales, presenta el inconveniente de que, a medida que se aumenta el número de ciudades, su complejidad polinómica hace difícil que se tenga un buen punto de partida para la solución final. Por esta razón, optamos por usar una heurística 2-opt que hace cambios en la misma ruta, logrando romper los subtours y encontrando soluciones de buena calidad mejoradas con la metaheurística Colonia de Abejas.