Matemáticas aplicadas

El problema del viajante

El problema del viajante, conocido como TSP (travelling salesman problem) es uno de los problemas más famosos de la historia: un viajante quiere visitar n ciudades, pasando una sola vez por cada una de ellas, empezando por una ciudad origen en la que terminará el recorrido. ¿Cúal es el recorrido que debe seguir para que la distancia total que recorra sea mínima?

Para explicar este problema introduciremos primero el concepto de grafo hamiltoniano: es un grafo en el que se pueden visitar todos los vértices de uno en uno sin volver a pasar por los ya visitados y acabando en un vértice adyacente adyacente al vértice desde el que se ha empezado. Si,además, el último vértice visitado es adyacente al primero, es un ciclo hamiltoniano.

El primero en proponer este problema fue el matemático W. R. Hamilton, quien propuso el juego Icosian: consiste en encontrar un ciclo hamiltoniano en el recorrido de las aristas de un dodecaedro. Hoy en día, las aplicaciones más relevantes aparecen en logística (agencias de viajes, repartos de comida a domicilio, planificación de horarios de transporte…), biología (árboles filogénicos), física (búsqueda de nuevos planetas), industria (placas de circuito impreso) y organización de datos.

A lo largo de la historia se han hecho varios avances en el TSP, no solo en el recorrido de ciudades sino también al intentar integrar el cableado en un microchip. Actualmente,el grafo con más vértices resuelto fue uno con 85900 vértices, que se aplicó  a un circuito integrado.

Hoy en día, el TSP es un problema NP-completo ya que aún no se ha encontrado la manera de  obtener una solución exacta en un tiempo razonable.Sin embargo, gracias a la búsqueda de un método de resolución para este problema tenemos grandes técnicas para resolución de problemas de programación entera como son el Branch&Bound y el Branch&Cut. Además, hay grandes algoritmos heurísticos que nos dan una solución aproximada, como el algoritmo de Christofides o el de los ahorros.

Uno de los mejores algoritmos que existen en la actualidad para resolver el TSP de forma exacta está implementado en el Software Concorde: http://www.math.uwaterloo.ca/tsp/concorde.html

Con este software se han resuelto la mayoría de problemas de la TSPLIB (una lista de problemas del viajante bastante complejos).