El problema del viajante de comercio (también llamado problema del viajante de comercio o TSP ) plantea la siguiente pregunta: "Dada una lista de ciudades y las distancias entre cada par de ciudades, ¿cuál es la ruta más corta posible que visita cada ciudad exactamente una vez y regresa al ciudad de origen?" Es un problema NP-difícil en optimización combinatoria , importante en informática teórica e investigación de operaciones .
En la teoría de la complejidad computacional , la versión de decisión del TSP (donde dada una longitud L , la tarea es decidir si el gráfico tiene un recorrido de como máximo L ) pertenece a la clase de problemas NP-completos . Por lo tanto, es posible que el tiempo de ejecución del peor de los casos para cualquier algoritmo para el TSP aumente superpolinomialmente (pero no más que exponencialmente ) con el número de ciudades.
El problema se formuló por primera vez en 1930 y es uno de los problemas de optimización más intensamente estudiados. Se utiliza como punto de referencia para muchos métodos de optimización. Aunque el problema es computacionalmente difícil, se conocen muchas heurísticas y algoritmos exactos , por lo que algunas instancias con decenas de miles de ciudades pueden resolverse completamente e incluso problemas con millones de ciudades pueden aproximarse en una pequeña fracción del 1%. [1]
El TSP tiene varias aplicaciones incluso en su formulación más pura, como la planificación , la logística y la fabricación de microchips . Ligeramente modificado, aparece como un subproblema en muchas áreas, como la secuenciación del ADN . En estas aplicaciones, el concepto ciudad representa, por ejemplo, clientes, puntos de soldadura o fragmentos de ADN, y el concepto distancia representa tiempos o costos de viaje, o una medida de similitud entre fragmentos de ADN. El TSP también aparece en astronomía, ya que los astrónomos que observan muchas fuentes querrán minimizar el tiempo dedicado a mover el telescopio entre las fuentes; en tales problemas, el TSP se puede incrustar dentro de unproblema de control óptimo . En muchas aplicaciones, se pueden imponer restricciones adicionales, como recursos limitados o ventanas de tiempo.
Los orígenes del problema del viajante de comercio no están claros. Un manual para vendedores ambulantes de 1832 menciona el problema e incluye viajes de ejemplo por Alemania y Suiza , pero no contiene ningún tratamiento matemático. [2]
El problema del viajante de comercio fue formulado matemáticamente en el siglo XIX por el matemático irlandés WR Hamilton y por el matemático británico Thomas Kirkman . El juego icosiano de Hamilton era un rompecabezas recreativo basado en encontrar un ciclo hamiltoniano . [3] La forma general del TSP parece haber sido estudiada por primera vez por matemáticos durante la década de 1930 en Viena y en Harvard, especialmente por Karl Menger , quien define el problema, considera el algoritmo de fuerza bruta obvio y observa la no optimización. de la heurística del vecino más cercano: