Introducción
El Problema del Viajante de Comercio, o también conocido como TSP por sus siglas en inglés (traveling salesman problem), es un problema de optimización combinatoria muy importante en la investigación de operaciones y en la ciencia de la computación. El problema responde a la siguiente pregunta:
Dada una lista de ciudades, o simplemente lugares de una ciudad, y las distancias entre cada par de ellas, ¿cuál es la ruta más corta posible que visita cada ciudad exactamente una vez y regresa a la ciudad origen?
Partiendo de estos lugares como una red de nodos, en cada paso, se tiene un valor \( C_{ij} \), que indica la distancia o el costo de ir del nodo \( i \) al nodo \( j \). Se trata de encontrar en qué orden recorrer los nodos de la red, de modo de minimizar la distancia total recorrida. Debemos indicar que ya que se busca un circuito completo, no importa el lugar que designemos como origen.
Este problema fue formulado por primera vez en 1930 y es uno de los problemas de optimización más estudiados. Es usado como prueba para muchos métodos de optimización. Aunque el problema es computacionalmente complejo, una gran cantidad de heurísticas y métodos exactos son conocidos, de manera que, algunas instancias desde cien hasta miles de ciudades pueden ser resueltas. Dichos métodos serán tratados en el apartado de Algoritmos de resolución.
Tiene diversas aplicaciones aún en su formulación más simple, tales como la planificación, la logística y en la fabricación de microchips. El Problema del Viajante de Comercio es la base para muchas aplicaciones de reparto de mercancía en una ciudad. Como variantes, aparece como un sub-problema en muchas áreas, como en la secuencia de ADN. El concepto de 'ciudad' puede representar, por ejemplo los clientes, puntos de soldadura o fragmentos de ADN, y el concepto de 'distancia' representa el tiempo de viaje o costo, o una medida de similitud entre los fragmentos de ADN. En muchas aplicaciones, restricciones adicionales como el límite de recursos o el tiempo hacen el problema considerablemente difícil.