Introducción, contexto, y planteamiento informal
El Problema del Viajante de Comercio o TSP por sus siglas en inglés -Travelling Salesman Problem. - es un problema clásico dentro de la Investigación Operativa, concretamente en los problemas de optimización combinatoria, con unos costes de cálculo computacional muy elevados. Su dificultad exponencial le hace entrar en la categoría de problema NP-Completo, por lo que probablemente no tenga solución en un tiempo polinómico (ver PvsNP).
Fue planteado por primera vez en los años 1800s por W. R. Hamilton y T. Kirkman a raíz del Puzzle Icosian que consistía en hallar ciclos hamiltonianos. Entre los años 1950 y 1960 el problema fue tomando popularidad conforme avanzaban las ciencias computacionales.
Destacamos los estudios llevados acabo por G. Dantzig, D. R. Fulkerson y S. M. Johnson, quienes plantearon por primera vez el problema como un Problema Lineal Entero y aplicaron el método de Planos Cortantes (coloquialmente de Ramificación y Poda) para hallar soluciones.
Más tarde R. M. Karp demostraría su pertenencia a los problemas NP-Completos
En los años 1990 nació el programa Concorde dedicado a la resolución de TSPs y en 2006 halló solución para 85900 nodos, tratándose en dicho caso del recorrido más óptimo para el grabado de un microchip.
El enunciado coloquial del problema reza:
Dada una lista finita de ciudades y la distancia entre cierto número de ellas ¿Cual es la forma más corta de pasar por todas ellas sólo una vez?
Obtener mejores resultados en la resolución del TSP resultaría de gran utilidad para agencias de transportes, servicios de correos, infinidad de procesos industriales, análisis del ADN, hobbits intentando llegar a Mordor, etc. En España, por ejemplo, el sector del transporte supuso entre 2005 y 2009 un 4.2% del Valor Añadido Bruto nacional y continuó su crecimiento situándose en el año 2011 en el 4.8% según los datos de la CEOE.
En el desarrollo de este curso veremos el desarrollo formal del problema, los métodos más competitivos para su resolución y expondremos el software que hemos diseñado para hallar soluciones de la forma más óptima acompañado de ejemplos implementados en la aplicación y una guía para que usted mismo pruebe sus propios problemas.