Resumen:
En este trabajo abordamos un problema clásico de optimización combinatoria famoso por ser sencillo de enunciar pero complejo de resolver: el problema del viajante, o más conocido como TSP (Traveling Salesman Problem). La importancia del TSP radica en que diversos problemas del mundo real pueden ser formulados como instancias de este. Tiene variadas aplicaciones prácticas en problemas que aparentemente no están relacionados: se lo aplica en áreas de logística de transporte, en robótica, en control y operación optimizada de semáforos. Organizamos esta tesis en cuatro capítulos. El primer capítulo describe los orígenes y la formulación matemática del problema. A continuación, enunciamos las nociones teóricas necesarias para la demostración de que el TSP es un problema NP-Hard. En el segundo capítulo comentamos distintas clases de algoritmos con que se cuenta para resolver el TSP. El tercer capítulo se centra en el algoritmo heurístico de Lin y Kernighan, que es uno de los mejores que se conoce hasta el momento. Luego de discutir los aspectos teóricos del algoritmo, exhibimos el código de una implementación en Visual Basic del mismo realizada como parte de esta tesis. Para concluir, comentamos algunos resultados computacionales que resultan de aplicar la implementación del algoritmo a tres problemas clásicos. En el último capítulo nos dedicamos al estudio de una aplicación en particular: la secuencia de trabajos. En este problema se quiere secuenciar una cierta cantidad de trabajos en una máquina. Para realizar un trabajo tras otro, se debe realizar una transformación a la máquina, lo que implica un costo. Analizamos un método para encontrar el orden en el que deben realizarse los trabajos de forma que se minimice el costo total.
Citación:
---------- APA ----------
Stockdale, María Lorena. (2011). El problema del viajante : un algoritmo heurístico y una aplicación. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nMAT000774_Stockdale
---------- CHICAGO ----------
Stockdale, María Lorena. "El problema del viajante : un algoritmo heurístico y una aplicación". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2011.https://hdl.handle.net/20.500.12110/seminario_nMAT000774_Stockdale
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nMAT000774_Stockdale.pdf
Distrubución geográfica
