تركيب الگوريتم‌هاي جستجوي ممنوع و جمعيت مورچگان براي مسئله مسيريابي وسيله نقليه

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