Análisis del Problema del Viajante: algoritmo del Vecino más Cercano (NN) versus Algoritmo Genético (GA)

Abstract

[ES]El presente trabajo analiza el Problema del Viajante (TSP, por sus siglas en inglés) a través del estudio de dos algoritmos diferentes para su resolución: el algoritmo heurístico del Vecino más Cercano (NN) y el algoritmo metaheurístico Genético (GA). Se desarrollan implementaciones de ambos algoritmos en el programa de RStudio y se aplican a tres problemas específicos: uno de elaboración propia (las nuevas 7 maravillas del mundo) y dos estudios previos (problemas de 15 y 20 ciudades). Se compararon los resultados obtenidos en términos de distancia mínima alcanzada y el tiempo de cómputo. Los resultados indican que el algoritmo NN, aunque es simple y rápido, es dependiente de la ciudad de inicio y de decisiones parciales, mientras el algoritmo genético GA, aunque es más complejo y tiene un mayor tiempo de cómputo, aborda soluciones globales y ofrece soluciones más optimizadas dependiendo de la configuración de sus operadores.

[EN]The present work analyses the Traveling Salesman Problem (TSP) through the study of two different algorithms for its resolution: the heuristic Nearest Neighbor Algorithm (NN) and the metaheuristic Genetic Algorithm (GA). Implementations for both algorithms were developed in RStudio and applied to three specific problems: one our own elaboration (the new 7 Wonders of the World) and two previous studies (problems of 15 and 20 cities). The obtained results were compared in terms of the minimum distance achieved and computation time. The results indicate that the NN algorithm, although simple and fast, is dependent on the starting city and partial decisions, while the GA, although more complex and having a longer computation time, deals with global solutions and offers more optimized solutions depending on the configuration of its operators.