حل مساله TSP با فواصل نامتقارن جهت مسیریابی وسیله ی نقلیه شرکت های توزیع کالا، با استفاده از الگوریتم فراابتکاری

محمدرضا دهقانی تفتی¹ عادل پورقادر چوبر² مهدی علی بخشی³

1) کارشناسی ارشد مهندسی صنایع، دانشگاه علم و هنر یزد، یزد، ایران
2) مدرس گروه مهندسی صنایع، دانشگاه پیام نور، گیلان، ایران
3) گروه مهندسی صنایع، دانشگاه تربیت مدرس، تهران، ایران

کد IOI مقاله : XDCZ-FACFA
محل انتشار : اولین کنفرانس مهندسی و فن آوری دانشگاه تبریز(ncoei.ir)
چکیده :
    مساله فروشنده دوره¬گرد یکی از معروف¬ترین مسائل بهینه¬سازی ترکیبی شناخته شده و جزء مسائل (NP-complete) می¬باشد که کاربرد¬های متعدد این مساله از لحاظ نظری و عملیاتی باعث توجه ویژه محققان به آن شده¬است. با توجه به اینکه روش¬های بهینه¬یابی موجود برای حل اینگونه مسائل به طور عمده شامل تعداد بسیار زیادی متغیر و محدودیت می-باشند و از کارایی عملی آن¬ها در حل مسائل با ابعاد بزرگتر می¬کاهد از این رو در دهه¬های اخیر شاهد استفاده از الگوریتم¬های فراابتکاری بوده¬ایم. در این پژوهش پس از تعیین یک مدل برنامه¬ریزی خطی برای مساله فروشنده دوره¬گرد با فواصل نامتقارن و حل آن در نرم افزار Lingo، ¬از دو الگوریتم فرا¬ابتکاری کلونی مورچگان و الگوریتم جستوجو ممنوع جهت حل مساله در ابعاد بزرگ استفاده نمودیم. پس از تنظیم پارامترهای دو الگوریتم با استفاده از روش تاگوچی جهت اثبات کارایی دو الگوریتم نتایج آن¬ها را با حل مدل برنامه¬ریزی خطی در مسائل با ابعاد کوچک مقایسه نمودیم. در ادامه برای مقایسه نتایج و زمان اجرای دو الگوریم به حل مساله در ابعاد متوسط و بزرگ پرداختیم.

کلمات کلیدی : فروشنده دوره¬گرد نامتقارن روش تاگوچی الگوریتم کلونی مورچگان الگوریتم جستوجو ممنوع