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

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