Análisis del problema del viajante.

Abstract

[ES]El problema del Viajante de Comercio (TSP) trata de encontrar el camino a seguir por un comerciante, que visita una serie de ciudades, con el objetivo de hacerlo en la menor distancia (o tiempo) posible. Además, el camino se debe recorrer con la condición de finalizar la ruta en el mismo punto de partida, habiendo visitado todas las ciudades una única vez. En el presente trabajo de fin de grado se indaga sobre este tema abordando distintos métodos de resolución, los cuales se pueden dividir en función de si la técnica empleada resuelve el problema de forma exacta o aproximada (heurísticas o metaheurísticas). Posteriormente, mediante el software ofrecido por el programa Mathematica, se realiza un caso práctico con 20 nodos cuyo objetivo es comparar las soluciones ofrecidas por tres técnicas de resolución distintas.

[EN]The Travelling Salesman Problem (TSP) is about finding the path to be followed by a trader, who visits a series of cities, with the objective of doing so in the shortest possible distance (or time). Moreover, the path must be followed under the condition that the route ends at the same starting point, having visited all the cities only once. This final degree thesis investigates this issue by addressing different resolution methods, which can be divided according to whether the technique used solves the problem in an exact or approximate way (heuristics or metaheuristics). Subsequently, using the software offered by the Mathematica programme, a case study is carried out with 20 nodes, the aim of which is to compare the solutions offered by three different resolution techniques.