— (291)

پایان نامه مقطع کارشناسی ارشد
مهندسی صنایع-صنایع
عنوان :
مساله مکان یابی- تخصیص چند تسهیله ظرفیت بندی شده در حضور منابع فرعی و تقاضای برنولی
استاد راهنما :
دکتر ایرج مهدوی
استاد مشاور :
مهندس صابر شیری پور
دانشجو :
مرتضی علی زاده
دی ماه 1390

تقدیم بهپدر و مادر مهربانم
و
همه آنان که بر ما تاثیر به یادماندنی می گذارند.
تقدیر و سپاسخداوند بزرگ را سپاسگزارم که در سخت ترین لحظات زندگی ام، بدون کوچکترین چشم داشتی، یاری- گر من بوده و با لطف و عنایت او توانسته ام این تحقیق را به پایان برسانم.
عالی ترین و بهترین مراتب سپاس و قدردانی خود را تقدیم به خانواده عزیزم می کنم که همواره در طول زندگی، دلسوزانه مرا یاری نموده و در راه کسب علم و دانش با وجود سختی های بسیار ، پشتیبانم بودند.
در اینجا بر خود لازم می دانم مراتب سپاس و قدردانی خود را تقدیم استاد فرزانه ام جناب آقای دکتر ایرج مهدوی نمایم که با زحمات بی انتهایش مرا در انجام این تحقیق راهنمایی نمودند. همچنین از استاد بزرگوارم جناب آقای مهندس صابر شیری پور به پاس نقطه نظرات و مشاوره ارزشمندشان کمال تشکر را دارم.
تقدیر و تشکر ویژه از دوست عزیزم مهندس حسن اسدی گنگرج که صمیمانه در کلیه مراحل تهیه و تنظیم این تحقیق، همراه و یارم بود. همچنین از تمامی دوستان و عزیزانی که به هر نحوی مرا در انجام این تحقیق یاری رساندند، سپاسگزارم.
چکیدهدر این تحقیق، یک مساله مکان یابی- تخصیص چند تسهیله ای که مشتریان آن دارای تقاضا های احتمالی مبنی بر تابع توزیع شناخته شده ای هستند، را در نظر گرفته شده است(CFLABDS). در این تحقیق، در کنار تسهیلات با محدودیت ظرفیت، می توانیم از منبع فرعی ظرفیت بندی شده هر تسهیل برای تامین تقاضاهای مشتریان استفاده نماییم. در این مساله احتمالی گسسته، هدف پیدا کردن مکان های بهینه تسهیلات از میان مکان های کاندید و تخصیص بهینه مشتریان موجود به این تسهیلات احداث شده می باشد، بطوریکه جمع هزینه های ثابت تسهیلات احداث شده بعلاوههزینه های تخصیص مشتریانبعلاوه مقدار انتظاری هزینه سرویس و هزینه های برون سپاری مینیمم گردد.
مساله پیشنهادی بصورت یک برنامه ریزی غیرخطی عدد صحیح مختلط فرموله شده و سپس با تغییر شکل محدودیت های غیرخطی به محدودیت های خطی، یک نسخه ساده تر مدل بدست آمده است. نتایج عددی نشان می دهند که نرم افزار 9LINGO برای حل مسائل با اندازه های کوچک کارا می باشد. برای مسائل با اندازه های بزرگ، یک الگوریتم فرا ابتکاری به نام الگوریتم ژنتیک به منظور بهینه سازی پیشنهاد شده است. نتایج محاسباتی نشان می دهند که الگوریتم پیشنهادی بطور قابل قبولی به جواب ها دست می یابد.
کلمات کلیدی:
مساله مکان یابی- تخصیص با محدودیت ظرفیت، تقاضاهای برنولی، برنامه ریزی غیرخطی عدد صحیح مختلط، تابع برون سپاری، الگوریتم ژنتیک.
فهرست مطالب
TOC \o “1-3” \h \z \u تقدیمبه PAGEREF _Toc315519179 \h ‌جتقدیروسپاس PAGEREF _Toc315519180 \h ‌دچکیده PAGEREF _Toc315519181 \h ‌هفصلاول:کلیاتتحقیقوساختارپایاننامه PAGEREF _Toc315519182 \h 11-1- مقدمه PAGEREF _Toc315519183 \h 21-2- ساختارپایاننامه PAGEREF _Toc315519184 \h 6فصلدوم:مروریبرادبیاتموضوعیمسائلمکانیابی- تخصیصباتقاضایاحتمالی PAGEREF _Toc315519185 \h 72-1- مقدمه PAGEREF _Toc315519186 \h 8فصلسوم :زمینههایعلمیتحقیق PAGEREF _Toc315519187 \h 173-1- مقدمه PAGEREF _Toc315519188 \h 183-2- دستهبندیکلیمسائلبرنامهریزیتسهیلات PAGEREF _Toc315519189 \h 203-3- دستهبندیمسائلمکانیابیبانگرشسنتی PAGEREF _Toc315519190 \h 203-4- دستهبندیمسائلمکانیابیبانگرشنوین PAGEREF _Toc315519191 \h 223-5- مسائلمکانیابی- تخصیص PAGEREF _Toc315519192 \h 243-5-1- طبقهبندیمسالهمکانیابی- تخصیص PAGEREF _Toc315519193 \h 243-5-2- انواعمدلهایمکانیابی- تخصیص PAGEREF _Toc315519194 \h 263-6- تشریحالگوریتمژنتیک PAGEREF _Toc315519195 \h 333-6-1- مفاهیمکلیدیالگوریتمژنتیک PAGEREF _Toc315519196 \h 343-6-2- ساختارکلیالگوریتمژنتیک PAGEREF _Toc315519197 \h 41فصلچهارم : ارائهمدلریاضیوالگوریتمپیشنهادی PAGEREF _Toc315519198 \h 434-1- مقدمه PAGEREF _Toc315519199 \h 444-2- ساختارمساله PAGEREF _Toc315519200 \h 454-2-1- توصیفتابعبرونسپاری PAGEREF _Toc315519201 \h 494-3- مدلریاضیپیشنهادی PAGEREF _Toc315519202 \h 524-3-1- سادهسازیمدلپیشنهادی PAGEREF _Toc315519203 \h 544-4- الگوریتمژنتیک PAGEREF _Toc315519204 \h 574-4-1- نمایشکروموزوم PAGEREF _Toc315519205 \h 584-4-2- آغازسازی PAGEREF _Toc315519206 \h 594-4-3- ارزیابی PAGEREF _Toc315519207 \h 604-4-4- عملگرانتخاب PAGEREF _Toc315519208 \h 614-4-5- نخبهگرایی PAGEREF _Toc315519209 \h 624-4-6- عملگرتقاطع PAGEREF _Toc315519210 \h 624-4-7- عملگرجهش PAGEREF _Toc315519211 \h 684-4-8- معیارتوقف PAGEREF _Toc315519212 \h 704-5-1- مسائلنمونه PAGEREF _Toc315519213 \h 72فصلپنجم : نتیجهگیریوپیشنهاداتآتی PAGEREF _Toc315519214 \h 845-1- نتیجهگیری PAGEREF _Toc315519215 \h 855-2- پیشنهاداتآتی PAGEREF _Toc315519216 \h 86مراجع PAGEREF _Toc315519217 \h 87مراجعفارسی PAGEREF _Toc315519218 \h 88مراجعلاتین PAGEREF _Toc315519219 \h 89Abstract PAGEREF _Toc315519220 \h 93
فهرست شکل ها
فصل سوم
TOC \h \z \c “شکل 3-” شکل (3- 1).دستهبندیکلیمسائلبرنامهریزیتسهیلات[1]. PAGEREF _Toc313266732 \h 20شکل (3- 2). دستهبندینوینمسائلمکانیابی [1]. PAGEREF _Toc313266733 \h 23
فصل چهارم
TOC \h \z \c “شکل 4-“شکل(4- 1). t- امینکروموزومهایصفرویک yiوχij PAGEREF _Toc313266815 \h 58شکل(4- 2). t- امینکروموزومهایعددصحیحrii’و vii’ PAGEREF _Toc313266816 \h 59شکل (4- 3). نحوهعملکردعملگرتقاطعنوع 1 PAGEREF _Toc313266817 \h 64شکل (4- 4). فرآیندعملگرتقاطعنوع 2 برایکروموزوممکانyi PAGEREF _Toc313266818 \h 65شکل (4- 5). فرآیندعملگرتقاطعنوع 2 برایکروموزومتخصیص χij PAGEREF _Toc313266819 \h 66شکل (4- 6). فرآیندعملگرتقاطعنوع 3 برایکروموزوممکانyi PAGEREF _Toc313266820 \h 67شکل (4- 7). فرآیندعملگرتقاطعنوع 3 برایکروموزومتخصیص χij PAGEREF _Toc313266821 \h 67شکل (4- 8). فرآیندعملگرجهشنوع 1 برایکروموزوممکانyi PAGEREF _Toc313266822 \h 68شکل (4- 9). فرآیندعملگرجهشنوع 1 برایکروموزومتخصیص χij PAGEREF _Toc313266823 \h 68شکل (4- 10). فرآیندعملگرجهشنوع 2 برایکروموزوممکانyi PAGEREF _Toc313266824 \h 69شکل (4- 11). فرآیندعملگرجهشنوع 2 برایکروموزومتخصیص χij PAGEREF _Toc313266825 \h 69شکل (4- 12). فرآیندعملگرجهشنوع 3 برایکروموزوممکانyi PAGEREF _Toc313266826 \h 69شکل (4- 13). فرآیندعملگرجهشنوع 3 برایکروموزومتخصیص χij PAGEREF _Toc313266827 \h 70شکل (4- 14). فلوچارتالگوریتمژنتیکپیشنهادی PAGEREF _Toc313266828 \h 71
فهرست جداول
TOC \h \z \c “جدول 4-“جدول (4- 1). مقادیرپارامترهایGA PAGEREF _Toc313268494 \h 73جدول (4- 2). نتایجمحاسباتیبرایمسائلاندازهکوچک PAGEREF _Toc313268495 \h 74جدول (4- 3). مقادیرپارامترهای fiوαi PAGEREF _Toc313268496 \h 75جدول (4- 4). مقادیرپارامتر θj PAGEREF _Toc313268497 \h 75جدول (4- 5). مقادیرپارامتر dij PAGEREF _Toc313268498 \h 76جدول (4- 6). مقادیرپارامترcij PAGEREF _Toc313268499 \h 77جدول (4- 7). مقادیرپارامترβii’ PAGEREF _Toc313268500 \h 78جدول (4- 8). نتایجبدستآمدهبرایمثالنمونه PAGEREF _Toc313268501 \h 78جدول (4- 9). نتایجمحاسباتیبرایمسائلاندازهبزرگ PAGEREF _Toc313268502 \h 81
فصل اول:کلیات تحقیق و ساختار پایان نامه1-1- مقدمهیکی از مسائلی که باید در مراحل اولیه طراحی سیستم های صنعتی مورد توجه قرار گیرد مساله مکان- یابی و استقرار تسهیلات است. مطالعه پیرامون مکان بهینه صنعتی از دیدگاه جغرافیدانان و علمای علم اقتصاد همواره دارای اهمیت و اولویت بوده است. مراکز صنعتی و کارخانجات برای تعیین مکان احداث کارخانه، استقرار تجهیزات و دپارتمان های خود در کارخانه، استقرار دفاترشان در سطح شهر، تعیین مراکز توزیع محصولات و… با چنین مسائلی سروکار دارند [1]. در ادبیات موضوعی، معمولا چند حالت از مسائل مکانیابی گسسته و تخصیص مورد بحث قرار گرفتند، مانند مساله مکان یابی تک تسهیله، مساله مکان یابی چند تسهیله، مسالهمکان یابی- تخصیص. در مساله مکان یابی تک تسهیله، هدف پیدا کردن مکان تسهیل جدید می باشد، بطوریکه مجموع فواصل وزن دهی شده بین تسهیل جدید و تسهیلات موجود حداقل گردد. چند مثال ساده از مسائل مکان یابی تک تسهیله عبارتند از مکان یابی یک بیمارستان، یک ایستگاه آتش نشانی یا یک کتابخانه در یک منطقه شهری ، مکان یابی یک فرودگاه جدید جهت ارائه خدمات به تعدادی پایگاه نظامی. همچنین مساله مکان یابی چند تسهیله بدنبال پیداکردن مکان های بهینه بیش از یک تسهیل جدید با توجه به مکان های تسهیلات موجود می باشد. کاربردهای زیادی از این مساله توسط استرش[2] ارائه شده اند، مانند تاسیس چندین انبار برای سرویس دهی به تعداد مشخصی از مناطق. بنابراین مساله مکان یابی تک تسهیله حالت خاصی از مساله مکان یابی چند تسهیله می باشد.هدف مساله مکان یابی – تخصیص، پیدا کردن مکان بهینه ی مجموعه ای از تسهیلات است بطوریکه، هزینه ی حمل و نقل از این تسهیلات به مشتریان مینیمم گردد. ازاینرو، در این مساله باید تعداد بهینه ای از تسهیلات بمنظور تامین تقاضای مشتریان در مکان های مناسب تاسیس گردند. در گونه ای از مسائل مکان یابی-تخصیص، با محدودیت ظرفیت تسهیلات مواجه هستیم. این محدودیت منجر به این امر می شود که تسهیل موردنظر نتواندتمام تقاضای یک نقطه مشتری را برآورده کند. لذا این امکان وجود دارد که کل تقاضای یک مشتری بین کارخانجات مختلف تقسیم شود و هر کارخانه کسری از تقاضای یک مشتری را تامین نماید.
1-2- تعریف مسئله
با توجه به اینکه در دنیای واقعی، فضای اطلاعات معمولا غیرقطعی و احتمالی است، لذا مسائل مکان یابی نیز از این مقوله مستثنا نیستند. اغلب در مسائل مکان یابی فرض شده است که تقاضای مشتریان جهت دریافت سرویس جز ورودی های مساله بوده و قطعی هستند. واضح است که این امر در عمل کمتر اتفاق می افتد و معمولا سطح بالایی از عدم قطعیت در تقاضای مشتریان وجود دارد. بنابراین از دیگر مسائلی که بهمراه مسائل مکان یابی-تخصیص در دنیای واقعی موجود است، تقاضای احتمالی می باشد، که افق جدیدی را پیش روی ما نهاده است. مدل پیشنهادی این تحقیق، یک مسئله مکان یابی-تخصیص چند تسهیله ظرفیت دهی شده با تقاضاهای احتمالی که دارای تابع توزیع برنولی می باشند، است. همچنین در این مدل هر تسهیل دارای یک منبع فرعی ظرفیت دهی شده می باشد که می تواند در صورت نیاز از آن استفاده کند.
1-3- اهداف تحقیق
همانطور که در تعریف مسئله ارائه شده این تحقیق در درجه اول یک مسئله مکان یابی و تخصیص بوده و به دنبال پیدا کردن مکان بهینه تعداد بهینه ای از تسهیلات از میان مجموعه ای از نقاط کاندید و تخصیص مشتریان موجود به تسهیلات احداث شده است. در این تحقیق هر تسهیل دارای یک منبع فرعی بوده که می-تواند در صورت نیاز از آن استفاده کرده و یا آن را در اختیار دیگر تسهیلات قرار دهد. بعبارت دیگر تعامل بین تسهیلات و همچنین تعامل بین یک تسهیل و منابع فرعی دیگرتسهیلات امکان پذیر است. تسهیلات و منابع فرعی در نظر گرفته شده برای آنها دارای ظرفیت محدود هستند. لازم به ذکر است که بدانیم محدودیت ظرفیت هر تسهیل مانع از تخصیص بیش از ظرفیتش به آن تسهیل نمی گردد و در ادامه تحقیق این ویژگی بطور مفصل تفسیر خواهد شد. از اینرو در این مدل این احتمال وجود دارد که تعداد مشتریان تخصیص یافته به هر تسهیل بیش از ظرفیتش بوده و تسهیل مورد نظر جهت سرویس دهی به مشتریانش مجبور به رجوع به منبع فرعی خود و یا دیگر تسهیلات و منابع فرعیشان گردد که این عمل برون سپاری نامیده می شود.
با بیان این مطالب می توان بطور خلاصه اذعان داشت که مدل ارائه شده در این تحقیق به دنبال کمینه کردن مجموع هزینه های مکان یابی تسهیلات، هزینه های تخصیص مشتریان، هزینه های انتظاری سرویس دهی به مشتریان و هزینه های انتظاری برون سپاری تسهیلات است.
1-4- مفروضات تحقیق
فرضیات مساله پیشنهادی بصورتذیل در نظر گرفته شده اند:
با مسئله مکان یابی-تخصیص چند تسهیله با ظرفیت محدود بهمراه تقاضاهای برنولی و منابع فرعی سروکار داریم، یعنی هدف یافتن مکان های بهینه مجموعه ای از تسهیلات در میان تعداد محدودی از نقاط کاندید و تخصیص مشتریان موجود با تقاضاهای برنولی به تسهیلات احداث شده می باشد، بطوریکه مجموع هزینه های مکان یابی، تخصیص مشتریان، هزینه انتظاری سرویس دهی به مشتریان و هزینه مقدار انتظاری تابع برونسپاری مینیمم گردد.
مساله برای کل افق برنامه ریزی در ابتدای دوره سیاست گذاری می کند، یعنی مسئله مکان یابی ایستا می باشد.
فضای حل مسئله گسسته بوده و تعداد نقاط کاندید برای مکان تسهیلات معین می باشد.
هر تسهیل دارای یک منبع فرعی بوده که می تواند در صورت نیاز از آن استفاده کند.
هرتسهیل و منبع فرعی آن دارای ظرفیت محدود هستند.
هر مشتری موجود دارای مکان ثابت و تقاضای احتمالی با تابع توزیع برنولی می باشد.
در این مدل علاوه بر تعامل میان تسهیلات احداث شده و مشتریان موجود، تعامل بین تسهیلات احداث شده با یکدیگر و همچنین تعامل میان یک تسهیل و منبع فرعی خودش ومنبع فرعی دیگر تسهیل نیز امکان پذیر می باشد.
1-5- ساختار پایان نامهدر ادامه در فصل 2، ادبیات موضوعی مسائل مکان یابی-تخصیص با تقاضاهای برنولی را مورد بررسی قرار خواهیم داد. در فصل 3، زمینه های علمی تحقیق شامل دسته بندی مسائل مکان یابی، مقوله عدم قطعیت و احتمالی بودن تقاضای مشتریان، مساله مکان یابی-تخصیص و الگوریتم ژنتیک بطور مفصل تشریح خواهند شد. در فصل 4، به تشریح مساله و مدل پیشنهادی پرداخته و برخی از ویژگی های مدل را بررسی خواهیم نمود. با توجه به پیچیدگی های مدل پیشنهادی، یک الگوریتم فراابتکاری بنام الگوریتم ژنتیک برای حل مسائل با مقیاس بزرگ معرفی شده است. در ادامه این فصل، چند مثال نمونه ای به منظور نشان دادن کارائی و دقت الگوریتم فراابتکاری پیشنهادی حل شده اند و نتایج محاسباتی مربوطه را مورد بررسی قرار خواهیم داد. در نهایت، تعدادی توسعه های آتی به همراه نتیجه گیری در فصل 5 ارائه شده اند.
فصل دوم:مروری بر ادبیات موضوعی مسائل مکان یابی- تخصیصبا تقاضای احتمالی2-1- مقدمهمسائل مکان یابی- تخصیص چندتسهیله، یکی از حوزه های گسترده در مدل سازی ریاضی در دنیای واقعی می باشند، که در این مسائل چند تسهیل جدید (تسهیل عرضه) به مجموعه ای از مشتریان موجود، با توجه به تقاضاهایشان، سرویس می دهند.
در ادبیات موضوعی، معمولا چند حالت مختلف از مسائل مکان یابی پیوسته مانند مساله مکان یابی میانه (تک تسهیله)، مساله مکان یابی میانه (چند تسهیله)، ، مساله مکان یابی گسسته و مساله مکان یابی-تخصیصمورد بحث قرار می گیرند. مسائل مکان یابی تسهیل، مکان یک مجموعه از تسهیلات (منابع) را به منظور کمینه کردن هزینه های تامین مجموعه هایی از تقاضاها (مشتریان) با توجه به تعدادی محدودیت، را تعیین می کند.
مطالعه برروی تئوری مکان یابی، رسما در سال 1909 وقتی که آلفرد وبر [3] در نظر گرفت که چگونه مکان یک انبار را بمنظور مینیمم کردن فاصله بین انبار و چندین مشتری تعیین نماید، آغاز شد. بعد از آن تئوری مکان یابی در بخش های مختلفی بکار گرفته شد. حکیمی [4] در پی تحقیقی، سعی در پیدا کردن مراکز مخابرات در یک شبکه ارتباطات و ایستگاه های پلیس در بزرگراه ها داشت.در مساله مکان یابی میانه(تک تسهیله) کلاسیک که غالبا مسئله وبر و مسئله حداقل مجموع نیز نامیده می شود، در صدد یافتن مکان تسهیل جدید هستیم بطوریکه مجموع فواصل وزن دهی شده با تسهیلات موجود، حداقل گردد. برای کسب اطلاعات بیشتر در این زمینه به فراهانی و حکمت فر [5] و نیکل و پارتو [6] مراجعه کنید.
زعفرانیه و همکاران [7] الگوریتمی برای مساله جایابی تک تسهیله در دو منطقه با نرم های متفاوت پیشنهاد داده اند و نشان داده اند که حل بهینه در تقاطع متعامد تسهیلات موجود است. این مسئله در حقیقت تعمیم یافته مساله جایابی تک تسهیله است.ردریگرز و همکاران [8] مدلی را برای مساله جایابی تک تسهیلاتی ناخوشایند پیشنهاد داده اند. در این پژوهش مجموعه ای متناهی از حل بهینه برای یک مساله با فاصله اقلیدسی تعیین گشته است.بریمبرگ و جول [9] یک روش خط سیر را برای ایجاد یک مرز کارایی نقاط برای یک مدل دو معیاره جایابی یک وسیله نیمه خوشایند در صفحه مورد بررسی قرار داده اند. معیار اول برای اندازه گیری هزینه حمل و نقل و دومی برای تخمین هزینه اجتماعی یا محیطی مورد استفاده قرار گرفته است. در اینجا وزن های نسبی به گونه ای تغییر می کنند که مجموع وزن های دو معیار مینیمم گردد.در مساله مکان یابی چند تسهیله حداقل مجموع در صدد یافتن مکان های تسهیلات جدید با توجه به مکان های تعدادی تسهیل موجود هستیم،بطوریکه مجموع فواصل بین تسهیلات جدید و فواصا بین تسهیلات جدید و تسهیلات موجود کمینه گردد. حال آنکه مساله مکان یابی چند تسهیله حداقل حداکثر به دنبال پیداکردن مکان یک مجموعه از تسهیلات جدید در میان تسهیلات موجود است با این هدف که ماکزیمم فواصل وزن دهی شده بین همه تسهیلات را مینیمم کند. لوین و بن [10] یک روش ابتکاری برای مسائل جایابی چند تسهیلاتی با مقیاس بالا پیشنهاد داده اند به گونه ای که مشتریان با استفاده از طبقه بندی دوباره نزدیکترین مرکز دوباره به تجهیزات تخصیص داده می شوند. ژانگ و روشتن [11] به بررسی مساله جایابی چندتسهیلاتی در سرویس های خدماتی رقابتی پرداخته اند. تابع هدف پیشنهادی یک مقیاس مطلوبیت فضایی کاربران را با توجه به محدودیت های زمان انتظار کاربران و بودجه مالکین تسهیلات، بیشینه می کند. همچنین برای اطلاعات بیشتر در این زمینه به دوبسن و کرمارکار [12] و لاو و همکارانش[13] مراجعه کنید. مساله مکان یابی انبار ابتدا توسط کوهن و هبمورگر [14] مطالعه شد. آنها الگوریتم ابتکاری پایه ای drop, add and swap را برا حل این مساله توسعه دادند. بعد از آنها خوماوالا [15] الگوریتم شاخه و حد را بر اساس فرمولبندی ضعیف ارائه کردند. فرمولبندی قوی خطی توسط ارلنکتر [16] استفاده شد تا رویه محاسباتی ارائه کتد که شاید موثرترین و سهل الوصول ترین ابزار برای حل این دسته از مسائل باشد. نتایج کار وی در گویناردو اسپیلبرگ [17] ارائه شده است. یک خلاصه عالی از مسئله مکان یابی بدون محدودیت ظرفیت نیز توسط کرنوجلس و همکارانش [18] گردآوری شده است.
مساله مکان یابی به دنبال پیدا کردن مکان های بهینه مجموعه ای از تسهیلات بمنظور تامین درخواست های تقاضای مجموعه ای از مشتریان می باشد. اغلب فرض شده است که درخواست تقاضای مشتریان معین و قطعی بوده و به عنوان بخشی از پارامترهای ورودی مساله است. واضح است که این امر در عالم واقعیت کمتر اتفاق می افتد و معمولا تقاضای مشتریان با یک سطح بالایی از عدم قطعیت همراه است. مثال های ساده ای از مسائل مکان یابی با تقاضاهای غیرقطعی، جاییکه سطوح تقاضا طی دوره های زمانی مختلف، تغییر می کنند عبارتند از مساله سرویس های پستی، فرودگاه ها، سوپرمارکت ها، انبارهای توزیع کالاها با تقاضا های فصلی. براندو و چیو [19] و لووکس[20] و اسنایدر [21] جنبه های مختلف مسائل مکان یابی احتمالی را مورد مطالعه قرار دادند. یک مساله مکان یابی صف احتمالی، بمنظور ماکزیمم کردن عملکرد سیستم توسط ماریانو و روله [22] مورد مطالعه قرار گرفت. آنها یک مدل احتمالی را طراحی کردند که در پی ماکزیمم کردن جمعیت تحت حمایت وسایل نقلیه اورژانس با سطح دسترسی α است. در این مدل سطح دسترسی وسایل نقلیه با استفاده از تئوری صف محاسبه می گردد. پن و همکاران [23] یک مدل دو مرحله ای برای یک خرده فروش حاکم در یک زنجیره تامین تولیدکننده-خرده فروش با تقاضاهای احتمالی در یک محیط قیمتی نزولی را ارائه کردند. این مدل بدنبال یکپارچه کردن پیش بینی تقاضا و تصمیمات راجع به قیمت و سفارش و پیدا کردن خطی و مشی قیمتی و سفارشی بهینه برای خرده فروش حاکم بمنظور ماکزیمم کردن سود انتظاری از یک محصول در دو دوره زمانی است.
شاید ساده ترین مساله، مکان یابی گسسته موردی باشد که یک تسهیل جدید قرار است مستقر شود. به عبارتی از بین تعداد محدودی سایت، مثلا n، باید یکی انتخاب شود. با فرض اینکه هزینه ی سالیانه استقرار تسهیل جدید در هر کدام از سایت ها مشخص است، جواب بدیهی این مسئله استقرار تسهیل جدید در سایتی است که کمترین هزینه را دارد. هنگامیکه که قرار است دو یا تعداد بیش تری تسهیل مستقر شوند وn سایت ممکن در دسترس است مساله مکان یابی دشوارتر می شود. در حقیقت هنگامیکه mتسهیل جدید و n سایت ممکن وجود دارد، بطوریکه m≤n، تعداد تخصیص های ممکن برابر باnmm!=n!n-m!است. با بزرگترشدن n, m تعداد گزینه های ممکن به سرعت افزایش می یابد به گونه ای که روش شمارش کامل (محاسبه و مقایسه هزینه همه گزینه ها) برای حل این مسائل ناکارآمد است. برای حل چنین مسائلی مدل تخصیص مفید است. مساله مکان یابی-تخصیص بدنبال پیدا کردن مکان بهینه یک مجموعهای از تسهیلات است بطوریکه هزینه ی حمل و نقل از تسهیلات به مشتریان موجود کمینه گردد و همچنین یک تعداد بهینه از تسهیلات بمنظور تامین تقاضاهای مشتریان باید گمارده شوند. در مساله مکان یابی-تخصیص گسسته، آنچه باید تعیین شود، تعداد و مکان تسهیلات جدید از میان یک تعداد متناهی مکانهای بالقوه و تخصیص تقاضاهای مشتریان مشخص به این تسهیلات است. در ابتدا کوپر [24]مسئلهکلاسیک مکان یابی-تخصیص را با دو تسهیل جدید و هفت نقطه ی تقاضا پیشنهاد نمود. کوپر ثابت کرد که تابع هدف این مساله نه مقعر است و نه محدب و شاید شامل چند جواب بهینه محلی باشد. از اینرو طبق گفته ی هنریک و روبرت [25] مسئله کلاسیک مکان یابی-تخصیص در حوزه مسائل بهینه سازی سراسری است. پس از کوپر مسئله مکان یابی-تخصیص شبکه و بسیاری مدل دیگر توسط بدری [26] ارائه شدند.گن و چنگ [27 ، 28] مسئلهمکان یابی-تخصیص را بطور مفصل مورد مطالعه قرار داده و در مورد همه انواع آن بحث کردند.
روله و الزینگا [29] یک مساله مکان یابی چندتسهیله ای را که در آن هر ناحیه تعریف شده حداقل به یک تسهیل تخصیص می یابد را درنظر گرفتند. در مدل پیشنهادی آنها نواحی تعریف شده کاملا از یکدیگر مستقل بوده و هیچ نوع تعامل میان آنها نمی باشد. برمن و همکاران [30] یک مدل مکان یابی- تخصیص تک تسهیله ای را ارائه کردند که در آن بر خلاف کار روله و الزینگا، تعامل میان نواحی امکان پذیر بوده است. البته هر دوی این کارها یک حالت خاصی از مدل ارائه شده توسط روله و سووین [31] هستند.
در مدل های قطعی مسائل مکان یابی- تخصیص، فرض شده است که درخواست تقاضای مشتریان کاملا مشخص و قطعی می باشد که البته این امر در جهان واقعی کمتر اتفاق می افتد. وقتی حالت قطعی در تقاضای مشتریان درنظر گرفته می شود، ما دقیقا نمی دانیم که کدام مشتری درخواست تقاضا دارد و کدامیک ندارد. بنابراین یک رویکرد معقول این است که درخواست تقاضای مشتریان بطور تصادفی اتفاق بیافتد که این امر منجر به افزایش حالت های احتمالی در مساله مکان یابی چند تسهیله می گردد. لوگندران و ترل [32] یک مساله مکان یابی- تخصیص بودن محدودیت ظرفیت را در حضور تقاضاهای احتمالی قیمت محور در نظر گرفتند و یک مدل بهینه سازی بمنظور ماکزیمم کردن سود خالص انتظاری پیشنهاد کردند. آنها یک روش ابتکاری برای حل مسائل با اندازه متوسط و بزرگ ارائه کردند. لووکس و پیترز [33] یک مساله مکان یابی تسهیل با ظرفیت نامحدود و تقاضاهای احتمالی را پیشنهاد کردند. آنها مجموعه ای از سناریوهایی را برای مساله درنظر گرفتند که با احتمالات خاص اتفاق می افتند.شرالی و ریزو [34] یک مساله مکان یابی- تخصیص ظرفیت بندی شده با تقاضایمستمررا بر روی یک نمودار زنجیری ارائه کردند.کاریزوسا و همکاران [35] یک مساله مکان یابی- تخصیص، جاییکه نواحی مکان های مشتریان و تسهیلات ممکن است با توزیع های احتمال متفاوتی نزدیک به یکدیگر باشند را مورد کنکاش قرار دادند.زو [36] یک مدل برنامه ریزی مقدار انتظاری با احتمال اجباری برای مساله مکان یابی- تخصیص با ظرفیت نامحدود و تقاضاهای احتمالی را پیشنهاد کرد.اگرچه مساله مکان یابی- تخصیص احتمالی با محدودیت ظرفیت به وسیله محققین زیادی مورد مطالعه قرار گرفت ولی به خاطر پیچیدگی مساله هیچ مدل برنامه ریزی احتمالی عمومی ای برای آن ارائه نگردید تا اینکه زو و لیو [37] سه مدل احتمالی عمومی، که کاملا از مدل های برنامه ریزی احتمالی پیشین متفاوت می باشند را ارائه کردند. این مدل ها عبارتند از: مدل مقدار انتظاری، برنامه ریزیاحتمال اجباریو برنامه ریزیاحتمال وابسته. همچنین محققین، الگوریتم سیمپلکس شبکه ای، شبیه سازی های احتمالی و الگوریتم ژنتیک را به منظور حل کارای مساله با یکدیگر یکپارچه کردند. لاپورت و همکارانش [38] یک مساله فروشنده دوره گرد را با تقاضا های احتمالی(PTSP) مورد مطالعه قرار دادند و یک مدل برنامه ریزی خطی ای که با رویکرد شاخه و برش حل می شود را ارائه کردند. از آنجاییکه مسائل PTSPبه دلیل ترکیب مسالهTSP و حالت احتمالی تقاضا، از جمله مسائل زمان بر در حل هستند، آنها یک الگوریتم دقیق برای حل این مساله ارائه کردند. بعداز آن، بیانچی و کمبل [39] یک روش ابتکاری برای حل مساله PTSPجاییکه همه مشتریان دارای احتمال یکسان برای تقاضا هستند، را پیشنهاد کردند. آنها یکمسئلهفروشندهدورگرداحتمالیناهمگنراتوسعهداده و الگوریتمهای حل مختلفیبرایحالتناهمگنپیشنهادکردند.مسئله آنها به دنبالپیداکردنمسیریکهکمترینهزینهانتظاریبرایمشتریانیکهدارایتقاضاهایاحتمالیهستند،میباشد. ماریا آلباردا سامبولا و همکاران [40] یک مساله مسیریابی تسهیل احتمالی که دارای مدلی دو مرحله ای است، را بیان کردند. در مرحله اول مدل آنها مجموعه ای از تسهیلات و خانواده ای از مسیرها مشخص می گردند و در مرحله دوم تصمیمات لازم (عمل توسل)به منظور انطباق این مسیرها به مجموعه واقعی مشتریانی که باید تامین گردند، گرفته می شوند. همچنین آنها یک روش ابتکاری برای حل مساله ارائه نمودند.پس از این تحقیق، ماریاآلباردا سامبولا و همکاران [41] بر روی یک مساله مکان یابی- تخصیص در محیط گسسته با تقاضاهای برنولی کار کردند. آنها دو نوع تصمیمی (عمل توسل) که مرتبط با مدل برنامه ریزی احتمالی دو مرحله ای می باشند، را درنظر گرفتند. برای هر نوع تصمیم، آنها یک روش تقریبی برای محاسبه مقدار انتظاری که تاثیر حالت احتمالی را بر روی مساله تخمین می زند، ارائه کردند. مجموعه جواب حاصله از مرحله اول شامل مکان های تسهیلات و نحوه تخصیص مشتریان به تسهیلات و مجموعه جواب مرحله دوم تخمینی از مقدار انتظاری تابع تصمیم گرفته شده (تابع توسل) می باشد.
از آنجایی که مسئله مکان یابی-تخصیص یک مسئله NP-hard است [42] ، دستیابی به جواب بهینهیکی از دغدغه های اصلی مساله می باشد. روش های حل مسائل مکان یابی-تخصیص به سه دسته اصلی طبقه بندی می شوند: روش های دقیق ، روش های ابتکاری و روش های فراابتکاری. از جمله روش های دقیق می توان به الگوریتم شاخه و کران که توسط کونه و سولند [43] برای مساله چند منبع ای وبر اجرا شده است اشاره کرد. روش های ابتکاری زیادی برای پیدا کردن جواب های بهینه مسئله کلاسیک مکان یابی-تخصیص به خوبی اندک الگوریتم های دقیق ارائه شده اند.روش های ابتکاری بمنظور حل سریع مسائل بزرگ و ایجاد کردن جواب های اولیه خوب برای الگوریتم های دقیق مورد نیاز هستند. اولین روش ابتکاری مشهور، الگوریتم مکان یابی-تخصیص تکراری کوپر [44] است. روش ابتکاری کوپرچندزیرمجموعه از نقاط ثابت ایجاد می کند و سپس هر کدام از آنها را با استفاده از الگوریتم دقیق برای حل یک مسئله مکان یابی تک تسهیله، حل می کند.روش های فرا ابتکاری زیادی نیز برای بدست آوردن جوابهای این گونه مسائل بکار گرفته شده اند، از جمله ، شبیه سازی تبرید (مورای و چرچ [45]) و جستجوی ممنوعه (بریمبرگ و ملادنویچ [46]). همچنین تعدادی الگوریتم پیوندی مانند الگوریتم پیوندی شبیه سازی تبرید و روش وراثت تصادفی (ارنست و کریشنامورسی [47]) و الگوریتم پیوندی روش ساده سازی لاگرانژ و الگوریتم ژنتیک (گنگ و همکاران [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-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)
در خطی و مشی برون سپاری، تقاضاهای برون سپاری شده تسهیل i ام به وسیله منبع فرعی متناظرش با هزینه αi به ازای هرتقاضای برون سپاری شده و به وسیله دیگر تسهیلات و یا منبع فرعیشان بترتیب با هزینه- های βii’و βii’+αi’، i,i’∈I,i’≠iبه ازای هرتقاضای برون سپاری شدهتامین خواهند شد.
از آنجاییکه تسهیل i ام مستقیماً به مشتریان احتمالی تقاضایش سرویس می دهد، از اینرو مقدار انتظاری هزینه سرویس می تواند بصورت ذیل محاسبه گردد:
EθService cost=i∈Ij∈Jfθj=1,pjcijχij=i∈Ij∈Jpjcijχij,(5)
با در نظر گرفتن حالت همگن، این عبارت به صورت عبارت ذیل نمایان می گردد:
EθService cost=i∈Ij∈Jpcijχij,(6)
مطابق با خطی و مشی برون سپاری، مقدار انتظاری هزینه برون سپاری



قیمت: 10000 تومان

متن کامل در سایت homatez.com

About: admin


دیدگاهتان را بنویسید

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