مسئله فروشنده دوره‌گرد یا Travelling Salesman Problem (TSP) یکی از مشهورترین مسائل بهینه‌سازی و علوم کامپیوتر است. صورت کلاسیک مسئله ساده به نظر می‌رسد:

یک فروشنده باید از یک شهر شروع کند، تمام شهرهای دیگر را دقیقاً یک بار ببیند و در پایان به شهر شروع برگردد. هدف این است که مجموع هزینه یا فاصله سفر حداقل باشد.

همین تعریف ساده باعث شده TSP به یکی از مهم‌ترین مثال‌ها برای درک تفاوت بین «پیدا کردن یک جواب» و «پیدا کردن بهترین جواب ممکن» تبدیل شود.

در این مقاله TSP را از صفر بررسی می‌کنیم؛ از مدل‌سازی آن به شکل گراف و Brute Force گرفته تا Dynamic Programming با الگوریتم Held–Karp، روش‌های تقریبی و کاربردهای واقعی.

TSP دقیقاً چه مسئله‌ای را حل می‌کند؟

فرض کنید پنج شهر داریم:

A, B, C, D, E

بین هر دو شهر ممکن است فاصله، زمان یا هزینه‌ای وجود داشته باشد.

هدف این نیست که فقط از A به E برسیم. هدف این است که:

1. از یک نقطه شروع کنیم.
2. همه نقاط را دقیقاً یک بار ببینیم.
3. دوباره به نقطه شروع برگردیم.
4. مجموع هزینه مسیر حداقل باشد.

بنابراین اگر مسیر زیر معتبر باشد:

A → B → D → C → E → A

باید هزینه آن را با تمام تورهای معتبر دیگر مقایسه کنیم.

مدل‌سازی TSP به شکل گراف

TSP معمولاً با یک Weighted Graph مدل می‌شود.

• هر شهر یا مقصد = Vertex
• ارتباط بین دو مقصد = Edge
• فاصله، زمان یا هزینه = Weight

مثلاً:

A ----10---- B
|            |
15           12
|            |
C ----8----- D

در نسخه کلاسیک، معمولاً فرض می‌کنیم بین هر دو شهر مسیری وجود دارد؛ یعنی گراف Complete است.

اما در مسائل واقعی ممکن است بعضی مسیرها وجود نداشته باشند یا هزینه بسیار بزرگی داشته باشند.

تفاوت TSP با Shortest Path

یکی از اشتباهات رایج این است که TSP را با الگوریتم‌هایی مثل Dijkstra اشتباه بگیریم.

Shortest Path

در Shortest Path می‌پرسیم:

کوتاه‌ترین مسیر از A به B چیست؟

مثلاً:

A → C → B

TSP

در TSP می‌پرسیم:

کم‌هزینه‌ترین توری که همه نقاط را ببیند و دوباره به A برگردد چیست؟

یعنی:

A → C → D → B → A

پس TSP یک مسئله Global Optimization است، نه صرفاً کوتاه‌ترین مسیر بین دو نقطه.

تفاوت TSP با Hamiltonian Cycle

Hamiltonian Cycle مسیری است که:

• هر رأس را دقیقاً یک بار می‌بیند.
• در پایان به رأس شروع برمی‌گردد.

اما در Hamiltonian Cycle معمولاً سؤال اصلی این است:

آیا چنین دوری وجود دارد؟

در TSP سؤال مهم‌تر است:

از بین تمام Hamiltonian Cycleها، کدام‌یک کمترین هزینه را دارد؟

پس می‌توان TSP را نسخه‌ی وزن‌دار و بهینه‌سازی‌شده‌ی مسئله Hamiltonian Cycle دانست.

یک مثال عددی ساده

چهار شهر داریم:

A, B, C, D

ماتریس فاصله:

      A   B   C   D
A     0  10  15  20
B    10   0  35  25
C    15  35   0  30
D    20  25  30   0

اگر از A شروع کنیم، چند تور ممکن عبارت‌اند از:

A → B → C → D → A
A → B → D → C → A
A → C → B → D → A
A → C → D → B → A
...

هزینه مسیر اول:

A → B = 10
B → C = 35
C → D = 30
D → A = 20

Total = 95

هزینه مسیر دوم:

A → B = 10
B → D = 25
D → C = 30
C → A = 15

Total = 80

بنابراین مسیر دوم بهتر است.

TSP باید تمام گزینه‌های لازم را بررسی کند یا با یک روش هوشمندتر بهترین جواب را پیدا کند.

روش اول: Brute Force

ساده‌ترین راه این است که تمام ترتیب‌های ممکن شهرها را تولید کنیم.

اگر n شهر داشته باشیم و شهر شروع را ثابت کنیم، تقریباً:

(n - 1)!

ترتیب ممکن داریم.

برای هر ترتیب:

1. مسیر کامل ساخته می‌شود.
2. هزینه تمام یال‌ها محاسبه می‌شود.
3. هزینه برگشت به نقطه شروع اضافه می‌شود.
4. بهترین تور نگه داشته می‌شود.

چرا Brute Force سریع منفجر می‌شود؟

تعداد permutationها بسیار سریع رشد می‌کند:

5!  = 120
10! = 3,628,800
15! ≈ 1.3 trillion
20! ≈ 2.43 × 10^18

به همین دلیل Brute Force فقط برای تعداد کمی نقطه مناسب است.

پیاده‌سازی Brute Force با JavaScript

function permutations(arr) {
  if (arr.length <= 1) return [arr];

  const result = [];

  for (let i = 0; i < arr.length; i++) {
    const current = arr[i];
    const remaining = [...arr.slice(0, i), ...arr.slice(i + 1)];

    for (const perm of permutations(remaining)) {
      result.push([current, ...perm]);
    }
  }

  return result;
}

function solveTSPBruteForce(dist) {
  const n = dist.length;
  const start = 0;

  const cities = [];

  for (let i = 1; i < n; i++) {
    cities.push(i);
  }

  let bestCost = Infinity;
  let bestTour = null;

  for (const order of permutations(cities)) {
    const tour = [start, ...order, start];

    let cost = 0;

    for (let i = 0; i < tour.length - 1; i++) {
      cost += dist[tour[i]][tour[i + 1]];
    }

    if (cost < bestCost) {
      bestCost = cost;
      bestTour = tour;
    }
  }

  return {
    cost: bestCost,
    tour: bestTour
  };
}

const dist = [
  [0, 10, 15, 20],
  [10, 0, 35, 25],
  [15, 35, 0, 30],
  [20, 25, 30, 0]
];

console.log(solveTSPBruteForce(dist));

خروجی یکی از بهترین تورها خواهد بود:

{
  cost: 80,
  tour: [0, 1, 3, 2, 0]
}

آیا Dynamic Programming بهتر است؟

بله، برای تعداد متوسطی از شهرها می‌توان از الگوریتم مشهور Held–Karp استفاده کرد.

ایده اصلی Held–Karp این است که یک مسئله مشابه را چند بار از صفر حل نکنیم.

State در Held–Karp

یک State می‌تواند چنین معنایی داشته باشد:

dp[visited][last]

یعنی:

کمترین هزینه برای شروع از شهر 0، دیدن مجموعه‌ی visited و پایان دادن مسیر در شهر last.

مجموعه شهرهای دیده‌شده معمولاً با Bitmask نمایش داده می‌شود.

مثلاً برای چهار شهر:

0001

یعنی فقط شهر 0 دیده شده.

0101

یعنی شهرهای 0 و 2 دیده شده‌اند.

1111

یعنی همه شهرها دیده شده‌اند.

رابطه بازگشتی Held–Karp

اگر اکنون در شهر u باشیم و بخواهیم به شهر v برویم:

newMask = mask | (1 << v)

و:

dp[newMask][v] =
min(
  dp[newMask][v],
  dp[mask][u] + dist[u][v]
)

در پایان باید هزینه برگشت به شهر شروع را نیز اضافه کنیم.

پیاده‌سازی Held–Karp با JavaScript

function tspHeldKarp(dist) {
  const n = dist.length;
  const size = 1 << n;

  const dp = Array.from(
    { length: size },
    () => Array(n).fill(Infinity)
  );

  dp[1][0] = 0;

  for (let mask = 1; mask < size; mask++) {
    for (let u = 0; u < n; u++) {
      if (!(mask & (1 << u))) continue;

      const current = dp[mask][u];

      if (current === Infinity) continue;

      for (let v = 0; v < n; v++) {
        if (mask & (1 << v)) continue;

        const nextMask = mask | (1 << v);

        dp[nextMask][v] = Math.min(
          dp[nextMask][v],
          current + dist[u][v]
        );
      }
    }
  }

  const fullMask = size - 1;
  let answer = Infinity;

  for (let last = 1; last < n; last++) {
    answer = Math.min(
      answer,
      dp[fullMask][last] + dist[last][0]
    );
  }

  return answer;
}

پیچیدگی Held–Karp

پیچیدگی زمانی:

O(n² × 2^n)

پیچیدگی فضایی:

O(n × 2^n)

این روش از O(n!) بسیار بهتر است، اما همچنان برای nهای بزرگ گران است.

چرا TSP مسئله سختی است؟

نسخه تصمیمی TSP در دسته مسائل NP-Complete و نسخه بهینه‌سازی آن NP-Hard است.

به زبان ساده، الگوریتم exact شناخته‌شده‌ای نداریم که برای ورودی عمومی TSP در زمان Polynomial بهترین جواب را تضمین کند.

به همین دلیل وقتی تعداد نقاط زیاد می‌شود معمولاً به سراغ یکی از این روش‌ها می‌رویم:

• Dynamic Programming
• Branch and Bound
• Approximation Algorithms
• Greedy Heuristics
• Local Search
• Genetic Algorithms
• Simulated Annealing
• Ant Colony Optimization

Heuristic چیست و چرا در TSP مهم است؟

در بسیاری از سیستم‌های واقعی، بهترین جواب ریاضی لزوماً لازم نیست.

مثلاً اگر 20,000 مقصد تحویل داشته باشیم، شاید مسیری که فقط 1٪ از جواب optimal بدتر است ولی در چند ثانیه پیدا می‌شود، بسیار کاربردی‌تر از جوابی باشد که محاسبه آن ساعت‌ها یا روزها زمان می‌برد.

اینجاست که Heuristicها مهم می‌شوند.

Nearest Neighbor

یکی از ساده‌ترین روش‌ها:

1. از یک شهر شروع کن.
2. نزدیک‌ترین شهر بازدیدنشده را انتخاب کن.
3. این کار را ادامه بده.
4. در پایان به شهر شروع برگرد.

مثلاً:

A → C → D → B → A

این روش بسیار سریع است اما تضمین نمی‌کند جواب optimal باشد.

2-opt

یکی از روش‌های محبوب برای بهتر کردن یک تور موجود است.

فرض کنید بخشی از تور:

A → B
C → D

باشد.

2-opt بررسی می‌کند آیا حذف این دو یال و اتصال به صورت:

A → C
B → D

هزینه را کمتر می‌کند یا نه.

این عملیات بارها تکرار می‌شود تا تور بهتر شود.

TSP متقارن و نامتقارن

Symmetric TSP

اگر:

cost(A, B) = cost(B, A)

مسئله متقارن است.

فاصله هندسی شهرها معمولاً چنین حالتی دارد.

Asymmetric TSP

اگر:

cost(A, B) ≠ cost(B, A)

مسئله نامتقارن است.

مثلاً در شبکه شهری:

• خیابان یک‌طرفه وجود دارد.
• ترافیک مسیر رفت و برگشت متفاوت است.
• عوارض مسیرها متفاوت است.

در این حالت جهت یال اهمیت دارد.

Metric TSP چیست؟

اگر فاصله‌ها از Triangle Inequality پیروی کنند:

d(A, C) ≤ d(A, B) + d(B, C)

به آن Metric TSP می‌گوییم.

این ویژگی مهم است زیرا برخی Approximation Algorithmها روی Metric TSP تضمین کیفیت دارند.

کاربردهای واقعی TSP

نام مسئله ممکن است شما را به یاد یک فروشنده بیندازد، اما کاربردهای TSP بسیار گسترده‌تر است.

1. مسیر تحویل کالا

یک خودرو باید چندین مقصد را بازدید کند.

مثلاً:

Warehouse
   ↓
Customer A
   ↓
Customer C
   ↓
Customer B
   ↓
Warehouse

اگر فقط یک خودرو و محدودیت‌های ساده داشته باشیم، مسئله به TSP نزدیک است.

در سیستم‌های واقعی با چند خودرو معمولاً وارد خانواده‌ی Vehicle Routing Problem (VRP) می‌شویم.

2. برنامه‌ریزی بازدید تکنسین

یک تکنسین باید در طول روز چند محل را بازدید کند.

هدف می‌تواند کمینه‌کردن:

• زمان رانندگی
• هزینه سوخت
• مسافت
• زمان کل مأموریت

باشد.

3. ربات‌های انبار

یک ربات باید مجموعه‌ای از Shelfها را برای جمع‌آوری کالاها بازدید کند.

ترتیب بازدید می‌تواند مستقیماً روی سرعت آماده‌سازی سفارش اثر بگذارد.

4. ترتیب بازدید مشتریان در CRM

فرض کنید تیم فروش باید 15 مشتری را در یک منطقه بازدید کند.

با داشتن مختصات مشتری‌ها می‌توان ترتیب بازدید را طوری بهینه کرد که زمان رفت‌وآمد کاهش یابد.

البته اگر Time Window، اولویت مشتری، ساعت کاری یا چند فروشنده داشته باشیم، مسئله از TSP کلاسیک پیچیده‌تر می‌شود.

5. تولید و CNC

در برخی ماشین‌های CNC، دریل یا لیزر باید تعداد زیادی نقطه را پردازش کند.

اگر ترتیب نقاط بد انتخاب شود، هد دستگاه حرکت اضافی زیادی خواهد داشت.

این مسئله را می‌توان مشابه TSP مدل کرد.

6. طراحی مسیر روی PCB

در برخی مسائل مربوط به تولید بردهای الکترونیکی، ترتیب بازدید نقاط می‌تواند روی زمان حرکت ابزار تولید تأثیر بگذارد.

7. DNA Sequencing و Bioinformatics

برخی مسائل ترتیب‌دهی می‌توانند با ایده‌هایی مشابه TSP مدل شوند، هرچند مدل دقیق مسئله ممکن است تفاوت داشته باشد.

تفاوت TSP با Vehicle Routing Problem

TSP معمولاً فرض می‌کند:

یک عامل
+
یک تور
+
بازدید از تمام نقاط

اما VRP می‌تواند شامل موارد زیر باشد:

• چند خودرو
• ظرفیت خودرو
• Time Window
• اولویت سفارش‌ها
• چند انبار
• محدودیت ساعت کاری
• Pickup و Delivery

پس:

TSP ⊂ خانواده مسائل Routing

و VRP تعمیم پیچیده‌تری از آن است.

آیا همیشه باید به نقطه شروع برگردیم؟

در تعریف کلاسیک TSP بله.

اما نسخه‌ای به نام Open TSP وجود دارد که در آن لازم نیست مسیر به نقطه شروع برگردد.

پس قبل از انتخاب الگوریتم باید دقیقاً Requirement مسئله را مشخص کنیم.

Edge Caseهای مهم

فقط یک شهر

هزینه تور می‌تواند صفر باشد.

دو شهر

تور عملاً:

A → B → A

است.

یال ناموجود

اگر بین دو نقطه مسیر وجود ندارد، باید آن یال را با Infinity یا ساختاری مشابه مدل کنیم.

وزن منفی

TSP از نظر نظری می‌تواند وزن‌های متفاوت داشته باشد، اما در کاربردهای فاصله و زمان معمولاً وزن منفی معنای واقعی ندارد.

گراف نامتقارن

نباید فرض کنیم:

dist[a][b] === dist[b][a]

مگر اینکه مسئله این ویژگی را تضمین کند.

چه زمانی از TSP استفاده کنیم؟

TSP مناسب است وقتی:

• یک عامل داریم.
• باید همه نقاط را بازدید کنیم.
• هر نقطه معمولاً یک بار دیده می‌شود.
• ترتیب بازدید اهمیت دارد.
• هدف کمینه‌کردن هزینه کل تور است.

چه زمانی TSP مناسب نیست؟

اگر فقط دنبال کوتاه‌ترین مسیر بین دو نقطه هستید:

Dijkstra / A*

ممکن است مناسب‌تر باشد.

اگر چند خودرو دارید:

Vehicle Routing Problem

مطرح می‌شود.

اگر برخی نقاط اختیاری‌اند و سود متفاوت دارند:

Orienteering Problem

ممکن است مدل مناسب‌تری باشد.

اگر فقط وجود دوری که همه رأس‌ها را ببیند مهم است:

Hamiltonian Cycle

مسئله دقیق‌تری است.

مقایسه روش‌های حل

نکته مهم در سیستم‌های واقعی

در پروژه واقعی فاصله لزوماً فاصله مستقیم جغرافیایی نیست.

ممکن است Weight بین دو نقطه برابر باشد با:

Driving Time

یا:

Fuel Cost

یا حتی:

Distance
+ Traffic Penalty
+ Toll Cost
+ Service Priority

بنابراین بخش مهم مسئله فقط Algorithm نیست؛ Cost Function نیز باید درست طراحی شود.

جمع‌بندی

Travelling Salesman Problem یکی از بهترین مسائل برای فهم بهینه‌سازی ترکیبیاتی است.

ایده مسئله ساده است:

همه نقاط را ببین
+
به نقطه شروع برگرد
+
کمترین هزینه را پیدا کن

اما تعداد مسیرهای ممکن با افزایش ورودی به‌شدت رشد می‌کند.

برای ورودی بسیار کوچک Brute Force قابل استفاده است. Held–Karp با Dynamic Programming تعداد زیادی محاسبه تکراری را حذف می‌کند و پیچیدگی را از Factorial به O(n²2^n) کاهش می‌دهد، اما همچنان برای داده‌های بزرگ مناسب نیست.

در مسائل بزرگ معمولاً از Heuristic، Approximation، Local Search یا روش‌های تخصصی Routing استفاده می‌شود.

مهم‌تر از حفظ کردن کد TSP این است که بتوانیم تشخیص دهیم مسئله واقعی ما واقعاً TSP است یا نسخه پیچیده‌تری مانند VRP، Open TSP یا مسئله‌ای کاملاً متفاوت.