کلمات کلیدی:مکانیابی چند تسهیلی ظرفیت دهی شده، مدلسازی غیر قطعی، مکانیابی پوششی، روش ابتکاری. فهرست مطالبعنوان صفحهفهرست شکلها........... حفهرست جدولها...... طفصل اول : مقدمه و كليات تحقيق......... 11-1 مقدمه.... 21-2 ساختار پایاننامه........ 4فصل دوم: ادبیات و پیشینه تحقیق........ 52-1 مقدمه........ 6فصل سوم: روش تحقیق........ 143-1 مقدمه......... 153-2 دسته بندی کلی مسایل برنامه ریزی تسهیلات173-3 دسته بندی مسایل مکان یابی با نگرشی سنتی173-4 دسته بندی مسایل مکان یابی با نگرشی نوین203-5 مسایل مکان یابی- تخصیص................ 213-5-1 طبقه بندی مساله مکان یابی- تخصیص........... 223-5-2 انواع مدل های مکان یابی- تخصیص................. 24فصل چهارم: مدل ریاضی............................ 3244-1 مقدمه................................. 334-2 مدل جانمایی تسهیلات در سناریوی اول..... 334-2-1 تابع حدود پوشش............................. 344-2-2 مدل قطعی سناریوی اول...................... 364-2-3 مدل با محدودیت احتمالی.................. 394-3 مدل تعیین سیاست تعمیر یا جایگزینی در سناریوی دوم 4154-4 روش ابتکاری مکانیابی – تخصیص ...... 454-4-1 تحلیلحساسیتگامچهارمروشابتکاری.............. 534-5 آزمون تجربی........................... 544-5-1 مدل قطعی 564-5-2 مدل با محدودیت احتمالی.................. 61فصل پنجم: نتیجهگیری و پیشنهادها................. 6655-4 نتیجهگیری............................. 675-5 پیشنهادها برای کارهای آتی............. 67فهرست منابع..................................... 686مراجع فارسی................................ 69مراجع لاتین................................. 69چکیده انگلیسی................................... 74 فهرست شکلهاعنوان صفحهشکل 3- 1. دستهبندی کلی مسایل برنامهریزی تسهیلات.. 17شکل 3- 2. دستهبندی نوین مسایل مکانیابی ......... 20شکل 4-1. تابع تقاضا............................. 35شکل 4-2. وضعیت تسهیلات تخصیص داده شده و مرکز زلزله42شکل 4-3. مکانهای نقاط تقاضا در ایالت لسآنجلس.... 55شکل 4-4. مقایسه روش ابتکاری مکانیابی- تخصیص و شبیهسازی تبرید57 فهرست جدولهاعنوان صفحهجدول 4-1. پارامترهای ورودی مساله اول............ 50جدول 4-2. خروجیهای مساله اول.................... 51جدول 4-3. پارامترهای ورودی مساله دوم............ 51جدول 4-4. خروجیهای مساله دوم.................... 52جدول 4-5. خروجیهای مسایل نمونه.................. 52جدول 4-6. خروجیهای مساله اول در حالت تغییر مساله53جدول 4-7. پوشش از مدل قطعی با استفاده از الگوریتم 58جدول 4-8. پوشش از مدل قطعی با استفاده از الگوریتم شبیهسازی تبرید................................................ 58جدول 4-9. پوشش از مدل قطعی با استفاده از الگوریتم تحت و ................................................ 59جدول 4-10. پوشش از مدل قطعی با استفاده از الگوریتم تحت و ................................................ 59جدول 4-11. پوشش از مدل قطعی با استفاده از الگوریتم تحت و ................................................ 59جدول 4-12. پوشش از مدل قطعی با استفاده از الگوریتم تحت و ................................................ 60جدول 4-13. پوشش از مدل قطعی با استفاده از الگوریتم تحت و ................................................ 60جدول 4-14. پوشش از مدل قطعی با استفاده از الگوریتم تحت و ................................................ 61جدول 4-15. پوشش از مدل محدودیت احتمالی.......... 62جدول 4-16. نسبت پوشش از تحت یک تقاضای تصادفی برای بهترین پوشش ممکن شناخته شده............................ 64جدول 4-17. نسبت عملکرد به در پاسخ به تقاضا تصادفی 65فصل اولمقدمه و کلیات تحقیق 1-1- مقدمهیکی از اتفاقاتی که بیشتر شهرهای جهان با آن مواجهاند، سوانح طبیعی است. سانحه یا بحران، رویداد یا واقعهای ناگهانی است که با آسیبهای انسانی و مادی گسترده همراه بوده و نیازمند انجام اقدامات فوری است.سوانح طبیعی بدون آن که بشر قادر به تاثیرگذاری مستقیم بر آن باشد، اتفاق میافتد و زندگی انسان را به مخاطره میاندازد. کشور ما از جمله کشورهای آسیبپذیر دنیا در برابر بلایای طبیعی است که در صورت وقوع آنها نیازهایی جدید مطرح میشود، الگوهای مرسوم و متعارف زندگی بر هم زده میشوند و انسانها در شرایط روحی و روانی خاصی قرار میگیرند. از طرفی، سوانح و بحرانها اغلب ناگهانی هستند و در صورت تدریجی بودن نیز به بشر فرصت کافی نمیدهند و ضایعات، خسارات و تخریبهای شدید محیطی را به دنبال دارند.بهطورطبيعي،اولين اقدام انساندربرخوردبابحرانوسوانحعبارتستازنجاتوكاهشاثراتواقعهكهباوجودزمان بسياركمنيازبهواكنش سريعدارد.واكنشسريعكهبخشبسيارمهممديريتبحرانراتشكيل میدهد،شاملشناسایي،ارزشيابي،تصميمگيريو اقداماتاضطراريموقتاستكهتمام مراحلاينواكنشدرزمانبسياركوتاهحتيگاهيدرچندساعتصورت ميگيرد. در نتیجه، يكيازاقدامات درمديريتبحرانانديشيدن تدابيريبه منظورامدادرسانيپسازوقوعاست. زیرا سوانح طبیعی علاوه بر تلفات انسانی موجب تخریب مراکز تولید موادغذایی (کارخانجات صنایع غذایی، مرغداریها، کشتارگاهها)، مراکز ذخیره مواد غذایی (انبارها، سردخانهها، سیلوها) و مراکز توزیع مواد غذایی و دارویی و خدماتی (فروشگاهها، مراکز پخش و غیره) میشوند و در نتیجه میان مردم اضطراب و نگرانی شدیدی پدید میآورند.در این پایاننامه سعی بر اینست تا با ارایه مدلی ریاضی تحت دو سناریو مکان بهینه برای ایجاد مراکز کمکرسانی به افراد خسارت دیده در یک منطقه ارایه شود که در آن، سطوح پوششی با توجه به شدت و مرکز حادثه در نظر گرفته میشوند و به این نکته توجه میشود که حادثه میتواند تسهیلات را نیز تحت تاثیر قرار دهد. مدل ارایه شده در سناریوی اول توسط مورالی و همکاران [2]ارایه شده است و مدل سناریوی دوم مدل پیشنهادی این تحقیق بوده است. فرضیات مساله پیشنهادی بدین قرارند: 1-2- ساختار پایان نامه در ادامه در فصل 2، ادبیات موضوع مسایل مکانیابی- تخصیص را بررسی میکنیم. در فصل 3، زمینههای علمی تحقیق شامل دستهبندی مسایل مکانیابی، مقوله عدم قطعیت و احتمالی بودن تقاضای مشتریان و مساله مکانیابی- تخصیص به طور مفصل تشریح میشوند. در فصل 4، به تشریح مساله و مدل پیشنهادی میپردازیم و برخی از ویژگیهای مدل را بررسی میکنیم. با توجه به پیچیدگی مدل پیشنهادی، یک الگوریتم ابتکاری برای حل مسایل با مقیاس بزرگ ارایه میشود. در ادامه این فصل، یک آزمون تجربی به منظور نشان دادن کارایی و دقت الگوریتم ابتکاری پیشنهادی انجام میشود و نتایج محاسباتی مربوط بحث و بررسی میشوند. سرانجام پیشنهادهایی برای توسعههای آتی به همراه نتیجهگیری در فصل 5 ارایه میشوند.فصل دومادبیات و پیشینه تحقیق 2-1- مقدمهمسایل مکانیابی- تخصیص چندتسهیلی، زمینهای گسترده در مدلسازی ریاضی در دنیای واقعی را تشکیل میدهند، که در این مسایل چند تسهیل جدید (تسهیل عرضه) به مجموعهای از مشتریان موجود، با توجه به تقاضاهایشان، خدمترسانی میکنند.در ادبیات موضوع، معمولا چند حالت مختلف از مسایل مکانیابی پیوسته مانند مساله مکانیابی میانه (تک تسهیلی)، مساله مکانیابی میانه (چند تسهیلی)، مساله مکانیابی گسسته و مساله مکانیابی- تخصیص بحث میشوند. مسایل مکانیابی تسهیل، مکان یک مجموعه از تسهیلات (منابع) را به منظور کمینه سازی هزینههای تامین مجموعههایی از تقاضاها (مشتریان) با توجه به تعدادی محدودیت را تعیین کند.مطالعه روی نظریهی مکانیابی، رسما در سال 1909 وقتی که آلفرد وبر [3] در نظر گرفت که چگونه مکان یک انبار را به منظور مینیمم سازی فاصله میان انبار و چندین مشتری را تعیین کند، آغاز شد. پس از آن، نظریهی مکانیابی در بخشهای مختلفی به کار گرفته شد. حکیمی [4] سعی در پیدا کردن مراکز مخابرات در یک شبکه ارتباطات و ایستگاههای پلیس در بزرگراهها داشت.در مساله مکانیابی میانه(تک تسهیلی) کلاسیک، که غالبا مساله وبر[1] و مساله حداقل مجموع[2] نیز نامیده میشود، در صدد یافتن مکان تسهیل جدید هستیم به طوری که مجموع فواصل وزندهی شده[3] با تسهیلات موجود، کمترین شود. برای اطلاعات بیشتر در این زمینه به فراهانی و حکمتفر [5] و نیکل و پارتو [6] مراجعه کنید.زعفرانیه و همکاران [7] الگوریتمی برای مساله جایابی تک تسهیلی در دو منطقه با نرمهای متفاوت پیشنهاد کردند و نشان دادند که حل بهینه در تقاطع متعامد تسهیلات موجود است. این مساله در حقیقت تعمیم یافته مساله جایابی تک تسهیلی است.ردریگرز و همکاران [8] مدلی را برای مساله جایابی تک تسهیلاتی ناخوشایند پیشنهاد دادند. در این پژوهش، مجموعهای متناهی از حل بهینه برای یک مساله با فاصله اقلیدسی تعیین شده است.بریمبرگ و جول [9] یک روش خط سیر را برای ایجاد یک مرز کارایی نقاط برای یک مدل دو معیاری جایابی یک وسیله نیمه خوشایند در صفحه بررسی کردند. معیار اول برای اندازهگیری هزینه حملونقل و معیار دوم برای تخمین هزینه اجتماعی یا محیطی استفاده شدند. اینجا وزن های نسبی به گونهای تغییر میکنند که مجموع وزنهای دو معیار مینیمم شود.در مساله مکان یابی چند تسهیلی حداقل مجموع[4] در صدد یافتن مکانهای تسهیلات جدید با توجه به مکانهای تعدادی تسهیل موجود هستیم،به طوری که مجموع فواصل میان تسهیلات جدید و فواصل میان تسهیلات جدید و تسهیلات موجود کمینه شود، حال آن که مساله مکانیابی چند تسهیلی حداقل حداکثر[5] به دنبال پیدا کردن مکان یک مجموعه از تسهیلات جدید در میان تسهیلات موجود است با این هدف که ماکزیمم فواصل وزن دهی شده میان همه تسهیلات را مینیمم کند. لوین و بن [10] یک روش ابتکاری برای مسایل جایابی چند تسهیلاتی با مقیاس بالا پیشنهاد دادند به گونه ای که مشتریان با استفاده از طبقهبندی دوباره نزدیکترین مرکز دوباره به تجهیزات تخصیص داده شوند. ژانگ و روشتن [11] به بررسی مساله جایابی چندتسهیلاتی در سرویسهای خدماتی رقابتی پرداختند. تابع هدف پیشنهادی یک مقیاس مطلوبیت فضایی کاربران را با توجه به محدودیتهای زمان انتظار کاربران و بودجه مالکین تسهیلات، بیشینه میکند. همچنین، برای اطلاعات بیشتر در این زمینه به دوبسن و کارمارکار [12] و لاو و همکاران [13] مراجعه کنید. مساله مکانیابی انبار ابتدا توسط کوئن و هبمورگر [14] مطالعه شد. آنها الگوریتم ابتکاری پایه ای drop, add and swap را برای حل این مساله توسعه دادند. پس از آنها، خوماوالا [15] الگوریتم شاخه و کران را بر اساس فرمولبندی ضعیف ارایه کرد. فرمولبندی قوی خطی توسط ارلنکاتر [16] استفاده شد و رویهای محاسباتی ارایه شد که شاید موثرترین و سهل الوصول ترین ابزار برای حل این دسته از مسایل باشد. نتایج کار وی در گویناردو اسپیلبرگ [17] ارایه شده است. یک خلاصه عالی از مساله مکانیابی بدون محدودیت ظرفیت نیز توسط کرنوجلس و همکاران [18] گردآوری شد.مساله مکانیابی به دنبال یافتن مکانهای بهینه مجموعهای از تسهیلات به منظور تامین درخواستهای تقاضای مجموعهای از مشتریان است. اغلب فرض میشود که درخواست تقاضای مشتریان معین و قطعی است و به عنوان بخشی از پارامترهای ورودی مساله است. واضح است که این در عالم واقعیت کمتر اتفاق میافتد و معمولا تقاضای مشتریان با یک سطح بالایی از عدم قطعیت[6] همراه است. مثالهای سادهای از مسایل مکانیابی با تقاضاهای غیرقطعی، که در آن سطوح تقاضا در دورههای زمانی مختلف، تغییر میکنند عبارتند از مساله سرویسهای پستی، فرودگاهها، سوپرمارکتها، انبارهای توزیع کالاها با تقاضاهای فصلی. براندو و چیو [19]، لووکس[20] و اسنایدر [21] جنبههای مختلف مسایل مکانیابی احتمالی را مطالعه کردند. یک مساله مکانیابی صف احتمالی، به منظور ماکزیمم سازی عملکرد سیستم توسط ماریانو و روله [22] مطالعه شد. آنها یک مدل احتمالی را طراحی کردند که در پی ماکزیمم سازی جمعیت تحت حمایت وسایل نقلیه اورژانس با سطح دسترسی است. در این مدل، سطح دسترسی وسایل نقلیه با استفاده از نظریه صف محاسبه میشود. پن و همکاران [23] یک مدل دو مرحلهای برای یک خردهفروش حاکم در یک زنجیره تامین تولیدکننده- خردهفروش با تقاضاهای احتمالی در یک محیط قیمتی کاهشی را ارایه کردند. این مدل به دنبال یکپارچه سازی پیشبینی تقاضا و تصمیمات راجع به قیمت و سفارش و پیدا کردن خطی و مشی قیمتی و سفارشی بهینه برای خرده فروش حاکم به منظور ماکزیمم سازی سود انتظاری از یک محصول در دو دوره زمانی است.شاید سادهترین مساله از نوع مکانیابی گسسته موردی باشد که یک تسهیل جدید قرار است مستقر شود. به عبارتی، از میان تعداد محدودی سایت، مثلا ، باید یکی انتخاب شود. با فرض این که هزینهی سالیانه استقرار تسهیل جدید در هر یک از سایتها مشخص است، جواب بدیهی این مساله استقرار تسهیل جدید در سایتی است که کمترین هزینه را دارد. وقتی که قرار است دو یا تعداد بیشتری تسهیل مستقر شوند و سایت ممکن در دسترس است، مساله مکانیابی دشوارتر میشود. در حقیقت وقتی تسهیل جدید و سایت ممکن وجود دارند، به طوری که ، آنگاه تعداد تخصیص های ممکن برابر با است. با بزرگترشدن وتعداد گزینههای ممکن به سرعت افزایش مییابد به گونهای که روش شمارش کامل (محاسبه و مقایسه هزینه همه گزینهها) برای حل این مسایل ناکارآمد است. برای حل چنین مسایلی مدل تخصیص[7] مفید است. مساله مکانیابی-تخصیص به دنبال پیدا کردن مکان بهینه مجموعهای از تسهیلات است به طوری که هزینهی حملونقل از تسهیلات به مشتریان موجود کمینه شود و هم چنین یک تعداد بهینه از تسهیلات به منظور تامین تقاضاهای مشتریان گمارده شوند. در مساله مکانیابی-تخصیص گسسته، آنچه باید تعیین شود، تعداد و مکان تسهیلات جدید از میان تعدادی متناهی مکانهای بالقوه و تخصیص تقاضاهای مشتریان مشخص به این تسهیلات است. ابتدا کوپر [24]مسالهکلاسیک مکانیابی- تخصیص را با دو تسهیل جدید و هفت نقطهی تقاضا پیشنهاد کرد. کوپر ثابت کرد که تابع هدف این مساله نه مقعر است، نه محدب و شاید شامل چند جواب بهینه موضعی[8] باشد. از این رو طبق گفتهی هنریک و روبرت [25] مساله کلاسیک مکانیابی- تخصیص در حوزه مسایل بهینهسازی سراسری[9] است. پس از کوپر، مساله مکانیابی- تخصیص شبکه[10] و بسیاری مدلهای دیگر توسط بدری [26] ارایه شدند.گن و چنگ [27 ، 28] مسالهمکانیابی-تخصیص را به طور مفصل مطالعه و در مورد همه انواع آن بحث کرد.