پایان نامه ارشد درمورد مکان یابی، محدودیت ها، برنامه ریزی خطی

دانلود پایان نامه ارشد

عمومی تقسیم می شوند. در صورتی که فضای حل را گسسته در نظر بگیریم و X j متغیری باشد که در صورت احداث تسهیل در مکان j مقدار یک و در غیر اینصورت مقدار صفر به خود بگیرد. در اینصورت تابع هدف مدل بصورت کمینه سازی هزینه مورد نیاز برای پوشش کلیه نقاط تقاضا بازنویسی خواهد شد:
Min ∑_j▒〖X j〗
این مسئله به مدل پوشش کامل کلاسیک نیز معروف است.
خروجی مسئله پوشش کامل مشخص می کند برای ضمانت سطح معینی از پوشش کل تقاضا، چه تعداد تسهیل مورد نیاز است، به عبارتی محل و تعداد وسائل جدید نامعلوم است و قرار است به گونه ای تعیین شود که بتوان با حداقل تعداد از وسائل جدید یک مجموعه از نقاط تقاضا را پوشش داد (Owen و Daskin،1998). مسئله پوشش اغلب دارای جواب بهینه چندگانه است و این ویژگی سبب می شود که بتوان اهداف دیگری را نیز به مسئله پوشش کامل اضافه کرد (زنجیرانی،1388).
3-4-2 روش های حل مسائل پوشش
به طور عام، چهار رویکرد اصلی در ادبیات حل مسائل پوشش گزارش شده است. اولین مورد رویکرد شمارش ضمنی مانند انشعاب و تحدید است. رویکرد دوم استفاده از روش های صفحه برش و حل بصورت تکرار تعدادی از مسائل برنامه ریزی خطی است. رویکرد سوم بکار بردن تکنیک های کاهش است و رویکرد چهارم شامل استفاده از روش های ابتکاری است.
3-4-3 نقاط ضعف مسئله پوشش
یکی از معایب مدل پوشش مجموعه، مشابه در نظر گرفتن تمام نقاط تقاضا هنگام پوشش، است. در این مدل تلاشی یکسان برای پوشش مناطقی با تقاضای بزرگ در مقایسه با مناطقی که تقاضای ناچیزی دارند، اعمال می شود. برای فائق آمدن به این مشکل مدل “حداکثر پوشش” با تعیین تعداد مشخصی از تسهیلات برای ارضا کردن سطح مطلوبی از تقاضا، توسعه داده شد (Baray و Cliquet،2013). هم چنین مسئله پوشش کامل نمی تواند کلیه مسائل مکان یابی دنیای واقعی که با فاصله پوشش مرتبط اند را پوشش دهد، زیرا اولا در بسیاری از مسائل، محدودیت های بودجه یا سایر محدودیت ها به ما اجازه پوشش تمام نقاط را نمی دهند. ثانیا مسئله پوشش کامل با تمام نقاط تقاضا بدون توجه به میزان تقاضای هر کدام یکسان برخورد می کند (زنجیرانی،1388). به عنوان مثال Baray و Cliquet در 2013 به مکان یابی زایشگاه در فرانسه پرداختند، نتایج حاصل از حل مدل نشان داد برای پوشش 80% تقاضا نیاز به 350 بیمارستان و برای افزایش پوشش به میزان 90% با رشد صد درصدی تسهیلات مواجه می شویم و به تعداد بیش از 700 بیمارستان نیاز خواهد بود (Baray و Cliquet،2013).
3-5 مسائل پوشش جزئی
برای مواجه با کمبودهای مسئله پوشش دسته ای از مسائل با عنوان مسئله پوشش جزئی بوجود آمدند. مسائل پوشش جزئی، یک فرمول بندی برنامه ریزی صفر و یک مرتبط با مساله پوشش کل است. مسئله پوشش کل شامل تعیین مینیمم تعداد و مکان های تسهیلات است، بطوریکه همه مشتریان پوشانیده شوند. در حالت های خاصی ممکن نیست تعداد تسهیلات مورد نیاز برای “پوشش کل” همه مشتریان فراهم شود، یا این که تعداد تسهیلات در دسترس برای جایابی ممکن است فقط برای “پوشش جزئی” مجموعه مشتریان کافی باشد. در چنین وضعیتی مطلوبست که k وسیله به سایت ها تخصیص یابد، به گونه ای که ماکزیمم تعداد مشتریان پوشش داده شوند.
3-5-1 نمونه هایی از مسائل پوشش جزئی
– مسئله کمینه سازی هزینه ها ناشی از عدم پوشش نقاط تقاضا
– مسئله کمینه سازی هزینه های استقرار تسهیلات و هزینه های ناشی از عدم پوشش
– مسئله بیشینه سازی پوشش (Maximum Covering Location Problem)
مسئله بیشینه سازی پوشش
یکی از معروفترین مسائل پوشش جزئی مسئله بیشینه سازی پوشش است. این مسئله اولین بار توسط Churh و Revelle در سال 1974 به منظور مواجه با زمانی که تعداد تسهیلات کافی برای پوشانیدن تمام نقاط تقاضا در دسترس نیست، معرفی شد. برای مثال فرض کنید در یک مورد خاص بتوان به کمک 5 تسهیل 90 درصد جمعیت را پوشش داد و برای پوشش 100 درصد جمعیت نیاز به 10 تسهیل باشد در این مواقع تصمیم گیران ممکن است ترجیح دهند هزینه اضافه ای که برای پوشش کل جمعیت لازم است را صرف کارهای سودمندتری کنند. بنابراین هدف مسئله مطرح شده حداکثر کردن جمعیت تحت پوشش توسط تعداد مشخصی از تسهیلات است (Church و Revelle). ایشان نقاط کاندیدای استقرار را به گره های شبکه محدود کردند. در این مسئله تعداد تسهیلات جدید محدود است (مسئله برون زا است) و هدف یافتن مکان این وسائل است به گونه ای که بتوان حداکثر تعداد ممکن از نقاط تقاضا را پوشش داد (زنجیرانی،1388؛ Owen و Daskin،1998). Church and Meadows در1979، برای مسئله حداکثر پوشش یک ویژگی “شبه حکیمی” ارائه دادند که گویای این مطلب بود: برای هر شبکه یک مجموعه متناهی از رئوس وجود دارد که شامل حداقل یک راه حل بهینه برای مسئله حداکثر پوشش خواهد بود (Hale و Moberg،2003).
فرموله کردن مسئله بیشینه سازی پوشش به صورت زیر است:
I اندیس نقاط تقاضا
J اندیس نقاط کاندیدا برای احداث تسهیل
P ماکزیمم تعداد تسهیلات
di مقدار تقاضای نقطه i ام
به علاوه پارامتر پوشش S را برای هر نقطه تقاضا به صورت زیر تعریف می کنیم:
Ni = {j ϵ J ׀ dij ≤ S}
Ni مجموعه مراکز کاندیدای احداث تسهیل که در فاصله استاندارد (S) از نقطه تقاضای i قرار دارند (Ni ϵ J)
yj در صورت احداث تسهیل در مکان j مساوی 1 و در غیر اینصورت مساوی 0 خواهد بود.
Xij در صورتی که نقطه تقاضای i توسط تسهیل مستقر در j پوشش داده شود 1 و در غیر اینصورت مساوی 0 خواهد بود.
Max ∑_iϵI ∑_(jϵNi )▒〖di Xij〗 (1)
Subject to:
∑_jϵJ▒〖yj ≤ p〗 (2)
Xij ≤yj ∀ iϵI , ∀ jϵNi (3)
xj = {0,1} ∀ iϵI (4)
yij = {0,1} ∀ i ϵI , ∀ j ϵJ (5)

تساوی (1) صورت تابع حداکثر پوشش را نشان می دهد به عبارتی بیان می کند که می خواهیم مجموع تقاضای پوشش یافته در یک شعاع پوشش خاص را حداکثر کنیم. محدودیت اول حداکثر تعداد تسهیلات را به P محدود می کند. . محدودیت دوم ضمانت می کند که نقطه تقاضای i در صورتی پوشانیده می شود که در فاصله حداکثر S از آن نقطه یک تسهیل مستقر شده باشد. دو محدودیت آخر متغیرهای باینری مدل را تعریف می کنند. مسئله MCLP در گروه مسائل مکان یابی- پوشش سخت (NP-HARD) دسته بندی می شود (Dell’Olmo و همکاران،2014). میزان جمعیت تحت پوشش یک مقیاس برای سنجش اثر بخشی یک تسهیل عمومی به شمار می رود. این مقیاس سنجش می تواند در غالب مسئله: ماکزیمم کردن جمعیت تحت پوشش بوسیله تعداد معینی تسهیل در یک فاصله مطلوب (همان MCLP)، مدل شود (Church و Revelle،1976). اولین تکنیک حل برای مسئله حداکثر پوشش توسط Church در 1974 به نام الگوریتم طماع (The Greedy Adding) ارائه شد. پس از آن دومین تکنیک حل به نام روش طماع با الگوریتم جانشین (The Greedy Adding with Substitutuion Algorithm(GAS)) که بر مبنای همان روش طماع طراحی شده بود، مطرح شد. و تنها تفاوتش با روش طماع در این بود که سعی داشت در هر تکرار جواب را بهبود ببخشد (Church و Revelle). علاوه بر روش های حل طماع از آزاد سازی لاگرانژ نیز برای حل MCLP استفاده شده است، Pirkul و Schilling برای حل MCLP خود این روش را به کار بردند. Revelle، Scholssberg و Williams در 2007 یک متاهیوریستیک دو مرحله ای را برای حل مسائل MCLP با ابعاد بزرگ و درصد پوشش بالا، ارائه دادند (Dell’Olmo و همکاران،2014).
مسئله بیشینه سازی پوشش با توجه به محدودیت های متفاوت به دسته های زیر تقسیم می شود:
مسئله بیشینه سازی مقدار پوشش مورد انتظار
در این مسئله تسهیل فقط در زمان های مشخصی قابل استفاده است (مانند آمبولانس). یعنی علاوه بر پوشش دادن نقاط تقاضا، تسهیلات باید در دسترس هم باشند. مدل مذبور تلاش می کند تا بوسیله مکان یابی تعداد مشخصی از تسهیلات، سطح معینی از تقاضای پوشش یافته را بیشینه کند. این مدل مواقعی که تسهیل احتمالا زمان مراجعه مشتری در دسترس نباشد، کاربرد دارد (Baray و Cliquet،2013).
مسئله بیشینه سازی پوشش با در نظر گرفتن تابع غیر صعودی پوشش
یکی از پیش فرض های مسئله پوشش این است که نقاط تقاضا در یک فاصله بحرانی بطور کامل پوشش داده شده و در خارج از آن فاصله هیچ پوششی دریافت نمی کنند. حالت فوق به شرایطی می پردازد که کسری از تقاضای نقاطی که در فاصله ی کمتر از شعاع پوشش نسبت به تسهیل قرار دارند، نیز می تواند برآورده شود (زنجیرانی،1388).
مدل P-Median
شروع علم مکان یابی را مسلما می توان در کارهای Pierre de Fermat، Evagelistica Torricelli (شاگرد گالیله) و Battista Cavallieri دنبال کرد. آنها بطور مستقل از هم در اوایل قرن هفدهم مسئله میانه در فضای اقلیدسی را مطرح کردند هم چنین Francis در 1964 و Francis and Cabot در 1972، مسئله P- میانه را با فاصله اقلیدسی ارائه کردند (Hale و Moberg،2003). طی مطالعاتی که در تئوری مکان یابی روی شبکه ها صورت گرفته اساسی ترین و متداول ترین مسائل، مدل های میانه و مرکز هستند. مسئله میانه جزء دسته مسائل برون زاست، به عبارتی تعداد تسهیلات در مسئله محدود است. و به دنبال یافتن تعدادی تسهیل است به گونه ای که مجموع وزین فاصله را کمینه کند. چرچ و رول یکی از راه های مهم برای اندازه گیری کارایی (effectiveness) مکان یک تسهیل را بوسیله تعیین میانگین فاصله (که می تواند بصورت هزینه نیز بیان شود) تسهیل تا نقاط تقاضا برآورد کردند. در صورتی که میانگین فاصله افزایش یابد، میزان دسترسی به تسهیل کاهش می یابد و در نتیجه کارایی مکان مورد نظر نیز کاهش می یابد. این ارتباط در مورد تسهیلاتی چون مدرسه، کتابخانه و مراکز خدمات اضطراری که نزدیکی به آنها مطلوب متقاضیان است صادق می باشد (Owen و Daskin، 1998). اساسی ترین فرض هایی که در هر دو مدل فوق مشاهده می شود شامل: سرویس دهنده های یکسان، ظرفیت نامحدود سرویس دهنده ها و دریافت خدمات هر مشتری از نزدیک ترین تسهیل، است. مسئله ی میانه با حداقل کردن میانگین فاصله کاربر تا تسهیل، برای یافتن محل تسهیلاتی مناسب است که خدماتی روتین ارائه می دهند (Brito و Perez). مدل P- میانه برای نخستین بار توسط Weber در 1909 برای تعیین محل قرار گیری یک مرکز تولیدی به کار گرفته شد. عملا بسیاری از شبکه های موجود نظیر شبکه جاده ای، هوایی و تلفن معرف مسئله P- میانه هستند (این مدل به نام P- MP نیز شناخته می شود) (Baray و Cliquet،2013). حکیمی مسئله p- میانه را روی شبکه مطرح کرد. وی در 1964 نشان داد مجموعه رئوس برای مسئله P- میانه یک dominating set Finite است (Brito و همکاران،1998). اگر چه حکیمی یک روش حل برای مسئله مذکور معرفی نکرد ولی ثابت کرد که: “حتما یک حل بهینه از قرار گیری تسهیلات روی گره های شبکه حاصل می شود.” کار وی مانند ابزاری که دانتزیگ برای برنامه ریزی خطی ارائه داد فضای حل بهینه را از یک مجموعه نامتناهی به یک مجموعه متناهی کاهش می دهد. این نتیجه به “قضیه حکیمی” یا “خاصیت گره” معروف است. Hua Lo-Keng و همکارانش نشان دادند که در مورد مسئله 1- میانه، زمانی که بیش از نیمی از وزن شبکه روی یکی از نقاط تقاضا باشد، حل بهینه مکان تسهیل را روی آن گره قرار می دهد. این مسئله برای حالت دو تسهیل در میانه هم صدق می کند. اما برای حالت چند تسهیلی یا P- میانه چنین نتایجی در دسترس نیست. با این حال طبق قضیه حکیمی می دانیم برای رسیدن به حل بهینه کافیست تنها گره های شبکه را مورد بررسی قرار دهیم (Revelle و Eiselt،2005).
ارتباط بین Median و MCLP
مسئله ماکزیمم پوشش می تواند مشابه یک مسئله P- میانه فرموله و حل شود. از آنجایی که تکنیک های حل مسئله میانه می توانند برای حل MCLP نیز اعمال شوند

پایان نامه
Previous Entries پایان نامه ارشد درمورد مکان یابی، تصمیم گیری چند معیاره، محدودیت ها Next Entries پایان نامه ارشد درمورد استان هرمزگان، بهینه سازی چند هدفه، دریای عمان