Travelling Salesman Problem

Travelling Salesman Problem (TSP) هي المسألة الأمّ للتحسين التركيبي في بحوث العمليات: بمعطى N عقدة ومصفوفة تكاليف ثنائية (مسافة، زمن، أو نقد)، إيجاد الجولة المغلقة التي تزور كلّ عقدة مرّة واحدة فقط بأدنى تكلفة كلّية. NP-hard شكلًا، لكنّها قابلة عمليًا للحلّ exact إلى الـoptimum المثبت بـbranch-and-cut على نطاقات واسعة جدًا — حلّ حلّال مجموعة بحث Princeton-Georgia Tech نسخًا بأكثر من 85K عقدة (Applegate وBixby وChvátal وCook 2006)؛ خوارزمية LKH الاسترشادية (Helsgaun 2000) تبقى ضمن 0.1-1% من الـoptimum حتى حجم ملايين العقد. متغيّرات: TSP متماثل (مسافة A→B = B→A)، TSP غير متماثل (ATSP، مسافة مرتبطة بالاتّجاه)، TSP إقليدي، TSP متري (متباينة المثلّث، ضمانة Christofides 3/2)، وTSP بربح. مصادر تأسيسية: Dantzig وFulkerson وJohnson (1954) لإختراق طريقة الـcutting plane؛ Lin وKernighan (1973) للخوارزمية الاسترشادية الكنسية؛ Held وKarp (1962) لصياغة DP بـO(n²·2^n). TSP هي العمود الفقري الهيكلي لكلّ عائلة vehicle-routing (VRP) — VRP وVRPTW وPDPTW امتدادات لـTSP بإضافة قيود السعة والنوافذ الزمنية والاقتران.