مقایسه الگوریتم‌های فراابتکاری به منظور حل مسئله فروشنده دوره گرد
Paper ID : 1186-ICTCK (R3)
Authors:
1نازنوش اطمینان, 2الهام پروین نیا *, 1محمد صفری, 1مهدی مسعودی چله گاهی
1دانشگاه آزاد شیراز
2عضو هیات علمی
Abstract:
مسئله فروشنده دوره گرد از جمله مسایل کاربردی در صنعت حمل و نقل است که حل بهینه آن، سرعت عمل بالاتر در سرویس‌دهی و رضایت مشتری را به دنبال خواهد داشت. در این مقاله ابتدا حل بهینه مسئله فروشنده دوره گرد با استفاده از روش برنامه نویسی پویا برای دو مجموعه داده Iran59 و مجموعه داده‌ای شامل ده شهر از ایران بدست آمده است. سپس این مسئله با سه الگوریتم فرا‌ابتکاری تپه نوردی، تبرید شبیه سازی شده و الگوریتم ژنتیک برای همان مجموعه داده‌ها حل شده و عملکرد روشهای فراابتکاری با حل بهینه مقایسه شده است. مقایسه ها از جهت نیل به جواب بهینه، زمان اجرا، و حافظه مصرفی می باشد. نتایج بدست آمده نشان می‌دهند که الگوریتم تپه نوردی در کمینه محلی متوقف می گردد و تور پیشنهادی آن طولانی تر از سایر روش‌ها می باشد. اما الگوریتم های تبرید شبیه سازی شده و ژنتیک موفق می شوند جواب بهینه را بدست آورند. مقایسه زمان اجرای این الگوریتم ها نشان می دهد که الگوریتم ژنتیک در کمترین زمان به جواب بهینه دست پیدا می کند. همچنین روش تپه نوردی کمترین مقدار حافظه مصرفی را داراست.
Keywords:
مسئله فروشنده دوره گرد، الگوریتم های فراابتکاری، الگوریتم ژنتیک، برنامه نویسی پویا.
Status : Paper Accepted