خرده فروشها باشد. با این وجود، اجرای عملگرهای همگذری و جهش ممکن است باعث تولید کروموزومهایی شوند که فاقد این خصوصیت هستند، بنابراین اصلاح این کروموزومها ضروری میباشد. در این تحقیق از یک روش اصلاح چرخهای[۷۹] [۶۵] برای اصلاح کروموزومهای نامعتبر استفاده می شود.
بر اساس این روش و در ارتباط با هر یک از بخشهای اول و دوم، اگر مجموع مقدار ژنهای آن بخش از تعداد محصولات سفارش داده شده توسط همه خرده فروشها کمتر باشد به مقدار فعلی ژنی که به صورت تصادفی انتخاب شده است یک واحد اضافه می شود در حالی که اگر مجموع مقدار
ژنهای آن بخش از تعداد محصولات سفارش داده شده توسط همه خرده فروشها بیشتر باشد از مقدار فعلی ژنی که به صورت تصادفی انتخاب شده است یک واحد کم می شود. این فرایند تا برابر شدن مجموع مقدار ژنها با تعداد محصولات سفارش داده شده توسط همه خرده فروشها تکرار
می شود.
شکل (۳-۹) نحوه عملکرد این روش به منظور اصلاح یک کروموزوم تولید شده پس از اعمال عملگرهای همگذری و جهش برای مثال (۳-۳) ارائه می کند. همان طوری که از شکل مشخص است مجموع مقدار ژنها در بخش اول از تعداد کل محصولات سفارش داده شده به وسیله خرده فروشها کمتر میباشد، بنابراین بر طبق روش بالا مقدار ژن دوم این بخش از عدد ۲ به عدد ۳ افزایش داده می شود، ولی هنوز این مجموع از تعداد کل محصولات سفارش داده شده به وسیله خرده فروشها کمتر میباشد، در نتیجه دوباره یک ژن به طور تصادفی انتخاب شده (ژن چهارم) و به مقدار آن یک واحد افزوده می شود. در این تکرار مجموع مقدار ژنها با تعداد کل محصولات سفارش داده شده به وسیله خرده فروشها برابر است. در بخش دوم، چون مجموع مقدار ژنها از تعداد کل محصولات سفارش داده شده به وسیله خرده فروشها بیشتر است، یک واحد از مقدار ژن انتخاب شده (ژن ششم) کم می شود. در این تکرار، یکسان بودن مجموع مقدار ژنها با تعداد کل محصولات سفارش داده شده به وسیله خرده فروشها باعث توقف الگوریتم می شود.
شکل ۳-۹: روش اصلاح چرخهای
۳-۷-۷- روش جستجوی محلی
جستجوی محلی به عنوان یک مکمل برای عملگرهای تکامل می تواند باعث بهبود خصوصیت تشدید[۸۰] به منظور دستیابی به جوابهای خوب موجود در همسایگی جوابهای فعلی شود [۶۶]. در الگوریتم توسعه داده شده در این تحقیق، روش جستجوی محلی مورد استفاده به منظور دستیابی به جوابهای بهتر بر روی درصدی از جوابهای فعلی اعمال می شود. قابل ذکر است که روش جستجوی محلی به طور متوالی بر روی بخشهای یک تا چهار اعمال می شود.
روش جستجوی محلی مورد استفاده برای هر یک از دو بخش اول بدین گونه است که نخست دو ژن به صورت تصادفی انتخاب شده سپس، کلیه حالاتی که مجموع دو عدد تخصیص داده شده به این دو ژن برابر مجموع دو مقدار فعلی باشند مورد بررسی قرار گرفته و در صورت بهتر بودن ( بر اساس تابع برازندگی) بهترین جواب همسایگی از جواب فعلی، این جواب جایگزین جواب فعلی می شود.
در ارتباط با بخشهای سه و چهار، روش جستجوی محلی با اجرای تعداد از پیش تعیین شدهای حرکت تعویض اعمال می شود. بدین نحو که در هر حرکت مقدار دو ژن انتخاب شده با یکدیگر تعویض میشوند. در این روش پس از اجرای هر حرکت تعویض، جواب جدید در صورت بهتر بودن (بر اساس تابع برازندگی) جایگزین جواب فعلی می شود.
فصل چهارم:
نتایج محاسباتی و تحلیل
در این فصل نتایج و تحلیلهای لازم در ارتباط با دو مسأله بررسی شده در فصل سوم ارائه خواهند شد. نخست نتایج مربوط به مسأله اول و تحلیلهای لازم در ارتباط با این نتایج و سپس، نتایج الگوریتم توسعه داده شده برای حل مسأله دوم و تحلیلهای آن ارائه خواهند شد.
۴-۱- نتایج محاسباتی مسأله اول
در این بخش، به منظور تصدیق مدل و روش حل ارائه شده مربوط به مسأله یکپارچه کردن
طرحهای تهیه مواد اولیه، تولید و توزیع، دو مسأله نمونه به صورت تصادفی تولید شده و به وسیله نرم افزار بهینهسازی Lingo توسط یک سیستم کامپیوتری با واحد پردازش مرکزی[۸۱] ۲ گیگا هرتز، حافظه اصلی[۸۲] ۲ گیگا بایت و پنتیوم ۴ حل میشوند. به منظور راحتی و بدون از دست دادن کلیت، از اعداد فازی مثلثی متقارن به منظور بیان عدم قطعیت موجود در عرضه، فرایند و تقاضا استفاده
می شود به طوریکه برای هر پارامتر فازی پس از تولید محتملترین مقدار، مقادیر بدبینانه و
خوشبینانه به ترتیب برابر ۸۰ و ۱۲۰ درصد محتملترین مقدار انتخاب میشوند [۶۷]. علاوه بر این، سطوح اطمینان محدودیتهای فازی دارای مقادیر یکسان هستند.
ابعاد اولین مسأله نمونه تولید شده بر حسب تعداد تأمینکنندگان، تولیدکنندگان، مراکز توزیع، باراندازهای میانی، خرده فروشها، مواد اولیه، محصولات و دوره های زمانی به وسیله جدول (۴-۱) نشان داده شده است. برای این مسأله نمونه، تعداد متغیرهای صفر و یک مدل (حاصلضرب تعداد محصولات، تعداد باراندازهای میانی، تعداد خرده فروشها و تعداد دوره های زمانی) برابر ۳۰۰ است، همچنین تعداد کل متغیرها و محدودیتها به ترتیب برابر با ۹۷۸ و ۸۸۶ است.
با در نظر گرفتن سطوح اطمینان مختلف، نتایج مربوط به مقادیر بهینه توابع هدف اول و دوم د
ر فرایند حل جداگانه ( و ) و همچنین بزرگترین مقدار هر یک از توابع هدف، مقدار تابع هدف به ازای جواب بهینه تابع هدف دیگر، ( و ) در جدول (۴-۲) ارائه شده اند.
جدول ۴-۱: ابعاد اولین مسأله نمونه
از آنجایی که تابع هدف دوم بر حسب میزان موجودی و کمبود محاسبه می شود و از طرف دیگر هیچگونه محدودیتی در ارتباط با تعداد محصولات تولید شده از طریق پیمانکاری وجود ندارد مشاهده می شود که حداقل مقدار این تابع صرف نظر از سطوح اطمینان انتخاب شده برابر صفر است.
جدول ۴-۲: حداقل و بزرگترین مقدار توابع هدف برای اولین مسأله نمونه
نتایج نهایی مربوط به اولین مسأله نمونه تولید شده به وسیله جدول (۴-۳) نشان داده شده است. ستونهای این جدول به ترتیب نشاندهنده سطح اطمینان، مقدار بهینه (حداکثر شده) حداقل سطح رضایتمندی توابع هدف (λ*)، مقدار هر یک توابع هدف در حداقل سطح رضایتمندی به دست آمده ( و ) و زمان محاسباتی مورد نیاز میباشند. با توجه به نتایج مشخص است که در همه موارد حداقل سطح درجه رضایتمندی به عدد یک نزدیک بوده و در نتیجه مقدار هر یک از توابع هدف به مقادیر بهینه آنها (جدول (۴-۲)) نزدیک است.
به منظور بررسی تغییرات توابع هدف در سطوح اطمینان مختلف، اختلاف مقادیر بدست آمده در حداقل سطح رضایتمندی و مقدار بهینه برای توابع هدف اول و دوم به ترتیب توسط شکلهای
(۴-۱) و (۴-۲) نمایش داده شده است. با توجه به شکلهای (۴-۱) و (۴-۲) مشخص است که مقدار بدست آمده از روند خاصی پیروی نمیکند. البته، مقدار اختلاف برای هر یک از توابع هدف با تغییرات سطح اطمینان از ۳۵/۰ تا ۹/۰ افزایش و با تغییرات از ۹/۰ تا ۹۹/۰ کاهش مییابند.
جدول ۴-۳: نتایج اولین مسأله نمونه
شکل ۴-۱: اختلاف بین مقدار تابع هدف اول در حداقل سطح رضایتمندی و مقدار بهینه با توجه به سطوح اطمینان مختلف برای اولین مسأله نمونه
به منظور ارزیابی بیشتر، یک مسأله نمونه دیگر با ابعاد ارائه شده در جدول (۴-۴) مورد بررسی قرار میگیرد. در این مسأله نمونه، تعداد متغیرهای صفر و یک، تعداد کل متغیرها و محدودیتها به ترتیب برابر ۵۷۶، ۲۰۶۵ و ۱۶۴۱ است. مقادیر توابع هدف و نتایج نهایی مربوط به این مسأله به وسیله جدولهای (۴-۵) و (۴-۶) ارائه شده اند.
شکل ۴-۲: اختلاف بین مقدار تابع هدف دوم در حداقل سطح رضایتمندی و مقدار بهینه با توجه به سطوح اطمینان مختلف برای اولین مسأله نمونه
جدول ۴-۴: ابعاد دومین مسأله نمونه
همان طور که مشخص است، مقدار حداقل درجه رضایتمندی توابع هدف (λ*) در این مسأله نیز نزدیک به عدد یک بوده و مشاهده می شود که بین مقدار هر یک از توابع هدف و مقدار بهینه مربوطه اختلاف زیادی وجود ندارد.
مشابه اولین مسأله نمونه تولید شده، در این مسأله نمونه نیز با تغییر سطوح اطمینان روند خاصی بر اساس مقدار اختلاف برای هر یک از توابع هدف مشاهده نمی شود (شکلهای (۴-۳) و (۴-۴)). در این مسأله مقدار اختلاف برای دو تابع هدف با تغییرات سطوح اطمینان از ۳۵/۰ تا ۵۰/۰ کاهش و با تغییرات سطوح اطمینان از ۵/۰ تا ۹۹/۰ افزایش مییابند.
جدول ۴-۵: حداقل و بزرگترین مقدار توابع هدف برای دومین مسأله نمونه
جدول ۴-۶: نتایج دومین مسأله نمونه
علاوه بر این، با مشاهده جدول (۴-۶) مشخص است که با افزایش ابعاد مسائل نمونه تولید شده حداکثر زمان مورد نیاز برای حل مدل مسئله اول تقریبا برابر ۶ ساعت و ۳۰ دقیقه است، لذا توسعه یک الگوریتم ابتکاری یا فراابتکاری برای حل این مدل مفید خواهد بود.
شکل ۴-۳: اختلاف بین مقدار تابع هدف اول در حداقل سطح رضایتمندی و مقدار بهینه با توجه به سطوح اطمینان مختلف برای دومین مسأله نمونه
شکل ۴-۴: اختلاف بین مقدار تابع هدف دوم در حداقل سطح رضایتمندی و مقدار بهینه با توجه به سطوح اطمینان مختلف برای دومین مسأله نمونه
۴-۲- نتایج محاسباتی مسأله دوم
در این بخش، چندین نتیجه عددی به منظور ارزیابی عملکرد الگوریتم ترکیبی توسعه داده شده ارائه می شود. الگوریتم ترکیبی توسعه داده شده به زبان برنامهنویسی C# کدنویسی شده و با یک سیستم کامپیوتری با واحد پردازش مرکزی ۲ گیگا هرتز، حافظه اصلی ۲ گیگا بایت و پنتیوم ۴ اجرا می شود. قبل از ارائه نتایج تجربی بدست آمده، نحوه تولید مسائل نمونه و تنظیم پارامترهای الگوریتم شرح داده میشوند.
۴-۲-۱- تولید مسائل نمونه و تنظیم پارامترهای الگوریتم
به دلیل عدم وجود مسائل مشابه به منظور مقایسه عملکرد الگوریتم توسعه داده شده، چندین مسأله نمونه به صورت تصادفی تولید میشوند. این مسائل در دو گروه مسائل با ابعاد کوچک و مسائل با ابعاد بزرگ طبقه بندی شده به طوریکه برای هر گروه سه مسأله با ابعاد مختلف تولید می شود.
ابعاد هر مسأله نمونه به وسیله تعداد تأمینکنندگان، باراندازهای میانی، خرده فروشها، محصولات سفارش داده شده توسط هر خرده فروش، وسایل نقلیه ورودی موجود در مکان هر تأمینکننده و وسایل نقلیه خروجی موجود در هر بارانداز میانی مشخص می شود (جدول (۴-۷)). همچنین به دلیل سادگی، تعداد محصولات سفارش داده شده توسط هر خرده فروش، تعداد وسایل نقلیه ورودی موجود در مکان هر تأمینکننده و تعداد وسایل نقلیه خروجی در هر بارانداز میانی یکسان در نظر گرفته شده اند.
جدول ۴-۷: ابعاد مسائل نمونه تولید شده
<br/ >برای هر یک از شش مسأله نمونه فوق ده مثال تولید می شود. بنابراین در مجموع ۶۰ مسأله نمونه به منظور ارزیابی عملکرد الگوریتم توسعه داده شده مورد بررسی قرار میگیرند.
طول افق برنامه ریزی برای هر یک از مسائل نمونه ای یکسان و برابر ۲۴ ساعت در نظر گرفته
می شود. سایر پارامترهای مورد نیاز بر اساس توزیعهای یکنواخت ارائه شده در جدول (۴-۸) تولید میشوند.
جدول ۴-۸: توزیعهای یکنواخت به منظور تولید پارامترهای مورد نیاز
به منظور تنظیم پارامترهای الگوریتم توسعه داده شده، ترکیبهای مختلف تشکیل شده از مقادیر مختلف برای هر پارامتر مورد بررسی قرار میگیرند. سپس، با در نظر گرفتن کیفیت جوابها و زمان لازم به منظور دستیابی به این جوابها، مقادیر مناسب برای پارامترهای الگوریتم انتخاب میشوند. در این تحقیق پس از تست ترکیبهای مختلف، مقادیر زیر برای پارامترهای الگوریتم انتخاب شده اند: اندازه جمعیت برابر با ۵۰۰، تعداد کل نسلها برابر با ۵۰۰، نرخ عملگر ادغام ۸۵%، نرخ عملگر جهش ۱۵%، نرخ نخبهگرایی ۵۰%، تعداد کروموزومهایی که روش جستجوی محلی بر روی آنها اعمال
می شود برابر با ۱۵ و تعداد حرکتهای تعویض (به منظور بهبود بخشهای سوم و چهارم یک کروموزوم در روش جستجوی محلی) برابر با ۲۰ است.