Problema del vendedor ambulante
El problema del vendedor ambulante (también llamado problema del vendedor ambulante 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 la optimización combinatoria , importante en la informática teórica y la investigación de operaciones .
En la teoría de la complejidad computacional , la versión de decisión del TSP (donde se le da 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 en el 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 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 se pueden resolver por completo e incluso los problemas con millones de ciudades se pueden aproximar en una pequeña fracción del 1%. [1]
El TSP tiene varias aplicaciones incluso en su formulación más pura, como planificación , logística y fabricación de microchips . Ligeramente modificado, aparece como un subproblema en muchas áreas, como la secuenciación del ADN . En estas aplicaciones, el concepto de ciudad representa, por ejemplo, clientes, puntos de soldadura o fragmentos de ADN, y el concepto de distancia representa los tiempos de viaje o el costo, o una medida de similitud entre los 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 . [2] [3] 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 viajantes de comercio de 1832 menciona el problema e incluye ejemplos de viajes por Alemania y Suiza , pero no contiene ningún tratamiento matemático. [4]
El problema del viajante 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 . [5] La forma general del TSP parece haber sido estudiada por primera vez por matemáticos durante la década de 1930 en Viena y Harvard, en particular por Karl Menger , quien define el problema, considera el algoritmo obvio de fuerza bruta y observa la no optimización de la heurística del vecino más cercano:
