دانلود ترجمه مقاله FL-MTSP: رویکرد منطق فازی برای حل مشکل فروشنده چند هدفه دوره گرد (اسپرینگر 2016)

FL-MTSP: یک رویکرد منطق فازی برای حل مشکل فروشنده چند هدفه دوره گرد برای سیستم های چند روباتی

FL-MTSP: a fuzzy logic approach to solve the multi-objective multiple traveling salesman problem for multi-robot systems

چکیده
1 مقدمه
2 آثار مرتبط
3 تدوین مساله
4 راه‌حل پیشنهادی
5 ارزیابی عملکرد
6 نتیجه
منابع

چکیده
این مقاله به بررسی مساله‌ی تخصیص لوکیشن‌های هدف -که قرار است بازدید شوند-، به ربات‌های سیار می‌پردازد. ما این مساله را بصورت مساله‌ی چند فروشنده‌ی دوره‌گردِ چندایستگاهیMD-MTSP تدوین می‌کنیم، یعنی یک نمونه مساله‌ی NP-Hard از MTSP. برخلاف اکثر آثار پژوهشیِ پیشین، ما به دنبال بهینه‌سازی معیارهای عملکرد هستیم، یعنی بیشینه مسافت طی‌شده و کل مسافت طی‌شده بطور همزمان. به منظور پرداختن به این مساله، ما FL-MTSP را مطرح می‌سازیم که یک رویکرد منطق فازیِ جدید است که هر دو معیار را در یک معیار فازیِ واحد ترکیب می‌کند، و مساله را به یک مساله‌ی بهینه‌سازیِ هدفِ واحد فرو می‌کاهد. شبیه‌سازی‌های گسترده حاکی از این هستند که رویکرد منطق فازیِ پیشنهادیِ ما، از نظر ارائه‌ی بده‌بستانی مطلوب از دو معیار عملکردیِ مورد نظر، عملکرد بهتری نسبت به یک الگوریتم عامِ تعمیم‌یافته دارد. بعلاوه، روشن شد که زمان اجرای FL-MTSP همیشه سریعتر از رویکرد MDMTSP_GA بود و عدد 89 درصد را نشان می‌داد.

2- آثار مرتبط
مساله تخصیص وظیفه‌ی چندرباته، یک محور پژوهشیِ چالش‌برانگیز در حوزه‌ی رباتیک است. در متون پژوهشی، پزوهشگران متعددی، مساله‌ی MRTA را بعنوان نمونه‌ای از مساله‌ی چند فروشنده‌ی دوره‌گرد، به دلیل مقایسه‌ی قویِ بین آنها، مدنظر قرار داده است.

در آثار پژوهشی، پژوهشگران راه‌حل‌های مختلفی را جهت حل MTSP مطرح کرده‌اند. در ساریل (2007)، نویسندگان یک الگوریتم توزیع‌شده را جهت حل MTSP ارائه کرده‌اند. در ابتدا، هر ربات اقدام به انتخاب نزدیکترین هدف می‌کند. سپس، هر ربات برای وظیفه‎‌ی خود یک حراج می‌گذارد و تخصیص وظیفه با استفاده از پروتکل خالص قرارداد انجام می‌گیرد. نتایج شبیه‌سازی، کارایی الگوریتم بلحاظ مقیاس‌پذیری، کل طول مسیر و پیغام ارتباطیِ سربار را اثبات کرده است. در مقاله کیولویچ (2013)، نویسندگان یک الگوریتم مبتنی بر بازار پیشنهاد دادند که از چهار مرحله تشکیل شده است: حراج بازار، دادوستد عامل-به-عامل، سوئیچ عامل و …. . در گام نخست، هر ربات بهترین وظیفه را بر عهده می‌گیرد. در مرحله دادوستدِ عامل-به-عامل، هر ربات توانایی خود را جهت انجام هر وظیفه‌ی سایر ربات‌ها، بررسی می‌کند. در گام سوئیچِ عامل، راه‌حل‌هایی که در مینیمم‌های محلی، مورد واکاوی قرار می‌گیرند. پس از چند تعامل بدون بهبود، الگوریتم متوقف می‌شوند. در شیخروهو (2014)، نویسندگان یک راه‌حل مبتنی‌بربازار به نام حرکت و بهبود، جهت حل MD-MTSP پیشنهاد داده‌اند. این راه‌حل از چهار مرحله تشکیل شده است: تخصیص اولیه‌ی هدف، ساخت تور، مذاکره‌ی اهداف متعارض و بهبود راه‌حل. از بررسی شبیه‌سازی، مشخص شد که الگوریتم حرکت و بهبود، نتایج خوبی در مقایسه با نتایج تولیدشده توسط رویکرد متمرکز، ارائه می‌دهد.

آثار پژوهشیِ متعددی، یک الگوریتم ژنتیک گروهبندی (GGA) را جهت حل مساله‌ی MTSP پیشنهاد داده‌اند. یک الگوریتم GGA بر مبنای تقسیم شهرها به m گروه قرار دارد؛ m تعداد فروشندگان است. در مقاله سینگ و باقل (2009)، نویسندگان مساله SD-MTSP را با استفاده از الگوریتم ژنتیک حل کرده‌اند. آنها یک الگوریتم ژنتیک گروهبندیِ وضعیت‌ثابت (GGA-SS) پیشنهاد دادند که از نمایش متفاوتِ کروموزوم و اپراتورهای ژنتیک استفاده می‌کند. آنها همچنین از مدل جایگزینی جمعیتِ وضعیت ثابت نیز استفاده کرده‌اند. این اهداف عبارتند از: 1) کمینه‌سازی کل مسافتی که تمام فروشندگان طی کرده‌‎اند و 2) کمینه‌سازی بیشینه‌ مسافتی که هر فروشنده طی کرده است. نتایج شبیه‌سازی نشان داده است که GGA-SS، راه‌حلِ کمترین هزینه‌ی متوسط را در مقایسه با راه‌حل‌های ارائه‌شده در مقالات کارتر و راگسداله (2006) و براون (2007)، پیدا می‌کند. نویسندگان هر فرض را بر این می‌گذارند که هر فروشنده باید دست‌کم یک شهر را بعلاوه‌ی شهر موطنِ خود، بازدید کند. این محدودیت می‌تواند به افزایش کل مسافت طی‌‎شده بیانجامد.