4-4-7- عملگرجهش68
4-4-8- معیارتوقف70
4-5-1- مسائلنمونه72
فصلپنجم : نتیجهگیریوپیشنهاداتآتی84

5-1- نتیجهگیری85
5-2- پیشنهاداتآتی86
مراجع87
مراجعفارسی88
مراجعلاتین89
Abstract93

در این سایت فقط تکه هایی از این مطلب با شماره بندی انتهای صفحه درج می شود که ممکن است هنگام انتقال از فایل ورد به داخل سایت کلمات به هم بریزد یا شکل ها درج نشود

شما می توانید تکه های دیگری از این مطلب را با جستجو در همین سایت بخوانید

ولی برای دانلود فایل اصلی با فرمت ورد حاوی تمامی قسمت ها با منابع کامل

اینجا کلیک کنید

فهرست شکل ها
فصل سوم
شکل (3- 1).دستهبندیکلیمسائلبرنامهریزیتسهیلات[1].20
شکل (3- 2). دستهبندینوینمسائلمکانیابی [1].23
فصل چهارم
شکل(4- 1). t- امینکروموزومهایصفرویک yiوχij58
شکل(4- 2). t- امینکروموزومهایعددصحیحrii’و vii’59
شکل (4- 3). نحوهعملکردعملگرتقاطعنوع 164
شکل (4- 4). فرآیندعملگرتقاطعنوع 2 برایکروموزوممکانyi65
شکل (4- 5). فرآیندعملگرتقاطعنوع 2 برایکروموزومتخصیص χij66
شکل (4- 6). فرآیندعملگرتقاطعنوع 3 برایکروموزوممکانyi 67
شکل (4- 7). فرآیندعملگرتقاطعنوع 3 برایکروموزومتخصیص χij67
شکل (4- 8). فرآیندعملگرجهشنوع 1 برایکروموزوممکانyi 68
شکل (4- 9). فرآیندعملگرجهشنوع 1 برایکروموزومتخصیص χij68
شکل (4- 10). فرآیندعملگرجهشنوع 2 برایکروموزوممکانyi 69
شکل (4- 11). فرآیندعملگرجهشنوع 2 برایکروموزومتخصیص χij69
شکل (4- 12). فرآیندعملگرجهشنوع 3 برایکروموزوممکانyi 69
شکل (4- 13). فرآیندعملگرجهشنوع 3 برایکروموزومتخصیص χij70
شکل (4- 14). فلوچارتالگوریتمژنتیکپیشنهادی71
فهرست جداول
جدول (4- 1). مقادیرپارامترهایGA73
جدول (4- 2). نتایجمحاسباتیبرایمسائلاندازهکوچک74
جدول (4- 3). مقادیرپارامترهای fiوαi75
جدول (4- 4). مقادیرپارامتر θj75
جدول (4- 5). مقادیرپارامتر dij 76
جدول (4- 6). مقادیرپارامترcij 77
جدول (4- 7). مقادیرپارامترβii’78
جدول (4- 8). نتایجبدستآمدهبرایمثالنمونه78
جدول (4- 9). نتایجمحاسباتیبرایمسائلاندازهبزرگ81
فصل اول:کلیات تحقیق و ساختار پایان نامه
1-1- مقدمه
یکی از مسائلی که باید در مراحل اولیه طراحی سیستم های صنعتی مورد توجه قرار گیرد مساله مکان- یابی2 و استقرار تسهیلات است. مطالعه پیرامون مکان بهینه صنعتی از دیدگاه جغرافیدانان و علمای علم اقتصاد همواره دارای اهمیت و اولویت بوده است. مراکز صنعتی و کارخانجات برای تعیین مکان احداث کارخانه، استقرار تجهیزات و دپارتمان های خود در کارخانه، استقرار دفاترشان در سطح شهر، تعیین مراکز توزیع محصولات و… با چنین مسائلی سروکار دارند [1]. در ادبیات موضوعی، معمولا چند حالت از مسائل مکانیابی گسسته و تخصیص مورد بحث قرار گرفتند، مانند مساله مکان یابی تک تسهیله3، مساله مکان یابی چند تسهیله4، مسالهمکان یابی- تخصیص5. در مساله مکان یابی تک تسهیله، هدف پیدا کردن مکان تسهیل جدید می باشد، بطوریکه مجموع فواصل وزن دهی شده بین تسهیل جدید و تسهیلات موجود حداقل گردد. چند مثال ساده از مسائل مکان یابی تک تسهیله عبارتند از مکان یابی یک بیمارستان، یک ایستگاه آتش نشانی یا یک کتابخانه در یک منطقه شهری ، مکان یابی یک فرودگاه جدید جهت ارائه خدمات به تعدادی پایگاه نظامی. همچنین مساله مکان یابی چند تسهیله بدنبال پیداکردن مکان های بهینه بیش از یک تسهیل جدید با توجه به مکان های تسهیلات موجود می باشد. کاربردهای زیادی از این مساله توسط استرش[2] ارائه شده اند، مانند تاسیس چندین انبار برای سرویس دهی به تعداد مشخصی از مناطق. بنابراین مساله مکان یابی تک تسهیله حالت خاصی از مساله مکان یابی چند تسهیله می باشد.هدف مساله مکان یابی – تخصیص، پیدا کردن مکان بهینه ی مجموعه ای از تسهیلات است بطوریکه، هزینه ی حمل و نقل از این تسهیلات به مشتریان مینیمم گردد. ازاینرو، در این مساله باید تعداد بهینه ای از تسهیلات بمنظور تامین تقاضای مشتریان در مکان های مناسب تاسیس گردند. در گونه ای از مسائل مکان یابی-تخصیص، با محدودیت ظرفیت6 تسهیلات مواجه هستیم. این محدودیت منجر به این امر می شود که تسهیل موردنظر نتواندتمام تقاضای یک نقطه مشتری را برآورده کند. لذا این امکان وجود دارد که کل تقاضای یک مشتری بین کارخانجات مختلف تقسیم شود و هر کارخانه کسری از تقاضای یک مشتری را تامین نماید.

1-2- تعریف مسئله
با توجه به اینکه در دنیای واقعی، فضای اطلاعات معمولا غیرقطعی و احتمالی است، لذا مسائل مکان یابی نیز از این مقوله مستثنا نیستند. اغلب در مسائل مکان یابی فرض شده است که تقاضای مشتریان جهت دریافت سرویس جز ورودی های مساله بوده و قطعی7 هستند. واضح است که این امر در عمل کمتر اتفاق می افتد و معمولا سطح بالایی از عدم قطعیت8 در تقاضای مشتریان وجود دارد. بنابراین از دیگر مسائلی که بهمراه مسائل مکان یابی-تخصیص در دنیای واقعی موجود است، تقاضای احتمالی می باشد، که افق جدیدی را پیش روی ما نهاده است. مدل پیشنهادی این تحقیق، یک مسئله مکان یابی-تخصیص چند تسهیله ظرفیت دهی شده با تقاضاهای احتمالی که دارای تابع توزیع برنولی می باشند، است. همچنین در این مدل هر تسهیل دارای یک منبع فرعی ظرفیت دهی شده می باشد که می تواند در صورت نیاز از آن استفاده کند.

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

فصل دوم:مروری بر ادبیات موضوعی مسائل مکان یابی- تخصیصبا تقاضای احتمالی

2-1- مقدمه
مسائل مکان یابی- تخصیص چندتسهیله، یکی از حوزه های گسترده در مدل سازی ریاضی در دنیای واقعی می باشند، که در این مسائل چند تسهیل جدید (تسهیل عرضه) به مجموعه ای از مشتریان موجود، با توجه به تقاضاهایشان، سرویس می دهند.
در ادبیات موضوعی، معمولا چند حالت مختلف از مسائل مکان یابی پیوسته مانند مساله مکان یابی میانه (تک تسهیله)، مساله مکان یابی میانه (چند تسهیله)، ، مساله مکان یابی گسسته و مساله مکان یابی-تخصیصمورد بحث قرار می گیرند. مسائل مکان یابی تسهیل، مکان یک مجموعه از تسهیلات (منابع) را به منظور کمینه کردن هزینه های تامین مجموعه هایی از تقاضاها (مشتریان) با توجه به تعدادی محدودیت، را تعیین می کند.
مطالعه برروی تئوری مکان یابی، رسما در سال 1909 وقتی که آلفرد وبر [3] در نظر گرفت که چگونه مکان یک انبار را بمنظور مینیمم کردن فاصله بین انبار و چندین مشتری تعیین نماید، آغاز شد. بعد از آن تئوری مکان یابی در بخش های مختلفی بکار گرفته شد. حکیمی [4] در پی تحقیقی، سعی در پیدا کردن مراکز مخابرات در یک شبکه ارتباطات و ایستگاه های پلیس در بزرگراه ها داشت.در مساله مکان یابی میانه(تک تسهیله) کلاسیک که غالبا مسئله وبر9 و مسئله حداقل مجموع10 نیز نامیده می شود، در صدد یافتن مکان تسهیل جدید هستیم بطوریکه مجموع فواصل وزن دهی شده11 با تسهیلات موجود، حداقل گردد. برای کسب اطلاعات بیشتر در این زمینه به فراهانی و حکمت فر [5] و نیکل و پارتو [6] مراجعه کنید.
زعفرانیه و همکاران [7] الگوریتمی برای مساله جایابی تک تسهیله در دو منطقه با نرم های متفاوت پیشنهاد داده اند و نشان داده اند که حل بهینه در تقاطع متعامد تسهیلات موجود است. این مسئله در حقیقت تعمیم یافته مساله جایابی تک تسهیله است.ردریگرز و همکاران [8] مدلی را برای مساله جایابی تک تسهیلاتی ناخوشایند پیشنهاد داده اند. در این پژوهش مجموعه ای متناهی از حل بهینه برای یک مساله با فاصله اقلیدسی تعیین گشته است.بریمبرگ و جول [9] یک روش خط سیر را برای ایجاد یک مرز کارایی نقاط برای یک مدل دو معیاره جایابی یک وسیله نیمه خوشایند در صفحه مورد بررسی قرار داده اند. معیار اول برای اندازه گیری هزینه حمل و نقل و دومی برای تخمین هزینه اجتماعی یا محیطی مورد استفاده قرار گرفته است. در اینجا وزن های نسبی به گونه ای تغییر می کنند که مجموع وزن های دو معیار مینیمم گردد.در مساله مکان یابی چند تسهیله حداقل مجموع12 در صدد یافتن مکان های تسهیلات جدید با توجه به مکان های تعدادی تسهیل موجود هستیم،بطوریکه مجموع فواصل بین تسهیلات جدید و فواصا بین تسهیلات جدید و تسهیلات موجود کمینه گردد. حال آنکه مساله مکان یابی چند تسهیله حداقل حداکثر13 به دنبال پیداکردن مکان یک مجموعه از تسهیلات جدید در میان تسهیلات موجود است با این هدف که ماکزیمم فواصل وزن دهی شده بین همه تسهیلات را مینیمم کند. لوین و بن [10] یک روش ابتکاری برای مسائل جایابی چند تسهیلاتی با مقیاس بالا پیشنهاد داده اند به گونه ای که مشتریان با استفاده از طبقه بندی دوباره نزدیکترین مرکز دوباره به تجهیزات تخصیص داده می شوند. ژانگ و روشتن [11] به بررسی مساله جایابی چندتسهیلاتی در سرویس های خدماتی رقابتی پرداخته اند. تابع هدف پیشنهادی یک مقیاس مطلوبیت فضایی کاربران را با توجه به محدودیت های زمان انتظار کاربران و بودجه مالکین تسهیلات، بیشینه می کند. همچنین برای اطلاعات بیشتر در این زمینه به دوبسن و کرمارکار [12] و لاو و همکارانش[13] مراجعه کنید. مساله مکان یابی انبار ابتدا توسط کوهن و هبمورگر [14] مطالعه شد. آنها الگوریتم ابتکاری پایه ای drop, add and swap را برا حل این مساله توسعه دادند. بعد از آنها خوماوالا [15] الگوریتم شاخه و حد را بر اساس فرمولبندی ضعیف ارائه کردند. فرمولبندی قوی خطی توسط ارلنکتر [16] استفاده شد تا رویه محاسباتی ارائه کتد که شاید موثرترین و سهل الوصول ترین ابزار برای حل این دسته از مسائل باشد. نتایج کار وی در گویناردو اسپیلبرگ [17] ارائه شده است. یک خلاصه عالی از مسئله مکان یابی بدون محدودیت ظرفیت نیز توسط کرنوجلس و همکارانش [18] گردآوری شده است.
مساله مکان یابی به دنبال پیدا کردن مکان های بهینه مجموعه ای از تسهیلات بمنظور تامین درخواست های تقاضای مجموعه ای از مشتریان می باشد. اغلب فرض شده است که درخواست تقاضای مشتریان معین و قطعی بوده و به عنوان بخشی از پارامترهای ورودی مساله است. واضح است که این امر در عالم واقعیت کمتر اتفاق می افتد و معمولا تقاضای مشتریان با یک سطح بالایی از عدم قطعیت14 همراه است. مثال های ساده ای از مسائل مکان یابی با تقاضاهای غیرقطعی، جاییکه سطوح تقاضا طی دوره های زمانی مختلف، تغییر می کنند عبارتند از مساله سرویس های پستی، فرودگاه ها، سوپرمارکت ها، انبارهای توزیع کالاها با تقاضا های فصلی. براندو و چیو [19] و لووکس[20] و اسنایدر [21] جنبه های مختلف مسائل مکان یابی احتمالی را مورد مطالعه قرار دادند. یک مساله مکان یابی صف احتمالی، بمنظور ماکزیمم کردن عملکرد سیستم توسط ماریانو و روله [22] مورد مطالعه قرار گرفت. آنها یک مدل احتمالی را طراحی کردند که در پی ماکزیمم کردن جمعیت تحت حمایت وسایل نقلیه اورژانس با سطح دسترسی α است. در این مدل سطح دسترسی وسایل نقلیه با استفاده از تئوری صف محاسبه می گردد. پن و همکاران [23] یک مدل دو مرحله ای برای یک خرده فروش حاکم در یک زنجیره تامین تولیدکننده-خرده فروش با تقاضاهای احتمالی در یک محیط قیمتی نزولی را ارائه کردند. این مدل بدنبال یکپارچه کردن پیش بینی تقاضا و تصمیمات راجع به قیمت و سفارش و پیدا کردن خطی و مشی قیمتی و سفارشی بهینه برای خرده فروش حاکم بمنظور ماکزیمم کردن سود انتظاری از یک محصول در دو دوره زمانی است.
شاید ساده ترین مساله، مکان یابی گسسته موردی باشد که یک تسهیل جدید قرار است مستقر شود. به عبارتی از بین تعداد محدودی سایت، مثلا n، باید یکی انتخاب شود. با فرض اینکه هزینه ی سالیانه استقرار تسهیل جدید در هر کدام از سایت ها مشخص است، جواب بدیهی این مسئله استقرار تسهیل جدید در سایتی است که کمترین هزینه را دارد. هنگامیکه که قرار است دو یا تعداد بیش تری تسهیل مستقر شوند وn سایت ممکن در دسترس است مساله مکان یابی دشوارتر می شود. در حقیقت هنگامیکه mتسهیل جدید و n سایت ممکن وجود دارد، بطوریکه m≤n، تعداد تخصیص های ممکن برابر با(■(n@m))m!=n!/(n-m)!است. با بزرگترشدن n, m تعداد گزینه های ممکن به سرعت افزایش می یابد به گونه ای که روش شمارش کامل (محاسبه و مقایسه هزینه همه گزینه ها) برای حل این مسائل ناکارآمد است. برای حل چنین مسائلی مدل تخصیص15 مفید است. مساله مکان یابی-تخصیص بدنبال پیدا کردن مکان بهینه یک مجموعهای از تسهیلات است بطوریکه هزینه ی حمل و نقل از تسهیلات به مشتریان موجود کمینه گردد و همچنین یک تعداد بهینه از تسهیلات بمنظور تامین تقاضاهای مشتریان باید گمارده شوند. در مساله مکان یابی-تخصیص گسسته، آنچه باید تعیین شود، تعداد و مکان تسهیلات جدید از میان یک تعداد متناهی مکانهای بالقوه و تخصیص تقاضاهای مشتریان مشخص به این تسهیلات است. در ابتدا کوپر [24]مسئلهکلاسیک مکان یابی-تخصیص را با دو تسهیل جدید و هفت نقطه ی تقاضا پیشنهاد نمود. کوپر ثابت کرد که تابع هدف این مساله نه مقعر است و نه محدب و شاید شامل چند جواب بهینه محلی16 باشد. از اینرو طبق گفته ی هنریک و روبرت [25] مسئله کلاسیک مکان یابی-تخصیص در حوزه مسائل بهینه سازی سراسری17 است. پس از کوپر مسئله مکان یابی-تخصیص شبکه18 و بسیاری مدل دیگر توسط بدری [26] ارائه شدند.گن و چنگ [27 ، 28] مسئلهمکان یابی-تخصیص را بطور مفصل مورد مطالعه قرار داده و در مورد همه انواع آن بحث کردند.
روله و الزینگا [29] یک مساله مکان یابی چندتسهیله ای را که در آن هر ناحیه تعریف شده حداقل به یک تسهیل تخصیص می یابد را درنظر گرفتند. در مدل پیشنهادی آنها نواحی تعریف شده کاملا از یکدیگر مستقل بوده و هیچ نوع تعامل میان آنها نمی باشد. برمن و همکاران [30] یک مدل مکان یابی- تخصیص تک تسهیله ای را ارائه کردند که در آن بر خلاف کار روله و الزینگا، تعامل میان نواحی امکان پذیر بوده است. البته هر دوی این کارها یک حالت خاصی از مدل ارائه شده توسط روله و سووین [31] هستند.
در مدل های قطعی مسائل مکان یابی- تخصیص، فرض شده است که درخواست تقاضای مشتریان کاملا مشخص و قطعی می باشد که البته این امر در جهان واقعی کمتر اتفاق می افتد. وقتی حالت قطعی در تقاضای مشتریان درنظر گرفته می شود، ما دقیقا نمی دانیم که کدام مشتری درخواست تقاضا دارد و کدامیک ندارد. بنابراین یک رویکرد معقول این است که درخواست تقاضای مشتریان بطور تصادفی اتفاق بیافتد که این امر منجر به افزایش حالت های احتمالی در مساله مکان یابی چند تسهیله می گردد. لوگندران و ترل [32] یک مساله مکان یابی- تخصیص بودن محدودیت ظرفیت را در حضور تقاضاهای احتمالی قیمت محور در نظر گرفتند و یک مدل بهینه سازی بمنظور ماکزیمم کردن سود خالص انتظاری پیشنهاد کردند. آنها یک روش ابتکاری برای حل مسائل با اندازه متوسط و بزرگ ارائه کردند. لووکس و پیترز [33] یک مساله مکان یابی تسهیل با ظرفیت نامحدود و تقاضاهای احتمالی را پیشنهاد کردند. آنها مجموعه ای از سناریوهایی را برای مساله درنظر گرفتند که با احتمالات خاص اتفاق می افتند.شرالی و ریزو [34] یک مساله مکان یابی- تخصیص ظرفیت بندی شده با تقاضایمستمررا بر روی یک نمودار زنجیری ارائه کردند.کاریزوسا و همکاران [35] یک مساله مکان یابی- تخصیص، جاییکه نواحی مکان های مشتریان و تسهیلات ممکن است با توزیع های احتمال متفاوتی نزدیک به یکدیگر باشند را مورد کنکاش قرار دادند.زو [36] یک مدل برنامه ریزی مقدار انتظاری با احتمال اجباری19 برای مساله مکان یابی- تخصیص با ظرفیت نامحدود و تقاضاهای احتمالی را پیشنهاد کرد.اگرچه مساله مکان یابی- تخصیص احتمالی با محدودیت ظرفیت به وسیله محققین زیادی مورد مطالعه قرار گرفت ولی به خاطر پیچیدگی مساله هیچ مدل برنامه ریزی احتمالی عمومی ای برای آن ارائه نگردید تا اینکه زو و لیو [37] سه مدل احتمالی عمومی، که کاملا از مدل های برنامه ریزی احتمالی پیشین متفاوت می باشند را ارائه کردند. این مدل ها عبارتند از: مدل مقدار انتظاری20، برنامه ریزیاحتمال اجباری21و برنامه ریزیاحتمال وابسته22. همچنین محققین، الگوریتم سیمپلکس شبکه ای، شبیه سازی های احتمالی و الگوریتم ژنتیک را به منظور حل کارای مساله با یکدیگر یکپارچه کردند. لاپورت و همکارانش [38] یک مساله فروشنده دوره گرد را با تقاضا های احتمالی(PTSP)23 مورد مطالعه قرار دادند و یک مدل برنامه ریزی خطی ای که با رویکرد شاخه و برش24 حل می شود را ارائه کردند. از آنجاییکه مسائل PTSPبه دلیل ترکیب مسالهTSP و حالت احتمالی تقاضا، از جمله مسائل زمان بر در حل هستند، آنها یک الگوریتم دقیق برای حل این مساله ارائه کردند. بعداز آن، بیانچی و کمبل [39] یک روش ابتکاری برای حل مساله PTSPجاییکه همه مشتریان دارای احتمال یکسان برای تقاضا هستند، را پیشنهاد کردند. آنها یکمسئلهفروشندهدورگرداحتمالیناهمگنراتوسعهداده و الگوریتمهای حل مختلفیبرایحالتناهمگنپیشنهادکردند.مسئله آنها به دنبالپیداکردنمسیریکهکمترینهزینهانتظاریبرایمشتریانیکهدارایتقاضاهایاحتمالیهستند،میباشد. ماریا آلباردا سامبولا و همکاران [40] یک مساله مسیریابی تسهیل احتمالی25 که دارای مدلی دو مرحله ای است، را بیان کردند. در مرحله اول مدل آنها مجموعه ای از تسهیلات و خانواده ای از مسیرها مشخص می گردند و در مرحله دوم تصمیمات لازم (عمل توسل26)به منظور انطباق این مسیرها به مجموعه واقعی مشتریانی که باید تامین گردند، گرفته می شوند. همچنین آنها یک روش ابتکاری برای حل مساله ارائه نمودند.پس از این تحقیق، ماریاآلباردا سامبولا و همکاران [41] بر روی یک مساله مکان یابی- تخصیص در محیط گسسته با تقاضاهای برنولی کار کردند. آنها دو نوع تصمیمی (عمل توسل) که مرتبط با مدل برنامه ریزی احتمالی دو مرحله ای می باشند، را درنظر گرفتند. برای هر نوع تصمیم، آنها یک روش تقریبی برای محاسبه مقدار انتظاری که تاثیر حالت احتمالی را بر روی مساله تخمین می زند، ارائه کردند. مجموعه جواب حاصله از مرحله اول شامل مکان های تسهیلات و نحوه تخصیص مشتریان به تسهیلات و مجموعه جواب مرحله دوم تخمینی از مقدار انتظاری تابع تصمیم گرفته شده (تابع توسل27) می باشد.
از آنجایی که مسئله مکان یابی-تخصیص یک مسئله NP-hard است [42] ، دستیابی به جواب بهینهیکی از دغدغه های اصلی مساله می باشد. روش های حل مسائل مکان یابی-تخصیص به سه دسته اصلی طبقه بندی می شوند: روش های دقیق ، روش های ابتکاری و روش های فراابتکاری. از جمله روش های دقیق می توان به الگوریتم شاخه و کران28 که توسط کونه و سولند [43] برای مساله چند منبع ای وبر اجرا شده است اشاره کرد. روش های ابتکاری29 زیادی برای پیدا کردن جواب های بهینه مسئله کلاسیک مکان یابی-تخصیص به خوبی اندک الگوریتم های دقیق ارائه شده اند.روش های ابتکاری بمنظور حل سریع مسائل بزرگ و ایجاد کردن جواب های اولیه خوب برای الگوریتم های دقیق مورد نیاز هستند. اولین روش ابتکاری مشهور، الگوریتم مکان یابی-تخصیص تکراری کوپر [44] است. روش ابتکاری کوپرچندزیرمجموعه از نقاط ثابت ایجاد می کند و سپس هر کدام از آنها را با استفاده از الگوریتم دقیق برای حل یک مسئله مکان یابی تک تسهیله، حل می کند.روش های فرا ابتکاری زیادی نیز برای بدست آوردن جوابهای این گونه مسائل بکار گرفته شده اند، از جمله ، شبیه سازی تبرید30 (مورای و چرچ [45]) و جستجوی ممنوعه31 (بریمبرگ و ملادنویچ [46]). همچنین تعدادی الگوریتم پیوندی32 مانند الگوریتم پیوندی شبیه سازی تبرید و روش وراثت تصادفی33 (ارنست و کریشنامورسی [47]) و الگوریتم پیوندی روش ساده سازی لاگرانژ34 و الگوریتم ژنتیک35 (گنگ و همکاران [48]) نیز پیشنهاد شده اند.
نتیجه حاصلنوع مسئله*برون سپاریتابع هدفظرفیت بندی شدهتقاضانویسنده(گان)بهینهFLPخیرکمینهخیرقطعیآلفرد وبر[3]ابتکاریFLPخیرکمینهخیرقطعیزعفرانیه و همکاران[7]بهینهFLPخیرمینیماکس، کمینهخیرقطعیردریگرزوهمکاران [8]بهینهFLPخیرمینیماکس، کمینهخیرقطعیبریمبرگوجول [9]ابتکاریLAPخیرکمینهخیرقطعیلوینوبن [10]بهینهLAPخیربیشینهبلهاحتمالیژانگوروشتن [11]ابتکاریFLPخیرکمینهخیرقطعیکوهنوهبمورگر [14]شاخه و کرانFLPخیرکمینهخیرقطعیخوماوالا [15]بهینهQ-MALPخیربیشینهبلهاحتمالیماریانووروله [22]بهینهSPPخیربیشینهبلهاحتمالیپن و همکاران[23]بهینه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-1). خلاصه ای از ادبیات موضوع
فصل سوم :زمینه های علمی تحقیق

3-1- مقدمه
برنامه ریزی تسهیلات که از مباحث مهم در مهندسی صنایع است دو بخش عمده مکان یابی (جانمایی) و طراحی36 را شامل می شود که مهم ترین بخش طراحی ، استقرار یا جانمایی37 و بخش های دیگر آن، حمل و نقل38 و طراحی ساختمان و تاسیسات39 است. منظور از تسهیلات، هر مجموعه، شامل کارخانه، دانشگاه، بیمارستان و غیره است.
در مکان یابی، ما به بررسی محل قرار گرفتن یک وسیله برای رسیدن به اهداف مورد نظر می پردازیم که برای تعیین محل آن، معیارهای مهمی موثرند، از جمله نزدیکی به جاده های اصلی، بازار مصرف، منابع تامین مواد اولیه، در دسترس بودن نیروی انسانی موردنظر، شرایط محیطی، امکان توسعه، مقررات و قوانین دولتی و غیره.همچنین در طرح استقرار می خواهیم نحو قرار گرفتن اجزای یک وسیله را برای رسیدن به بهترین بهره وری تعیین کنیم. روش های زیادی تاکنون برای حل این گونه مسائل مطرح شده اند که از آن جمله می توان به برنامه ریزی، استفاده از تصمیم گیری چندگانه و غیره اشاره کرد [1].
همان طور که قبلا بدان اشاره کردیم، مراکز صنعتی و کارخانجات برای تعیین مکان احداث کارخانه، استقرار تجهیزات و دپارتمان های خود در کارخانه، استقرار دفاترشان در سطح شهر، تعیین مراکز توزیع محصولات و غیره با چنین مسائلی سر و کار دارند. در واقع، تصمیمات مربوط به مکان یابی و استقرار، نه تنها در مسائل صنعتی، بلکه در مسائل گوناگونی در بخش های دولتی و خصوصی، اعم از صنعتی و غیرصنعتی ظاهر می شود. در بخش دولتی، تعیین مکان مراکز خدماتی، نظیر ایستگاه های پلیس راه، اورژانس، بیمارستان ها ایستگاه های آتش نشانی و غیره نیاز به اتخاذ چنین تصمیماتی دارد. لذا تصمیم گیری در مورد مکان یابی تسهیلات عمدتا از تصمیم گیری های بلند مدت و استراتژیک شرکت های بزرگ خصوصی و عمومی است و هزینه های بالای مربوط به مکان یابی و استقرار و راه اندازی تسهیلات، پروژه های مکان یابی را به سرمایه گذاری های بلندمدت تبدیل کرده است. لذا موفقیت یا شکست مراکز تسهیلاتی در هر کدام از بخش های دولتی و خصوصی، بستگی کامل به مکان های انتخابی برای آنها دارد. بدین ترتیب، اهمیت مساله مکان یابی و استقرار تسهیلات و ضرورت پرداختن بدان بر همگان روشن است [1].
3-2- دسته بندی کلی مسائل برنامه ریزی تسهیلات
مسائل برنامه ریزی تسهیلات به چهار دسته عمده مکان یابی، مسیریابی، تخصیص و طراحی تقسیم می شود. با ترکیب این مولفه ها مسائل مکان یابی- مسیریابی40، مکان یابی- تخصیص41 به دست می آید [1].
├ ■(تسهیلات تخصیص@@تسهیلات یابی مکان@@تسهیلات یابی مسیر@@تسهیلات طراحی@)}تسهیلات ریزی برنامه{█(@@)┤مکان یابی-تخصیص تسهیلات{█(@@)┤مکان یابی- مسیریابی تسهیلات├ ■(تسهیلات جانمایی@مواد انتقال@ساختاری طراحی)}شکل (3- 1). دسته بندی کلی مسائل برنامه ریزی تسهیلات[1].
3-3- دسته بندی مسائل مکان یابی با نگرش سنتی
دسته بندی های کلاسیک مسائل مکان یابی عمدتا بر اساس موارد زیر بوده است:
براساس خصوصیات وسایل جدید
مساله مکان یابی تک وسیله/چند وسیله
مساله مکان یابی با وسایل نقطه ای/ ناحیه
براساس خصوصیات وسایل موجود
مساله مکان یابی با وسایل ایستا/پویا
مساله مکان یابی وسایل با مکان قطعی/احتمالی
براساس نوع ارتباط وسایل موجود و جدید
مساله مکان یابی با ارتباطات برون زا/درون زا
مساله مکان یابی با ارتباطات ایستا/پویا
مساله مکان یابی با ارتباطات قطعی/احتمالی

براساس فضای جواب
مساله مکان یابی روی خط/صفحه
مساله مکان یابی گسسته/روی شبکه
مساله مکان یابی با فضای مقید/نامقید
براساس نوع تابع فاصله
مساله مکان یابی با فواصل متعامد/چپیشف
مساله مکان یابی با فواصل اقلیدسی/مجذور اقلیدسی
مساله مکان یابی با سنجه های خاص
بر اساس نوع و تعداد هدف و شاخص انتخاب
مسائل تک هدفه/چندهدفه
مسائل تک شاخصه/چندشاخصه
مسائل میانه (هدف: مینیمم مجموع هزینه ها)/ مرکز(هدف: مینیمم حداکثر هزینه ها)/
پوشش42 (هدف: حداکثر پوشش تقاضا یا حداقل تعداد وسیله)

براساس زمینه مساله
مساله مکان یابی انبار
مساله مکان یابی نقاط تبادل (هاب)43
مساله مکان یابی وسایل ناخوشایند
مساله مکان یابی وسایل گردشی (مسائل مکان یابی-مسیریابی)
مساله مکان یابی وسایل سلسله مراتبی
3-4- دسته بندی مسائل مکان یابی با نگرش نوین
مسائل مکان یابی و استقرار را بر مبنای نگرش در مدل سازی و حل در شکل (3-2) دسته بندی شده اند. در این دسته بندی چهار رویکرد عمده نظری و عملی وجود دارد.

رویکردهای استراتژیکCFLDFLSLFهوش مصنوعیMHNNFLرویکردهای عملیITEGرویکردهای دیگرEMDMSCMیادداشت:SLF: مکان یابی تسهیلات استراتژیکDFL: مکان یابی تسهیلات پویاCFL: مکان یابی تسهیلات رقابتیFL: منطق فازیNN: شبکه های عصبیMH: الگوریتم های فراابتکاریEG: جغرافیای اقتصادیIT: فناوری اصلاعاتSCM: مدیریت زنجیره تامینDM: داده کاویEM: سنجش بهره وری شکل (3- 2). دسته بندی نوین مسائل مکان یابی [1].
3-5- مسائل مکان یابی-تخصیص
مسئله مکان یابی- تخصیص به دنبال مکان یابی مجموعه ای از تسهیلات جدید است بطوریکه هزینه ی حمل و نقل از تسهیلات به مشتریان مینیمم گردد و تعداد بهینه ای از تسهیلات باید در نقاط کاندید به منظور تامین تقاضای مشتریان احداث شوند.
این مساله در بسیاری از زمینه های عملی جاییکه تسهیلات خدمات یکسانی را ارائه می کنند، بکار گرفته می شود مانند مکان یابی انبارها، مراکز توزیع، مراکز ارتباطات و تسهیلات تولید [5].

3-5-1- طبقه بندی مساله مکان یابی- تخصیص
اجزای اصلی مسائل مکان یابی- تخصیص شامل تسهیلات، مکان ها و مشتریان می باشند. مشخصات و ویژگی های این اجزای اصلی در این بخش به همراه انواع مدل های مکان یابی- تخصیص به تفضیل توضیح داده خواهند شد.

3-5-1-1- طبقه بندی تسهیلات
تسهیلات معمولا براساس تعداد، نوع و یا هزینه هایشان از دیگر چیزها متمایز می شوند. دیگر خواص مرتبط با تسهیلات شامل سود، ظرفیت، دامنه جذب (ناحیه ای که مشتریان به تسهیل تخصیص می یابند) و نوع سرویس ارائه شده توسط هر یک از این تسهیلات می باشد.
یکی از این خواص متمایزکننده، تعداد تسهیلات جدید است. ساده ترین مورد، مسئله مکان یابی تک وسیله ای است، جاییکه تنها مکان یک تسهیل جدید باید مشخص گردد. مساله بعدی، مساله مکان یابی چند وسیله ای است که در این نوع مسائل، هدف تعیین همزمان مکان بیش از یک تسهیل جدید است.
نوع هر تسهیل، یکی دیگر از خواص متمایزکننده انواع مسائل می باشد. در ساده ترین حالت، همه تسهیلات برحسب اندازه و نوع سرویسی که ارائه می کنند، یکسان درنظر گرفته می شوند. دربعضی مورد، ما نیازمند به مکان یابی تسهیلاتی هستیم که از لحاظ نوع ارائه سرویس با هم متفاوت هستند مانند بیمارستان ها و واحدهای مراقبت های بهداشتی کوچکتر. مدل های مکان یابی- تخصیص برحسب اینکه تسهیلات بتوانند تنها یک نوع سرویس ارائه کنند یا بیشتر، به انواع تک سرویسه و یا چندسرویسه تقسیم می شوند.
همچنین باید درنظر داشت که تسهیلات می توانند تقاضاهای نامحدود را تامین کنند و یا اینکه ظرفیت تولید و تامین آنها محدود باشد. در این حالت مسائل مکان یابی- تخصیص به دو دسته ی مسائل با ظرفیت نامحدود و مسائل با ظرفیت محدود تقسیم می شوند[5].

3-5-1-2- طبقه بندی فضای فیزیکی یا مکان ها
مجموعه مکان های مطلوب به سه شکل قابل نمایش هستند: فضاهای گسسته، پیوسته، شبکه ای.
مدل های فضای پیوسته اغلب اوقات به مدل های مکان-ساخت44ارجاع داده می شوند. چرا که این مدلها در پی ایجاد مکان های مناسب برای تسهیلات در فضای پیوسته هستند.
از آنجاییکه در مدل های فضای گسستهیک شناخت قبلی از مکان های کاندید داریم، این مدل مسائل به مدل های مکان-انتخاب45 ارجاع داده می شوند.
مدل شبکه ای فضا، سومین نوع مسائل مکان یابی است که برحسب مکان ها قابل شناسایی است. مسائلی که بروی شبکه ها طراحی می شوند ، می توانند طبق لینک های شبکه که بصورت یک مجموعه پیوسته از نقاط کاندید یا فقط گره های مطلوب برای احداث تسهیلات جدید درنظر گرفته شده اند، پیوسته یا گسسته باشند[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- مدل عمومی مکان یابی- تخصیص46
اولین بار کوپر [19]در سال 1963 یک مدل عمومی مکان یابی- تخصیص را با دو تسهیل جدید و هفت نقطه تقاضای معرفی و حل نمود.
3-5-2-1-1 فرضیات مدل
فرضیات مسئله بصورت زیر است(همچنین این مساله به عنوان مسئله چندمنبع ای وبر47 نیز مشهور است):
فضای جواب پیوسته است.
تقاضای هر مشتری می تواند توسط چندین تسهیل بدون درنظر گرفتن هزینه احداث تسهیل جدید تامین گردد.
ظرفیت تسهیلات نامحدود است.
پارامترهای مساله به منظور تامین تقاضاها قطعی هستند.
هیچ رابطه ای بین تسهیلات جدید وجود ندارد[5].
3-5-2-1-2- ورودی ها و خروجی های (متغیرهای تصمیم) مدل
ورودی های مدل عبارتند از :
nتعداد مشتریان (تسهیلات موجود)r_jتقاضاهای مشتریانj=1,…,na_jمختصات های مشتریانj=1,…,n متغیرهای تصمیم مدل عبارتند از :
mتعداد تسهیلاتx_iمختصات تسهیلات جدیدi=1,…,mw_ijتعداد تقاضای تامین شده مشتری jام بوسیله تسهیل iامd(x_i,a_j)فاصله بین مشتری jام و تسهیل جدید iام
3-5-2-1-3- تابع هدف و محدودیت های مدل عمومی
تابع هدف این مدل و محدودیت های مرتبط با آن عبارتند از:
Min ϕ =∑_(i=1)^m▒∑_(j=1)^n▒〖w_ij d(x_i,a_j)〗(1.3)Subject to∑_(i=1)^m▒〖w_ij=r_j 〗j=1,…,n(2.3)w_ij≥0i=1,…,m
j=1,…,n(3.3)
3-5-2-2- مدل مکان یابی- تخصیص که هر مشتری فقط توسط یک تسهیل تامین می گردند48
در این مدل دومین فرض از فرضیات مدل عمومی مکان یابی- تخصیص تغییر می کند، بدین صورت که هر مشتری فقط می تواند از یک تسهیل استفاده نماید. دیگر فرضیات این مدل شبیه به مدل عمومی هستند. ورودی های این مدل همان ورودی های مدل عمومی هستند. در این مدل، متغیرهای تصمیم، متغیرهای تصمیم مدل عمومی غیر از متغیر w_ij و باانضمام متغیر زیر هستند [5] :
Z_ij=1 اگر مشتری j ام به تسهیل iام تخصیص یابد و در غیر اینصورت 0.
3-5-2-2-1- تابع هدف و محدودیت های این مدل
Min ϕ =∑_(i=1)^m▒∑_(j=1)^n▒〖Z_ij r_j d(x_i,a_j)〗(4.3)Subject to∑_(i=1)^m▒〖z_ij=1〗j=1,…,n(5.3)Z_ij ϵ{0,1}i=1,…,m
j=1,…,n(6.3)
3-5-2-3- مدل مکان یابی- تخصیص با هزینه احداث تسهیل49
در این مدل سومین فرض از فرضیات مدل عمومی مکان یابی- تخصیص تغییر می کند، بدین صورت که به ازای احداث هر تسهیل هزینه ای معین به هزینه های کل اضافه می گردد. دیگر فرضیات این مدل با مدل عمومی یکسان هستند. ورودی های این مدل همان ورودی های مدل عمومی هستند باانضمام پارامتر f(x_i). همچنین متغیرهای تصمیم این مدل، متغیرهای تصمیم مدل عمومیهستند.
f(x_i)هزینه احداث تسهیلi ام.
3-5-2-3-1- تابع هدف و محدودیت های این مدل
تفاوت بین تابع هدف این مدل و مدل عمومی مکان یابی- تخصیص بصورت زیر می باشد:
عبارت (1.3) از تابع هدف حذف شده و عبارت زیر به آن اضافه می گردد :
(7.3)∑_(i=1)^m▒〖f(x_i)〗 محدودیت های این مدل کاملا با مدل عمومی مکان یابی- تخصیص یکسان هستند.
اگر فرض کنیم که هزینه احداث تسهیلات مستقل از مکان تسهیلات باشد و مقدار mنیز مشخص باشد و با توجه به این که اکنون جمع هزینه های احداث تسهیلات ثابت است و می تواند از تابع هدف مساله حذف گردد، مساله به یک مساله چند منبع ای وبرکه از جمله مسائل مشهور است، ساده سازی می گردد[5].
3-5-2-4- مدل مکان یابی- تخصیص ظرفیت دهی شده با تقاضاهای احتمالی50
این مدل توسط زو و لیو[32] در سال 2003 پیشنهاد شد.
3-5-2-4-1- فرضیات مدل
در این مدل چهارمین و پنجمین فرض از فرضیات مدل عمومی مکان یابی- تخصیص تغییر می کند، بدین صورت که ظرفیت تسهیلات محدود بوده و تقاضاهای مشتریان احتمالی است. دیگر فرضیات این مدل با فرضیات مدل عمومی یکسان می باشد.
3-5-2-4-2- ورودی ها و خروجی های (متغیرهای تصمیم) مدل
ورودی های این مدل همان ورودی های مدل عمومی هستند باانضمام پارامترهای زیر:
ξ_j: تقاضای احتمالی مشتری j ام.ξ_j (ω): تحققی از بردار احتمالی jام.S_i: ظرفیت تسهیل i ام. همچنین متغیرهای تصمیم این مدل، همان متغیرهای تصمیم مدل عمومیهستند. در مدل مکان یابی- تخصیص قطعی، تخصیص w ، متغیر تصمیمی است که در تمام دوره های زمانی ثابت است. در صوریتکه در یک مساله مکان یابی- تخصیص احتمالی، تصمیم wمتغیر است و در هر دوره زمانی بعد از آنکه تقاضاهای مشتریان مشخص گردید، شکل می گیرد.

3-5-2-4-3- تابع هدف و محدودیت های مدل
تابع هدف این مدل شبیه به تابع هدف مدل عمومی مکان یابی- تخصیص است.
Min ϕ =∑_(i=1)^m▒∑_(j=1)^n▒〖w_ij d(x_i,a_j)〗(8.3)Subject to∑_(i=1)^m▒〖w_ij=〗 ξ_j (ω)j=1,…,n(9.3)∑_(i=1)^m▒〖w_ij≤〗 S(10.3)w_ij≥0i=1,…,m
j=1,…,n(11.3) اگر نقاط شدنی برای w بدست نیاید، بنابراین تامین کردن بعضی از مشتریان امکان پذیر نخواهد شد و سمت راست عبارت (8.3) بی معنی خواهد شد و بعنوان هزینه پنالتی تابع هدف زیر جایگزین می شود [5] :
Min ϕ =∑_(i=1)^m▒∑_(j=1)^n▒〖ξ_j (ω)d(x_i,a_j)〗(12.3)
3-6- تشریح الگوریتم ژنتیک
الگوریتم های ژنتیک تکنیک نسبتا جدید هستند که، از آنها برای حل مسائل مختلف استفاده شده است. دو ویزگی اصلی این تکنیک یکی الهام گیری آن از پدیده های طبیعی خلقت و دیگری قابلیت پردازش موازی می باشد. الگوریتم های ژنتیک با الهام از فرایند تکامل طبیعی به عنوان یک روش جستجوی هوشمند در حل مسائل بهینه سازی کاربرد گسترده ای یافته است. الگوریتم ژنتیک برگرفته از الگوریتم تکاملی است که اولین بار توسط جان هالند [33] در دانشگاه میشیگان پیشنهاد شد و استراتژی ها و برنامه ریزی های تکاملی که توسط رچنبرگ51 و چیفل52 و فوگوگل53 و کوزا54 ایجاد شدند، از جمله روش های محاسبه تکاملی هستند.
روش های بهینه سازی الهام گرفته از طبیعت با روش های متعارف بهینه سازی تفاوت مهمی دارند. در روش های متعارف هر جواب کاندیدای جدید در صورتی به عنوان جواب جدید انتخاب می شود که مقدار تابع هدف را بهبود بخشد ولی در الگوریتم های الهام گرفته از طبیعت به تمام جواب های کاندیدای جدید شانس انتخاب داده می شود. الگوریتم های ژنتیک، تکنیک های جستجوی تصادفی هستند که بر اساس انتخاب طبیعی و نسل شناسی طبیعی کار می کنند. الگوریتم ژنتیک روشی مستقل از دامنه مساله است و به سرعت فضای جستجو را برای نقاطی با تابع صلاحیت بهتر، جستجو می کند.

3-6-1- مفاهیم کلیدی الگوریتم ژنتیک
با نگاهی به آنچه که تاکنون مطرح شده مشخص است که در تبیین الگوریتم ژنتیک مباحث کلیدی ذیل باید مورد بررسی قرار گیرند. بنابراین در ادامه این مباحث بررسی خواهند شد:
تعریف یک سیستم کدینگ
ایجاد جمعیت اولیه
تعریف عملیات ژنتیک
تابع برازش55
استراتژی برخورد با محدودیت ها56
3-6-1-1- کدینگ
اولین گام در بکارگیری و پیاده سازی یک الگوریتم ژنتیک نمایش جوابهای مساله بصورت یک کروموزوم است. در حقیقت این عمل یک مفهوم کلیدی در الگوریتم های ژنتیک می باشد که با استفاده از عمل کدینگ ما می توانیم مساله را به زبان برنامه نویسی تبدیل نماییم.

3-6-1-2- ایجاد جمعیت اولیه
اولین مرحله بعد از تعیین تکنیکی که برای تبدیل هر جواب به یک کروموزوم بکار می رود، ایجاد یک جمعیت اولیه از کروموزوم هاست. در این مرحله جواب اولیه معمولا بصورت تصادفی تولید می شود. البته در بعضی موارد با توجه به نوع مساله و برای بالا بردن سرعت همگرایی الگوریتم از روش های ابتکاری نیز استفاده گردیده است.
3-6-1-3- عملگرهای الگوریتم های ژنتیک

دسته بندی : پایان نامه ارشد

پاسخ دهید