El problema del viajante (TSP)

Abstract

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.