کنفرانس بین المللی محاسبات نرم

صفحه اصلی / ششمین کنفرانس بین المللی محاسبات نرم

بهبود عملکرد الگوریتم زنبور عسل در حل مسئله مسیریابی وسایل نقلیه با محدودیت ظرفیت

نویسندگان :

امیرحسین بیرانوند¹ حمیدرضا افتخاری² سجاد اسفندیاری³

1- دانشگاه ملایر 2- دانشگاه ملایر 3- دانشگاه ملایر

کلمات کلیدی :

مساله مسیریابی وسیله نقلیه،الگوریتم فراابتکاری،الگوریتم کلونی زنبور عسل،هوش ازدحامی

چکیده :

چکیده مساله مسیریابی وسیله نقلیه با ظرفیت محدود یکی از مسائل کلاسیک در حوزه تحقیق در عملیات و پرکاربرد در صنایع گوناگون از همچون زنجیره تامین، خدمات پستی، مدیریت پسماند شهری، لجستیک امدادرسانی است. در این پژوهش از الگوریتم بهبود یافته کلونی زنبور عسل برای حل مساله مسیریابی استفاده شده است. در این پژوهش به حل مسئله‌ی مسیریابی وسایل نقلیه با ظرفیت محدود به‌عنوان یکی از مسائل مهم و پرکاربرد در حوزه‌ی لجستیک و بهینه‌سازی ترکیبی پرداخته شده است. هدف اصلی، ارائه‌ی روشی کارآمد برای کاهش هزینه‌ی کل مسیرها و افزایش پایداری نتایج در ابعاد مختلف مسئله است. بدین منظور، ابتدا عملکرد دو الگوریتم فراابتکاری ژنتیک و کلونی زنبور عسل بر روی بنچمارک‌های استاندارد ارزیابی شد. نتایج اولیه نشان داد که هرچند الگوریتم ژنتیک در مسائل کوچک دقت بالایی دارد، اما الگوریتم پایه‌ی زنبور عسل به‌دلیل همگرایی زودهنگام و افت تنوع، در یافتن جواب‌های نزدیک به بهینه دچار ضعف است. به‌منظور رفع این مشکل، نسخه‌ای بهبود‌یافته از الگوریتم زنبور عسل پیشنهاد گردید که با به‌کارگیری مقداردهی اولیه‌ی هوشمند مبتنی بر الگوریتم نزدیک‌ترین همسایه، تنظیم تطبیقی تعادل میان اکتشاف و استخراج و جایگزینی پویا برای منابع کم‌بازده، توانست دقت و پایداری جست‌وجو را به‌طور قابل ملاحظه‌ای ارتقا دهد. نتایج تجربی حاصل از اجرای الگوریتم‌ها بر روی مجموعه‌بنچمارک‌های مختلف نشان داد که الگوریتم بهبود یافته در مقایسه با نسخه‌ی پایه‌ی زنبور عسل به طور میانگین 20 درصد و نسبت به الگوریتم ژنتیک در عمده سناریوها بیش از 10 درصد بهبود در هزینه‌ی نهایی مسیرها ارائه داده است.