برق. قدرت. کنترل. الکترونیک. مخابرات. تاسیسات.

دایره المعارف تاسیسات برق (اطلاعات عمومی برق)

مساله فروشنده دوره گرد (TSP ) یكی از مسائل مشهور بهینه سازی تركیبی است كه اساس آن به این صورت است كه یك فروشنده دوره گرد می خواهد بهN شهر برود و كالای خود را به فروش برساند ، به طوری كه از هر شهر فقط یك بار عبور كند و تمام شهر ها را رفته باشد و در نهایت كمترین مسیر را طی كرده باشد عکس. دراینجا یك ماتریس فاصله شهر ها (d) وجود دارد كه فاصله شهر i از j را با dij نشان می دهد و فاصله شهر i از خودش را با dii نشان می دهیم كه مقدار آن صفر است و روی قطر اصلی ماتریس می باشد . یك تور یك جایگشت Π از {n،......1,2,} می باشد . هدف مساله فروشنده دوره گرد پیدا كردن جایگشتی است كه كمترین طول را دارد. فضای حل مساله TSP با زیاد شدن تعداد شهرها به سرعت افزایش می باشد و دیگر با روشهای برنامه ریزی خطی نمی توان جواب بهینه آن را به دست آورد.







از لحاظ مهم بودن و كاربرد بسیار زیاد TSP در مسائل گو.ناگون تا كنون افراد زیادی روی این مساله با روشهای گوناگونی كار كره اند . تاریخ ابداع مساله TSP دقیقا معلوم نیست . ولی برای اولین بار در سال 1700 برای مساله حركت اسب در شطرنج به كار برده شد و در سال 1800 آقای William Rowan Hamilton در تئوری گراف از مساله فروشنده دوره گرد استفاه كرد .و در سال 1832 در آلمان به نام مساله فروشنده دوره گرد شناخته شد .و در سال 1930 Whitney Hassler ، مساله TSP را در دانشگاه Harvard و Princeton در ایالات متحده معرفی كرد. در سال 1940 آقای M Floodاین مساله را در شركت RAND در كالیفرنیا مشهور كرد و Dantzig, Fulkerson و Johnson برای اولین بار یك روش به نام روش صفحه برش كه قسمتی از برنامه ریزی خطی می باشد را برای حل TSP ارائه كردند .و بدین ترتیب روشهای گوناگونی برای حل ان پیدا شد و مساله كاربرد بیشتری پیدا كرد.و كم كم از سال 1978 به بعد از الگوریتمهای متا هیوریستیك برای حل آن استفاده شد. حل این مساله کاربرد وسیعی در حوزه های مختلف مهندسی از جمله حل انواع مسایل زمانبندی، مسیریابی، جایابی کالا در انبار، جایابی ماشینها در کارگاهها، طراحی مدارات چاپی و.. دارد.


با توجه به درخواست های مکرر مراجعین، گروه متخصصین برنامه نویسی هوشمند متلب سایت اقدام به تهیه برنامه حل مسئله فروشنده دوره گرد با استفاده از الگوریتم ژنتیک کرده و کد متلب آن را برای دانلود در اختیار مراجعین قرار داده است.

در ادامه لینک دانلود این برنامه قرار داده شده است:

http://ifile.it/ba0gqfk (35.5 KB)

برای دانلود از لینک فوق ابتدا روی لینک کلیک کنید و کمی منتظر بمانید. سپس در صفحه جدید باز شده روی گزینه Request Download Ticket کلیک کنید. با کمی انتظار در صفحه جدید باز شده نیز گزینه Download را کلیک کرده و فایل را ذخیره کنید. اگر فایلهای زیپ شده نیاز به پسورد داشتند، پسورد matlabsite.com را وارد کنید.

http://linuxboy.blogfa.com/post-92.aspx

صفحات جانبی

نظرسنجی

    لطفاً نظرات خود را درمورد وبلاگ با اینجانب در میان بگذارید.(iman.sariri@yahoo.com)نتایج تاکنون15000مفید و 125غیرمفید. با سپاس


  • آخرین پستها

آمار وبلاگ

  • کل بازدید :
  • تعداد نویسندگان :
  • تعداد کل پست ها :
  • آخرین بازدید :
  • آخرین بروز رسانی :