يك روش پيوند - تجزيه زيرحلقه اي براي حل مسئله فروشنده دوره گرد

اصفهان : دانشگاه صنعتي اصفهان . دانشكده صنايع و مركز برنامه ريزي سيستم ها

كارشناسي ارشد (مهندسي سيستمهاي اقتصادي)

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

10418

مهندسي صنايع و سيستم ها

دانشگاه صنعتي اصفهان

محمدسعيد صباغ