Trabajo Fin de Grado
El problema del viajante (TSP)
Autor/es | Infantes Durán, Miguel |
Director | Puerto Albandoz, Justo |
Departamento | Universidad de Sevilla. Departamento de Estadística e Investigación Operativa |
Fecha de publicación | 2018 |
Fecha de depósito | 2018-07-24 |
Titulación | Universidad de Sevilla. Grado en Matemáticas |
Resumen | El clásico problema del viajante de comercio se puede enunciar como: ’si un viajante parte de una ciudad y las distancias a otras ciudades son conocidas, ¿cuál es la ruta óptima que debe elegir para visitar todas las ... El clásico problema del viajante de comercio se puede enunciar como: ’si un viajante parte de una ciudad y las distancias a otras ciudades son conocidas, ¿cuál es la ruta óptima que debe elegir para visitar todas las ciudades y volver a la ciudad de partida?’. El estudio de este problema de programación entera es el objeto de este trabajo. Comenzaremos con una introducción histórica mostrando las inquietudes que hicieron nacer el problema del viajante a mediados del siglo XX. A continuación, veremos la gran dificultad del problema, hallar un circuito Hamiltoniano. En el último capítulo estudiaremos diferentes métodos de resolución basados en la ramificación y la acotación. Por último, veremos algún ejemplo a modo de aplicación del problema. |
Cita | Infantes Durán, M. (2018). El problema del viajante (TSP). (Trabajo Fin de Grado Inédito). Universidad de Sevilla, Sevilla. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
Infantes Durán Miguel TFG.pdf | 547.8Kb | [PDF] | Ver/ | |