الگوریتم ترکیبی موثر ژنتیک برای حل مساله مسیریابی وسیله نقلیه

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

Keywords:

الگوریتم ژنتیک , همگرایی زودرس , مسائل NP-تام , مساله مسیریابی وسیله نقلیه