Problema del Vendedor Viajero

El problema del vendedor viajero o TSP está enfocado en encontrar la ruta más corta en un entre un conjunto de ciudades que deben ser visitadas solo una vez. Al final de la ruta se debe volver a la ciudad por la que se partió. Todas estas ciudades deben ser visitadas por un vendedor el cual debe mantener los costos y/o las distancias viajadas lo más bajo posible, esto implica que es un problema de minimización.

Enfocado en la optimización, este problema se usa para encontrar la ruta más eficiente para viajar entre varios nodos. Fue descrito por primera vez por el matemático irlandés W.R. Hamilton y el matemático británico Thomas Kirkman en la década de 1800 a través de la creación de un juego que se podía resolver al encontrar un circuito de Hamilton, que es un camino compuesto por distintos nodos donde deben recorrerse todos sin superponerse, y el primer y último nodo deben estar conectados.

TSP se ha estudiado durante décadas y se han teorizado varias soluciones, siendo la más simple la de probar todas las posibilidades, pero también es la más lenta y costosa. Es por esto por lo que se utilizan metaheurísticas, pero estas entregan soluciones aproximadas y no siempre óptimas.

Para terminar de comprender el TSP de forma práctica, se tiene la siguiente figura, donde se tienen varios nodos representando los puntos que se deben recorrer los cuales están conectados entre sí con sus respectivas distancias.

Notemos que si se define una ruta 1: {A, B, C, D, E, A}, la distancia sería de 21, y si se define una ruta 2: {A, B, C, E, D, A}, la distancia sería de 35, por lo que la ruta 1 resulta mejor y sería una mejor solución para TSP.