برای جستجو در بین هزاران پایان نامه در موضوعات مختلف     

      و دانلود متن کامل آنها با فرمت ورد اینجا کلیک کنید     

 
دانلود پایان نامه
در ادبیات موضوعی، معمولا چند حالت مختلف از مسائل مکان یابی پیوسته مانند مساله مکان یابی میانه (تک تسهیله)، مساله مکان یابی میانه (چند تسهیله)، ، مساله مکان یابی گسسته و مساله مکان یابی-تخصیصمورد بحث قرار می گیرند. مسائل مکان یابی تسهیل، مکان یک مجموعه از تسهیلات (منابع) را به منظور کمینه کردن هزینه های تامین مجموعه هایی از تقاضاها (مشتریان) با توجه به تعدادی محدودیت، را تعیین می کند.
مطالعه برروی تئوری مکان یابی، رسما در سال 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 سایت ممکن وجود دارد، بطوریکه ، تعداد تخصیص های ممکن برابر بااست. با بزرگترشدن 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
خیر
کمینه
دسته بندی : علمی