Metaheurística de optimización combinatoria para aproximar soluciones al problema del agente viajero multi-objetivo mediante cluster de ciudades

Abstract

La presente investigación propone una estrategia para la solución de problemas combinatorios. En particular, para el problema del agente viajero Multi-Objetivo. En este sentido, se presenta una metaheurística de optimización combinatoria basada en búsqueda tabú, el método del vecino más cercano y el cluster de ciudades a través del algoritmo K-Medoids. Para efectos prácticos, le llamaremos TS-KNN (por sus siglas en inglés: -Tabu Search using K-medoids and Nearest Neighbor). Este algoritmo va a permitir un avance en el campo de la optimización combinatoria, debido a que, la estrategia de cluster de ciudades, no ha sido trabajada para el problema del agente viajero multi-Objetivo. Asimismo, será de gran interés para la comunidad científica y académica, ya que la literatura cataloga al TSP (Traveling Salesman Problem), como uno de los temas de investigación más tratados dentro de la rama de la optimización combinatoria, debido a su complejidad de solución, y a que muchos problemas en la industria y en la ciencia pueden ser reducidos al problema del agente viajero. Con el fin de validar la calidad de las soluciones, se tendrán en cuenta algunas instancias KRO (por las iniciales del primer autor) presentadas por Krolak, Felts, y Marble (1971) y que están disponibles en la librería de soluciones para el problema del agente viajero, TSPLIB (En inglés: Library of sample instances for the Traveling Salesman Problem), y se compararán los resultados con soluciones generadas por otros algoritmos documentados en la literatura científica.