یک الگوریتم ترکیبى اصلاحى مورچگان براى حل مساله مسیریابى وسیله نقلیه باز ظرفیت دار

مساله مسیریابی وسیله نقلیه شامل مسیریابی براى یک ناوگان وسیله نقلیه به منظور سرویس دهی به تعدادى مشترى با هدف کمینه سازى فاصله هاى پیموده شده توسط همه وسایل نقلیه است. در این مساله، وسایل نقلیه باید بعد از انجام کامل خدمات به انبار کالا بازگردند. مساله مسیریابی وسیله نقلیه باز (OVRP) با اکثر نسخه هاى مسایل مسیریابی وسیله نقلیه در ادبیات موضوع متفاوت است و در آن وسایل نقلیه بعد از انجام خدمات به انبار کالا بازنمیگردند. محدودیتهاى مورد ملاحظه در این مساله به شرح زیر میباشند. همه وسایل نقلیه داراى ظرفیت یکسانی هستند. زمان مسافرت هر وسیله نقلیه نباید از یک مقدار آستانه، که بهوسیله مقدار زمان مسافرت قانونی هر راننده تعیین میشود، تجاوز کند. تقاضاهاى کلی همه مشترىها در یک مسیر نباید از ظرفیت وسیله نقلیه بیشتر باشد. هر مشترى فقط یکبار باید توسط یک وسیله نقلیه مورد ملاقات قرار گیرد و تقاضاى آن برطرف شود. الگوریتم جمعیت مورچگان (ACS) یکی از مشهورترین روشهاى فراابتکارى است که در قانون انتقال و بهروزرسانی فرمون با سایر نسخه هاى الگوریتم مورچگان (ACO) تفاوت دارد. بر اساس معایب موجود در الگوریتم ACS براى حل مساله OVRP، دو اصلاح موثر شامل اطلاعات ابتکارى و قانون انتقال در این مقاله پیشنهاد میگردد. بعلاوه براى بهبود جوابهاى به دست آمده بهوسیله مورچه ها، الگوریتم پیشنهادى با روش جستجوى محلی لین-کرنیگان ترکیب میشود. نتایج روى 16 مثال استاندارد، کارایی روش پیشنهادى را در به دست آوردن جوابهاى باکیفیت نسبت به بهترین روشهاى فراابتکارى نشان میدهد.