Problema del vendedor ambulante (TSP)

El problema del viajante de comercio (TSP) es un problema algorítmico cuya tarea es encontrar la ruta más corta entre un conjunto de puntos y ubicaciones que deben visitarse. En el enunciado del problema, los puntos son las ciudades que puede visitar un vendedor. El objetivo del vendedor es mantener los costos de viaje y la distancia recorrida lo más bajos posible.

Enfocado en la optimización, TSP se usa a menudo en ciencias de la computación para encontrar la ruta más eficiente para que los datos viajen entre varios nodos. Las aplicaciones incluyen la identificación de métodos de optimización de red o hardware. Fue descrito por primera vez por el matemático irlandés WR Hamilton y el matemático británico Thomas Kirkman en el siglo XIX a través de la creación de un juego que se podía resolver al encontrar un ciclo de Hamilton, que es una ruta que no se superpone entre todos los nodos.

TSP se ha estudiado durante décadas y se han teorizado varias soluciones. La solución más simple es probar todas las posibilidades, pero también es el método más costoso y que consume más tiempo. Muchas soluciones utilizan heurística, que proporciona resultados probables. Sin embargo, los resultados son aproximados y no siempre óptimos. Otras soluciones incluyen algoritmos de bifurcación y enlace, Monte Carlo y Las Vegas.

En lugar de centrarse en encontrar la ruta más eficaz, TSP suele preocuparse por encontrar la solución más barata. En los TSP, la gran cantidad de variables crea un desafío a la hora de encontrar la ruta más corta, lo que hace que las soluciones aproximadas, rápidas y económicas sean aún más atractivas.