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

مسئله مسیریابی خودرو ظرفیت دار CVRP یکی از مشهورترین مسائل بهینه سازی ترکیباتی است که تاکنون بسیار مورد توجه قرارگرفته است و امروزه نیز توجه بسیاری از دانشمندان و محققان را به خود جلب کرده است. این مسائل به سرویس دهی به مجموعه ای از مشتری ها با تقاضای معین، تمرکز دارد. مسیریابی خودرو تحت محدودیت ظرفیت، شامل طراحی مسیرهای توزیع با کمترین هزینه برای ناوگانی از خودروهاست که در پایانه ای مرکزی واقع شده و در آنجا نیز توقف می کنند تا به مجموعه ای از مشتری ها با تقاضای مشخص، سرویس دهی کنند. این هزینه می تواند مسافت کل طی شده توسط ناوگان، تعداد خودروهای لازم برای توزیع یا ترکیبی از هر دو باشد. بسیاری از روش های دقیق، ابتکاری و فراابتکاری در دهه های اخیر برای حل آن ارایه شده اند. در این تحقیق ابتدا تغییراتی در جهت بهبود الگوریتم علف هرز اعمال و سپس از ترکیبی از الگوریتم های علف هرز و دیفرانسیل تکاملی برای حل این مسئله استفاده شده و به منظور ارزیابی کارایی الگوریتم پیشنهادی نتایج آن با دیگر الگوریتم های فراابتکاری مورد مقایسه قرارگرفته است. در این ارزیابی که با استفاده از نمونه های استاندارد مسئله انجام شده است، بطور متوسط الگوریتم پیشنهادی نسبت به الگوریتم علف هرز 7/26 درصد، نسبت به الگوریتم ژنتیک 12/52 درصد و نسبت به الگوریتم ازدحام ذرات 15/2 درصد بهبود عملکرد نشان می دهد.

Keywords:

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