Travelling Salesman Problem

El Travelling Salesman Problem (TSP) es el problema fundacional de la optimización combinatoria en investigación de operaciones: dados N nodos y una matriz pairwise de costes (distancia, tiempo o dinero), hallar la ruta cerrada que visita cada nodo exactamente una vez con coste total mínimo. Formalmente NP-difícil, pero resoluble en la práctica al óptimo demostrado por branch-and-cut a gran escala — el solver del grupo de investigación Princeton-Georgia Tech ha resuelto instancias de 85K+ nodos (Applegate, Bixby, Chvátal y Cook 2006); la heurística LKH (Helsgaun 2000) se mantiene dentro de 0,1-1% del óptimo hasta escala de millones de nodos. Variantes: TSP simétrico (distancia A→B = B→A), TSP asimétrico (ATSP, distancia dependiente de dirección), TSP euclídeo, TSP métrico (desigualdad triangular, garantía de aproximación de Christofides 3/2) y TSP con beneficios. Fuentes fundacionales: Dantzig, Fulkerson y Johnson (1954) para el avance de los planos de corte; Lin y Kernighan (1973) para la heurística canónica; Held y Karp (1962) para la formulación DP O(n²·2^n). TSP es la columna vertebral estructural de toda la familia VRP — VRP, VRPTW y PDPTW son extensiones del TSP con restricciones de capacidad, ventanas horarias y emparejamiento añadidas.