مقایسه الگوریتم های فراابتکاری به منظور حل مسیله فروشنده دوره گرد

مسیله فروشنده دوره گرد از جمله مسایل کاربردی در صنعت حمل و نقل است که حل بهینه آن، سرعت عمل بالاتر در سرویس دهی و رضایت مشتری را به دنبال خواهد داشت. در این مقاله ابتدا حل بهینه مسیله فروشنده دوره گرد با استفاده از روش برنامه نویسی پویا برای دومجموعه داده Iran59 و مجموعه دادهای شامل ده شهر از ایران بدست آمده است. سپس این مسیله با سه الگوریتم فراابتکاری تپه نوردی، تبرید شبیه سازی شده و الگوریتم ژنتیک برای همان مجموعه داده ها حل شده و عملکرد روش های فراابتکاری با حل بهینه مقایسه شده است. مقایسه ها از جهت نیل به جواب بهینه، زمان اجرا، و حافظه مصرفی می باشد. نتایج بدست آمده نشان می دهند که الگوریتم تپه نوردی در کمینه محلی متوقف می گردد و تور پیشنهادی آن طولانی تر از سایر روشها می باشد. اما الگوریتم های تبرید شبیه سازی شده و ژنتیک موفق می شوند جواب بهینه را بدست آورند. مقایسه زمان اجرای این الگوریتم ها نشان می دهد که الگوریتم ژنتیک در کمترین زمان به جواب بهینه دست پیدا می کند. همچنین روش تپه نوردی کمترین مقدار حافظه مصرفی را داراست.

کلیدواژه ها:

مسیله فروشنده دوره گرد ، الگوریتم های فراابتکاری ، الگوریتم ژنتیک ، برنامه نویسی پویا