مسئله فروشنده دوره گرد ( 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 راس تقریباً ۱۰۱۷  ۲.۸*سال نیاز داریم درحال حاضر، برای حل حالت کلی مساله فروشنده دوره گرد هیچالگوریتم شناخته شده ای وجود ندارد، تا از کارایی کافی برخوردار باشد.


مطالب مشابه :


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

شهرستان بناب و مراكز علمی و آموزشی. بناب با 840 كيلومتر مربع وسعـــــت وبا جمعيتي بالغ بر




شهرستان بناب

بناب از يك موقعيت خاص جغرافيايي در قسمت شمال و شمال غربي بناب در مسافت حدود 3 الي 5




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

دپارتمان مهندسی صنایع دانشگاه آزاد بناب - مسئله فروشنده دوره گرد ( Traveling Salesman Problem یا TSP ) - Bonab




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

راهنماي سفردر ايران Travel Guide in Iran - راهنماي سفر به مشهد مقدس شهر مولايمان امام رضا(ع) Travel guide to




برچسب :