Estudio de El Problema del Agente Viajero (TSP) y Variaciones

El Problema del Agente Viajero (TSP, por sus siglas en inglés) es uno de los problemas de optimización más estudiados en la ciencia de la computación. El problema consiste en encontrar la ruta más corta para un vendedor que visite una lista de ciudades exactamente una vez y regrese a la ciudad de origen. Normalmente, se representa el esquema de ciudades como un grafo completo, donde cada arista tiene un peso asociado que representa la distancia entre ciudades. El TSP se relaciona con los ciclos hamiltonianos, que son caminos cíclicos en grafos que pasan por cada nodo una única vez y tienen el mismo punto de llegada y salida. A pesar de ser un problema estudiado, encontrar la solución óptima para el TSP en grafos grandes puede ser muy costoso en términos de tiempo y recursos computacionales. El TSP pertenece a la clase NP, lo que significa que es un problema cuya complejidad es muy alta y se requiere mucho tiempo y muchos pasos para encontrar la solución correcta. El trabajo se divide en 4 capítulos: en el primero se revisan los conceptos necesarios para hacer el análisis del problema, como la eficiencia y complejidad de los algoritmos, la teoría de máquinas de Turing y las clases de complejidad P, NP y NP-completo. En el segundo capítulo se analiza el Problema del Agente Viajero (TSP) en detalle, incluyendo su definición, formulaciones matemáticas, complejidad y ejemplos de problemas de la vida real que pueden ser planteados como instancias del TSP. En el tercer capítulo se explican y analizan los métodos de Robinson, Danztig, Fulkerson y Johnson para resolver el TSP. Por último, en el cuarto capítulo se desarrolla un algoritmo basado en el método de Robinson y se muestran los resultados obtenidos mediante una simulación en Python. El objetivo final es entender la complejidad del problema y los métodos utilizados para resolverlo.

• Autores: Giraldo Botero, Santiago
• Tipo de recurso: Trabajo de grado de pregrado
• Fecha de publicación: 2022
• Institución: Universidad de los Andes
• Repositorio: Séneca: repositorio Uniandes
• Idioma: spa
• OAI Identifier: oai:repositorio.uniandes.edu.co:1992/64001
• Acceso en línea: http://hdl.handle.net/1992/64001
• Palabra clave: TSP; Travelling salesman problem; Complejidad; Máquinas de Turing; Ciencia de la computación; Clases de complejidad; Matemáticas
• Rights: openAccess
• License: Attribution-NoDerivatives 4.0 Internacional