روشهای ابتکاری

روشهای ابتکاری

هم چنین، متغیرهای تصمیم این مدل، همان متغیرهای تصمیم مدل عمومی هستند. در مدل مکانیابی- تخصیص قطعی، تخصیص w ، متغیر تصمیمی است که در همه دورههای زمانی ثابت است، در حالی که در یک مساله مکانیابی- تخصیص احتمالی، تصمیم w متغیر است و در هر دوره زمانی پس از آن که تقاضاهای مشتریان مشخص شوند، مسخص میشود.
2-5-2-4-3- تابع هدف و محدودیتهای مدل
تابع هدف این مدل شبیه به تابع هدف مدل عمومی مکانیابی- تخصیص است:
(2-8)
(2-9)
(2-10)

(2-11)
هدف این مدل اینست که فاصله میان تسهیلات موجود و تسهیلات جدیدی که به تسهیلات موجود تخصیص داده میشود با در نظر گرفتن ضریب میزان تقاضای برآورده شده توسط تسهیلات جدید کمینه شود. محدودیت (2-9) تضمین میکند که تقاضای تسهیل موجود که به تسهیلات جدید تخصیص داده شده است برابر با تقاضای احتمالی تسهیل موجود باشد. محدودیت (2-10) تضمین میکند که تقاضای تخصیص داده شده به تسهیلات جدید از کل ظرفیت تسهیلات جدید بیشتر نباشد.
اگر نقاط شدنی برای w بدست نیایند، آنگاه تامین کردن بعضی از مشتریان امکان پذیر نخواهد شد و سمت راست عبارت (2-8) بیمعنی خواهد شد و به عنوان هزینه جریمهای تابع هدف زیر جایگزین میشود [3]:
(2-12)
2-6- ادبیات و پیشینه تحقیق
مسایل مکانیابی- تخصیص چندتسهیلی، زمینهای گسترده در مدلسازی ریاضی در دنیای واقعی را تشکیل میدهند، که در این مسایل چند تسهیل جدید (تسهیل عرضه) به مجموعهای از مشتریان موجود، با توجه به تقاضاهایشان، خدمترسانی میکنند.
در ادبیات موضوع، معمولا چند حالت مختلف از مسایل مکانیابی پیوسته مانند مساله مکانیابی میانه (تک تسهیلی)، مساله مکانیابی میانه (چند تسهیلی)، مساله مکانیابی گسسته و مساله مکانیابی- تخصیص بحث میشوند. مسایل مکانیابی تسهیل، مکان یک مجموعه از تسهیلات (منابع) را به منظور کمینه سازی هزینههای تامین مجموعههایی از تقاضاها (مشتریان) با توجه به تعدادی محدودیت را تعیین کند.
مطالعه روی نظریهی مکانیابی، رسما در سال 1909 وقتی که آلفرد وبر [6] در نظر گرفت که چگونه مکان یک انبار را به منظور مینیمم سازی فاصله میان انبار و چندین مشتری را تعیین کند، آغاز شد. پس از آن، نظریهی مکانیابی در بخشهای مختلفی به کار گرفته شد. حکیمی [7] سعی در پیدا کردن مراکز مخابرات در یک شبکه ارتباطات و ایستگاههای پلیس در بزرگراهها داشت. در مساله مکانیابی میانه (تک تسهیلی) کلاسیک، که غالبا مساله وبر و مساله حداقل مجموع نیز نامیده میشود، در صدد یافتن مکان تسهیل جدید هستیم به طوری که مجموع فواصل وزندهی شده با تسهیلات موجود، کمترین شود. برای اطلاعات بیشتر در این زمینه به فراهانی و حکمتفر [8] و نیکل و پارتو [9] مراجعه کنید.
زعفرانیه و همکاران [10] الگوریتمی برای مساله جایابی تک تسهیلی در دو منطقه با نرمهای متفاوت پیشنهاد کردند و نشان دادند که حل بهینه در تقاطع متعامد تسهیلات موجود است. این مساله در حقیقت تعمیم یافته مساله جایابی تک تسهیلی است. ردریگرز و همکاران [11] مدلی را برای مساله جایابی تک تسهیلاتی ناخوشایند پیشنهاد دادند. در این پژوهش، مجموعهای متناهی از حل بهینه برای یک مساله با فاصله اقلیدسی تعیین شده است. بریمبرگ و جول [12] یک روش خط سیر را برای ایجاد یک مرز کارایی نقاط برای یک مدل دو معیاری جایابی یک وسیله نیمه خوشایند در صفحه بررسی کردند. معیار اول برای اندازهگیری هزینه حملونقل و معیار دوم برای تخمین هزینه اجتماعی یا محیطی استفاده شدند. اینجا وزن های نسبی به گونهای تغییر میکنند که مجموع وزنهای دو معیار مینیمم شود. در مساله مکان یابی چند تسهیلی حداقل مجموع در صدد یافتن مکانهای تسهیلات جدید با توجه به مکانهای تعدادی تسهیل موجود هستیم، به طوری که مجموع فواصل میان تسهیلات جدید و فواصل میان تسهیلات جدید و تسهیلات موجود کمینه شود، حال آن که مساله مکانیابی چند تسهیلی حداقل حداکثر به دنبال پیدا کردن مکان یک مجموعه از تسهیلات جدید در میان تسهیلات موجود است با این هدف که ماکزیمم فواصل وزن دهی شده میان همه تسهیلات را مینیمم کند. لوین و بن [13] یک روش ابتکاری برای مسایل جایابی چند تسهیلاتی با مقیاس بالا پیشنهاد دادند به گونه ای که مشتریان با استفاده از طبقهبندی دوباره نزدیکترین مرکز دوباره به تجهیزات تخصیص داده شوند. ژانگ و روشتن [14] به بررسی مساله جایابی چندتسهیلاتی در سرویسهای خدماتی رقابتی پرداختند. تابع هدف پیشنهادی یک مقیاس مطلوبیت فضایی کاربران را با توجه به محدودیتهای زمان انتظار کاربران و بودجه مالکین تسهیلات، بیشینه میکند. همچنین، برای اطلاعات بیشتر در این زمینه به دوبسن و کارمارکار [15] و لاو و همکاران [16] مراجعه کنید. مساله مکانیابی انبار ابتدا توسط کوئن و هبمورگر [17] مطالعه شد. آنها الگوریتم ابتکاری پایه ای drop, add and swap را برای حل این مساله توسعه دادند. پس از آنها، خوماوالا [18] الگوریتم شاخه و کران را بر اساس فرمولبندی ضعیف ارایه کرد. فرمولبندی قوی خطی توسط ارلنکاتر [19] استفاده شد و رویهای محاسباتی ارایه شد که شاید موثرترین و سهل الوصول ترین ابزار برای حل این دسته از مسایل باشد. نتایج کار وی در گوینارد و اسپیلبرگ [20] ارایه شده است. یک خلاصه عالی از مساله مکانیابی بدون محدودیت ظرفیت نیز توسط کرنوجلس و همکاران [21] گردآوری شد.
مساله مکانیابی به دنبال یافتن مکانهای بهینه مجموعهای از تسهیلات به منظور تامین درخواستهای تقاضای مجموعهای از مشتریان است. اغلب فرض میشود که درخواست تقاضای مشتریان معین و قطعی است و به عنوان بخشی از پارامترهای ورودی مساله است. واضح است که این در عالم واقعیت کمتر اتفاق میافتد و معمولا تقاضای مشتریان با یک سطح بالایی از عدم قطعیت همراه است. مثالهای سادهای از مسایل مکانیابی با تقاضاهای غیرقطعی، که در آن سطوح تقاضا در دورههای زمانی مختلف، تغییر میکنند عبارتند از مساله سرویسهای پستی، فرودگاهها، سوپرمارکتها، انبارهای توزیع کالاها با تقاضاهای فصلی. براندو و چیو [22]، لووکس [23] و اسنایدر [24] جنبههای مختلف مسایل مکانیابی احتمالی را مطالعه کردند. یک مساله مکانیابی صف احتمالی، به منظور ماکزیمم سازی عملکرد سیستم توسط ماریانو و روله [25] مطالعه شد. آنها یک مدل احتمالی را طراحی کردند که در پی ماکزیمم سازی جمعیت تحت حمایت وسایل نقلیه اورژانس با سطح دسترسی است. در این مدل، سطح دسترسی وسایل نقلیه با استفاده از نظریه صف محاسبه میشود. پن و همکاران [26] یک مدل دو مرحلهای برای یک خردهفروش حاکم در یک زنجیره تامین تولیدکننده- خردهفروش با تقاضاهای احتمالی در یک محیط قیمتی کاهشی را ارایه کردند. این مدل به دنبال یکپارچه سازی پیشبینی تقاضا و تصمیمات راجع به قیمت و سفارش و پیدا کردن خطی و مشی قیمتی و سفارشی بهینه برای خرده فروش حاکم به منظور ماکزیمم سازی سود انتظاری از یک محصول در دو دوره زمانی است.
شاید سادهترین مساله از نوع مکانیابی گسسته موردی باشد که یک تسهیل جدید قرار است مستقر شود. به عبارتی، از میان تعداد محدودی سایت، مثلا ، باید یکی انتخاب شود. با فرض این که هزینهی سالیانه استقرار تسهیل جدید در هر یک از سایتها مشخص است، جواب بدیهی این مساله استقرار تسهیل جدید در سایتی است که کمترین هزینه را دارد. وقتی که قرار است دو یا تعداد بیشتری تسهیل مستقر شوند و سایت ممکن در دسترس است، مساله مکانیابی دشوارتر میشود. در حقیقت وقتی تسهیل جدید و سایت ممکن وجود دارند، به طوری که ، آنگاه تعداد تخصیص های ممکن برابر با است. با بزرگترشدن و تعداد گزینههای ممکن به سرعت افزایش مییابد به گونهای که روش شمارش کامل (محاسبه و مقایسه هزینه همه گزینهها) برای حل این مسایل ناکارآمد است. برای حل چنین مسایلی مدل تخصیص مفید است. مساله مکانیابی- تخصیص به دنبال پیدا کردن مکان بهینه مجموعهای از تسهیلات است به طوری که هزینهی حملونقل از تسهیلات به مشتریان موجود کمینه شود و هم چنین یک تعداد بهینه از تسهیلات به منظور تامین تقاضاهای مشتریان گمارده شوند. در مساله مکانیابی- تخصیص گسسته، آنچه باید تعیین شود، تعداد و مکان تسهیلات جدید از میان تعدادی متناهی مکانهای بالقوه و تخصیص تقاضاهای مشتریان مشخص به این تسهیلات است. ابتدا کوپر [27] مساله کلاسیک مکانیابی- تخصیص را با دو تسهیل جدید و هفت نقطهی تقاضا پیشنهاد کرد. کوپر ثابت کرد که تابع هدف این مساله نه مقعر است، نه محدب و شاید شامل چند جواب بهینه موضعی باشد. از این رو طبق گفتهی هنریک و روبرت [28] مساله کلاسیک مکانیابی- تخصیص در حوزه مسایل بهینهسازی سراسری است. پس از کوپر، مساله مکانیابی- تخصیص شبکه و بسیاری مدلهای دیگر توسط بدری [29] ارایه شدند. گن و چنگ [30 ، 31] مساله مکانیابی- تخصیص را به طور مفصل مطالعه و در مورد همه انواع آن بحث کرد.
روله و الزینگا [32] یک مساله مکانیابی چندتسهیلی را که در آن هر ناحیه تعریف شده دستکم به یک تسهیل تخصیص مییابد درنظر گرفتند. در مدل پیشنهادی آنها، نواحی تعریف شده کاملا از یکدیگر مستقل هستند و هیچ نوع تعامل میان آنها وجود ندارند. برمن و همکاران [33] یک مدل مکانیابی- تخصیص تکتسهیلی را ارایه کردند که در آن بر خلاف کار روله و الزینگا، تعامل میان نواحی امکانپذیر است. البته، هر دوی این کارها یک حالت خاصی از مدل ارایه شده توسط رول و سواین [34] هستند.
در مدل های قطعی مسایل مکانیابی- تخصیص، فرض شده است که درخواست تقاضای مشتریان کاملا مشخص و قطعی است که البته این در جهان واقعی کمتر اتفاق میافتد. وقتی حالت قطعی در تقاضای مشتریان درنظر گرفته میشود، ما دقیقا نمیدانیم که کدام مشتری درخواست تقاضا دارد و کدام ندارد. بنابراین، یک رویکرد معقول اینست که درخواست تقاضای مشتریان به طور تصادفی اتفاق بیافتد که این منجر به افزایش حالت های احتمالی در مساله مکانیابی چندتسهیلی میشود. لوگندران و ترل [35] یک مساله مکانیابی- تخصیص بدون محدودیت ظرفیت را در حضور تقاضاهای احتمالی قیمت محور در نظر گرفتند و یک مدل بهینهسازی به منظور ماکزیمم سازی سود خالص انتظاری پیشنهاد کردند. آنها یک روش ابتکاری برای حل مسایل با اندازه متوسط و بزرگ ارایه کردند. لووو و پیترز [36] یک مساله مکانیابی تسهیل با ظرفیت نامحدود و تقاضاهای احتمالی را پیشنهاد کردند. آنها مجموعهای از سناریوها را برای مساله درنظر گرفتند که با احتمالات خاص اتفاق میافتند. شرالی و ریزو [37] یک مساله مکانیابی- تخصیص ظرفیتبندی شده با تقاضای مستمر را بر روی یک نمودار زنجیری ارایه کردند. کاریزوسا و همکاران [38] یک مساله مکانیابی- تخصیص را که در آن نواحی مکانهای مشتریان و تسهیلات ممکن است با توزیعهای احتمال متفاوتی نزدیک به یکدیگر باشند، را بررسی کردند. زو [39] یک مدل برنامه ریزی مقدار انتظاری با احتمال اجباری برای مساله مکانیابی- تخصیص با ظرفیت نامحدود و تقاضاهای احتمالی را پیشنهاد کرد. اگرچه مساله مکانیابی- تخصیص احتمالی با محدودیت ظرفیت به وسیله محققین زیادی مطالعه شد ولی به خاطر پیچیدگی مساله هیچ مدل برنامهریزی احتمالی عمومیای برای آن ارایه نشد تا این که زو و لیو [40] سه مدل احتمالی عمومی را، که کاملا از مدل های برنامهریزی احتمالی پیشین متفاوت هستند، ارایه کردند. این مدلها عبارتند از: مدل مقدار انتظاری، برنامهریزی احتمال اجباری و برنامهریزی احتمال وابسته. هم چنین، محققین الگوریتم سیمپلکس شبکهای، شبیهسازیهای احتمالی و الگوریتم ژنتیک را به منظور حل کارای مساله با یکدیگر یکپارچه کردند. لاپورت و همکاران [41] یک مساله فروشنده دوره گرد را با تقاضاهای احتمالی(PTSP) مطالعه و یک مدل برنامهریزی خطی را که با رویکرد شاخه و برش حل میشود، ارایه کردند. از آنجا که مسایل PTSP به دلیل ترکیب مساله TSP و حالت احتمالی تقاضا، از جمله مسایل پیچیده (محاسباتی) در حل هستند، آنها یک الگوریتم دقیق برای حل این مساله ارایه کردند. پس از آن، بیانچی و کمبل [42] یک روش ابتکاری برای حل مساله PTSP را که در آن همه مشتریان دارای احتمال یکسان برای تقاضا هستند، پیشنهاد کردند. آنها یک مساله فروشنده دورهگرد احتمالی ناهمگن را توسعه دادند و الگوریتمهای حل مختلفی برای حالت ناهمگن پیشنهاد کردند. مساله آنها در پی پیدا کردن مسیری که کمترین هزینه انتظاری برای مشتریانی که دارای تقاضاهای احتمالی هستند، است. آلباردا سامبولا و همکاران [43] یک مساله مسیریابی تسهیل احتمالی را که دارای مدلی دو مرحلهای است، بیان کردند. در مرحله اول، مدل آنها مجموعهای از تسهیلات و خانوادهای از مسیرها را مشخص میکند و در مرحله دوم، تصمیمات لازم (عمل توسل) به منظور انطباق این مسیرها به مجموعه واقعی مشتریانی که باید تامین شوند، گرفته میشوند. هم چنین آنها روشی ابتکاری را برای حل مساله ارایه کردند. پس از این تحقیق، آلباردا سامبولا و همکاران [44] بر روی یک مساله مکان یابی- تخصیص در محیط گسسته با تقاضاهای برنولی کار کردند. آنها دو نوع تصمیمی (عمل توسل) را که با مدل برنامهریزی احتمالی دو مرحلهای مرتبط هستند، درنظر گرفتند. برای هر نوع تصمیم، آنها یک روش تقریبی برای محاسبه مقدار انتظاری که تاثیر حالت احتمالی را بر روی مساله تخمین میزند، ارایه کردند. مجموعه جواب حاصل از مرحله اول شامل مکانهای تسهیلات و نحوه تخصیص مشتریان به تسهیلات و مجموعه جواب مرحله دوم تخمینی از مقدار انتظاری تابع تصمیم گرفته شده (تابع توسل) است.
از آنجا که مساله مکان یابی- تخصیص یک مساله NP- سخت است [45] ، دستیابی به جواب بهینه یکی از دغدغههای اصلی مساله است. روشهای حل مسایل مکانیابی- تخصیص به سه دسته اصلی طبقهبندی می شوند: روش های دقیق ، روش های ابتکاری و روش های فراابتکاری. از جمله روشهای دقیق میتوان به الگوریتم شاخه و کران که توسط کوئن و سولند [46] برای مساله چند منبعی وبر اجرا شده است، اشاره کرد. روشهای ابتکاری زیادی برای پیدا کردن جوابهای بهینه مساله کلاسیک مکانیابی- تخصیص به خوبی اندک الگوریتمهای دقیق ارایه شدهاند. روشهای ابتکاری به منظور حل سریع مسایل بزرگ و ایجاد جوابهای اولیه خوب برای الگوریتمهای دقیق مورد نیاز هستند. اولین روش ابتکاری مشهور، الگوریتم مکانیابی- تخصیص تکراری کوپر [47] است. روش ابتکاری کوپر چند زیرمجموعه از نقاط ثابت ایجاد میکند و سپس هر یک از آنها را با استفاده از الگوریتم دقیق برای حل یک مساله مکانیابی تکتسهیلی، حل می کند. روشهای فراابتکاری زیادی نیز برای بدست آوردن جوابهای این گونه مسایل به کار گرفته شدهاند، از جمله ، شبیهسازی تبرید (موری و چرچ [48]) و جستجوی ممنوعه (بریمبرگ و ملادنویچ [49]). هم چنین، تعدادی الگوریتم پیوندی مانند الگوریتم پیوندی شبیهسازی تبرید و روش وراثت تصادفی (ارنست و کریشنامورتی [50]) و الگوریتم پیوندی روش سادهسازی لاگرانژ و الگوریتم ژنتیک (گونگ و همکاران [51]) نیز پیشنهاد شدهاند.
فصل سوم
مدل ریاضی

Share