از آنجایی که در مسأله -میانه، هدف کمینهسازی جابجایی کل است، لذا کمینهسازی در سطح اول مدل قرار گرفته است. در واقع این مدل میخواهد جوابی را پیدا کند که را با شانس بیشینه، بهینه کند.
همانطور که از مدل برمیآید، پارامترهایی که در دو مدل برنامهریزی با محدودیت شانس و برنامهریزی وابسته به شانس از تصمیمگیر گرفته میشوند، در این مدل به صورت متغیر در نظر گرفته شده و توسط مدل، متناسب با هم و به صورت بهینه بدست میآیند.
در بخش بعد، روش حل ارائه شده برای این مدل تشریح میشود.
روش حل
روشی که برای حل مدل (۳-۷) پیشنهاد میشود، ترکیب دو سطح اول و دوم این مدل است. در حقیقت این روش، برداشتی از روش جستجوی شبکهای[۲۹] در برنامهریزی دوسطحی است که از ترکیب خطی دوسطح به عنوان تابع هدف استفاده میکند [۳۳]. در ادامه، روش ترکیب کردن دو سطح، بیان خواهد شد.
مسأله زیر را در نظر بگیرید.
اگر ، در اینصورت فضای جواب در حالتیکه بزرگتر از فضای جواب در حالت است. لذا بدتر از نیست؛ یعنی، با توجه به اینکه مسأله کمینهسازی است، اگر آنگاه . در اینصورت با توجه به نامعادله برقرار است. با توجه به این موضوع، در مسأله فوق، اگر شرط کوچکتر بودن از را برای قرار داده شود، یعنی بجای اینکه تعداد زیادی از ها بررسی شود، هایی بررسی شوند که از کوچکترند (تحدید مجموعه ها)، در جواب مسأله تغییری ایجاد نمیشود؛ چراکه مقدار بهینه ها (یعنی ) از کوچکتر است. همچنین از تصمیمگیر خواسته میشود که سطحی از که بدتر از آن را نمیپذیرد، مشخص کند. این مقدار را ( ) و متناظر با آن نامیده میشود. باز هم از تحدید مجموعه ها استفاده شده و هایی را بررسی میشوند که از بیشتر باشند.
پس کار با ادامه مییابد. از این شرط نتیجه میشود که و . با ترکیب این دو نامساوی و با توجه به اینکه (چون ) نامساوی زیر بدست میآید:
هدف اینست که کاهش یابد، لذا افزایش مییابد.
با توجه به آنچه گفته شد، تابع هدف مدل اصلی به صورت زیر است:
در اینصورت مدل دو سطحی (۳-۷) به مدل یک سطحی زیر تبدیل میشود:
که در آن، تقاضای نقطه ، فاصله نقطه تقاضای از نقطه کاندید استقرار ، تعداد تسهیلاتی که باید مکانیابی شوند، برابر ۱ است اگر تسهیلی در نقطه کاندید استقرار قرار داده شود در غیراینصورت برابر صفر است، برابر ۱ است اگر تسهیل به نقطه تقاضای تخصیص یابد درغیراینصورت برابر صفر است، تعداد نقاط تقاضا، تعداد نقاط کاندید استقرار، قابلیت اطمینان، حداقل سطح قابلیت اطمینان قابل قبول برای تصمیمگیر، حداکثر مقدار (جواب مسأله (۳-۸) به ازای )، و حداقل مقدار (جواب مسأله (۳-۸) به ازای ) است.
با مقدار دادن به میتوان به ترکیب مناسبی از و دست یافت. البته، با درنظر گرفتن ترتیب و اولویت سطوح در مسأله (۳-۷)، باید وزن بیشتر از وزن در تابع هدف مسأله (۳-۱۱) باشد. لذا باید مقدار را بین ۵/۰ و ۱ انتخاب نمود.
قابل ذکر است که در مدل –میانه ترکیبی مورد بحث در این پایاننامه، تقاضای نقاط ( ) به ازای هر یک متغیر ترکیبی در نظر گرفته شده است. فرض کنید مجموعه پشتیبان پارامتر فازی متغیر باشد. لذا برای هر تحقق ، یک متغیر احتمالی است.
برای تایی مرتب تابع عضویت به صورت زیر تعریف میشود:
لذا شانس برقراری شرط با توجه به رابطه (۲-۴) به صورت زیر است:
برای حل مدل (۳-۱۱) از الگوریتم ژنتیک استفاده شده است. در ادامه، الگوریتم ژنتیک ارائه شده جهت حل مدل (۳-۱۱) را بیان شده است.
الگوریتم ژنتیک
در این قسمت به توضیح و تشریح الگوریتم ژنتیک به کار برده شده در این پایاننامه جهت حل مدل (۳-۱۱) پرداخته میشود.
معرفی کروموزومها[۳۰]
کروموزومها در این الگوریتم، نه رمزنگاری[۳۱] میشوند و نه رمزگشایی[۳۲]. بلکه به جای هر ژن[۳۳]، اندیس نقطه کاندید استقرار قرار داده میشود. در واقع، تعداد ژنهای هر کروموزوم برابر است با تعداد نقاط تقاضا به اضافه ۲٫ در ژنهای ابتدایی، شماره نقاطی که تسهیل در آن استقرار مییابد، قرار میگیرد تا مشخص شود که هر نقطه تقاضا به کدام تسهیل تخصیص مییابد. در ژن بعدی، عددی به تصادف قرار میگیرد که نشاندهنده مقدار تابع هدف برای تخصیص فوق الذکر است. و در ژن پایانی، شانس اینکه تخصیص فوق الذکر به مقدار تابع هدف فوق برسد را نشان میدهد. لازم به ذکر است که برای بدست آوردن این شانس، یک الگوریتم ژنتیک دیگر اجرا میشود. برای نمونه فرض کنید تعداد ۷ نقطه تقاضا و ۵ نقطه کاندید استقرار داریم. کروموزم زیر را در نظر بگیرید:
نمونهای از کروموزوم الگوریتم ارائه شده
هفت ژن اول این کروموزوم نشاندهنده جایابی و تخصیص تسهیلات هستند. یعنی باید در نقاط ۱ و ۳ و ۴ تسهیل مستقر شود. سپس تسهیل ۱ به نقاط نقاضای ۲ و ۶ و ۷، تسهیل ۳ به نقاط تقاضای ۴ و ۵، و تسهیل ۴ به نقاط تقاضای ۱ و ۳ تخصیص داده میشود.
دو ژن آخر بیان میکنند که این تخصیص با حداقل شانس ۳/۰ میتواند به مقدار تابع هدف ۷۵۰ دست یابد.
جمعیت اولیه[۳۴]
برای تولید جمعیت اولیه از مقداردهی تصادفی هوشمند به ژنهای اولیه و محاسبه مقدار تابع هدف و شانس آن در دو ژن آخر استفاده میشود. منظور از مقداردهی تصادفی هوشمند اینست که به طورتصادفی محل از نقاط تقاضا انتخاب و تسهیلات در آنجا مستقر میشوند. سپس هر نقطه تقاضا به نزدیکترین تسهیل تخصیص داده میشود. با بهره گرفتن از تولید تصادفی هوشمند، جمعیت اولیه نزدیک به جواب مسأله تولید میشود که باعث تسریع در رسیدن به جواب بهینه مسأله میشود. کد تولید تصادفی هوشمند جمعیت اولیه به صورت زیر است:
function ip = Initial Population (nop, nof)
% nop : number of nodes
% nof : number of facilities
% sof : Set of facilities
sof = generate random nodes for facilities through demand;
for i=1:nop
if i is in sof
ip(i) = i;
else