Solución al Problema del Agente Viajero usando un algoritmo de colonia de abejas

Solution to the TSP Problem Using an Algorithm Bee Colony

Resumen Autores/as Métricas disponibles Referencias Cómo citar

Resumen (es)

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.

Resumen (en)

The Traveling Salesman Problem (TSP) is an optimization problem that seeks the shortest possible route for a tour of n cities, starting from an origin city (node zero), visiting each city, and returning to the city of departure. This article present a solution to the Traveling Salesman Problem is presented using an exact heuristic called 2-opt combined with a bee colony metaheuristic. This combination allows for finding high-quality solutions.
Objective: To use the 2-opt heuristic and the Bee Colony metaheuristic algorithm to find solutions close to or equal to the optimum for the Traveling Salesman Problem.
Methodology: The MTZ and 2-opt heuristics were employed to generate good-quality initial solutions, which were subsequently refined through the Bee Colony algorithm to improve performance and approach optimal results.
Results: Among the results obtained for the instances from TSPLIB, which include some well-known ones such as att48, berlin52, dantzig42, datasahara, oliver30, among others, when applying the Bee Colony metaheuristic.
Results above 10 percent of the optimum were obtained, which was not satisfactory. However, by combining it with the 2-opt heuristic, the solution was improved, reaching values close to the optimum in instances such asoliver30, dantzig42, and datashara
Conclusions: Although the MTZ model is a heuristic that, due to its mathematical formulation, helps break subtours and find good initial solutions, it has the drawback that as the number of cities increases, its polynomial complexity makes it difficult to obtain a good starting point for the final solution. For this reason, we opted to use a 2-opt heuristic, which makes changes to the same route, successfully breaking subtours and finding good-quality solutions that are further improved with the Bee Colony metaheuristic.