بخشی از مقاله
چکیده
تکنیک شبیه سازی فرآیندی است که به سازمان ها کمک می کند تا نتایج عملکرد و فرآیند تصمیم گیری خود را پیش بینی، مقایسه و بهینه سازی کنند، بدون اینکه هزینه و ریسک تغییر فرآیند های جاری و اجرای جدید را متحمل شوند. بوسیله این ابزار کارآمد، می توان هزینه ها و ریسک اتخاذ تصمیم های نادرست در سازمان را کاهش داد و فرآیند ها و محصولات سازمان را بهبود بخشید. یکی از کاربردهای گسترده شبیه سازی در حل مدل های پیچیده و بزرگ است.
مساله فروشنده دوره گرد، یکی از آن مسائل پیچیده و مشکل است که سال ها ذهن بشر را به خود مشغول کرده است. اگرچه محققان زیادی با روش ها و الگوریتم های مختلف نسبت به حل این مساله اهتمام ورزیده اند، اما حل این مساله بوسیله تکنیک شبیه سازی و تعداد 30 شهر فرض شده یک روش نسبتا جدیدی محسوب می شود. در این تحقیق سعی شده است تا این مساله شبیه سازی شده و بتوان یک جواب نزدیک به بهینه بطوریکه فروشنده دوره گرد از تمامی شهرها عبور کرده و دوباره به شهر مبدا خود باز گردد را بدست آورد.
-1 مقدمه
مساله فروشنده دوره گرد - TSP - 1یکی از مسائل مهم و پیچیده ای است که سال ها ذهن محققان و نویسندگان را به خود مشغول کرده است . بطور کلی مساله بدین گونه است که در محدوده جغرافیایی فروشنده دوره گرد تعدادی شهر وجود دارد که فاصله بین هر زوج از شهرها مشخص و عددی ثابت است که فروشنده از یکی از شهرها شروع کرده و کلیه شهرها را فقط یکبار ملاقات کند و با کمترین مسافت پیموده شده به نقطه شروع باز گردد.[1]
در این تحقیق سعی شده بوسیله تکنیک شبیه سازی این مساله با فرض تعداد 30 شهر حل گشته و مسیرها و ترتیب عبور از شهرها و محاسبه کل مسافت عبوری نزدیک به بهینه را بدست آورد. با توجه به بزرگ شدن مدل و جواب های موجه بدست آمده که به تعداد 30! است، حل مدل بوسیله نرم افزار های تحقیق در عملیات2 نظیر لینگو3امکان پذیر نبوده و عملا مساله، یک مساله NP سخت 4 محسوب می شود. چرا که هرچه به تعداد شهرهای ملاقات شده اضافه شود، تعداد زیر حلقه های5 تصادفی ایجاد شده در مدل افزایش یافته و به تبع آن تعداد محدودیت های مدل نیز افزایش خواهد یافت.با استفاده از تکنیک های شبیه سازی و فرموله کردن مساله به زبان برنامه نویسی در نرم افزار شبیه سازی می توان این مساله پیچیده و مشکل را به راحتی و پس از زمان اجرای6 نسبتا کوتاهی حل نمود.
-2 سوابق مربوط به مطالعات گذشته
تحقیقات و مطالعات زیادی در رابطه با حل مساله فروشنده دوره گرد بوسیله روش ها و الگوریتم های مختلف توسط محققان و نویسندگان انجام شده است، با توجه به ماهیت مشخص مساله فروشنده دوره گرد و هدف آن، محققان برای حل این مساله از روش های حل مختلفی برای حل این مدل استفاده کرده و نشان داده اند که مزیت روش جدید خود در چه بوده است و می توان اظهار نمود که اکثر روش های حل برای این مساله توسط الگوریتم ژنتیک پیشنهاد شده است. در اینجا بطورخلاصهبه معرفی برخی از آن ها و روش های حل بکارگرفته شده می پردازیم:
گلدبرگ و لینگل[2] دو روش مختلف را برای حل یک مساله فروشنده دوره گرد توسط الگوریتم ژنتیک با 10 شهر پیشنهاد دادند و نشان دادند که می توان توسط این روش ها به جواب نزدیک به بهینه رسید.گرفنستت و همکاران[3]، آمباتی و همکاران[4]، فانگ گنگ ژاو و همکاران[5]، مسافومی کورادا و همکارن[6] سعی در حل این مساله به کمک الگوریتم ژنتیک گماردند، آنان در اظهارات خود بیان داشتند که با توجه به بزرگ تر شدن مساله و غیر عملی شدن حل آن توسط نرم افزار ها و الگوریتم های ساده و وجود مسیرها و شبکه های گسترده موجه و قابل قبول برای حرکت، نشان دادند که بایستی برای حل این مسائل پیچیده روی به الگوریتم های فرا ابتکاری آورد. آنان برای حل مدل خود از الگوریتم فراابتکاری ژنتیک بهره جستند و توانستند مساله فروشنده دوره گرد را با استفاده از عملگرهای تقاطع1 وجهش2 مورد نظر خود در هر با اجرا به یک همگرایی قابل قبولی رسیده و هر بار جواب های بهتر و مسیرهای حرکت با مسافت پیموده شده کمتری را بدست آورند.
-3 مدل ریاضی مساله فروشنده دوره گرد
همانطور که ذکر شد، مساله فروشنده دوره گرد یافتن مسیری است که فروشنده پس از شروع از یک شهر و ملاقات تمامی شهرها با کمترین مسافت پیموده شده، دوباره به شهر آغازین خود بازگردد. در ابتدا به معرفی پارامترها و متغیر تصمیم در این مدل پرداخته و سپس تابع هدف و محدودیت های مساله را تشریح خواهیم کرد.
-1-3 پارامترهای مساله
تابع هدف مساله فروشنده دوره گرد کمینه نمودن کل مسافت های عبوری و طی شده است. محدودیت های 2 و 3 تضمین کننده آن هستند که فرد دقیقا باید یکبار از هر شهر عبور کند. محدودیت 4 که در آن از U استفاده شده است، از ایجاد هر نوع زیر شبکه1جلوگیری می کند.
