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

مسئله مسیریابی وسیله نقلیه1 (VRP) یکی از مهم ترین مسایل بهینه سازی ترکیباتی است که بسیار مورد توجه دانشمندان و محققان قرار گرفته است. این مسئله شامل مسیریابی برای یک ناوگان وسیله نقلیه است که در آن هر کدام از وسایل، مجموعه ای از مشتری ها را مورد ملاقات قرار می دهند، به شرط آن که هر مشتری فقط و تنها فقط به وسیله یک وسیله نقلیه ملاقات شود. هدف در این مسئله کمینه سازی فاصله های پیموده شده توسط همه وسایل نقلیه است. مسئله مسیریابی وسیله نقلیه همراه با دریافت و تحویل همزمان کالا2 (VRP_SPD) یک گسترش از مسئله VRP که در آن وسایل نقلیه نه تنها کالاهایی را به مشتریان تحویل می دهند، بلکه همزمان کالاهایی را نیز از مشتریان تحویل می گیرند. روش بهینه سازی مورچگان3 (ACO) یک تکنیک احتمالی است که رفتار غذایابی مورچگان را شبیه سازی کرده و آن را برای حل مسایلی که تاکنون الگوریتم کارایی برای آن وجود ندارد، مورد استفاده قرار می دهد. الگوریتم جمعیت مورچگان4 (ACS) یکی از مشهورترین روش های فراابتکاری است که در قانون انتقال و بروزرسانی فرمون با سایر نسخه های ACO تفاوت دارد. این مقاله یک روش بهبود یافته روش ACS ترکیب شده با الگوریتم جستجوی محلی سه گانه را برای حل مسئله VRP_SPD ارایه می کند که در اطلاعات ابتکاری و ضریب تبخیر فرمون الگوریتم ACS با روش معمولی تفاوت دارد. این عمل سبب جلوگیری از همگرایی زودرس، فرار از نقاط بهینه محلی و یافتن جواب های بهتر برای الگوریتم می شود. الگوریتم پیشنهادی روی 34 مثال استاندارد از ادبیات موضوع اجرا شده است. نتایج محاسباتی نشان می دهد که الگوریتم توانسته است که بهترین جوابی که تاکنون به دست آمده را در چهار مثال ارتقا دهد و رقابت نزدیکی را با دیگر الگوریتم های فراابتکاری برای حل مسئله VRP_SPD داشته باشد.