Travelling Salesman Problem

Travelling Salesman Problem (TSP), operasyon araştırmasının kurucu kombinatoryel optimizasyon problemidir: N adet düğüm ve düğümler arası maliyet (mesafe, süre ya da para) matrisi verildiğinde, her düğümü tam bir kez ziyaret edip başlangıca dönen kapalı turu minimum toplam maliyetle bul. Formal olarak NP-hard, ancak pratikte branch-and-cut ile çok büyük ölçekte exact optimum'a çözülür — Princeton-Georgia Tech araştırma grubunun solver'ı 85K+ düğümlü nüshaları çözmüştür (Applegate, Bixby, Chvátal ve Cook 2006); Helsgaun (2000) LKH sezgiseli milyon düğüm ölçeğinde optimum'a %0.1-1 yaklaşır. Varyantlar: simetrik TSP (mesafe A→B = B→A), asimetrik TSP (ATSP, yön-bağımlı mesafe), Euclidean TSP, metrik TSP (üçgen eşitsizliği, Christofides 3/2 yaklaşıklık garantisi), TSP with profits. Kurucu kaynaklar: Dantzig, Fulkerson ve Johnson (1954) kesme-düzlemi atılımı; Lin ve Kernighan (1973) kanonik sezgisel; Held ve Karp (1962) O(n²·2^n) dinamik programlama formülasyonu. TSP, tüm vehicle-routing (VRP) ailesinin yapısal omurgasıdır — VRP, VRPTW ve PDPTW, TSP'ye kapasite, zaman penceresi ve eşleştirme kısıtları eklenerek elde edilir.