El problema del viajante

El problema del viajante o the traveling salesman problem (TSP), consiste en encontrar la ruta que lleva a cabo un vendedor, que comenzando por un origen visita un determinado y preestablecido conjunto de ciudades y vuelve a ese origen, de manera que la distancia recorrida total es mínima y cada ciudad sólo se visita una vez.

Si se desea expresar el problema de forma matemática utilizando la teoría de grafos, el TSP consistiría en encontrar en una red G el ciclo Hamiltoniano tal que la suma de los costes de las aristas que componen este ciclo sea lo más pequeña posible.

La naturaleza de la red definirá el tipo de TSP que se construye a partir de ella, y más concretamente lo hará su matriz de costes. Así, si la matriz de costes es simétrica, es decir, el grafo de la red es no dirigido, el TSP es llamado the symmetric traveling salesman problem (STSP). Si el grafo de la red es dirigido, la matriz de costes no tendrá porqué ser necesariamente simétrica, y en este caso se define el asymmetric traveling salesman problem (ATSP). Como todo grafo no dirigido puede transformarse en uno dirigido duplicando las aristas de manera que haya una en cada sentido, el STSP puede verse como un caso especial del ATSP.

El TSP es uno de los más típicos y mejor estudiados problemas de la optimización combinatoria, pero a pesar de ello aún no se conocen algoritmos que lo resuelvan de forma exacta. Los algoritmos utilizados para su resolución sólo ofrecen aproximaciones, y la solución óptima sólo es alcanzable para casos concretos del problema.

Dentro de esta optimización combinatoria de la cual el TSP es objeto de estudio, se le cataloga como un problema NP-completo, lo que significa que el esfuerzo computacional que se debe llevar a cabo para encontrar una solución óptima crece de forma exponencial con la entrada del problema, que en el caso concreto de TSP sería el número de nodos o vértices de la red.

Por lo tanto el número de nodos de la red va a ser fundamental en determinar la complejidad del problema. Cuanto mayor sea el número de nodos, mayor va a ser el número de rutas posibles, y por lo tanto mayor será el esfuerzo requerido para calcular todas ellas. Así, el número de rutas posibles entre N nodos va a ser igual a N!, lo que hace que la resolución del TSP mediante la obtención de todas las rutas posibles y comparación entre ellas sea poco factible incluso para un número de nodos no elevado. Sólo con tener una red simple de 7 nodos, ya sería necesario calcular más de 5000 combinaciones, (7!=5040), y elevando simplemente hasta 10 el número de vértices de la red, las posibles rutas se disparan hasta más de tres millones (10!=3.628.800).

Por esta razón, la resolución del TSP en redes relativamente simples mediante el método de obtención y comparación de todas las rutas es absolutamente inabordable mediante los medios computacionales disponibles actualmente, lo que hace que sea necesario utilizar otras vías que aunque no obtengan la solución óptima si que ofrecen una respuesta aproximada lo suficientemente optimizada. Mediante estas aproximaciones se han conseguido resolver TSP con varios miles de nodos, e incluso más, y estas soluciones no son ni un 1% peores que la óptima.

En cuanto a las soluciones óptimas, como se dijo anteriormente no existen métodos que resuelvan de manera exacta cualquier TSP, pero sí que existen soluciones exactas para algunos casos concretos. A lo largo de los últimos cincuenta años se han producido continuos avances en la resolución óptima del TSP, lo que ha permitido obtener soluciones óptimas para TSP con cada vez mayor número de nodos, hasta alcanzar una cifra de casi 86.000. En la siguiente tabla se recoge la cronología de los TSP resueltos óptimamente, junto con su tamaño y los autores de la solución:

AÑO AUTORES Nº CIUDADES
Evolución del TSP óptimo
1954 G. Dantzig, R. Fulkerson, S. Johnson 49
1971 M. Held , R.M. Karp 64
1975 P.M. Camerini, L. Fratta, F. Maffioli 67
1977 M. Grötschel 120
1980 H. Crowder, M.W. Padberg 318
1987 M. Padberg , G. Rinaldi 532
1987 M. Grötschel , O. Holland 666
1991 M. Padberg , G. Rinaldi 1002
1991 M. Padberg , G. Rinaldi 2392
1994 D. Applegate, R. Bixby, V. Chvátal, W. Cook 7397
1998 D. Applegate, R. Bixby, V. Chvátal, W. Cook 13509
2001 D. Applegate, R. Bixby, V. Chvátal, W. Cook 15112
2004 D. Applegate, R. Bixby, V. Chvátal, W. Cook 18512
2004 D. Applegate, R. Bixby, V. Chvátal, W. Cook, K. Helsgaun 24978
2004 W. Cook, Espinoza, Goycoolea 33810
2006 D. Applegate, R. Bixby, V. Chvátal, W. Cook 85900