لینک دانلود و خرید پایین توضیحات
فرمت فایل word و قابل ویرایش و پرینت
تعداد صفحات: 45
روش شناسی
مقدمه:
ما مطمئناً فریب خواهیم داد آن دسته از خوانندگانی را که تاکنون به اندازه کافی برای خواندن کتاب موجود صبور بوده اند و کسانی که را که می خواستند بدانند برای حل مساله در نظر خود باید از کدام متاهیورستیک (فوق اکتشافی)کمک بگیرند در واقع،این سوال ،سوال مناسبی است،اما ما باید اقرار کنیم که پیشنهاد یک یا چند راه حل مشخص ممکن نیست دیده شده است نتایج تئوری ضعیفی که در مورد متاهیورستیک ها شناخته شده اند اکثراًدر عمل مفید نیستند در واقع،این نظریه ها تا حدی بیان می کنند که برای اطمینان از اینکه حالت مطلوب به درستی مشخص شده باشد نیاز بوده است که تعدادی از راه حل ها که بزرگتر از تعداد کل راه حل ها ی مساله هستند آزمایش شوند به عبارت دیگر آنها(بطور معمول) پیشنهاد می کردند که از یک روش مشخص استفاده شود اگر نیاز بوده است که حالت مطلوب به صورت کاملاًدرست مشخص شده باشد با این وجود ،در این بخش تلاش خواهد شد که تعدادی راه حل ارائه شود برای ایجاد یک روش اکتشافی بر اساس قوانین فرا علمی که قبلاً مورد بحث قرار گرفت بر اساس قوانین قبلی که ما در قسمت جستجوی تا بو آن
را پذیرفته بودیم ،این توضیح با کمک مساله بهینه سازی داده شده ارائه خواهد شد مساله مسیریابی ماشین برای این مورد خاص انتخاب شده است برای اینکه مثال تا حد ممکن روشن شود ما خود را به ساده ترین مدل مساله محدود کردیم که آن را به عنوان مساله مسیریابی ماشین توانا شده در کتابها می شناسند با این وجود ،روش شناسی پیشنهاد شده یکی از کلی ترین آنهاست و باید برای تمام مسائل پیچیده نیز به همین خوبی قابل اجرا باشد
مساله مسیریابی ماشین مناسب برای آموزش
یک مساله مناسب برای آموزش ،که ساده شده مسائل مسیریابی سودمند هستند می توانند به صورت زیر تعریف شوند یک مجموعه نامشخص از ماشین ها که هر کدام قادر هستند حجمv از کالاها را حمل کنند،نیاز است که n تا از سفارش های مشتری ها را تحویل دهند،از یک ایستگاه مشخص شروع کنند،به ترتیبی که مسافت کلی پیموده شده به وسیله ماشین ها مینیمم شود هر سفارش (یا به طور عادی می توان گفت هر مشتری)
Iحجمی به اندازهvi دارد (I=1 ,..,n) مسیر مستقیم ( dij ) بین مشتری های I,j(I,j=0,...,n) معلوم است،و صفر نشان دهنده ایستگاه شروع (انبار ) است صفرهای ماشین ها با Tk(k=1,2,3..) مشخص می شود که از نقطه آغاز (ایستگاه)شروع شده و با برگشت شان به نقطه آغاز (ایستگاه) تمام می شود یک نوع دیگر از مساله است که محدودیت دیگری را اعمال می کند ،به این صورت که طول مسیر باید از مقدار محدود شده Lبیشتر باشد شکل 7.1 شکل نمودار یک مساله اقلیدسی را نشان می دهد که در نوشته ها ی [christofides et al.,1979]
آمده است با 75 مشتری (که در شکل با دایره های توخالی مشخص شده است و اندازه دایره ها به میزان حجم در خواستی مشتری بستگی دارد ،یعنی هر چه میزان حجم در خواستی مشتری بیشتر باشد ،اندازه دایره بزرگتر است و بالعکس) و یک نقطه شروع (ایستگاه)(که با یک دایره توپر سیاه مشخص شده است و اندازه آن متناسب با ظرفیت ماشین ها می باشد) یک راه حل این مساله می تواند به صورت یک بخش از مجموعه مشتری ها به یک تعداد از زیر مجموعه های سفارشات در نظر گرفته شود،سفارشی که مشخص می کند سلسله مراتبی را که حد آن هر ماشین مجبور است کلیه مشتری هایی که تشکیل یک توررا می دهند ملاقات می کند اولین سوالی که باید به آن پاسخ داده شود درباره تعداد تورهایی است که نیاز است ایجاد شود باید در اینجا ذکر شود که برای مسائل کاربردی ،محدود نیستند و همیشه یافتن یک راه حل ممکن برای مساله بدیهی نیست در واقع،تقسیم مشتری ها به صورت یک تعداد زیر مجموعه مشخص بر اساس وزن کالای در خواستی شان مساله مشهور فشرده سازی np کامل مواد اولیه است حتی اگر تعداد ماشین ها نامحدود نباشد
در نظر گرفتن تمام راه حل های ممکن مساله ممکن است مفید نباشد و این به خاطر این است که مجموعه مورد نظر ممکن است شامل تعداد زیادی از راه حل هایی باشد که کیفیت پایینی دارند و مرغوبیت پایین آنها به آسانی قابل مشاهده است ،برای نمونه هایی که شامل تعداد زیادی از سفرها با یک مشتری هستند یک راهنمای اولیه ممکن است سعی کند که انفجار ترکیبی راه حل ها را محدود کند این راهنما می تواند با داشتن آگاهی درباره مساله و در واقع با به کاربردن یک روش اکتشافی بدست بیاید به عبارت دیگر اندازه مجموعه راه حل های ممکن باید محدود شود یک نوع مثال برای cvrp این است که محدودیت هایی اعمال شود به این صورت که همه سفارشاتی که به وسیله یک مشتری قرار گرفته اند باید در یک سفر یک وسیله مشخص قرار داده شوند به شرطی که ماشین ظرفیت کافی داشته باشد روش دیگری وجود دارد که فقط شامل آن دسته از راه حل هایی می شود که حداکثر از یک یا دو ماشین بیشتر از مینیمم تعداد ماشین های مورد نیاز برای تحویل سفارشات به تمام مشتری ها استفاده می کنند (این حد پایین(مینیمم) تعداد ماشین به آسانی و به صورت مستقیم کل حجم سفارشات ظرفیت یک ماشین بدست می آید)با این وجود اگر به این صورت عمل شود ممکن است یافتن یک راه حل ممکن یا مشخص کردن ساختار یک همسایگی مناسب مشکل است
مدل سازی مساله
این توجه طبیعتاً منجر به این می شود که ما درباره مشخصات s،مجموعه راه حل های ممکن بحث کنیم در واقع ممکن است شکل این مجموعه بسیار پیچیده شود،یعنی بدون داشتن مشخصاتی از یک همسایه بزرگ ایجاد تمام راه حل های ممکن غیر ممکن است یا به صورت دقیق تر ممکن نیست به یک راه حل بهینه دست پیدا کرد با شروع از هر راه حل ممکن در این حالت ،برای اجتناب از تعریف یک همسایه بزرگ و غیر قابل کنترل (بنابراین به اعمال محاسباتی برای انجام یک بار جستجوی محلی که بازدارنده باشد نیاز است) مجموعه راه حل های ممکنگسترش می یابد تا زمانیکه راه حل های جریمه کننده محدودیت های اولیه مساله را نقض کنند بنابراین مساله به صورت زیر اصلاح می شود بهبود می یابد):
Min f(s)+p(s)
Sextendeds
که در آن Sextended s و p(s)=0 برایSsوP(S)>0 برایSs
روش شناس 45 ص