یک الگوریتم ترکیبی اصلاحی مورچگان برای حل مساله مسیریابی وسیله نقلیه باز ظرفیتدار | ||
| مدل سازی در مهندسی | ||
| مقاله 14، دوره 15، شماره 50، 1396، صفحه 179-191 اصل مقاله (1.37 M) | ||
| نوع مقاله: پژوهشی | ||
| شناسه دیجیتال (DOI): 10.22075/jme.2017.2560 | ||
| نویسندگان | ||
| مجید یوسفی خوشبخت* 1؛ اعظم دولت نژاد2؛ اسماعیل خرم3 | ||
| 1استادیار، دانشگاه آزاد اسلامی، واحد همدان، باشگاه پژوهشگران جوان و نخبگان، همدان، ایران | ||
| 2دانشگاه آزاد اسلامی، واحد تهران شمال، باشگاه پژوهشگران جوان و نخبگان، تهران، ایران | ||
| 3دانشکده ریاضی و علوم کامپیوتر، دانشگاه امیرکبیر تهران، تهران، ایران | ||
| چکیده | ||
| مساله مسیریابی وسیله نقلیه (VRP) شامل مسیریابی برای یک ناوگان وسیله نقلیه برای سرویسدهی به تعدادی مشتری است که در آن هدف کمینهسازی فاصلههای پیموده شده توسط همه وسائل نقلیه است. در این مساله وسایل نقلیه باید بعد از انجام کامل خدمات به انبار کالا بازگردند. مساله مسیریابی وسیله نقلیه باز (OVRP) با اکثر نسخههای مسائل مسیریابی وسیله نقلیه در ادبیات موضوع متفاوت است و در آن وسائل نقلیه بعد از انجام خدمات به انبار کالا باز نمیگردند. محدودیتهای مورد ملاحظه در این مساله به شرح زیر میباشند. همه وسائل نقلیه دارای ظرفیت یکسانی هستند؛ زمان مسافرت هر وسیله نقلیه نباید از یک مقدار آستانه، که بوسیله مقدار زمان مسافرت قانونی هر راننده تعیین میشود، تجاوز کند؛ تقاضاهای کلی همه مشتریها در یک مسیر نباید از ظرفیت وسیله نقلیه بیشتر باشد؛ هر مشتری فقط یکبار باید بوسیله یک وسیله نقلیه مورد ملاقات قرار گیرد و تقاضای آن برطرف شود. الگوریتم جمعیت مورچگان (ACS) یکی از مشهورترین روشهای فراابتکاری است که در قانون انتقال و بروزرسانی فرمون با سایر نسخههای الگوریتم مورچگان (ACO) تفاوت دارد. براساس معایب موجود در الگوریتم ACS برای حل مساله OVRP، دو اصلاح موثر شامل اطلاعات ابتکاری و قانون انتقال در این مقاله پیشنهاد میگردد. بعلاوه برای بهبود جوابهای بدست آمده بوسیله مورچهها، الگوریتم پیشنهادی با روش جستجوی محلی لین-کرنیگان ترکیب میشود. نتایج روی 16 مثال استاندارد کارایی روش پیشنهادی را در بدست آوردن جوابهای باکیفیت نسبت به بهترین روشهای فراابتکاری نشان میدهد. | ||
| کلیدواژهها | ||
| الگوریتم جمعیت مورچگان؛ الگوریتم لین-کرنیگان؛ اطلاعات ابتکاری؛ قانون انتقال؛ مساله مسیریابی وسیله نقلیه باز | ||
| مراجع | ||
|
| ||
|
آمار تعداد مشاهده مقاله: 1,903 تعداد دریافت فایل اصل مقاله: 739 |
||
| تعداد نشریات | 22 |
| تعداد شمارهها | 722 |
| تعداد مقالات | 10,383 |
| تعداد مشاهده مقاله | 72,841,192 |
| تعداد دریافت فایل اصل مقاله | 64,538,201 |