توصيفگر ها :
فروشنده سيار , روش مجارستاني , مسئله تخصيص , گلوگاهي , دسته بندي هاپفيلد , لاگرانژي , كران ليتل , ايستمن , 1-EERT , مسيريابي , سيم كشي , يك آرايه , خطوط پوشا
چكيده فارسي :
مسئله فروشنده سيار جزء مسائل مشهور كلاسيك تحقيق در عمليات مي باشد. اين مسئله از جمله مسائل بهينه سازي تركيبي است كه زمان حل آن تابعي غيرچند جمله اي دارد به اين معني كه با زياد شدن تعداد شهرها زمان حل آن بصورت نمايي افزايش پيدا مي كند. در مسئله فروشنده سيار تعدادي شهر وجود دارد كه يك فروشنده مي خواهد از يكي از اين شهرها شروع و به تمام شهرها سفر نمايد و در نهايت به شهر اول باز گردد به شرطي كه از هر شهر فقط يكبار عبور نمايد. هدف بدست آوردن يك مسير براي اين فروشنده مي باشد. بنحويكه طول ( هزينه ، زمان ) كل مسير طي شده توسط وي حداقل مقدار را دارا باشد. طي چند دهه اخير، راه حلهاي زيادي براي حل اين مسئله ارائه شده است . از جمله روشهاي كامل مي توان به روشهاي شاخه و كران ، ساده سازي لاگرانژي، برنامه ريزي پويا و ... اشاره نمود. همچنين روشهاي ابتكاري زيادي از جمله شبكه هاي عصبي ، جستجوي ممنوع ، الگوريتم ژنتيك و ... نيز براي حل مسئله فروشنده سيار مورد استفاده قرار گرفته است . در اين تحقيق يك راه حل كامل ، براساس شاخه و كران و حل مجارستاني مسئله تخصيص براي حل مسئله فروشنده سيار بسط داده شده است . در ادامه روشهايي براي تحليل حساسيت مسئله فروشنده سيار ارائه شده كه اين روشها برمبناي راه حل پيشنهادي مي باشد. يكي از معروفترين روشهاي حل كامل مسئله فروشنده سيار، روش شاخه و كران ليتل مي باشد كه در اين تحقيق روش پيشنهادي را با آن و روش شاخه و كران ايستمن مقايسه نموده ايم . براي اين منظور الگوريتم هرسه روش به زبان C++كد شده اند و با استفاده از اعداد تصادفي مسائل مختلف فروشنده سيار توليد شده و با هرسه روش حل شده اند. نتايج نشان مي دهد كه متوسط زمان روش پيشنهادي كمتر از دو روش ديگر مي باشد و با افزايش تعداد شهرها كارآيي روش پيشنهادي بيشتر مي شود
