مسئله فروشنده دوره گرد ( Traveling Salesman Problem یا TSP )

مسئله فروشنده دوره گرد ( Traveling Salesman Problem یا TSP ) :<?xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" />

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

(این مسئله در کامپیوتر و طراحی الگوریتم خیلی معروف است . یک فروشنده هست که می خواهد مابین چند شهر یک دور همیلتنی بزند . مسافرت از هر شهر به شهر دیگری دارای هزینه ای مثبت است . میخواهم دوری همیلتنی با حداقل هزینه را بیابیم .)

شبکه ی بین شهری را می توان به وسیله ی یک گراف ارزش گذاری شده جهت دار نمایش داد. نظر به اینکه برخی مسیرها ممکن است یک طرفه باشد، گراف بدون جهت توصیه نمی شود. چنین گرافی را نیز می توان توسط یک ماتریس مجاورتی نمایش داد.

در حالت عادی که بررسی کلیه روش های ممکن است پیدا کردن جواب دارای مرتبه ی زمانی !nخواهد بود. با استفاده از روش برنامه سازی پویا این زمان اجرا برابر <?xml:namespace prefix = v ns = "urn:schemas-microsoft-com:vml" />خواهد بود. یکی از راههای حل این مسئله استفاده از روش ها ی ذهنی است که طبق طبیعت مسئله از ژنتیک الگوذیتم برای حل آن بکار گرفته شده است. استفاده از ژنتیک الگوریتم زمان رسیدن به یک جواب قابل قبول را در مقایسه با روش های قبلی بطور قابل ملاحظه ای کاهش می دهد. البته ذکر این نکته ضروری است که ژنتبک الگوریتم رسیدن به بهترین جواب را تضمین نمی کند ولی در زمانی محدود جوابی قابل قبول برای مسئله ارائه می کند که می تواند بهترین جواب ممکن باشد یا جوابی نزدیک به آن باشد. استفاده از الگوریتم ژنتیک برای حل مسئله ی فروشنده ی دوره گرد اولین بار توسط وتزل ( Wetzel) در سال 1983 صورت گرفت.

فرض کنید نمودار شکل زیر نقشه چهار شهر و فاصله بین آنها برحسب کیلومتر باشد.

فرض کنید یک فروشنده بخواهد از هر شهر تنها یکبار عبور کند که نقطه شروع و پایان شهر باشد. کمترین مسافتی که فروشنده می تواندهمه مسیر را بپیماید، کدام است؟

حل مسئله

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

مسیر

مسافت (کیلومتر)

ABCDA

ABDCA

ACBDA

ACDBA

ADBCA

ADCBA

30+30+25+40=125

30+35+25+50=140

50+30+35+40=155

140

155

125

بنابراینمسیر یا حداقل مسافت کل یعنی، 125 کیلومتر را به دست می دهد. حالت کلیمسالهفروشنده دوره گردشامل یافتن یکدور همیلتونیبرای یک گراف دلخواه راسی باحداقل مسافت پیموده شده است، که هر یال در آن مسافت بین دو راس را نشان می دهد. یکراه برای حل مساله، حالت کلی استفاده از روش مثال بالا است. برای این منظور،همهدورهای همیلتونی را که از یک راس خاص شروع شده و به همان راس پایان می یابد مینویسیم و مسافت کل هر دور را حساب می کنیم و از میان آنها، آن دوری را انتخاب میکنیم، که مسافت کل آن حداقل است، با این حال حتی برای مقادیر متوسط این روش غیرعملی است. مثلاً برای یکگرافکامل با 30 راس تعداد ۲۹! دور همیلتونی مختلف با شروع و پایان از یک راس خاص وجود دارد، که باید بررسی شود. حتی اگر برای هر دور پیدا شده در محاسبه مسافت کل به یک میکروثانیه زمان احتیاجباشد، برای 30 راس تقریباً ۱۰۱۷ ۲.۸*سال نیاز داریم درحال حاضر، برای حل حالت کلی مساله فروشنده دوره گرد هیچالگوریتم شناخته شده ای وجود ندارد، تا از کارایی کافی برخوردار باشد.

مسئله فروشنده دوره گرد ( Traveling Salesman Problem یا TSP )

مطالب مشابه :

شهرستان بناب مشخصات اجتماعی و فرهنگی و تاریخی و...

شهرستان بناب

مسئله فروشنده دوره گرد ( Traveling Salesman Problem یا TSP )

مشهد به شيراز 1350 كيلومتر