مسئله فروشنده دوره‌گرد

مسئله فروشنده دوره گرد یا Traveling Salesman Problem (به اختصار TSP)، یکی از مسائل بسیار مهم و پرکاربرد در علوم کامپیوتر و تحقیق در عملیات است.

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

الف) نمایش جواب به صورت رشته گسسته جایگشتی که در الگوریتم‌های زیر قابل استفاده است: الگوریتم ژنتیک یا Genetic Algorithms (به اختصار GA) شبیه‌سازی تبرید یا Simulated Annealing (به اختصار SA) جستجوی ممنوعه یا Tabu Search (به اختصار TS) جستجوی همسایگی متغیر یا Variable Neighborhood Search (به اختصار VNS) بهینه‌سازی کلونی مورچگان یا Ant Colony Optimization (به اختصار ACO) جستجوی هارمونی یا Harmony Search (به اختصار HS) و سایر الگوریتم‌های بهینه‌سازی گسسته

ب) نمایش جواب به صورت کلیدهای تصادفی یا Random Key که در الگوریتم‌های زیر قابل استفاده است: الگوریتم ژنتیک یا Genetic Algorithms (به اختصار GA) بهینه‌سازی ازدحام ذرات یا Particle Swarm Optimization (به اختصار PSO) الگوریتم رقابت استعماری یا Imperialist Competitive Algorithm (به اختصار ICA) تکامل تفاضلی یا Differential Evolution (به اختصار DE) بهینه‌سازی مبتنی بر جغرافیای زیستی یا Bio-geography Based Optimization (به اختصار BBO) استراتژی‌های تکاملی یا Evolution Strategies (به اختصار ES) برنامه‌ریزی تکاملی یا Evolutionary Programming (به اختصار EP) و سایر الگوریتم‌های بهینه‌سازی پیوسته

پ) نمایش جواب به شکل ماتریس‌های شبیه فرومون که توسط تمامی الگوریتم‌های اشاره شده در مورد (ب) قابل استفاده می‌باشد.

• مسئله معادل در نظریه گراف به این صورت است که یک گراف وزن‌دار کامل داریم که می‌خواهیم کم‌وزن‌ترین دور همیلتونی را پیدا کنیم.
• مسئله تنگراه فروشنده دوره‌گرد (به انگلیسی: Bottleneck traveling salesman problem، به‌اختصار: bottleneck TSP) مسئله‌ای بسیار کاربردی است که در یک گراف وزن‌دار کم‌وزن‌ترین دور همیلتونی را می‌خواهد که شامل سنگین‌ترین یال باشد.
• تعمیم‌یافته مسئله فروشنده دوره‌گرد دارای ایالت‌هایی است که هر کدام حداقل یک شهر دارند و فروشنده باید از هر ایالت دقیقاً از یک شهر عبور کند. این مسئله به «مسئله سیاست‌مدار مسافر» نیز شهرت دارد.

مسئله فروشنده دوره‌گرد جزء مسائل ان‌پی سخت است. راه‌های معمول مقابله با چنین مسائلی عبارتند از:

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

C({1},1) = 0
  for (S=2 to n)
  for All Subsets S subset of {1,2,3,...} of size S and containing1
  C(S,1) = &
  for All J member of S , J<>1
  C (S , J) = min { C (S - { J } , i) + D i,J: i member of S , i <> J }
 return min j C ({1 . . . n}, J) + D J,1

مسئله:یک تور بهینه برای یک گراف وزن دار و جهت دار مشخص نمایید. وزن‌ها اعدادی غیر منفی هستند

ورودی:یک گراف وزن دار و جهت دار و n تعداد گره‌های گراف. گراف با یک ارائه دو بعدی w مشخص می‌شود که سطرها و ستون‌هایش از ۱ تا n شاخص دهی شده‌اند و در ان [w[i][j معرف وزن لبه از گره iام به گره jام است.۴

خروجی:یک متغیر minlength که مقدار ان طول تور بهینه است و یک ارائه دو بعدی p که یک تور بهینه را از روی ان می‌توان ساخت . سطرهای p از ۱ تا n و ستون‌های ان با تمامی زیر مجموعه‌های {v-{v1 شاخص دهی شده‌اند . [P[i][A شاخص اولین گره بعد از vi بر روی کوتاهترین مسیر از viتاvj است که از تمام گره‌های A دقیقاً یکبار می‌گذرد.

* Void travel ( int n ,
 *            const number W[][],
 * index p[][],
 * number&minlength
* )
* {
* Index i, j, k;
* number D[1..n][subset of V-{vi}];
* for (i= 2 ; i<=n;i++)
* D[i][∅} = w[i][1];
* for(k=1; k<=n-2 ; k++)
* for (all subsets A v-{v1} containing k vertices
* for (i such that j≠1 and vi is not in A){
* D[i][A] = minimum (W[i][j]+ D[vj][A-{vj}]);
* P[i][A]= value of j that gave the minimum
* }
* D[1][v-{vi}]= minimum (W[1][j]+ D[vj][V-{v1}];
* P[1][V-{v1}]= value of j that gave the minimum ;
* Minlength = D[1][V-{v1}];
* }

الگوریتم جستجوی ممنوعه یا Tabu Search یا به اختصار TS، یکی از قوی‌ترین الگوریتم‌ها در زمینه حل مسائل بهینه‌سازی، به خصوص مسائل بهینه‌سازی مبتنی بر گراف و مسائل بهینه‌سازی ترکیباتی (Combinatorial Optimization) است. این الگوریتم در اواخر دهه ۱۹۸۰ و توسط گلووِر (Glover) و همکارانش ارائه گردید. غالباً یکی از مسائلی که برای حل آن‌ها از الگوریتم TS استفاده می‌شود، مسئله فروشنده دوره گرد یا TSP است. این الگوریتم پاسخ‌های بسیار مناسبی را برای انواع مسائل گسسته به خصوص مسئله TSP ارائه می‌کند!

• مسئله پل‌های کونیگسبرگ
• مسئله پستچی چینی
• مسئله مسافر کانادایی

• مشارکت‌کنندگان ویکی‌پدیا. «Travelling salesman problem». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۲ ژوئیه ۲۰۰۸.

در ویکی‌انبار پرونده‌هایی دربارهٔ مسئله فروشنده دوره‌گرد موجود است.

• حل مسئله فروشنده دوره گرد با شبکه عصبی در متلب