ترکیب الگوریتمهای جستجوی ممنوع و جمعیت مورچگان برای مسئله مسیریابی وسیله نقلیه
نویسندگان
1 Lecturer, Robat karim Branch, Islamic Azad University, Robat karim, Iran
2 Lecturer, Young Researchers & Elite Club, North Tehran Branch, Islamic Azad University, Tehran, Iran
3 Assistant Professor, Young Researchers & Elite Club, Hamedan Branch, Islamic Azad University, Hamedan, Iran
doi
چکیده
مسئله مسیریابی وسیله نقلیه (VRP) یکی از مهمترین مسائل بهینهسازی ترکیباتی است که امروزه به علت کاربردهای وسیع که در مشکلات روزمره دارد بسیار مورد توجه قرار میگیرد. در این مسئله ناوگانی از وسایل نقلیه با ظرفیت Q از گرهای به نام انبار شروع به حرکت میکنند و بعد از سرویسدهی به مشتریان به آن باز میگردند به شرط آنکه هر کدام از مشتریان را فقط یکبار مورد ملاقات قرار دهند و در هیچ زمانی بیشتر از ظرفیت محدود Q بارگذاری نکنند. هدف در این مسئله کمینهکردن تعداد وسایل نقلیه به همراه مسیرهای پیموده شده توسط آنها است. این مقاله نوعی روش ترکیبی جستجوی ممنوع را برای این مسئله پیشنهاد میکند. در این روش برای جستجوی همسایگی و حرکت از یک جواب به جواب دیگر از سه حرکت درج، جابجایی و الگوریتم جمعیت مورچگان استفاده میشود. برای آزمایش کارایی الگوریتم، چهارده مثال استاندارد کریستوفیدز در نظر گرفته شده و الگوریتم بر روی آن مورد اجرا قرار گرفته است. نتایج محاسباتی روی این مثالها که دارای اندازهای از 50 تا 199 میباشند نشان میدهد که الگوریتم پیشنهادی توانسته است که رقابت خوبی با الگوریتمهای مشهور فراابتکاری از نظر کیفیت جوابها داشته باشد. به علاوه جوابهای نزدیک به بهترین جوابهای تاکنون بدست آمده برای بیشتر مثالها بدست آورده است به طوری که سه بهترین جواب توسط این الگوریتمبه دست آمد.
