بخشی از مقاله
چکیده
مسئله فروشنده دوره گرد در پی یافتن کوتاه ترین مسیر در بین مجموعه ای از شهرها هست، به گونه ای که هر شهر فقط یکبار در مسیر قرارگرفته و مسیر ساختهشده به شهر اولی منتهی شود. این مسئله علاوه بر جنبه نظری از جنبه عملی نیز کاربرد فراوانی دارد. به عنوان مثال در مواردی مانند مسیریابی، ساخت تراشه های الکترونیکی، زمان بندی کارها و غیره مورداستفاده قرار گیرد.
در حالتی خاص از مسئله فروشنده دوره گرد هزینه - فاصله بین شهرها - به صورت فازی در نظر گرفته می شود، این حالت از مسئله را، مسئله فروشنده دوره گرد فازی می گویند؛ در مواجهه با چالش حل مسائل بهینه سازی، روش های کلاسیک اغلب با مشکل مواجه م ی شوند؛ بنابراین با استفاده از روش های فرا ابتکاری که بهطور چشمگیری توانایی ما را در حل کردن مسائل مهم علمی بالابردهاند استفاده می شود. در این پژوهش به بررسی و مقایسه برخی از روش های فراابتکاری برای حل مسئله فروشنده دوره گرد فازی پرداخته شده است.
– 1 مقدمه
مسئله فروشنده دورهگرد جزء مسائل مشهور کلاسیک میباشد، این مسئله از جمله مسائل بهینه سازی ترکیبی است، بدین معنی که با زیاد شدن تعداد شهرها زمان حل آن بهصورت نمایی افزایش می یابد. این الگوریتم بطور مستقیم1 در مرتبه زمانی O - n! - حل میشود اما اگر از روش برنامه نویسی پویا2 برای حل آن استفاده کنیم مرتبه زمانی آن O - n^2*2^n - خواهد شد.
در مسئله فروشنده دورهگرد تعدادی شهر وجود دارد که یک شخص می خواهد از یکی از شهرها شروع و به تمام شهر ها سفر نماید و در نهایت به شهر اول بازگردد، به شرطی که از هر شهر فقط یکبار عبور نماید و با توجه به اینکه رفتن از هر شهر به شهر دیگر دارای هزینه میباشد، هدف به دست آوردن یک مسیر برای این فروشنده میباشد بطوریکه هزینه کل مسیرطی شده توسط فروشنده مینیمم شود.
مسئله فروشنده دورهگرد را می توان به انواع مختلفی از قبیل، فروشنده دورهگرد احتمالی3، مسئله فروشنده دورهگرد با پنجره زمانی4، مسئله فروشنده دورهگرد چند کالایی5، مسئله فروشنده دورهگرد شبکه راه آهن6 و مسئله فروشنده دوره گرد فازی تقسیم نمود.[1] مساله فروشنده دورهگرد سال های زیادی است که مطرح شده است. اولین بار شخصی به نام ایولر7 در سال 1759 مبنی بر جابجایی اسب به تمامی خانه های صفحه شطرنج بهصورتی که مهره اسب فقط یک بار وارد هر خانه شود، مطرح نمود. بعد ها این مسئله توسط دانتزیک8 و همکاران در سال 1954 مطرح شد.
در سالهای بعد، پژوهش های مختلفی در این زمینه صورت گرفت به عنوان مثال، فیلت و همکاران[2]9 در سال 2005 مسئله فروشنده دورهگرد با سود را مطرح کردند. منظور از سود در این مسئله درآمد حاصل از بازدید هر گره میباشد. هدف در این مسئله، جمع آوری همزمان بیشترین سود همراه با کمترین هزینه توسط فروشنده میباشد.
کوتکس و همکاران[3]10 در سال 2010 حالتی از مسئله فروشنده دورهگرد را بیان کردند که در آن برای هر یال رنگ متفاوتی منظور می شود. هدف، یافتن مسیری با حداکثر یا حداقل تعداد رنگ بیان شد. جنتیلینی و همکاران[4]11 مسئله فروشنده دورهگرد با همسایگی را در سال 2013 مطرح کردند. در این پژوهش برای هر گره i، یک همسایگی تعریف شده به گونه ای که گره i مربوطه مجاز به جابه جایی در آن است. هدف در این مسئله، یافتن مکان بهینه قرارگیری هر گره در همسایگی میباشد. از کاربرد های این مسئله، زمینه های روباتیک و هواپیماهای بدون سرنشین را می توان نام برد.
-2 انواع حالت های مسئله فروشنده دوره گرد
مسئله فروشنده دوره گرد یکی ازمسائل کلاسیک درحوزه بهینه سازی ترکیبی می باشد و این مسئله به سبب کاربرد وسیع آن درحوزه های مختلف مهندسی همواره مورد توجه محققین بوده است بهصورت کلی مسئله فروشنده دورهگرد دارای 3 حالت زیر است.
1 - فروشنده دورهگرد متقارن:12 در حالت متقارن مسئله، تعدادی شهر وجود دارد که هزینه رفتن مستقیم از یکی به دیگری مشخص است. مطلوب است کم هزینهترین مسیری که از یک شهر شروع شود و از تمامی شهرها دقیقا یکبار عبور کند و به شهر شروع بازگردد.
2 - فروشنده دورهگرد نامتقارن :13 - ATSP - مسألهی فروشندهی دورهگرد نامتقارن، یک TSP است که فاصله بین رئوس آن، متقارن نیست. این بدان معنی است اگر فاصله بین دو گره i و j با d[i,j] نشان داده شود d[i,j] با d[j,i] احتمالا برابر نخواهد بود.ATSP بسیار مشکلتر از TSP است، در حقیقت TSP متقارن، در گرافهای با چندین هزار رأس، به طور بهینه، قابل حل است، اما فروشنده دوره گرد نامتقارن تنها در نمونههایی از مسئله فروشنده دوره گرد به جواب بهینه می رسد که دارای تعداد شهر های بسیار کمتری هستند.
3 - فروشنده دورهگرد با پنجره های زمانی: - TSPTW - 14 مسئله فروشنده دورهگرد با پنجره زمانی، شامل یافتن کوتاهترین طول توری است که به وسیله یک فروشنده دورهگرد طی میشود با این شرایط که فروشنده باید هر گره را فقط یکبار ملاقات کند و در پنجره زمانی معینی به آن سرویس دهد. به این معنا که اگر فروشنده زودتر از محدوده زمانی تعیین شده به آن گره برسد باید منتظر بماند تا بازه زمانی سرویس دهی مربوط به آن گره شروع شود. همچنین اگر دیرتر از پنجره زمانی برسد ارائه سرویس به آن گره دیگر امکان پذیر نخواهد بود.[5]
مسئله فروشنده دوره گرد می توان به مسئلهGTSP15 تعمیم مسئله TSP میباشد. به گونه ای که فروشنده نیازی به رعایت محدودیت بازدید شهرها را ندارد. این مسئله ابتدا در سال 1989 توسط نون[6] 1 شرح داده شد. سپس در سال 1997 فیسچی و همکاران[7]2 به بیان این مسئله در حالت متقارن پرداختند. در سالهای بعد، مسئله در حالت خوشه بندی مورد بررسی قرار گرفت به طوری که کچیانی و همکاران3 همکاران[8] 3 این مسئله را به گونه ای مطرح ساختند که در آن، تعداد تعداد گرههای هر خوشه - مجموعه گرهها - بهصورت مساوی در نظر گرفته شد. هدف در این مسئله، یافتن مسیری با کمترین هزینه میباشد به گونه ای که فروشنده از هر خوشه یکبار عبور کند.
- 3 مسئله فروشنده دوره گرد فازی
منطق فازی یکی از اشکال منطق چند ارزشی4 است که با استدلال تقریبی سروکار دارد. در مقایسه با مجموعههای دودویی کلاسیک، مقادیر صحت در متغیرهای منطق فازی طیفی را در بازه صفر و یک شامل میشوند. منطق فازی به منظور در بر گرفتن مفهوم صحت جزئی توسعه داده شده است. علاوه بر این، وقتی متغیرهای زبانشناختی استفاده شوند، این درجات صحت می-توانند توسط توابع ویژهای تحت عنوان توابع عضویت توصیف شوند. امروزه منطق فازی در حوزههای مختلف کاربرد گستردهای دارد.
از زمانی که اعدادفازی بهصورت تابع عضویت ارائه شدند، تعیین کوچکتر یا بزرگ تر بودن یک عدد نسبت به عدد دیگر در حالت فازی کمی دشوار بود، این همان چیزی است که باعث بهبود سختی در حل مسئله میشود. به عنوان مثال دو مسیر با وزن های فازی W1 و W2 را در نظر بگیرید، برای تعیین مینیمم آنها نیازی به مقدار دقیق W1 یا W2 نداریم.
بهترین ایده تبدیل اعداد فازی به اعداد حقیقی میباشد؛ اما نکته مهم این است که روش های مختلفی در در رتبه بندی اعداد فازی وجود دارد؛ و در بیشتر موارد، برای تصمیم گیری جامع اندازه گیری تکی کافی است. زمانی که چندین معیار تصمیم گیری وجود دارد، به جای جواب بهینه مشخص با مجموعه ای از جواب های مغلوب نشده - جواب هایی که توسط هیچ یک از معیارهای تصمیم گیری دیگر مغلوب نشده اند - مواجه هستیم.
به طور کلی فازی بودن می تواند در انواع شبکه ها معرفی شود، اما در مسئله فروشنده دوره گرد فازی برای گنجایش یال ها، وزن یال ها یا محدودیت در گرهها می تواند استفاده شود. در دنیای واقعی، بر اثر برخی رویدادهای غیرمنتظره، ممکن است وزن یال ها در شبکه تغییر نماید. از این رو، در بیشتر مواقع، وزن تنها می تواند در یک بازه ی معین تخمین زده شود.
در نتیجه، اگر بخواهیم وزن یال ها را بطور دقیق برای انتخاب مسیر نشان دهیم کاری بسیار دشوار است. در چنین شرایطی، به نظر می رسد که رویکرد فازی برای حل مسئله کوتاه ترین مسیر، انطباق بیشتری با واقعیت داشته باشد. مسئله کوتاه ترین مسیر فازی در دو حالت قابل بحث است در حالت اول وزن هر یال به عنوان یک عدد فازی به تصویر کشیده شود، در حالت دوم طول مسیر از مبدا تا مقصد بعنوان یک عدد فازی در نظر گرفته شود.[9] به عنوان مثال فرض کنید دو شهر A و B را داریم، در حالت کلاسیک فاصله بین دو شهر تنها یک عدد ثابت می باشد، مثلا X در حالی که در حالت فازی فاصله بین دو شهر A و B بسته به نوع در نظر گرفتن حالت فازی - فازی مثلثی یا فازی ذوزنقه ای - می تواند متشکل از 3 عدد - X,Y,Z - یا - X,Y,Z,W - باشد و مسئله با این اعداد حل خواهد شد.
– 4 فازی سازی مسئله فروشنده دوره گرد
به منظور حل مسئله فروشنده دوره گرد فازی، باید از داده های فازی استفاده شود، اما نکته مهم و مورد بحث تهیه دیتاست5 استاندارد فازی می باشد. در واقع به دلیل نبود دیتاست استاندارد، باید داده های مسئله را یا به صورت تصادفی ایجاد کنیم که این کار باعث می شود که دیگر نتوان نتیجه مسئله را با روش های دیگر مورد مقایسه قرار داد و یا اینکه از طریق داده های استاندارد مسئله فروشنده دوره گرد، آنها را بسازیم، که به این ترتیب تنها با نگاشت تور تولید شده بر روی تور غیر فازی و با به دست آوردن هزینه غیر فازی آن، هزینه را با تور های استاندارد می توان مقایسه نمود. بدیهی است که روش های مختلفی برای فازی کردن داده های استاندارد وجود دارد، و انتخاب هر روش به طراح الگوریتم بستگی دارد. حال یکی از روش هایی که می توان از طریق آن داده های استاندارد مسئله فروشنده دوره گرد را فازی کرد، به شرح زیر می باشد:[9]
1. داده های اولیه را از دیتاست استاندارد فروشنده دوره گرد استخراج می کنیم - این داده ها در سایت TSPLIB به صورت فایل تکس موجود است -
2. در مرحله دوم باید فاصله بین نقاط را که محاسبه آن به صورت فاصله اقلیدسی می باشد محاسبه و فاصله هر دو شهر را - dij - در نظر گرفت.
3. دو عدد تصادفی مثبت کوچکتر از dij* را ایجاد می کنیم و اعداد تصادفی را با mij , pij در نظر می گیریم، همچنین مقدار لاندا بزرگتر از صفر و کوچکتر از یک در نظر گرفته شده.
.4 حال 3 نقطه به دست آمده را که به صورت - dij-mij ,dij, dij+pij - داریم، به عنوان یک نقطه فازی در نظر می گیریم.
