Travelling Salesman Problem

Travelling Salesman Problem (TSP) è il problema fondante dell'ottimizzazione combinatoria nella ricerca operativa: dati N nodi e una matrice pairwise di costi (distanza, tempo o denaro), trovare il tour chiuso che visita ogni nodo esattamente una volta a costo totale minimo. Formalmente NP-difficile, ma in pratica risolvibile all'ottimo dimostrato tramite branch-and-cut su scala molto grande — il solver del gruppo di ricerca Princeton-Georgia Tech ha risolto istanze da 85K+ nodi (Applegate, Bixby, Chvátal e Cook 2006); l'euristica LKH (Helsgaun 2000) resta entro lo 0,1-1% dall'ottimo fino a scala di milioni di nodi. Varianti: TSP simmetrico (distanza A→B = B→A), TSP asimmetrico (ATSP, distanza dipendente dalla direzione), TSP euclideo, TSP metrico (disuguaglianza triangolare, garanzia di approssimazione di Christofides 3/2) e TSP con profitti. Fonti fondanti: Dantzig, Fulkerson e Johnson (1954) per la svolta dei piani di taglio; Lin e Kernighan (1973) per l'euristica canonica; Held e Karp (1962) per la formulazione DP O(n²·2^n). TSP è l'ossatura strutturale dell'intera famiglia vehicle-routing (VRP) — VRP, VRPTW e PDPTW sono estensioni del TSP con vincoli di capacità, finestre temporali e accoppiamento aggiunti.