شماره ركورد كنفرانس :
4398
عنوان مقاله :
مقايسه الگوريتم هاي فراابتكاريبه منظور حل مسئله فروشنده دوره گرد
پديدآورندگان :
اطمينان نازنوش na.etminan@yahoo.com دانشگاه آزاد اسلامي، واحد شيراز، گروه مهندسي كامپيوتر، شيراز، ايران , پروين نيا الهام parvinnia@iaushiraz.ac.ir دانشگاه آزاد اسلامي، واحد شيراز، گروه مهندسي كامپيوتر، شيراز، ايران , صفري محمد safari.md@gmail.com دانشگاه آزاد اسلامي، واحد شيراز، گروه مهندسي كامپيوتر، شيراز، ايران , مسعودي چله گاهي مهدي masoudi737@gmail.com دانشگاه آزاد اسلامي، واحد شيراز، گروه مهندسي كامپيوتر، شيراز، ايران
كليدواژه :
مسئله فروشنده دوره گرد , الگوريتم هاي فراابتكاري , الگوريتم ژنتيك , برنامه نويسي پويا
عنوان كنفرانس :
سومين كنگره بين المللي فن آوري، ارتباطات و دانش (ICTCK2016)
چكيده فارسي :
مسئله فروشنده دوره گرد از جمله مسايل كاربردي در صنعت حمل و نقل است كه حل بهينه آن، سرعت عمل بالاتر در سرويس دهي و رضايت مشتري را به دنبال خواهد داشت. در اين مقاله ابتدا حل بهينه مسئله فروشنده دوره گرد با استفاده از روش برنامه نويسي پويا براي دو مجموعه داده Iran59 و مجموعه داده اي شاملده شهر از ايران بدست آمده است. سپس اين مسئله با سه الگوريتم فرا ابتكاري تپه نوردي، تبريد شبيه سازي شده و الگوريتم ژنتيك براي همانمجموعه داده ها حل شده و عملكرد روشهاي فراابتكاري با حل بهينه مقايسه شده است. مقايسه ها از جهت نيل به جواب بهينه، زمان اجرا، و حافظه مصرفي مي باشد. نتايج بدست آمده نشان مي دهند كه الگوريتم تپه نوردي در كمينه محلي متوقف مي گردد و تور پيشنهادي آن طولاني تر از ساير روش ها مي باشد. اما الگوريتم هاي تبريد شبيه سازي شده و ژنتيك موفق مي شوند جواب بهينه را بدست آورند. مقايسه زمان اجراي اين الگوريتم ها نشان مي دهد كه الگوريتم ژنتيك در كمترين زمان به جواب بهينه دست پيدا مي كند. همچنين روش تپه نوردي كمترين مقدار حافظه مصرفي را داراست.
