— -فایل منابع علمی مقاله-منابع تحقیق-291)

بهینه LAP خیرکمینه خیر قطعی کوپر[24]
بهینه MLCP خیر کمینه بله قطعی رولهوالزینگا [29]
ابتکاری LAP خیر بیشینه خیر احتمالی لوگندرانوترل[32]
ابتکاری FLP خیر کمینه خیر احتمالی لووکسوپیترز [33]
ابتکاری LAP خیر کمینه بله احتمالی شرالیوریزو [34]
فرا ابتکاری(الگوریتم ژنتیک) FLP خیر کمینه خیر احتمالی زو [36]
ابتکاری LAP خیر کمینه بله احتمالی زوولیو [37]
شاخه- برش FLP خیر کمینه بله احتمالی لاپورت و همکاران[38]
ابتکاری و فرا ابتکاری (جستجو محلی) TSP خیر کمینه خیر احتمالی بیانچیوکمبل [39]
ابتکاری و حد پایین LRP خیر کمینه بله احتمالی سامبولا و همکاران [40]
ابتکاری FLP بله کمینه بله احتمالی سامبولاوهمکاران [41]
ابتکاری LAP خیر کمینه خیر قطعی کوپر[44]
فرا ابتکاری(الگوریتم ژنتیک) LAP بله کمینه بله احتمالی این تحقیق
* FLP: Facility Location Problem; LAP: Location- allocation Problem; Q-MALP: Queueing Maximal Availability Location Problem; MLCP: Maximal Location Covering Problem; LRP: Location- Routing Problem; TSP: Traveling Salesman Problem; SC: Supply Chain; SPP: Single Product Problem.
جدول(2-SEQ جدول_2. \* ARABIC1). خلاصه ای از ادبیات موضوع
فصل سوم :زمینه های علمی تحقیق3-1- مقدمهبرنامه ریزی تسهیلات که از مباحث مهم در مهندسی صنایع است دو بخش عمده مکان یابی (جانمایی) و طراحی را شامل می شود که مهم ترین بخش طراحی ، استقرار یا جانمایی و بخش های دیگر آن، حمل و نقل و طراحی ساختمان و تاسیسات است. منظور از تسهیلات، هر مجموعه، شامل کارخانه، دانشگاه، بیمارستان و غیره است.
در مکان یابی، ما به بررسی محل قرار گرفتن یک وسیله برای رسیدن به اهداف مورد نظر می پردازیم که برای تعیین محل آن، معیارهای مهمی موثرند، از جمله نزدیکی به جاده های اصلی، بازار مصرف، منابع تامین مواد اولیه، در دسترس بودن نیروی انسانی موردنظر، شرایط محیطی، امکان توسعه، مقررات و قوانین دولتی و غیره.همچنین در طرح استقرار می خواهیم نحو قرار گرفتن اجزای یک وسیله را برای رسیدن به بهترین بهره وری تعیین کنیم. روش های زیادی تاکنون برای حل این گونه مسائل مطرح شده اند که از آن جمله می توان به برنامه ریزی، استفاده از تصمیم گیری چندگانه و غیره اشاره کرد [1].
همان طور که قبلا بدان اشاره کردیم، مراکز صنعتی و کارخانجات برای تعیین مکان احداث کارخانه، استقرار تجهیزات و دپارتمان های خود در کارخانه، استقرار دفاترشان در سطح شهر، تعیین مراکز توزیع محصولات و غیره با چنین مسائلی سر و کار دارند. در واقع، تصمیمات مربوط به مکان یابی و استقرار، نه تنها در مسائل صنعتی، بلکه در مسائل گوناگونی در بخش های دولتی و خصوصی، اعم از صنعتی و غیرصنعتی ظاهر می شود. در بخش دولتی، تعیین مکان مراکز خدماتی، نظیر ایستگاه های پلیس راه، اورژانس، بیمارستان ها ایستگاه های آتش نشانی و غیره نیاز به اتخاذ چنین تصمیماتی دارد. لذا تصمیم گیری در مورد مکان یابی تسهیلات عمدتا از تصمیم گیری های بلند مدت و استراتژیک شرکت های بزرگ خصوصی و عمومی است و هزینه های بالای مربوط به مکان یابی و استقرار و راه اندازی تسهیلات، پروژه های مکان یابی را به سرمایه گذاری های بلندمدت تبدیل کرده است. لذا موفقیت یا شکست مراکز تسهیلاتی در هر کدام از بخش های دولتی و خصوصی، بستگی کامل به مکان های انتخابی برای آنها دارد. بدین ترتیب، اهمیت مساله مکان یابی و استقرار تسهیلات و ضرورت پرداختن بدان بر همگان روشن است [1].
3-2- دسته بندی کلی مسائل برنامه ریزی تسهیلاتمسائل برنامه ریزی تسهیلات به چهار دسته عمده مکان یابی، مسیریابی، تخصیص و طراحی تقسیم می شود. با ترکیب این مولفه ها مسائل مکان یابی- مسیریابی، مکان یابی- تخصیص به دست می آید [1].
تسهیلات تخصیصتسهیلات یابی مکانتسهیلات یابی مسیرتسهیلات طراحیتسهیلات ریزی برنامه23495-10350600 مکان یابی-تخصیص تسهیلات
254008064400 مکان یابی- مسیریابی تسهیلات
تسهیلات جانماییمواد انتقالساختاری طراحیشکل (3- SEQ شکل_3- \* ARABIC1). دسته بندی کلی مسائل برنامه ریزی تسهیلات[1].3-3- دسته بندی مسائل مکان یابی با نگرش سنتیدسته بندی های کلاسیک مسائل مکان یابی عمدتا بر اساس موارد زیر بوده است:
براساس خصوصیات وسایل جدید
مساله مکان یابی تک وسیله/چند وسیله
مساله مکان یابی با وسایل نقطه ای/ ناحیه
براساس خصوصیات وسایل موجود
مساله مکان یابی با وسایل ایستا/پویا
مساله مکان یابی وسایل با مکان قطعی/احتمالی
براساس نوع ارتباط وسایل موجود و جدید
مساله مکان یابی با ارتباطات برون زا/درون زا
مساله مکان یابی با ارتباطات ایستا/پویا
مساله مکان یابی با ارتباطات قطعی/احتمالی
براساس فضای جواب
مساله مکان یابی روی خط/صفحه
مساله مکان یابی گسسته/روی شبکه
مساله مکان یابی با فضای مقید/نامقید
براساس نوع تابع فاصله
مساله مکان یابی با فواصل متعامد/چپیشف
مساله مکان یابی با فواصل اقلیدسی/مجذور اقلیدسی
مساله مکان یابی با سنجه های خاص
بر اساس نوع و تعداد هدف و شاخص انتخاب
مسائل تک هدفه/چندهدفه
مسائل تک شاخصه/چندشاخصه
مسائل میانه (هدف: مینیمم مجموع هزینه ها)/ مرکز(هدف: مینیمم حداکثر هزینه ها)/
پوشش (هدف: حداکثر پوشش تقاضا یا حداقل تعداد وسیله)
براساس زمینه مساله
مساله مکان یابی انبار
مساله مکان یابی نقاط تبادل (هاب)
مساله مکان یابی وسایل ناخوشایند
مساله مکان یابی وسایل گردشی (مسائل مکان یابی-مسیریابی)
مساله مکان یابی وسایل سلسله مراتبی
3-4- دسته بندی مسائل مکان یابی با نگرش نوینمسائل مکان یابی و استقرار را بر مبنای نگرش در مدل سازی و حل در شکل (3-2) دسته بندی شده اند. در این دسته بندی چهار رویکرد عمده نظری و عملی وجود دارد.
-6667627622500
رویکردهای استراتژیک CFL DFL SLF هوش مصنوعی MH NN FL رویکردهای عملی IT EG رویکردهای دیگر EM DM SCM -2047875190500-73025253900یادداشت:
SLF : مکان یابی تسهیلات استراتژیک
DFL : مکان یابی تسهیلات پویا
CFL : مکان یابی تسهیلات رقابتی
FL : منطق فازی
NN : شبکه های عصبی
MH : الگوریتم های فراابتکاری
EG : جغرافیای اقتصادی
IT : فناوری اصلاعات
SCM : مدیریت زنجیره تامین
DM : داده کاوی
EM : سنجش بهره وری
شکل (3- SEQ شکل_3- \* ARABIC2). دسته بندی نوین مسائل مکان یابی [1].3-5- مسائل مکان یابی-تخصیصمسئله مکان یابی- تخصیص به دنبال مکان یابی مجموعه ای از تسهیلات جدید است بطوریکه هزینه ی حمل و نقل از تسهیلات به مشتریان مینیمم گردد و تعداد بهینه ای از تسهیلات باید در نقاط کاندید به منظور تامین تقاضای مشتریان احداث شوند.
این مساله در بسیاری از زمینه های عملی جاییکه تسهیلات خدمات یکسانی را ارائه می کنند، بکار گرفته می شود مانند مکان یابی انبارها، مراکز توزیع، مراکز ارتباطات و تسهیلات تولید [5].
3-5-1- طبقه بندی مساله مکان یابی- تخصیصاجزای اصلی مسائل مکان یابی- تخصیص شامل تسهیلات، مکان ها و مشتریان می باشند. مشخصات و ویژگی های این اجزای اصلی در این بخش به همراه انواع مدل های مکان یابی- تخصیص به تفضیل توضیح داده خواهند شد.
3-5-1-1- طبقه بندی تسهیلات
تسهیلات معمولا براساس تعداد، نوع و یا هزینه هایشان از دیگر چیزها متمایز می شوند. دیگر خواص مرتبط با تسهیلات شامل سود، ظرفیت، دامنه جذب (ناحیه ای که مشتریان به تسهیل تخصیص می یابند) و نوع سرویس ارائه شده توسط هر یک از این تسهیلات می باشد.
یکی از این خواص متمایزکننده، تعداد تسهیلات جدید است. ساده ترین مورد، مسئله مکان یابی تک وسیله ای است، جاییکه تنها مکان یک تسهیل جدید باید مشخص گردد. مساله بعدی، مساله مکان یابی چند وسیله ای است که در این نوع مسائل، هدف تعیین همزمان مکان بیش از یک تسهیل جدید است.
نوع هر تسهیل، یکی دیگر از خواص متمایزکننده انواع مسائل می باشد. در ساده ترین حالت، همه تسهیلات برحسب اندازه و نوع سرویسی که ارائه می کنند، یکسان درنظر گرفته می شوند. دربعضی مورد، ما نیازمند به مکان یابی تسهیلاتی هستیم که از لحاظ نوع ارائه سرویس با هم متفاوت هستند مانند بیمارستان ها و واحدهای مراقبت های بهداشتی کوچکتر. مدل های مکان یابی- تخصیص برحسب اینکه تسهیلات بتوانند تنها یک نوع سرویس ارائه کنند یا بیشتر، به انواع تک سرویسه و یا چندسرویسه تقسیم می شوند.
همچنین باید درنظر داشت که تسهیلات می توانند تقاضاهای نامحدود را تامین کنند و یا اینکه ظرفیت تولید و تامین آنها محدود باشد. در این حالت مسائل مکان یابی- تخصیص به دو دسته ی مسائل با ظرفیت نامحدود و مسائل با ظرفیت محدود تقسیم می شوند[5].
3-5-1-2- طبقه بندی فضای فیزیکی یا مکان ها
مجموعه مکان های مطلوب به سه شکل قابل نمایش هستند: فضاهای گسسته، پیوسته، شبکه ای.
مدل های فضای پیوسته اغلب اوقات به مدل های مکان-ساختارجاع داده می شوند. چرا که این مدلها در پی ایجاد مکان های مناسب برای تسهیلات در فضای پیوسته هستند.
از آنجاییکه در مدل های فضای گسستهیک شناخت قبلی از مکان های کاندید داریم، این مدل مسائل به مدل های مکان-انتخاب ارجاع داده می شوند.
مدل شبکه ای فضا، سومین نوع مسائل مکان یابی است که برحسب مکان ها قابل شناسایی است. مسائلی که بروی شبکه ها طراحی می شوند ، می توانند طبق لینک های شبکه که بصورت یک مجموعه پیوسته از نقاط کاندید یا فقط گره های مطلوب برای احداث تسهیلات جدید درنظر گرفته شده اند، پیوسته یا گسسته باشند[5].
3-5-1-3- طبقه بندی تقاضا
تقاضاهای مشتریان قطعی یا احتمالی هستند که در ادامه بیشتر در مورد آنها بحث خواهیم کرد.
3-5-2- انواع مدل های مکان یابی- تخصیصمدل های مسئله مکان یابی- تخصیص به دو بخش اصلی تبدیل می شوند: مدل های عمومی که در بخش 3-5-2-1 مورد بحث قرار می گیرند و مدل های توسعه یافته که در بخش های 3-5-2-2 ، 3-5-2-3 و 3-5-2-4 تفسیر می شوند. برای مدل سازی این مسائل،تحقیق در عملیات به منظور مینیمم کردن هزینه های کل مورد استفاده قرار گرفته است. مدل مکان یابی- تخصیص دارای چندین متغیر به شکل زیر می باشد:
تعداد تسهیلات
مکان تسهیلات
تعداد تخصیصات مشتریان به تسهیلات
ظرفیت هر تسهیل
3-5-2-1- مدل عمومی مکان یابی- تخصیص
اولین بار کوپر [19]در سال 1963 یک مدل عمومی مکان یابی- تخصیص را با دو تسهیل جدید و هفت نقطه تقاضای معرفی و حل نمود.
3-5-2-1-1 فرضیات مدل
فرضیات مسئله بصورت زیر است(همچنین این مساله به عنوان مسئله چندمنبع ای وبر نیز مشهور است):
فضای جواب پیوسته است.
تقاضای هر مشتری می تواند توسط چندین تسهیل بدون درنظر گرفتن هزینه احداث تسهیل جدید تامین گردد.
ظرفیت تسهیلات نامحدود است.
پارامترهای مساله به منظور تامین تقاضاها قطعی هستند.
هیچ رابطه ای بین تسهیلات جدید وجود ندارد[5].
3-5-2-1-2- ورودی ها و خروجی های (متغیرهای تصمیم) مدل
ورودی های مدل عبارتند از :
nتعداد مشتریان (تسهیلات موجود)
rjتقاضاهای مشتریان j=1,…,najمختصات های مشتریان j=1,…,nمتغیرهای تصمیم مدل عبارتند از :
mتعداد تسهیلات
xiمختصات تسهیلات جدید i=1,…,mwijتعداد تقاضای تامین شده مشتری jام بوسیله تسهیل iام
d(xi,aj)فاصله بین مشتری jام و تسهیل جدید iام
3-5-2-1-3- تابع هدف و محدودیت های مدل عمومی
تابع هدف این مدل و محدودیت های مرتبط با آن عبارتند از:
Min ϕ =i=1mj=1nwijd(xi,aj)(1.3)
Subject toi=1mwij=rjj=1,…,n(2.3)
wij≥0i=1,…,mj=1,…,n(3.3)
3-5-2-2- مدل مکان یابی- تخصیص که هر مشتری فقط توسط یک تسهیل تامین می گردند
در این مدل دومین فرض از فرضیات مدل عمومی مکان یابی- تخصیص تغییر می کند، بدین صورت که هر مشتری فقط می تواند از یک تسهیل استفاده نماید. دیگر فرضیات این مدل شبیه به مدل عمومی هستند. ورودی های این مدل همان ورودی های مدل عمومی هستند. در این مدل، متغیرهای تصمیم، متغیرهای تصمیم مدل عمومی غیر از متغیر wij و باانضمام متغیر زیر هستند [5] :
Zij=1 اگر مشتری j ام به تسهیل iام تخصیص یابد و در غیر اینصورت 0.
3-5-2-2-1- تابع هدف و محدودیت های این مدل
Min ϕ =i=1mj=1nZijrjd(xi,aj)(4.3)
Subject toi=1mzij=1j=1,…,n(5.3)
Zijϵ{0,1}i=1,…,mj=1,…,n(6.3)
3-5-2-3- مدل مکان یابی- تخصیص با هزینه احداث تسهیل
در این مدل سومین فرض از فرضیات مدل عمومی مکان یابی- تخصیص تغییر می کند، بدین صورت که به ازای احداث هر تسهیل هزینه ای معین به هزینه های کل اضافه می گردد. دیگر فرضیات این مدل با مدل عمومی یکسان هستند. ورودی های این مدل همان ورودی های مدل عمومی هستند باانضمام پارامتر f(xi). همچنین متغیرهای تصمیم این مدل، متغیرهای تصمیم مدل عمومیهستند.
f(xi)هزینه احداث تسهیلi ام.
3-5-2-3-1- تابع هدف و محدودیت های این مدل
تفاوت بین تابع هدف این مدل و مدل عمومی مکان یابی- تخصیص بصورت زیر می باشد:
عبارت (1.3) از تابع هدف حذف شده و عبارت زیر به آن اضافه می گردد :
(7.3) i=1mf(xi)محدودیت های این مدل کاملا با مدل عمومی مکان یابی- تخصیص یکسان هستند.
اگر فرض کنیم که هزینه احداث تسهیلات مستقل از مکان تسهیلات باشد و مقدار mنیز مشخص باشد و با توجه به این که اکنون جمع هزینه های احداث تسهیلات ثابت است و می تواند از تابع هدف مساله حذف گردد، مساله به یک مساله چند منبع ای وبرکه از جمله مسائل مشهور است، ساده سازی می گردد[5].
3-5-2-4- مدل مکان یابی- تخصیص ظرفیت دهی شده با تقاضاهای احتمالی
این مدل توسط زو و لیو[32] در سال 2003 پیشنهاد شد.
3-5-2-4-1- فرضیات مدل
در این مدل چهارمین و پنجمین فرض از فرضیات مدل عمومی مکان یابی- تخصیص تغییر می کند، بدین صورت که ظرفیت تسهیلات محدود بوده و تقاضاهای مشتریان احتمالی است. دیگر فرضیات این مدل با فرضیات مدل عمومی یکسان می باشد.
3-5-2-4-2- ورودی ها و خروجی های (متغیرهای تصمیم) مدل
ورودی های این مدل همان ورودی های مدل عمومی هستند باانضمام پارامترهای زیر:
ξj: تقاضای احتمالی مشتری j ام.
ξj(ω): تحققی از بردار احتمالی jام.
Si: ظرفیت تسهیل i ام.
همچنین متغیرهای تصمیم این مدل، همان متغیرهای تصمیم مدل عمومیهستند. در مدل مکان یابی- تخصیص قطعی، تخصیص w ، متغیر تصمیمی است که در تمام دوره های زمانی ثابت است. در صوریتکه در یک مساله مکان یابی- تخصیص احتمالی، تصمیم wمتغیر است و در هر دوره زمانی بعد از آنکه تقاضاهای مشتریان مشخص گردید، شکل می گیرد.
3-5-2-4-3- تابع هدف و محدودیت های مدل
تابع هدف این مدل شبیه به تابع هدف مدل عمومی مکان یابی- تخصیص است.
Min ϕ =i=1mj=1nwijd(xi,aj)(8.3)
Subject toi=1mwij=ξj(ω)j=1,…,n(9.3)
i=1mwij≤S(10.3)
wij≥0i=1,…,mj=1,…,n(11.3)
اگر نقاط شدنی برای w بدست نیاید، بنابراین تامین کردن بعضی از مشتریان امکان پذیر نخواهد شد و سمت راست عبارت (8.3) بی معنی خواهد شد و بعنوان هزینه پنالتی تابع هدف زیر جایگزین می شود [5] :
Min ϕ =i=1mj=1nξj(ω)d(xi,aj)(12.3)
3-6- تشریح الگوریتم ژنتیکالگوریتم های ژنتیک تکنیک نسبتا جدید هستند که، از آنها برای حل مسائل مختلف استفاده شده است. دو ویزگی اصلی این تکنیک یکی الهام گیری آن از پدیده های طبیعی خلقت و دیگری قابلیت پردازش موازی می باشد. الگوریتم های ژنتیک با الهام از فرایند تکامل طبیعی به عنوان یک روش جستجوی هوشمند در حل مسائل بهینه سازی کاربرد گسترده ای یافته است. الگوریتم ژنتیک برگرفته از الگوریتم تکاملی است که اولین بار توسط جان هالند [33] در دانشگاه میشیگان پیشنهاد شد و استراتژی ها و برنامه ریزی های تکاملی که توسط رچنبرگ و چیفل و فوگوگل و کوزا ایجاد شدند، از جمله روش های محاسبه تکاملی هستند.
روش های بهینه سازی الهام گرفته از طبیعت با روش های متعارف بهینه سازی تفاوت مهمی دارند. در روش های متعارف هر جواب کاندیدای جدید در صورتی به عنوان جواب جدید انتخاب می شود که مقدار تابع هدف را بهبود بخشد ولی در الگوریتم های الهام گرفته از طبیعت به تمام جواب های کاندیدای جدید شانس انتخاب داده می شود. الگوریتم های ژنتیک، تکنیک های جستجوی تصادفی هستند که بر اساس انتخاب طبیعی و نسل شناسی طبیعی کار می کنند. الگوریتم ژنتیک روشی مستقل از دامنه مساله است و به سرعت فضای جستجو را برای نقاطی با تابع صلاحیت بهتر، جستجو می کند.
3-6-1- مفاهیم کلیدی الگوریتم ژنتیکبا نگاهی به آنچه که تاکنون مطرح شده مشخص است که در تبیین الگوریتم ژنتیک مباحث کلیدی ذیل باید مورد بررسی قرار گیرند. بنابراین در ادامه این مباحث بررسی خواهند شد:
تعریف یک سیستم کدینگ
ایجاد جمعیت اولیه
تعریف عملیات ژنتیک
تابع برازش
استراتژی برخورد با محدودیت ها
3-6-1-1- کدینگ
اولین گام در بکارگیری و پیاده سازی یک الگوریتم ژنتیک نمایش جوابهای مساله بصورت یک کروموزوم است. در حقیقت این عمل یک مفهوم کلیدی در الگوریتم های ژنتیک می باشد که با استفاده از عمل کدینگ ما می توانیم مساله را به زبان برنامه نویسی تبدیل نماییم.
3-6-1-2- ایجاد جمعیت اولیه
اولین مرحله بعد از تعیین تکنیکی که برای تبدیل هر جواب به یک کروموزوم بکار می رود، ایجاد یک جمعیت اولیه از کروموزوم هاست. در این مرحله جواب اولیه معمولا بصورت تصادفی تولید می شود. البته در بعضی موارد با توجه به نوع مساله و برای بالا بردن سرعت همگرایی الگوریتم از روش های ابتکاری نیز استفاده گردیده است.
3-6-1-3- عملگرهای الگوریتم های ژنتیک
عملیات ژنتیک فرآیند انتقال موروثی ژن ها را برای ایجاد اولاد جدید در هر نسل تقلید می کنند. یک بخش مهم در الگوریتم ژنتیک ایجاد کروموزوم های جدید موسوم به اولاد از طریق بعضی کروموزوم های قدیم موسوم به والدین است. این فرآیند مهم توسط عملیات ژنتیک صورت می گیرد. به طور کلی این عملیات توسط دو عملگر عمده انجام می شود. عملگر جهشی و عملگر تقاطعی. اما عملا عملگرها بر حسب نوع مساله تعریف شده و کاملا به توانایی تحلیل گر وابسته بوده و تجربی می باشند. کارایی این عملگرها در رسیدن به جواب بهنه در مسائل مختلف متفاوت است. بعضی از عملگرها فقط یک کروموزوم را در نظر گرفته و بر اساس اطلاعات آن، کروموزوم ایجاد می کنند اما بعضی دیگر بر روی چند کروموزوم یا حتی کلیه کروموزوم های جمعیت قبل عملیات انجام می دهند.
3-6-1-3-1- عملگرهای جهشی
عملگرهایی که یک یا چند ژن از یک کروموزوم را انتخاب و مقادیر آنها را تغییر می دهند. در این عملگرها یک یا چند محل از یک رشته کاراکتری با طول خاص در نظر گرفته شده و مقادیر کاراکترها در آن محل ها تغییر می یابند. مواردی که در این نوع مهم است عبارتند از:
تعداد محل هایی که قرار است تغییر یابند،
نحوه انتخاب محل ها،
نحوه عملیات تغییر،
با مشخص شدن موارد فوق یک عملگر خاص ایجاد می شود که به آن عملگر جهشی گفته می شود. در این نوع عملگرها از اطلاعات یک جواب استفاده کرده و جواب دیگری ایجاد می شود. این تغییر ممکن است کم یا زیاد بوده که به همان میزان از اطلاعات کم یا زیاد استفاده می شود. به عبارت دیگر هر چه تغییرات زیادتر باشد جواب حاصله تصادفی تر خواهد بود و این تصادفی بودن برای ورود مواد ژنتیکی جدید به داخل جمعیت مفید است.
وقتی که جمعیت به سمت جوابی خاص همگرا می شود، احتمال جهش باید زیاد شده تا از این عمل جلوگیری نماید و بالعکس وقتی جمعیت دارای جواب های غیر یکسان است باید احتمال جهش کم شود.
3-6-1-3-2- عملگرهای تقاطعی
عملگرهایی که یک یا چند نقطه از دو یا چند جواب را انتخاب و مقادیر آنها را تعویض می کنند. این عملگرها یک جواب را درنظر گرفته و محل هایی از جواب را با جواب های دیگر معاوضه کرده و جواب های جدید را بوجود می آورند. به این نوع عملگرها، عملگرهایتقاطعی گفته می شود.
عملگر تقاطعی در یک لحظه بر روی دو کروموزوم اعمال شده و دو نوزاد به وسیله ترکیب ساختار دو کروموزوم ایجاد می گردد. یک مفهوم مهم که در ارتباط با این عملگر مطرح است نرخ تقاطعی می باشد.
3-6-1-3-3- مکانیسم نمونه گیری
مکانیسمنمونهگیری به چگونگی انتخاب کروموزوم ها از فضای نمونه گیری مربوط می شود و یکی از رویکردهای آن نمونه گیری تصادفی است:
دو نمونه گیری تصادفی که اکثرا از آنها استفاده می شود عبارتند از: انتخاب چرخه رولت و انتخاب کلی تصادفی. انتخاب چرخه رولت که اولین بار توسط هالند پیشنهاد شد یکی از مناسب ترین انتخاب های تصادفی بوده که ایده آن احتمال انتخاب می باشد. احتمال انتخاب متناظر با هر کروموزوم، براساس برازندگی آن محاسبه می شود بطوریکه اگر fk مقدار برازندگی کروموزوم k ام باشد، احتمال بقای متناظر با آن کروموزوم عبارت است از:
(13.3) pk=fki=0nfi,
بطوریکه n اندازه جمعیت هر نسل می باشد. حال کروموزوم ها را براساس pk مرتب کرده و qk که همان مقادیر تجمعی pk می باشد به صورت زیر بدست می آید:
(14.3) qk=j=0kpj,
در روش انتخاب چرخه رولت بدین صورت عمل می شود که برای انتخاب هر کروموزوم ابتدا یک عدد تصادفی بین صفر و یک تولید شده و سپس عدد مذکور در هر بازه ای که قرار گرفت کروموزوم متناظر با آن انتخاب می شود. البته روش پیاده کردن چرخه رولت بدین شکل است که یک دایره را درنظر گرفته و آن را به تعداد کروموزوم ها طوری تقسیم می کنیم که هر بخش متناظر با مقدار برازندگی کروموزوم مربوطه باشد. حال چرخ را چرخانده و هر کجا که چرخ متوقف شد به شاخص چرخ نگاه کرده، کروموزوم مربوط به آن بخش انتخاب می گردد.
3-6-1-4- تابع برازش
همانطور که دیده شد در فرایند انتخاب بارها از عبارت کروموزوم مناسب تر صحبت به بیان می آید. بدیهی است که برای تشخیص کروموزوم مناسب تر باید یک شاخص جهت ارزیابی کروموزوم ها وجود داشته باشد.
در مورد مسائل بهینه سازی توابع، معمولا این شاخص همان مقدار تابع هدف مساله می باشد، یعنی هر کروموزوم تبدیل به جواب متناظر شده و در تابع هدف قرار می گیرد، آنگاه مقدار تابع هدف برای هر جوابی که بهتر باشد کروموزوم متناظر با آن جواب مناسبب تر خواهد بود. اما در مورد بعضی مسائل که پیچیده تر هستند باید اقدام به تعریف این تابع برازش نمود.
3-6-1-5- استراتژی برخورد با محدودیت ها
بحث دیگری که در اجرای الگوریتم ژنتیک وجود دارد، چگونگی برخورد با محدودیت های مساله است زیرا عملگرهای ژنتیک مورد استفاده در الگوریتم باعث تولید کروموزوم های غیرموجه می شود. چند تکنیک معمول جهت مواجهه با محدودیت وجود دارد که در ادامه به چندتا از آنها اشاره می شود.
3-6-1-5-1- استراتژی اصلاح عملگرها
یک روش برای جلوگیری از تولید کروموزوم غیرموجه این است که عملگر ژنتیکی طوری تعریف گردد که پس از عمل بر روی کروموزوم ها، کروموزوم تولید شده نیز موجه باشد. در این حالت یکسری مشکل ها وجود دارند. مثلا پیدا کردن عملگری که دارای شرایط فوق باشد بسیار دشوار بوده و از مساله ای به مساله دیگر متفاوت می باشد.
3-6-1-5-2- استراتژی ردی
در این روش پس از تولید هر کروموزوم آن را از نظر موجه بودن تست کرده و در صورت غیرموجه بودن حذف می گردد این روش بسیار ساده و کارا می باشد.
3-6-1-5-3- استراتژی اصلاحی
در این روش به جای اینکه کروموزوم غیرموجه حذف گردد تبدیل به یک کروموزوم موجه می گردد. این روش نیز مانند روش اول به مساله وابسته بوده و یافتن فرآیند اصلاح گاهی بسیار پیچیده می باشد.
3-6-1-5-4- استراتژی جریمه ای
در این روش بر خلاف سه روش قبل که از ورود جواب های غیر موجه جلوگیری می کردند، جواب های غیرموجه با احتمال کم امکان حضور می یابند. سه روش فوق دارای این اشکال بودند که به هیچ نقطه ای بیرون از فضای موجه توجه نمی کردند، اما در بعضی از مسائل بهینه سازی، جواب های غیرموجه درصد زیادی از جمعیت را اشغال می کنند. در چنین شرایطی اگر جستجو فقط در ناحیه موجه انجام گیرد شاید یافتن جواب موجه خیلی وقت گیر و مشکل باشد. استراتژی جریمه ای از متداولترین تکنیک های مورد استفاده برای پذیرش با جواب های غیرموجه می باشد که در آن از ابتدا محدودیت های مساله درنظر گرفته نمی شوند، سپس برای هر تخلف از محدودیت ها، یک جریمه اختصاص داده می شود که این جریمه در تابع هدف قرار می گیرد.
3-6-2- ساختار کلی الگوریتم ژنتیکساختار کلی یک الگوریتم ژنتیک را می توان به صورت ذیل تصور کرد.
ابتدا پیش از هر چیز باید مکانیسمی برای تبدیل هر جواب مساله به یک کروموزوم تعریف کرد. پس از آن یک مجموعه از کروموزوم ها که در حقیقت مجموعه ای از جواب های مساله هستند به عنوان یک جمعیت آغازینتهیه می گردند. این مجموعه که اندازه آن دلخواه است و توسط کاربر تعریف می شود، اغلب به صورت تصادفی ایجاد می گردد.
بعد از این مرحله باید با بکارگیری عملیات ژنتیک اقدام به ایجاد کروموزوم های جدید موسوم به نوزاد نمود. این عملیات به دو گونه عمده تقاطعی و جهشی تقسیم می شوند. همچنین برای گزینش کروموزوم هایی که باید نقش والدین را بازی کنند دو مفهوم نرخ تقاطعی و نرخ جهشی کاربرد فراوان دارند که این دو نیز پیش از شروع الگوریتم توسط کاربر تعیین می شوند.
بعد از تولید یک سری کروموزوم جدید یا اولاد باید با استفاده از عمل تحول اقدام به انتخاب برازنده- ترین کروموزوم ها نمود. این فرآیند که در فرآیند انتخاب نمود می یابد، گلچین کردن کروموزوم های برازنده در میان والدین و اولاد است، به طوریکه تعداد کروموزوم های منتخب برابر با اندازه جمعیت اولیه باشد. فرآیند انتخابی مبتنی بر مقدار برازندگی هر رشته است. در حقیقت فرآیند ارزیابی محوری ترین بحث در فرآیند انتخاب است.
تا بدین مرحله یک تکرار یا یک نسل از الگوریتم طی شده است. الگوریتم پس از طی چندین نسل به تدریج به سمت جواب بهینه همگرا می شود. شرط توقف مساله نیز طی کردن تعداد معینی تکرار است که پیش از آغاز الگوریتم توسط کاربر تعیین می شود.ساختار کلی یک الگوریتم ژنتیک را بصورت ذیل بیان شده است:
روند الگوریتم ژنتیک
Step 1: Set t:=0
Step 2: Generate initial population, p(t)
Step 3: Evaluate p(t) to create fitness values
Step 4: While (Not termination condition) do:
Recombine p(t) to yield c(t), selecting from p(t) according to
the fitness values.
Evaluate c(t)
Generate p(t+1) from p(t) and c(t)
Set t:=t+1
End.
Step 5:Stop.
فصل چهارم : ارائه مدل ریاضی و الگوریتم پیشنهادی4-1- مقدمهمعمولا برای ساده سازی و نمادگذاری، از طبقه بندی pos 1/pos 2/pos 3/pos 4/pos 5 در مسائل مکان یابی همانگونه که هاماخر[34] و هاماخر و نیکل [35]، معرفی کرده اند، استفاده می شود. در این طرح طبقه بندی، pos 1 ، تعداد (یا شکل) تسهیلات جدید را مشخص می سازد. در حالتی که می خواهیم برای N≥1 ، مکان نقاط جدید (x1,…,xN∈Rn، را بیابیم، این مکان، شامل عدد صحیح مثبت می باشد. در pos 2، نوع فضای تصمیم مساله مکان یابی را نشان می دهیم، یعنی،Rn برای مسائل n- بعدی پیوسته، یا p (یاR2 )برای مسائل بر روی سطح. علاوه براین برای شناسایی مسائل مکان یابی شبکه و مسائل مکان یابی گسسته در این مکان بترتیب از نماد Gو D ، استفاده می شود. در این مدل طبقه بندی pos 3 ، برای اختصاص ویژگی های خاص از مساله مکان یابی مفروض می باشد. برای نمونه این مکان، می تواند برای تاکید بر روی تخصیص تسهیلات موجود به تسهیلات جدید در محیط پیوسته باشد که توسط نماد alloc ، نشان داده شده است. همچنین از نماد cap ، برای نشان دادن محدودیت های ظرفیت تسهیلات در محیط گسسته بکار گرفته می شود. در محیط های گسسته، pos 4، شامل هر گونه اطلاعات و محدودیت هایی راجع به هزینه Cij، می باشد. همچنین در محیط های پیوسته این مکان برای نشان دادن هر گونه اطلاعاتی راجع به تابع فاصله می باشد، برای مثال l1 نشان دهنده فاصله متعامد (منهتن یا پله ای)، l2 نشان دهنده فاصله اقلیدسی است. برای مسائل مکان یابی شبکه، این posبرای مشخص کردن فواصل در شبکه می باشد، خواه فواصل فقط مابین گره های شبکه dG(V,V) باشد، و خواه، محاسبه فاصله مابین هر نقطه در گراف dG(V,E)باشد، مورد استفاده قرار می گیرد. در این طبقه بندی pos 5 ، نشان دهنده تابع هدف مساله می باشد. برای نمونه اگر یک مسئله وبر یا میانه مدنظر باشد، از نماد Σ در این مکان استفاده می شود. مسائل مرکز با نماد maxو مسائل وبر ترتیبی توسط Σord نشان داده می شوند. همچنین مسائل مکان یابی رقابتی با نماد Σcomp و تابع هدف مسائل تخصیص درجه دو با نماد QAP نشان داده می شوند. اگر فرض خاصی در هر کدام از مکان ها مدنظر قرار نگیرد، آنگاه این مکان را با نماد یک گلوله (".")، نشان می دهند.


خلاصه مبحث فوق این است که، مساله مکان یابی- تخصیص ظرفیت بندی شده با تقاضاهای برنولی در فضای گسسته طبق این دسته بندی از نوعN/D/cap/Bernoulli –demand/●می باشد.
4-2- ساختار مسالهفرض کنید i=1,2,…,I ، یک مجموعه از اندیس های مکان های کاندید برای احداث تسهیلات و j=1,2,…,J ، یک مجموعه از اندیس های مشتریان موجود باشند. در بسیاری از مسائل، درخواست تقاضای مشتریان به وسیله "کمیت"آن تقاضاها مشخص می گردد بدین صورت که مقدار این تقاضاها در واقع مقداری از ظرفیت های تسهیلات هستند که باید استفاده شوند تا این درخواست های تقاضای مشتریان تامین گردند. در این تحقیق، هر درخواست تقاضا یک واحد محسوب می شود، بدین معنی که هر درخواست تقاضا یک واحد از ظرفیت تسهیل مربوطه را مورد استفاده قرار می دهد. درخواست تقاضای هر مشتری به وسیله ی متغیر تصادفی صفر و یک θj، نشان داده می شود بطوریکه اگر مشتری j ام تقاضا داشته باشد، این متغیر مقدار یک و در غیر اینصورت مقدار صفر می گیرد. از اینرو، در این تحقیق، این امکان پذیر است که تعدادی از مشتریان درخواست تقاضا داشته و تعدادی نداشته باشند.از آنجاییکه درخواست های تقاضای مشتریان از یک تابع توزیع احتمالی پیروی می کند، بنابراین متغیر تصادفی θj به شکل ذیل بیان می گردد:
θj=1,pj,0,1-pj,∀j∈J,جاییکه پارامتر pj احتمال درخواست تقاضای مشتری j ام را نمایان می سازد. در این تحقیق فرض شده است که متغیر θj دارای تابع توزیع برنولی می باشد، بنابراین تابع احتمال θj می تواند به شکل ذیل نوشته شود:
fθj,pj=pjθj(1-pj)1-θj,∀j∈J,این بدین معنی است که هر مشتری با احتمال pj دارای تقاضا و با احتمال 1-pjتقاضا ندارد. نمادگذاری های بکار رفته در این مطالعه در ذیل گرآوری شده اند:
fiهزینه ثابت برای احداث تسهیل در مکان کاندیدi ام.
liحداقل تعداد مشتریانی که باید به تسهیل i ام تخصیص یابد.
kiحداکثر تعداد مشتریانی که می توانند از تسهیل i ام سرویس بگیرند.
uiحداکثر تعداد مشتریانی که می توانند از منبع فرعی تسهیل i ام، سرویس بگیرند.
dijهزینه تخصیص مشتری j ام به تسهیل i ام.
cijهزینه سرویس مشتری j ام از تسهیل i ام.
αiهزینه تامین تقاضای برون سپاری شده ی تسهیل iام به وسیله منبع فرعی این تسهیل.
βii'هزینه تامین تقاضای برون سپاری شده ی تسهیل iام به وسیله یک تسهیلدیگر(i')، i'∈I\i.
علاوه براین ما فرض کردیم که وقتی یک تسهیلی احداث می شود، حداقل li مشتری باید به آن تخصیص یابند. همچنین ماki را به عنوان حد بالای تعداد مشتریانی می توانند از تسهیل i ام سرویس بگیرند و uiرا به عنوان حد بالای تعداد مشتریانی می توانند از منبع فرعی تسهیل i ام سرویس بگیرند، در نظر می گیریم. در ادامه این تحقیق، هر مشتری که درخواست تقاضا دارد را "مشتری تقاضا" می نامیم.همچنین ما درنظر گرفتیم که هر تسهیل دارای ظرفیت محدود می باشد و یک منبع فرعی که آن هم دارای محدویت ظرفیت است نیز به آن اختصاص یافته است. توجه داشته باشید که، محدودیت ظرفیت هر دوی تسهیلات و منابع فرعی نشان- دهنده حداکثر تعداد مشتریانی است که می توانند از این تسهیلات و منابع فرعی سرویس بگیرند و تاثیری بر روی تعداد مشتریانی که می توانند به هر تسهیل تخصیص یابند، ندارد.از اینرو در مدل ما، این امکان پذیر است که، تعداد مشتریانی که به یک تسهیل تخصیص می یابند از ظرفیت این تسهیل بیشتر باشد.
بنابراین، به منظور تامین این مشتریان تقاضای مازاد بر ظرفیت، ما به دیگر تسهیلات و یا منابع فرعیشان مراجعه می کنیم که این فرآیند" برون سپاری" نامیده می شود. همچنین، این مشتریان تقاضای مازاد "تقاضاهای برون سپاری شده" نامیده می شوند.اجازه دهید که Ωiنشان دهنده مجموعه مشتریانی که به تسهیل iام تخصیص یافته اند و φi نشان دهنده تعداد مشتریان تقاضایی که به تسهیل i ام تخصیص یافته اند، باشند (i.e.φi=jϵΩiθj).اگر در میان مشتریانی که به تسهیل iام تخصیص یافته اند، تعداد مشتریان تقاضا از حد بالای ki تجاوز نکند، بنابراین همه آن مشتریان تقاضا از تسهیل مربوطه سرویس می گیرند. درغیرانصورت، اگر مقدار φi از حد بالای ki تجاوز کند، به منظور تامین این اختلاف ما به خطی و مشی برون سپاری مراجعه می کنیم.در اینجا برون سپاری می تواند به چندین روش انجام پذیرد. می دانیم که هر تسهیل i،iϵI ، دارای یک منبع فرعی با حد بالای ui می باشد. ایده نوین تحقیق ما این است هر تسهیل دارای یک منبع فرعی با محدودیت ظرفیت می باشد. همچنین، هر تسهیل می تواند به دیگر تسهیلات و یا منابع فرعیشان به منظور تامین تقاضاهای برون سپاری شده، مراجعه کند. اگر ki<φi≤ ki+ ui، تسهیل i ام در ابتدا به منظور تامین این تقاضاهای برون سپاری شده می تواند از ظرفیت منبع فرعی متناظرش استفاده کند.اگر φi>ki+ui(به عبارت دیگر وقتی تعداد مشتریان تقاضای تسهیل i ام بیشتر از جمع ظرفیت این تسهیل و ظرفیت منبع فرعی اش باشد)،تسهیل i ام در ابتدا باید به دیگر تسهیلاتی که دارای ظرفیت اضافه هستند (به عبارت دیگر وقتی φi'< ki', i'ϵI\i) مراجعه نماید. حال اگر هیچ تسهیلی وجود نداشته باشد که دارای ظرفیت اضافه باشد (به عبارت دیگر وقتی φi'≥ki', i'ϵI\i)، تسهیل مورد نظر می تواند به منابع فرعی آنها مراجعه کند. هر کدام از این فرآیندهای برون سپاری دارای هزینه ای خاص می باشند که در صورت وقوع به تابع مجموع هزینه ها اضافه می گردد. دانستن این نکته حائز اهمیت است که برای هر منبع فرعی، سرویس دادن به تسهیل مربوطش در اولویت قرار دارد. این بدین معناست که هر منبع فرعی در ابتدا به تسهیل مربوطش سرویس داده و در صورت اضافه داشتن ظرفیت می تواند آنها را در اختیار دیگر تسهیلات، در صورت نیاز، قرار دهد.
به منظور فرموله کردن برنامه ریزی ریاضی این مدل، مجموعه ای از متغیر های لازم بصورت ذیل در نظر گرفته شده اند:
.گردد احداث کاندید مکان امینiدر تسهیل یک اگر1.اینصورت غیر در0=yi∀ iϵI,.یابد تخصیص ام iتسهیل به ام jمشتری اگر1.اینصورت غیر در0=xij∀ iϵI, jϵJ, .اند شده تامین ام i'تسهیل وسیله به که ام iتسهیل شده سپاری برون تقاضاهای تعدادrii'∀ i,i'∈I,i'≠i,.اند شده تامین ام i'تسهیلفرعیمنبع وسیله به که ام iتسهیل شده سپاری برون تقاضاهای تعداد vii'∀ i,i'∈I,i'≠i,4-2-1- توصیف تابع برون سپاریدرابتدا، متغیرهای تصمیم ρi و φi را به صورت ذیل تعریف می نماییم:
ρi=j∈Jχij , ∀ iϵI,(1)
φi=j∈Jθj.χij , ∀ iϵI,(2)
جاییکه ρi، تعداد مشتریان تخصیص یافته به تسهیل i ام است. طبق عبارت (2)، وابستگی میان توزیع احتمالφiو مقدار واقعی متغیرتصمیمxij بر روی مجموعهΩi=j∈J :χij =1, i∈Iکاملا بدیهی است.با در نظر گرفتن توزیع برنولی برای درخواست تقاضای هر مشتری خواهیم داشت:
Pxφi=si=Pxj∈Jθjχij =si=SiϲΩi:Si=sij∈Sipjj∈Ωi\Si(1-pj),∀ iϵI,(3)
جاییکه si , i∈I,یک مقدار شدنی به خود می گیرد. عبارت (3) یک حالت ناهمگن می باشد، بنابراین به منظور ساده سازی مساله در این تحقیق، ما این عبارت را به حالت همگن تغییر شکل خواهیم داد. حالت همگن، حالتی است که همه مشتریان دارای درخواست تقاضا با احتمال یکسان pj=p, jϵJمی باشند.
بنابراین، مطابق با عبارت های (2) و (3)، متغیر φiدارای توزیع احتمالی دوجمله ای با پارامترهای niوp ، جاییکه ni=ρi ، می باشد. این بدین معناست که متغیر φiوابسته به تعداد مشتریان تخصیص یافته به تسهیلiاماست و از اینرو خواهیم داشت: Pxφi=si∼Bin(si;ni,p). بنابراین عبارت (3) به عبارت (4) تغییر شکل می دهد:
Pxφi=si=nisipsi1-pni-si, si=0,1,…, ni,∀ iϵI,(4)

پاسخ دهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *