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

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