منبع علمی مقاله user8233

 برای دانلود فایل کامل به سایت منبع مراجعه کنید  : elmname.com

یا برای دیدن قسمت های دیگر این موضوع در سایت ما کلمه کلیدی را وارد کنید :

 

جدول (4-10). نقاط پایداری حاصل ازمیانه در ترکیب تکی ربع ها...................................................102
جدول (4-11). نقاط پایداری حاصل ازمیانه در ترکیب دو تایی ربع ها..............................................102
جدول (4-12). نقاط پایداری حاصل ازمیانه در ترکیب سه تایی ربع ها.............................................102
جدول (4-13). نقاط پایداری حاصل ازمیانه در ترکیب چهار تایی ربع ها.........................................103
جدول (4-14). نقاط با تابع هدف مینیمم حاصل ازدو روش در ترکیب تکی ربع ها......................... 103
جدول (4-15). نقاط با تابع هدف مینیمم حاصل ازدو روش در ترکیب دو تایی ربع ها.....................103
جدول (4-16). نقاط با تابع هدف مینیمم حاصل ازدو روش در ترکیب سه تایی ربع ها....................104
جدول (4-17). نقاط با تابع هدف مینیمم حاصل ازدو روش در ترکیب چهار تایی ربع ها................104
جدول (4-18). مقدار تابع هدف در نقاط حاصل از گام پنجم...........................................................104
فهرست اشکال
عنوان صفحه
فصل دوم :
شکل (2 -1- 1). نواحی با محدودیت در قرارگیری و یا حرکت..............................................................8
شکل (2-2-1) . نوع مانع در نظر گرفته شده توسط کاتز و کوپر............................................................9
شکل( 2- 2- 2) رویکرد در نظر گرفته شده برای حل مسایل مکان یابی با مانع توسط بایشوف و کلامروس.................................................................................................................................................10
شکل( 2- 2-3)0 رویکرد در نظر گرفته شده برای حل مسایل مکان یابی با مانع توسط کلامروس.......11
شکل (2-2-4) . نوع مانع در نظر گرفته شده توسط آنجا و پارلر...........................................................12
فصل سوم :
شکل (3-1). دسته بندی مسایل برنامه ریزی تسهیلات...........................................................................22
شکل(3-2). فاصله اقلیدسی بین دو نقطه................................................................................................25
شکل(3-3). فاصله متعامد بین دو نقطه...................................................................................................26
فصل چهارم :
شکل (4-1). مانع آرکی شکل احتمالی در صفحه...................................................................................44
شکل (4-2). وضعیت دو تسهیل در حالت پدیدار نبودن........................................................................46
شکل (4-3). وضعیت دو تسهیل در حالت پدیدار بودن.........................................................................46
شکل (4-4). گام های شرایط پدیدار بودن دو تسهیل نسبت به هم........................................................47
شکل (4-5). شرایط گام اول پدیداری....................................................................................................49
شکل (4-6). شرایط گام سوم پدیداری...................................................................................................53
شکل (4-7) .حالت اول شرایط با مانع جهت آزمون برخورد راستای افق تسهیل جدید با مانع..............56
شکل (4-8) .ترکیب اول از شرایط با مانع...............................................................................................59
شکل (4-9) .ترکیب دوم از شرایط با مانع..............................................................................................60
شکل (4-10) .ترکیب سوم از شرایط با مانع...........................................................................................60
شکل (4-12) .ترکیب چهارم از شرایط با مانع........................................................................................63
شکل (4-13) .ترسیم خطوط متناظر در حالت تک ریشه........................................................................65
شکل (4-14).نمای تصویری جهت محاسبه پاره خط T.........................................................................70
شکل (4-15).مسیرهای جابجایی بین دو تسهیل در زمان وجود مانع.....................................................74
شکل (4-16).ترسیم رابطه بین خطوط ابتدای مانع و انتهای مانع............................................................76
شکل (4-17) . مکان تسهیلات موجود و تسهیل جدید در شرایط با مانع و بدون مانع..........................90
شکل (4-18) . ارائه الگوریتم پیشنهادی حل مساله.................................................................................93
فصل اول
کلیات تحقیق و ساختار پایان نامه
2670810213296500
مقدمه
برنامه ریزی تسهیلات دو بخش عمده جایابی و طراحی را شامل میشود که مهمترین بخش طراحی، استقرار یا جانمایی تسهیلات میباشد.منظور از تسهیلات،هر مجموعه، شامل کارخانه، بیمارستان، دانشگاه ... است. با افزایش میزان هزینه حمل و نقل و هزینههای تحویل،مساله مکانیابی تسهیلات نقش مهمی در محیطهای صنعتی ایفا میکند.نظریه مکانیابی به عنوان شاخهای از تحقیق در عملیات از یک سو در جایابی تسهیلات و از سوی دیگر در تصمیم گیری های مدیریتی ،اقتصادی و برنامه ریزی تولید تاثیرگذار است و فواید بسیاری برای واحد های صنعتی از جمله سرمایه کمتر و بازدهی بیشتر، زمان بازگشت سرمایه کمتر و سود بیشتر به دنبال خواهد داشت.انتخاب مکان بهینه و متعاقبا مسیر بهینه کاری پیچیده و دارای فرایند تکراری می باشد.مکان بهینه همچنین باید بتواند پاسخگوی حجم تردد در محیط صنعتی باشد.مطالعه پیرامون مکان بهینه از دیدگاه جغرافی دانان و علمای اقتصادی هموراه دارای اهمیت بوده و در محاسبات خود مد نظر قرار می دهند [1].مراکز صنعتی و کارخانجات برای تعیین مکان احداث کارخانه، استقرار تجهیزات و دپارتمانهای خود در کارخانه، استقرار دفاترشان در سطح شهر، تعیین مراکز توزیع محصولات و ... با چنین مسائلی سر و کار دارند.
در مسایل مکان یابی دو نوع محیط پیوسته و گسسته در نظر گرفته میشود.از جمله مسایل مکانیابی پیوسته میتوان به مسایل مکان یابی میانه ، و مساله مرکز میانه نام برد. تصمیمات مکانیابی اهداف مختلفی را دنبال می کند.برای مثال کمینه کردن مجموع وزنی فاصلههای بین تسهیل جدید و سایر تسهیلات موجود و کمینه کردن بیشترین فاصله بین تسهیل جدید و سایر تسهیلات موجود از این نوع هستند. در مساله میانه هدف، پیدا کردن مکان وسیله (تسهیل) جدید می باشد، بطوری که مجموع فواصل وزندهی شده بین تسهیل جدید و تسهیلات موجود ، حداقل گردد.چنین مساله به مساله مکانیابی کمینه مجموع شهرت دارد.نوع دیگر طبقه بندی مسایل مکانیابی بر اساس نوع فاصله مورد نظرمی باشد.فواصل مورد محاسبه میتواند بصورت متعامد یا اقلیدسی باشد. مساله کمینه مجموع با فاصله اقلیدسی از ابتدایی ترین و قدیمی ترین مسایل مکان یابی تسهیلات می باشد.در این نوع مکان یابی با محدودیت در قرار گیری و یا حرکت در مسیر مواجه می شویم.در دسته ای از این مسایل ،نواحی وجود دارد که تسهیل جدید نه می تواند در آنجا استقرار یابد و نه می تواند از میان آن عبور کند. این نواحی ، نواحی بامانع نامیده می شوند. دریاچه ها، کوهستان ها، مناطق نظامی، رودخانه ها و بزرگ راه ها و در مقیاس کوچکتر، ماشین آلات و واگن های حمل مواد در کارخانجات، مثال هایی از این نواحی می باشند.در حقیقت مساله مکان یابی با مانع در واقعیت نقش مهمتری را ایفا می کند. این مسایل در مقایسه با مسایل مکانیابی کلاسیک خیلی عملی تر و نزدیک تر به دنیای واقعی می باشند، اما به علت پیچیدگی محاسباتی که این نوع مسایل دارند، تنها در چند دهه اخیر مورد بررسی قرار گرفتند و کمتر در محاسبات و مدل های مکان یابی تسهیلات به حضور مانع پرداخته شده است.کارهای ابتدایی که در زمینه مکان یابی با مانع مورد بررسی قرار گرفت همه زمانی که مانع ساکن باشند مورد بررسی قرار گرفت.بعد ازآن ان بعلت بالا بودن حجم محاسبات به روش های حل متفاوت برای مسایل مکان یابی با مانع پرداخته شد. اما از سوی دیگر موانع احتمالی بطور طبیعی در دنیای واقعی وجود دارد، یعنی موانع می توانند دارای موجودیت تصادفی، مکان تصادفی و یا اندازه تصادفی باشند.بعبارتی دیگر اجسام متحرک نقش بیشتر وواقعی تر در مسایل روزمره دارندو همچنین وجود همین موانع متحرک نقش اثر گذاری را در محاسبات ایفا می کنند و در نهایت بر روی میزان هزینه تاثیر گذار هستند. یک مثال ساده آن یک واگن در یک کارخانه می باشد که در یک مسیر ثابت در رفت و آمد می باشد.یا مساله یافتن مسیر بهینه برای یک ربات در نظر بگیرید که به عنوان یکی از مهمترین مسایل روز دنیای صنعت می باشد.یک ربات جهت جابجایی از یک نقطه به نقطه دیگر ، با توجه به رقابت های موجود در کاهش زمان ،نیازمند یافتن کوتاهترین مسیر می باشد که در طول پیمودن مسیر خود با موانع بسیار متحرک و ثابت برخورد می کند.بنابراین برنامه ریزی آن باید بصورتی باشد که بتواند با موانع موجود مسیر بهینه خود را بیابد. مدل پیشنهادی این تحقیق، یک مساله میانه با فواصل متعامد می باشد، بطوری که در ناحیه پیوسته یک مانع آرکی شکل وجود دارد که در مسیر دایره ای حرکت خود، از توزیع احتمال یکنواخت با پارامتر معین پیروی می کند. فرضیات مساله پیشنهادی بقرار زیر در نظر گرفته می شوند:
1- با مساله مکان یابی پیوسته میانه متعامد تک تسهیله با ظرفیت نامحدود سروکار داریم، یعنی هدف یافتن مکان تک تسهیل نقطه ای در میان یک تعداد متناهی تسهیلات موجود متناهی می باشد، بطوریکه ظرفیت تسهیل جدید برای خدمت دهی نامحدود می باشد.
2- مساله برای کل افق برنامه ریزی در ابتدای دوره، سیاست گذاری می کند، یعنی مساله مکان یابی ایستا می باشد.
3- هر تسهیل موجود دارای مکان ثابت با مختصات معین، قطعی و دارای وزن غیرمنفی می باشد.
4- با مساله مکان یابی محدود با یک مانع آرکی شکل احتمالی سر و کار داریم که در یک مسیر دایره ای شکل در حال رفت و برگشت می باشد.
5- مکان شروع مانع آرکی شکل، از توزیع یکنواخت با پارامترهای معین پیروی می کند.
6- تسهیلات موجود در مسیر مانع مستقر نیستند.
7- تسهیل جدید بر روی مسیر مانع آرکی شکل نمی توانند استقرار یابد.
8- تعامل مابین تسهیل جدید و موجود برقرار است.
1-2- ساختار پایان نامه
در ادامه در فصل 2، ادبیات موضوعی مسایل با مانع و مسایل مکان یابی تک تسهیله را مورد بررسی قرار خواهیم داد. در فصل 3 زمینه های علمی تحقیق شامل دسته بندی مسایل مکان یابی، انواع توابع فاصله، مساله مکان یابی کلاسیک، الگوریتم ابتکاری بطور مفصل تشریح خواهند شد. در فصل 4 به تشریح مساله و مدل پیشنهادی می پردازیم. در ادامه این فصل به منظور درک بهتر رفتار مدل، یک مثال نمونه ای ارائه خواهیم داد، اما با توجه به پیچیدگی های مدل پیشنهادی در مقیاس های بزرگ، الگوریتم ابتکاری نتایج محاسبات مربوط به این الگوریتم را مورد بررسی قرار خواهیم داد. در نهایت تعدادی از توسعه های آتی به همراه نتیجه گیری در فصل 5 مورد بررسی قرار گرفتند.

فصل دوم
مروری بر ادبیات موضوعی مسائل مکان یابی با مانع
25914351638935002-1- مقدمه
مسایل مکان یابی تک وسیله ای (تک تسهیله) پیوسته در سطح، یکی از حوزه های گسترده در مدل سازی ریاضی، در دنیای واقعی می باشند، که در این مسایل یک تسهیل جدید (تسهیل عرضه) به مجموعه ای از تسهیلات موجود (تسهیلات متقاضی)، با تقاضاهایشان، سرویس می دهد. در ادبیات موضوعی ، معمولا چند حالت از مسایل مکان یابی پیوسته، مورد بحث قرار می گیرند، مانند مساله میانه، مساله مرکز و مساله مرکز میانه. در مساله میانه کلاسیک (که غالبا مساله وبر، مساله فرمارت اشنایدر وبر و مساله حداقل مجموعنیز نامیده می شود)، در صدد یافتن مکان تسهیل جدید هستیم، بطوریکه مجموعه فواصل وزن دهی شده با تسهیلات موجود، حداقل گردد. برای اطلاعات بیشتر در این زمینه به فراهانی و حکمت فر]3[ و کلامروس ]4[ مراجعه کنید. در گونه ای از مسایل میانه، با محدودیت در قرارگیری و یا حرکت مواجه هستیم. در ادبیات موضوعی این نوع مسایل، معمولا سه دسته از این مسایل مورد مطالعه قرار گرفته اند. اولین دسته، نواحی ممنوعه نامیده می شوند که در این نواحی تسهیلات نمی توانند در آنجا قرار گیرند اما حرکت در میان این نواحی بلامانع و بدون جریمه می باشد (مانند مناطق و پارک های حفاظت شده و یا مناطقی که مشخصه های جغرافیایی از قبیل شیب تند زمین از ایجاد تسهیل مورد نظر ممانعت می کند). برای مطالعه بروی مسایل مکان یابی میانه و مرکز در نواحی ممنوعه به هاماخر و نیکل ]5[ مراجعه کنید.این دو نوسینده با استفاده از مفهوم طبقه بندی های مسایل مکان یابی تسهیلات را به عنوان مسایل کابردی ارایه دادند. دسته دوم به عنوان نواحی متراکم شناخته می شوند که در این نواحی قرار گیری یک تسهیل ممنوع بوده اما حرکت از میان آن با جریمه همراه می باشد (مانند دریاچه ای که، با قایق بتوان از دو طرف‌ آن عبور و مرور کرد. برای نمونه، مسایل مکان یابی با نواحی متراکم، با سرعت و هزینه های سفر مختلف، در بوت]6[ و بوت و کاوالیر ]7[ مورد بحث و بررسی قرار گرفته اند. دسته سوم نواحی هستند که تسهیل جدید نه می تواند در آنجا استقرار یابد و نه می تواند از میان آن عبور کند. این نواحی، نواحی با مانع نامیده می شوند. دریاچه ها، و بزرگراه ها و در مقیاس کوچکتر، نوار نقاله ها، ماشین آلات موجود در کارخانجات، مثال هایی از این نواحی می باشند. جدول (2-1) یک مرور اجمالی بر مسایل مکان یابی تسهیلات در حضور موانع وشکل (2 -1) شرایط مذکور را نشان می دهد.
476256350جدول (2-1). مروری اجمالی بر مسایل مکان یابی تسهیلات در حضور موانع
00جدول (2-1). مروری اجمالی بر مسایل مکان یابی تسهیلات در حضور موانع

نواحی با مانع نواحی متراکم نواحی ممنوعه غیر مجاز مجاز مجاز تردد
غیر مجاز غیر مجاز غیر مجاز استقرار

الف: نواحی ممنوعه. ب: نواحی متراکم ج: نواحی با مانع.
خطوط ممتد نشان دهنده نواحی ممنوع و خطوط خط چین نشان دهنده مجاز بودن است.
شکل (2 -1). نواحی با محدودیت در قرارگیری و یا حرکت.
2-2- مسایل مکان یابی همراه با موانع
مساله مکان یابی با مانع در حالتی در نظر گرفته می شود تسهیل جدید نه می تواند در آنجا استقرار یابد و نه می تواند از میان آن عبور کند. که اگرچه مسایل مکان یابی با مانع، در مقایسه با مسایل مکان یابی کلاسیک خیلی عملی تر و نزدیک تر به دنیای واقعی می باشند اما به علت پیچیدگی محاسباتی که این نوع مسایل دارند، تنها در چند دهه اخیر، وارد ادبیات موضوعی شده اند.
مدلسازی مکان یابی با نواحی با مانع، برای اولین بار توسط کاتز و کوپر ]8[ معرفی شد. نویسندگان یک مساله وبر صفحه ای را با فواصل اقلیدسی و یک مانع دایره ای در نظر گرفتند. همچنین آنها، نشان دادند که چنین مسایلی دارای تابع هدف غیرمحدب هستند و در ادامه برای حل آن یک روش ابتکاری مبتنی بر تکنیک کمینه سازی متوالی بدون محدودیت (SUMT) پیشنهاد دادند.شکل (2-2) مساله در نظر گرفته شده توسط کاتز و کوپر را نشان می دهد.
8610602063115شکل (2-2) . نوع مانع در نظر گرفته شده توسط کاتز و کوپر.
00شکل (2-2) . نوع مانع در نظر گرفته شده توسط کاتز و کوپر.

با توجه به بزرگ بودن ابعاد حل مساله در بدست آوردن نقاط بهینه در مسایل مکان یابی با مانع بایشوف و کلامروس ]27[، با پیشنهاد یک روش حل مبتنی بر الگوریتم ژنتیک (GA)، بر این مشکل فائق گشتند و در این کار آنها فاصله مورد نظر را به صورت متعامد در نظر گرفتند.این دو نویسنده دو روش ابتکاری که هر کدام از روشها از دو حل ابتدایی که توسط یک الگوریتم ابتکاری بدست می آید، را معرفی کردند، سپس براساس نتیجه محاسباتی، به بررسی روش های ابتکاری معرفی شده پرداختند و نتایج محاسبات خود را با الگوریتم های پیشین مقایسه کردند.شکل (2-3) نمای کلی الگوریتم های ابتکاری را نشان می دهد، بصورتی که توده ابری مورد نظر به عنوان نقاط ابتدایی برای الگوریتم استفاده شده است که شعاع این توده در هر سمت می تواند متفاوت باشد.بعبارتی دیگر با نرخ های متفاوت می توان قطرهای متفاوتی برای مساله تعریف کرد که در نهایت بر جواب مساله تاثیرگذار هستند.از آنجاییکه تعیین این اقطار دشوار بوده است از یک شیوه تخمینی استفاده کردند که در این شیوه چند نقطه مختلف در صفحه را درنظر گرفتند سپس پاره خط هایی مماس بر دایره ترسیم کرده که متوسط زاویه های ایجاد شده اساس کار می باشد.
-8623302142490شکل( 2- 3). رویکرد در نظر گرفته شده برای حل مسایل مکان یابی
با مانع توسط بایشوف و کلامروس.
00شکل( 2- 3). رویکرد در نظر گرفته شده برای حل مسایل مکان یابی
با مانع توسط بایشوف و کلامروس.

بایشوف و همکاران ]30[مساله مکان یابی – تخصیص تسهیلات در حضور مانع چند وجهی و فاصله اقلیدسی در نظر گرفته اند و جهت حل مساله با ابعاد بزرگ از الگوریتم فرا ابتکاری ژنتیک استفاده کرده اند. کلامروس ]24[ جهت حل مساله مکان یابی در ابعاد بزرگ ناحیه شدنی را به یک تعداد سلول های محدب با تابع هدف محدب تجزیه کرد. شکل(2-4) فضای حل را که بصورت نواحی تقسیم شده نسبت به تسهیل جدید و تسهیل موجود را نشان می دهد در نظر می گیرد.
1676402545715شکل( 2- 4). رویکرد در نظر گرفته شده برای حل مسایل مکان یابی با مانع توسط کلامروس.
00شکل( 2- 4). رویکرد در نظر گرفته شده برای حل مسایل مکان یابی با مانع توسط کلامروس.

بوت و کاوالیر ]12[ مساله محدب مکان یابی را با استفاده از تقسیم صفحه مختصات به زیر صفحه های معادل، روشهای ابتکاری را توسعه داد. آنجا و پارلر ]11[ مساله مکان یابی با مانع چند وجهی میانه را با استفاده از یک روش ابتکاری حل نموده و جواب های حاصل را با روش ابتکاری پیشین مقایسه کرد.
و در کار خود یک مانع چند وجهی متوازن را با فاصله اقلیدسی در نظر گرفته و شرایط حضور مانع را تشریح کرده اند و با استفاده از الگوریتم شبیه سازی تبرید (SA) بر مبنای الگوریتم کوتاه ترین مسیر دایجسترا حل تقریبی را بدست آوردند.شکل (2-5) شکل مانع در نظر گرفته شده توسط آنجا و پارلر را نشان میدهد.
9569452293620شکل (2-5) . نوع مانع در نظر گرفته شده توسط آنجا و پارلر.
00شکل (2-5) . نوع مانع در نظر گرفته شده توسط آنجا و پارلر.

کلاچانکوتو [46] مساله مکان یابی تسهیلات با مانع را با در نظر گرفتن یک مانع مستطیلی شکل را با رویکرد الگوریتم ابتکاری حل کرده است.شکل (2-6) شکل مانع در نظر گرفته شده توسط کلاچانکوتو را نشان می دهد.
6972301717675شکل (2-6) . نوع مانع در نظر گرفته شده توسط کلاچانکوتو.
00شکل (2-6) . نوع مانع در نظر گرفته شده توسط کلاچانکوتو.

روش ابتکاری بوت و کاوالیر ]12[ مساله وبر محدودیت دار را به دو مساله تقسیم کرده و با استفاده از تکرار محدودیت ها ،الگوریتم پیش رفته و شرط توقف را بهتر نشدن جواب قرار دادند، سپس براساس شرط توقف معرفی شده، الگوریتم منجر به حل بهینه تخمینی می شود.بر مبنای کار بوت و کاوالیر کلامروس ]14[ با تقسیم مساله اصلی غیر محدب را به یک تعداد زیر مساله محدب رویکردی کاراتر و موثر تر را ایجاد کرده، سپس یک حل دقیق و یک روش ابتکاری مبتنی بر این رویکرد تجزیه سازی، توسعه دادو نتایج را با تقسیم مساله به زیر ناحیه های غیر محدب مقایسه و کارایی بیشتر را اثبات کردند.
فریث و همکاران ]26[ با استفاده از رویکرد انتشار امواج رادیویی دایره ای ، کوتاه ترین فاصله بین نقاط را یک مساله مکان یابی مرکز را در حضور موانع چندوجهی همراه با تابع فاصله اقلیدسی تعیین کردند و سپس یک شبیه سازی کامپیوتری برای فواصل اقلیدسی و متعامد جهت اثبات کارایی این رویکرد، ارائه کردند.
مک گاروی و کاوالیر [ 22 [مساله مکان یابی میانه در حضور موانع چند وجهی و فواصل اقلیدسی در نظر گرفت. روش بکار گرفته توسط این دو نویسنده روش اصلاح شده «مربع بزرگ مربع کوچک (BSSS) » می باشد. روش BSSS یک الگوریتم هندسی شاخه و کران می باشد که توسط هانسن و همکاران ]32[ پیشنهاد شد. روش BSSS در ابتدا برای حل مسایل مکان یابی تسهیلات ناخوشایند پیشنهاد شد. این الگوریتم برای مسایل مکان یابی پیوسته به این صورت طراحی شد که از طریق گسسته سازی، یک سطح یا صفحه پیوسته ناحیه شدنی را به یک تعداد زیر منطقه مربعی شکل تقسیم می کند.
باتا و همکاران ]10[ ، یک مساله مکان یابی سطحی با فاصله متعامد را بصورت یک مساله p-median برای نواحی ممنوعه در نظر گرفتند و مساله مکان یابی دیگر را با موانع با اشکال دلخواه مورد ارزیابی قرار دادند.نوع فاصله در این مساله بصورت اقلیدسی در نظر گرفته شده است. رویکرد حل این مساله در نظر گرفتن مساله بصورت یک مساله صف احتمالی میانه بوده و میزان اثرگذاری رویکرد را پیدا کردن نقطه بهینه در زمانی که تعداد تسهیلات زیاد می شوند را به تصویر کشیده اند.
مساله وبر با اشکال دلخواه موانع در حالت خاص از فاصله منهتن (متعامد)، توسط لارسون و صدیق]9[ بررسی شد. نویسندگان با ایجاد ساختار شبکه ای (شبکه موازاییکی) از گره و یال و با تعیین مجموعه متناهی مسلط و با بکارگیری مساله p-median مشخص کردند که این شبکه حاوی حداقل یک حل بهینه می باشد.رویکرد حل در این شیوه تحدید جواب های بدست آمده از نقاط مختلف بوده و گام به گام الگوریتم به سمت جواب های بهینه پیش می رود. دسته ای دیگر از تحقیقات ، در ادامه ی مطالعات لارسون و صدیق ]9[ و باتا و همکاران ]10[ توسط ساواش و همکاران ]20[ آغاز شد. نویسندگان مدلی برای قرارگیری تسهیلات با اندازه متناهی توسعه دادند که ممکن است اندازه شان برای خودشان به عنوان مانع عمل کنند، بصورتی که وجود یک تسهیل در یک فضای کوچک برای تشهیل دیگر مانع محسوب می شودکه با استفاده از این مفهوم مساله تبدیل به یک مساله مکان یابی با مانع می شود.
هاماخر و کلامروس ]13[مساله وبر با موانع و فواصل بلوکی ، که یک مساله مکان یابی گسسته می باشد را درنظر گرفته و محاسبات دقیق ریاضی جهت حل این مساله ارائه دادند. کارایی محاسبات انجام شده و مقایسه رویکرد حل بدست آمده با کارهای پیشین و برطرف کردن فاصله های ایجاد شده با استفاده از یک مجموعه مسلط کاهیده شده،در کار هاماخر و کلامروس ] 13] ، توسط دیرینگ و سگراس]18-17[ بطور قابل ملاحظه ای بهبود داده شد. دیرینگ و همکاران ]25[ فواصل با نرم بلوکی را بر مبنای کار دیرینگ و همکاران ]16[ توسعه دادند.اساس کار این الگوریتم مبتنی بر یک مجموعه متناهی کاندید، به نام مجموعه مسلط برای مساله مرکز با فواصل متعامد می باشد.
وانگ و همکاران ]21[، مساله مکان یابی تک تسهیله را در جانمایی کف یک فروشگاه با فواصل متعامد مورد مطالعه قرار دادند. در این مقاله با توجه به نقاط ورودی و خروجی تسهیلات تقاضای مستطیلی شکل با مکان ثابت، حداقل هزینه ی مسافت کل، از تسهیل عرضه، که به این تسهیلات سرویس می دهد، بدست آمد. کلاچنکاتیو و همکاران ]28[ استقرار یک تسهیل با اندازه محدود را در چیدمان در صورتی که تسهیل جدید و دپارتمان های موجود مستطیل شکل و فواصل از نوع نرم باشند، در نظر گرفتند. آنها این فرض را در مساله خود در نظر گرفتند که تسهیل جدید بعلت برخی محدودیت ها نمی تواند در مکان بهینه تسهیلات استقرار یابد، بنابر این از خطوط کانتور به منظور یافتن مکان مناسب جایگزین برای دپارتمان جدید استفاده کردند.
ناندیکوندا و همکاران ]23[ مساله مکان یابی مرکز با اندازه نامحدود را در حضور موانع با اشکال دلخواه و فواصل منهتن بررسی کرده و از تکنیک تجزیه سازی ناحیه شدنی به سلول های محدب برای این مساله استفاده کردند. در راستای کار تجزیه سازی ناحیه شدنی، سرکار و همکاران ]29[ که مکان یابی یک تسهیل با اندازه محدود و شکل دلخواه را در حضور موانع با اشکال دلخواه و تابع هدف مرکز و تابع فاصله متعامد در نظر گرفتندو تفاوت در جواب های حاصل شده ناشی از تفاوت در اندازه فضای جواب می باشد . نویسندگان ، در ادبیات موضوعی مسایل وبر علاوه بر موانع چند وجهی و دایره ای ، یک مانع خطی، همراه با تعدادی گذرگاه توسط کلامروس ]15[ برای هر نوع فاصله دلخواه ، معرفی کردند.و هدف بیان این مساله مشخص کردن بهترین جواب در نواحی شدنی در صورت وجود خطوط موانع عبوری می باشد. کلامروس و ویچک ]19[ مدل جایابی تسهیلات را با حضور یک مانع خطی را بصورت یک مساله دو هدفه میانه بررسی کردند.
موانع احتمالی بطور طبیعی در برخی موارد از دنیای واقعی اتفاق می افتد. موانع ممکن است، دارای موجودیت تصادفی، مکان تصادفی و یا اندازه تصادفی باشند. برای مثال، در چیدمان تسهیلات، واگن های که می توان از عرض آن نسبت به طول آن صرفنظر کرد و در روی ریل برای حمل داخل کارخانه بطور مداوم در حرکتند، برای جریان مواد داخل کارخانه تداخل ایجاد می کنند را می توان، یک نمونه از این موانع خطی با مکان احتمالی برشمرد. کانبولات و وسولوسکی ]31[ برای اولین بار، بطور رسمی بروی موانع احتمالی بحث کردند. نویسندگان برای مساله میانه، مکان یابی یک تسهیل را در حضور یک مانع خطی با مکان احتمالی و فواصل متعامد را در نظر گرفتند. نویسندگان فرض کردند که نقطه شروع مانع خطی احتمالی دارای توزیع یکنواخت در یک بعد می باشد و با استفاده از مفهمو امید ریاضی توابع یکنواخت ، فاصله انتظاری بین دو تسهیل را محاسبه کرده و الگوریتمی ابتکاری برای حل مدل ارائه کردندو مکان یابی تک تسهیله مدنظر قرار گرفته شده است. در راستای کار کانبولات و وسولوسکی ]31[ مکان یابی چند تسهیله در حضور یک مانع خطی احتمالی توسط شیری پور و همکاران [46] ارائه شد. نویسندگان فاصله انتظاری تسهیلات را در حالتی که چندین تسهیل در صفحه وجودداشته باشد محاسبه کرده و از دو الگوریتم فرا ابتکاری ژنتیک و رقابت استعماری برای حل مساله در ابعاد بزرگ استفاده کردند.امیری عارف و همکاران [47] ، نیز مکان یابی تک تسهیله را درحضور یک مانع خطی احتمالی را بصورت یک مساله مکان یابی مرکزی در نظر گرفته و رویکرد حل را برای این مساله نیز ارائه شده است.
2-3- مسایل مکان یابی تک تسهیله
در دسته ای دیگر از مسایل وبر که مسئله مکانیابی تک تسهیله نامیده می شوند، ما مکان های بیش از یک تسهیل جدید را در فضای شدنی مسئله جستجو می کنیم. در این مساله تعیین مکان یک وسیله جدید نسبت به یک تعداد وسیله موجود مورد بررسی قرار می گیرد.مکانی که به دنبال آن هستیم، جایی است که یک تابع هزینه کل تعریف شده را حداقل می کند و هزینه کل مذکور متناسب با فاصله در نظر گرفته می شود. در واقع مسایل مکان یابی تک تسهیله حالت خاصی از مسایل مکان یابی چند تسهیله می باشند با این تفاوت که در مکان یابی تک تسهیله تنها بین تسهیلات جدید و موجود تعامل برقرار است .تعدادی از مسائل جایابی تک تسهیله پر کابرد عبارتند از:
ماشیت تراش جدید در یک مکان تولیدی
سبد ابزار در یک وسیله تولیدی
انبار جدید برای تسهیلات تولیدی و مشتریان
بیمارستان،ایستگاه آتش نشانی، اداره پلیس در یک کلان شهر
منبع آب در یک ساختمان
سکوی بارگیری در یک انبار
دستگاه کپی در یک کتابخانه.
با توجه کاربرد های زیاد مکان یابی تک تسهیله مطالعه های زیادی دز این زمینه انجام شده است.
انواع مکان یابی تک تسهیله عبارت است از:
مسائل جایابی با فاصله متعامد
مسائل جایابی با فاصله مجذور اقلیدوسی
مسائل جایابی با فاصله اقلیدوسی
در مسائل جایابی تک تسهیلاتی هزینه گردش مواد یا یک تابع خطی از فاصله متعامد یا اقلیدسی یا یک تابع درجه دوم از فاصله اقلیدسی می باشد.یکی از رویکردهای حل این مساله استفاده از خطوط همتراز می باشد که این خطوط هم تراز برای کمک کردن به تحلیل استقرار در انتخاب یک جای مناسب برای وسیله جدید ترسیم می شوند.در نتیجه اگر شما وسیله جدید را نزدیک به مکان بهینه قرار دهید، یک حل بسیار خوب بدست می آید.اگر مکان بهینه برای وسیله جدید نزدیک وسیله موجود قرار گیرد، اگر عملی بود که مشکلی وجود ندارد در غیر این صورت خطوط هم تراز می توانند برای جستجوی یک مکان شدنی مورد استفاده قرار گیرند.
زعفرانیه و همکاران [33] الگوریتمی برای مساله جایابی تک تسهیلاتی در دو منطقه با نرم های متفاوت پیشنهاد داده بوده اند و نشان داده اند که حل بهینه در تقاطع متعامد تسهیلات موجود است.این مساله در حقیقت تعمیم یافته مساله جایابی تک تسهیله است.
پارلار]34[ در مورد این مساله با فاصله اقلیدسی و متعامد بحث کرده است. وی نشان داده است که تابع هدف در این جا محدب نیست و به صورت برنامه ریزی عدد صحیح مختلط فرموله می گردد.
بریمبرگ و همکاران [35] نشان داده اند که این مساله معادل با حل تعدا معینی برنامه ریزی محدب است و استراتژی های بهینه سازی را پیشنهاد داده اند.رودریگوز و همکاران [36] مدلی را برای مساله جایابی تک تسهیلاتی نا خوشایند پیشنهاد داده اند.در این منبع علمی مقاله مجموعه ای متناهی از حل بهینه برای یک مساله با فاصله اقلیدسی تعیین گشته است.بریمبرگ و جویل ]37[یک روش خط سیر را برای ایجاد یک مرز کارای نقاط برای یک مدل دو معیاره جایابی تک تسهیله نیمه خوشایند در صفحه مورد بررسی قرار داده اند.معیار اول برای اندازه گیری هزینه حمل و نقل و دومی برای تخمین هزینه اجتماعی یا محیطی مورد استفاده قرار گرفته است. در این جا وزن های نسبی تغییر می کنند به گونه ای که مجموع وزن های دو معیاره مینیمم گردد. تامیر ]38[ مساله جایابی تک تسهیلاتی تعریف شده بر روی فضاهای متعامد و فضاهای به وجود آمده توسط شبکه های درختی را مورد بررسی قرار داده است. در اینجا فضاهای گسسته که در آن ها وسیله جدید مجبور است که در یک مجموعه متناهی مشخص شده قرار بگیرد در نظر گرفته شده است و هدف ارزیابی در هر نقطه فضای تعریف شده است. سیلوا و دلافیگورا ]39[ یک مسئله مکانیابی تسهیل ظرفیت دهی شده با احتمالات پشتیبانی محدود شده را معرفی کردند. آنها تقاضا را بصورت احتمالی در نظر گرفتند و هر یک از تسهیلات را بصورت یک صف مستقل فرمول بندی کردند. سپس یک روش ابتکاری برای حل مدل فرمول بندی معرفی کردند. لاو [40] مساله جایابی بهینه تک تسهیله خدمت دهی با فاصله متعامد را مورد بحث قرار داد. فضاهای به صورت متعامد در نظر گرفته شده اند. زانتوپولوس و ملاچرینودیس [41] مساله جایابی ت تسهیلاتی نیمه زیان آور را درفضای اقلیدسی مورد بررسی قرار داده اند. دو هدف برای این مساله در نظر مینیمم آن نسبت به همه نقاط تقاضا و دیگری مینیمم کردن هزینه حمل و نقل کل از وسیله جدید به همه نقاط تقاضا است گرفته شده است. یکی مینیمم کردن اثرات ناخوشایند وسیله جدید با بیشینه کردن فاصله اقلیدسی.
.
فصل سوم
زمینه های علمی تحقیق
265620571437500
3-1- مقدمه
یکی از مسائلی که باید در مراحل اولیه طراحی سیستم های صنعتی مورد توجه قرار گیرد، مساله مکان یابی و استقرار تسهیلات است.برنامه ریزی تسهیلات که از مباحث مهم در مهندسی صنایع است دو بخش عمده مکان یابی (جایابی) و طراحی را شامل می شود که مهم ترین بخش طراحی، استقرار یا جانمایی و بخش های دیگر آن، حمل و نقل و طراحی ساختمان و تاسیسات منظور از تسهیلات، هر مجموعه، شامل کارخانه، دانشگاه، بیمارستان و غیره است.مراکز صنعتی و کارخانجات برای تعیین مکان احداث کارخانه، استقرار دفاتر خود در سطح شهر ،تعیین مراکز توزیع محصولات و ... با چنین مسائلی سروکار دارند.
در مکان یابی، ما به بررسی محل قرار گرفتن یک وسیله برای رسیدن به اهداف مورد نظر می پردازیم که برای تعیین محل آن، معیارهای مهمی موثرند، از جمله نزدیکی به جاده های اصلی، بازار مصرف، منابع تامین مواد اولیه، در دسترس بودن نیروی انسانی مورد نیاز، شرایط محیطی، امکان توسعه ، مقررات و قوانین دولتی و ...، و در طرح استقرار می خواهیم نحوه قرار گرفتن اجزای یک وسیله را برای رسیدن به بهترین بهره وری تعیین کنیم. روش های زیادی تاکنون برای حل این گونه مسایل مطرح شده اند که از آن جمله می توان به برنامه ریزی ریاضی، استفاده از تصمیم گیری های چندگانه و غیره اشاره کرد ]1[.
در بخش دولتی، تعیین مکان مراکز خدماتی نظیر ایستگاه های پلیس راه ، بیمارستان ها، ایستگاه های آتش نشانی و غیره نیاز به اتخاذ چنین تصمیماتی دارد. لذا تصمیم گیری در مورد مکان یابی تسهیلات عمدتا از تصمیم گیری های بلندمدت و استراتژیک شرکت های بزرگ خصوصی و دولتی است و هزینه های بالا مربوط به جایایی و استقرار و راه اندازی تسهیلات، پروژه های مکان یابی را به سرمایه گذاری های بلندمدت تبدیل کرده است. لذا موقعیت یا شکست مراکز تسهیلاتی در هر کدام از بخش های دولتی و خصوصی، بستگی کامل به مکان های انتخابی برای آنها دارد. بدین ترتیب، اهمیت مساله مکان یابی و استقرار تسهیلات و ضرورت پرداختن بدان بر همگان روشن است ]1[.
3-2- دسته بندی کلی مسایل برنامه ریزی تسهیلات
مسایل برنامه ریزی تسهیلات به چهار دسته عمده زیر تقسیم می شوند:
1-مکان یابی
2 –مسیریابی
3-تخصیص
4-طراحی تقسیم می شود. ]1[
-351790401320مکان یابی- تخصیص تسهیلات
مسیر یابی- تخصیص تسهیلات
طراحی ساختاری
انتقال مواد
جانمایی تسهیلات
تخصیص تسهیلات
مسیر یابی تسهیلات
طراحی تسهیلات
برنامه ریزی تسهیلات
مکان یابی تسهیلات
00مکان یابی- تخصیص تسهیلات
مسیر یابی- تخصیص تسهیلات
طراحی ساختاری
انتقال مواد
جانمایی تسهیلات
تخصیص تسهیلات
مسیر یابی تسهیلات
طراحی تسهیلات
برنامه ریزی تسهیلات
مکان یابی تسهیلات
در شکل (3-1) این دسته بندی نشان داده شده است.
3
229235247650شکل (3-1). دسته بندی مسایل برنامه ریزی تسهیلات.
00شکل (3-1). دسته بندی مسایل برنامه ریزی تسهیلات.

3-3- دسته بندی مسایل مکان یابی با نگرش سنتی
دسته بندهای کلاسیک مسایل مکان یابی عمدتا براساس موارد زیر بوده است [1] :
براساس خصوصیات وسایل جدید
مساله مکان یابی تک وسیله / چند وسیله
مساله مکان یابی با وسایل نقطه ای / ناحیه
براساس خصوصیات وسایل جدید
مساله مکان یابی با وسایل ایستا /پویا
مساله مکان یابی وسایل با مکان قطعی / احتمالی
براساس نوع ارتباط وسایل موجود و جدید
مساله مکان یابی با ارتباطات برون زا / درون زا
مساله مکان یابی با ارتباطات ایستا / پویا
مساله مکان یابی با ارتباطات قطعی/احتمالی
براساس فضای جواب
مسایل مکان یابی روی خط / صفحه
مساله مکان یابی گسسته / روی شبکه
مساله مکان یابی با فضای مقید / نامفید
براساس نوع تابع فاصله
مساله مکان یابی با فواصل متعامد / چبی شف
مساله مکان یابی با فواصل اقلیدسی / مجذور اقلیدسی
مساله مکان یابی با سنجه های خاص
براساس نوع و تعداد هدف و شاخص انتخاب
مسایل تک هدفه / چند هدفه
مسایل تک شاخصه / چند شاخصه
مسایل میانه / مرکز / پوشش
براساس زمینه مساله
مساله مکان یابی انبار / کارخانه
مساله مکان یابی نقاط تبادل
مساله مکان یابی وسایل ناخوشایند
مساله مکان یابی وسایل گردشی «مسایل مکان یابی ـ مسیریابی»
مساله مکان یابی سلسله مراتبی
3-4- فواصل در مسایل برنامه ریزی تسهیلات
اگر مختصات تسهیل جدید و برای وسیله موجود در صفحه 2 بعدی باشند، آنگاه فواصل زیر را می توانیم تعریف کنیم.
3-4-1- فاصله خط مستقیم یا اقلیدسی
فاصله اقلیدسی بین دو نقطه xi,yi) Ai= (و B=(a,b) به صورت زیر تعریف می شود :
(3-1) dAi,B=[(xi-a)2+(yi-b)2]12فاصله اقلیدسی برای برخی از مسایل جایایی شبکه، شامل نقاله به کار می رود. برخی از مسایل سیم کشی الکتریکی و مسایل طراحی لوله کشی نیز نمونه هایی از مسایل فاصله اقلیدسی هستند. شکل (3-2) مسیر حاصل از فاصله اقلیدسی را نشان می دهد.
4533902032000شکل(3-2). فاصله اقلیدسی بین دو نقطه.
00شکل(3-2). فاصله اقلیدسی بین دو نقطه.

3-4-2- فاصله مجذور خط مستقیم یا اقلیدسی
در برخی مسایل جایایی تسهیلات، هزینه تابع درجه اول فاصله نیست. به عنوان مثال، انتظار می رود هزینه مرتبط با عکس العمل یک ماشین آتش نشانی با فاصله غیر خطی باشد. فرض کنید، هزینه با مربع فاصله اقلیدسی بین و متناسب باشد. فاصله مجذور خط مستقیم یا فاصله اقلیدسی بین دو نقطهAi=(xi,yi) و B=(a,b) به صورت زیر تعریف می شود :
(3-2) dAi,B=(xi-a)2+(yi-b)2این نوع فاصله می تواند در مسایل خدمات اورژانسی و آتش نشانی کاربرد داشته باشد.
3-4-3- فاصله منهتن یا متعامد
در بیشتر مسایل مکان یابی ماشین، فاصله در مجموعه ای از راهروهایی پیموده می شود که در الگویی مستطیلی و موازی با دیوارهای مجموعه هستند. در چنین وضعیتی ، فاصله متناسب به صورت متعامد مستطیلی کلان شهری یا منهتن است (گاهی اوقات فاصله خطی شکسته، پله ای و راهرویی نیز نامیده می شود). در این فواصل فاصله بین دو نقطه بصورت خطوط شکسته محاسبه می شود بصورتی که حرکت از یک نقطه به نقطه دیگر در راستای افق و قائم انجام می شود. فاصله متعامد بین دو نقطهAi=(xi,yi) و B=(a,b) به صورت زیر تعریف می شود:
(3-3) dAi,B=│yi-b│+│xi-a│فاصله متعامد برای تحلیل های جایابی شهری مناسب است که در آن سفر در امتداد مجموعه محدبی از خیابان ها اتفاق می افتد. به علاوه تعدادی از ادارات ، مجموعه از راهروهای و تالارهای متعامد را برای حرکت پرسنل به کار می برند. شکل (3-3) مسیرمتعامد را بین دو نقطه نشان می دهد.
5181602093595شکل(3-3). فاصله متعامد بین دو نقطه.
00شکل(3-3). فاصله متعامد بین دو نقطه.

3-4-4- فاصله چبی شف
فاصله چبی شف برابر است با ماکزیمم فواصل افقی و عمودی. فاصله چبی شف بین دو نقطه xi,yi) Ai= (و B=(a,b) به صورت زیر تعریف می شود:
(3-4) dAi,B=max⁡{│yi-b│,│xi-a│}از جمله کاربردهای این فاصله این است که حرکت مواد در کارخانه به کمک جرثقیل های مجهز به دو موتور انجام می شود که موتور سبب حرکت در جهت محور x ها و دیگری سبب حرکت در محور y ها است. همچنین در مسایل انتخاب سفارش نیز این فاصله کاربرد دارد که کدامین سفارش پذیرفته شود.اما معملا این نوع فاصله در مواقع خاص مورد استفاده قرار می گیرد.
3-4-5- کوتاه ترین مسیر
در مسایل مکان یابی روی شبکه از آن جا که معمولا بیش از یک مسیر بین هر دو گره وجود دارد، روش کوتاه ترین مسیر برای تعیین فاصله بین دو گروه مورد استفاده قرار می گیرد.بصورتی که ابتدا مجموعه ای از گره ها در نظر گرفته می شود و برای هرگروه میزان فاصله کل طی شده محاسبه می شود سپس کمترین میزان به عنوان کوتاهترین مسیر شناخته می شود. شیوه دیگر در جریان های شبکه ای استفاده از روابط بازگشتی است که آخرین گره به سمت اولین گره مسیرهای مختلف طی می شود و مسیری بعنوان مسیر بهینه شناخته می شودکه کوتاهترین فاصله راطی کرده باشد.برای شبکه های کوچک با بررسی تمام مسیرهای ممکن می توان به کوتاهترین مسیر رسید،اما در شبکه های بزرگ استفاده از الگوریتم های ابتکاری لازم می باشد
3-5- مسایل مکان یابی میانه تک تسهیله با انواع فاصله
در این قسمت مساله تعیین مکان یک وسیله جدید نسبت به یک تعداد وسیله موجود مورد بررسی قرارمی گیرد. مکان های که به دنبال آنها هستیم، جایی است که یک تابع هزینه کل تعریف شده را حداقل می کند و هزینه کل مذکور متناسب با فاصله در نظر گرفته می شود.
تعدادی از مسایل مکان یابی تک تسهیله جالب وجود دارند که برای نمونه تعیین مکان تسهیلات زیر قابل ارائه است :
ماشین تراش جدید در یک مکان تولیدی،
انبار جدید برای تسهیلات تولیدی و مشتریان،
بیمارستان، ایستگاه آتش نشانی، اداره پلیس یا کتابخانه در یک کلان شهر.
جهت فرمولبندی کلی مساله مکانیابی تک تسهیله mوسیله موجود در نقاط مشخص قرار گرفتهاند.یک وسیله جدید قرار است در نقطهx قرار گیرد.هزینه حمل و نقل مستقیما متناسب با فاصله بین وسیله جدید و موجود در نظر گرفته می شود. dAi,B فاصله پیوده شده در تعداد سفرهای سالیانه بین وسیله جدید و موجود را نشان می دهد. هزینه کل سالیانه سفر بین وسیله جدید و همه تسهیلات موجود به وسیله فرمول زیر بیان می شود:
(3-5) fx=i=1mWidAi,Bبه عنوان نمونه خیلی ساده از مساله مکان یابی تک تسهیله، وسلیه جدید می تواند کارخانه هایی باشند که تامین کننده انبارهایی است که تسهیلات موجودند و هزینه های حمل و نقل متناسب با فاصله بین کارخانه و انبارها هستند؛ wj می باشد.
در نمونه دیگر وسایل جدید می توانند ماشین هایی جدید باشند که قرار است در یک طرح استقرار ماشین آلات جایابی شوند. از آنجا که محصولات بین ماشین جدید و موجود به عقب و جلو سفر می کنند، هزینه ها متناسب با فاصله هستند.در خیلی از موارد، هزینه در هر واحد فاصله، عدد ثابتی است.بنابراین مساله مینیمم سازی اغلب به تعیین مکانی که فاصله را مینیمم می کند ،کاهش می یابد.در بحث مسائل جایابی تک تسهیلاتی فرض می شود که داده های واقعی در دسترس بودند که در برخی موارد مقادیر در طول زمان می توانند تغییر یابند که در این حالت می توان مینیمم کردن هزینه تخفیف گردش مواد را در مسائل در نظر گرفت.که در این حالت پیشنهاد می شود که تعدادی تخمین متفاوت برای این مقادیر زده شده و مسأله جایابی با هر ترکیبی از تخمین ها حل شود.
در ادامه به بررسی انواع مسائل مکان یابی تک تسهیله می پردازیم.
3-5-1- مسایل مکان یابی میانه تک تسهیله با فاصله متعامد
در بیشتر مسایل جایابی ماشین، فاصله در مجموعه ای از راهروهایی پیموده می شود که الگویی مستطیلی و موازی با دیوارهای ساختمان هستند. در چنین وضعیتی، فاصله متناسب به صورت متعامد، مستطیلی، یا منهتن است. مساله جایابی با فاصله متعامد، هم برای تعداد زیادی از مسائل جایابی بکار می رود و هم برای تحلیل خیلی ساده تر است و از این رو کاربرد فراوانی خواهد داشت.تعداد مسیرهای متعامد مابین دو نقطه متناهی بوده و مسیرهای متفاوتی می توان تعریف کرد.مساله مکان یابی تک تسهیله با فاصله متعامد بصورت زیر بیان می شود:
(3-6) fx=i=1mWi(│yi-b│+│xi-a│)فاصله متعامد برای برخی تحلیل های جایابی شهری مناسب است که در آن سفر در امتداد مجموعه محدبی از خیابان ها اتفاق می افتد. به علاوه ، تعدادی از ادارات، مجموعه ای از راهروها و تالارهای متعامد را برای حرکت پرسنل به کار می برند. در این حالت هزینه تایع خطی درجه اول از فاصله است.
برخی از خاصیت های یک حل بهینه برای مساله جایابی با فاصله متعامد بصورت زیر هستد:
خاصیت انطباق
مختصه افق وسیله جدید با مختصه افق برخی از تسهیلات موجود یکسان خواهد بود.به طور مشابه، مختصه قایم وسیله جدید بر مختصه قایم برخی از تسهیلات موجود منطبق خواهد شد.البته لزومی ندارد که هر دو مختصه مشابه یک وسیله موجود باشند.
خاصیت میانی
مکان بهینه مختصهx برای وسیله جدید یک مکان میانه است.یک مکان میانه است اگر بیش تر از نیمی از گردش مواد در سمت چپ آن و بیش تر از نیمی از گردش مواد در سمت راست آن نباشد.شاید اصطلاح میانه برای خاصیت فوق چندان مناسب نباشد،زیرا غلط انداز است و این معنا را تداعی می کند که نیمی از تسهیلات موجود در سمت چپ و نیمی دیگر در سمت راست میانه قرار گیرد.لذا اصطلاح مکان نیم-مجموع برای خاصیت فوق مناسب تر باشد.
راه حل های متفاوتی برای یافتن مکان میانه در حالت مسایل مکان یابی میانه تک تسهیله با فاصله متعامد وجود دارند که این راه حل ها عبارتند است از:
روش تجمع اوزان برای یافتن مکان میانه
برای مسائل جایابی که تعداد زیادی از تسهیلات موجود و مقادیر بزرگی از وزنها را در بر می گیرد،روش کارآمدتری برای تعیین مکان میانه وجود دارد.ما وزن های تجمعی را بر 2 تقسیم کرده و مکانی را تعیین می کنیم که بیش از نیمی از وزن ها در سمت راست و بیش از نیمی در سمت چپ نباشند.
روش خطوط تراز برای یافتن مکان میانه
این شیوه زمانی بکار می رود که نقطه ای به عنوان یک محل قرار دادن در دسترس نباشد.برای مثال نقطه ممکن است غیر قابل دسترس باشد یا بر ساختار دیگری مثل یک رودخانه یا یک پارک شهرداری منطبق گردد.از آن جا که احتمال دارد چنین اتفاقی برای تعدادی از مسائل جایابی تسهیلات وجود داشته باشد، بررسی بیشتری برای این سؤال مورد نیاز خواهد بود.خطوط همتراز به عنوان یک ابزار مفید ارزیابی مکان های مختلف برای وسیله جدید،دید قابل ملاحظه ای به شکل سطح تابع هزینه کل می دهد. خطوط همتراز بر هزینه جریمه مرتبط با انتخاب یک مکان غیر بهینه اشاره می کند.از آن جا همه فاکتورهای مهم در تصمیم گیری برای جایابی در تابع هدف دیده نمی شود، تصمیم نهایی،که در آن قضاوت درونی وارد می شود از طریق ساختار خطوط هم تراز ساده تر خواهد بود.
روش برنامه ریزی خطی برای یافتن مکان میانه
یکی دیگر از روش های حل مسأله تک تسهیلاتی با فاصله متعامد،استفاده از برنامه ریزی خطی است که در آن صورت باید بگونه ای مسأله از حالت قدرمطلقی خارج گردد و پس از این کار به راحتی نقطه بهینه قابل محاسبه خواهد بود.
3-5-2- مسایل مکان یابی میانه تک تسهیله با مربع فاصله اقلیدسی
یکی دیگر از شکل های f(x) غیرخطی که در این قسمت بررسی می شود مساله مرکز ثقل یا مربع اقلیدسی است. فرض کنید هزینه با مربع فاصله اقلیدسی متناسب باشد، در این حالت مسأله جایابی تک تسهیلاتی را که در آن هزینه با مربع فاصله اقلیدسی متناسب است بیان می کنیم.مطالعه مسأله با فاصله مجذور(مرکز ثقل) بدین دلیل است که مسائل جایابی وجود دارندکه در آن ها هزینه به جای این که به طور خطی افزایش یابد، بر حسب فاصله اقلیدسی بین تسهیل جدید و موجود به صورت درجه دوم افزایش می یابد.مسأله مرکز ثقل می تواند به صورت زیر فرمول بندی شود:
(3-7) minfx,y=i=1mWi[xi-a2+yi-b2]23- 5-3- مسایل مکان یابی میانه تک تسهیله با مجذور مربع فاصله اقلیدسی
در برخی مسایل جایابی تسهیلات، هزینه، تابع خطی درجه اول نیست. به عنوان مثال، انتظار می رود هزینه مرتبط با عکس العمل یک ماشین آتش نشانی با فاصله غیر خطی متناسب باشد، بنابراین در مساله جایابی f(x) می تواند فرمول بندی های متفاوتی داشته باشد.
یکی از شکل های f(x) غیرخطی هنگامی است که فاصله به صورت خط مستقیم یا اقلیدسی باشد. اگر مختصات تسهیلات جدید و برای وسیله موجود باشند. فاصله اقلیدسی برای برخی از مسایل جایابی شبکه، شامل نقاله ها و سفر هوایی به کار می رود. برخی از مسایل سیم کشی الکتریکی و مسایل طراحی لوله کشی نیز نمونه هایی از مسایل فاصله اقلیدسی هستند.
مسایل جایابی که فرمول بندی داده شده در رابطه فوق را دارند به مسایل مرکز ثقل تعبیر می شوند.
مسأله با فاصله اقلیدسی به صورت زیر بیان می شود:
(3-8) minfx,y=i=1mWi[xi-a2+yi-b2]12مسأله با فاصله اقلیدسی به مسأله وبر شهرت دارد و مسأله عمومی فرمات نیز نامیده می شود و سابقه طولانی در تاریخ بهینه سازی دارد و در زمینه های مختلف روی می دهد.
3-6- رویکردهای نوین در مکان یابی تسهیلات
تصمیم گیری در مورد مکان یابی تسهیلات عمدتا از تصمیم گیری های بلند مدت و استراتژیک شرکت های بزرگ خصوصی و عمومی است و هزینه های بالا،پروژه های مکان یابی را به سرمایه گذاری های بلند مدت تبدیل کرده است. لذا موفقیت یا شکست مراکز تسهیلاتی در هر کدام از بخش های دولتی و خصوصی بستگی کامل به مکان های اتخابی دارد. شرکت ها برنامه ریزی تسهیلات را بگونه ای انجام می دهند که برای مدت زیادی بتوانند سودآور باقی بمانند.لذا ضروری است که مکان هایی برای استقرار تسهیلات در نظر بگیرند که نه تنها در شرایط فعلی مناسب هستند بلکه در طول عمر تسهیلات سودآور باقی بمانند، حتی اگر عوامل محیطی تغییر کنند، جمعیت متحول یا گرایش بازار دگرگون شود.لذا باید شرایط غیر مطمئن را وراد بازار کرد.پیچیدگی این مسأله باعث شده است که اغلب ادبیات مکان یابی به مسائل ایستا بپردازد [1] .گرچه تعداد بسیار کمی از محققان جنبه احتمالی و پویایی مکان یابی تسهیلات را در سال ها قبل معرفی کرده اند، بیش تر تحقیقات این حوزه در سال های اخیر انجام و گزارش شده است.در حقیقت مدل های احتمالی و پویا عدم قطعیت ناشی از وضعیت خود تصمیم گیرنده را مدل سازی می کنند.
انواع رویکردهای مسائل مکان یابی ایستا عبارتند است از:
1-رویکرد احتمالی
2-رویکرد برنامه ریزی سناریور. در ادامه به بحث در این پیرامون می پردازیم.
فضای اطلاعات در دنیای واقعی معمولا یک فضای غیر قطعی و احتمالی است.لذا مسائل مکان یابی نیز از این مقوله مستثنا نیستند در این رویکرد به طور صحیح توزیع احتمال متغیر های تصادفی مدل،
در نظر گرفته می شود.برخی این توزیع های احتمال درقالب استاندارد برنامه ریزی های ریاضی گنجانده و برخی آن ها را در چارچوب تئوری صف قرار داده اند.بنابراین این رویکرد احتمالی به 2 دسته تقسیم می شود:
رویکرد احتمالی استاندارد
رویکرد تئوری صف
مانه [42] یکی از اولین مقالات خود را در زمینه توسعه ظرفیت احتمالی را منتشر کرد.کاربون [43] مسأله مکان یابی تسهیلات عمومی بر روی شبکه با تقاضای احتمالی را برری کرد.اودنی و میرچاندانی[44] مسأله میانه را بر روی شبکه باطول کمان های احتمالی بررسی کردند با این فرض که طول کمان ها توزیع احتمال گسسته معلوم دارد.آنها بیان کردند که نتیجه ای که حداقل یک جواب بهینه مسائل میانه بر روی گره ها قرار دارد برای حالت احتمالی نیز صدق می کند.چورروچ و ویاور[45] رویه حلی برای مسأله میانه بر روی یک شبکه احتمالی بر اساس برنامه ریزی خطی عدد صحیح و تخفیف لاگرانژ ارائه کردند. پرداختن به وزن های تصادفی اغلب در مکان یابی سرویس هاس اضطراری مفید است.جایی که متوسط سرعت برای رفتن از نقطه ای به نقطه دیگر بستگی به ترافیک و نوع جاده دارد.
یک معیار بهینه سازی برای تعیین مکان عبارت است ازحداکثر کردن احتمال این که ماکزیمم فاصله تجهیز تا همه نقاط احتیاج از شعاع مشخصی تجاوز نکند.این مسأله برای توزیع یکنواخت در کار برمن و همکارانش [48] بررسی شده ، شرایط تحدب به دست آمده و یک الگوریتم شاخه و حد برای حالتی که تابع هدف نه محدب است نه مقعر پیشنهاد شده است.حد پایینی که برای این الگوریتم محاسبه شده است مخصوص توزیع یکنواخت است و برای سایر توزیع ها کاربرد ندارد.هیچ تجارب محاسباتی در این مقاله گزارش نشده و هیچ راه حلی برای مسأله نامحدب ارائه نشده است.
گرچه سابقه بررسی مسائل مکان یابی احتمالی زیاد و تقریبا به اندازه سابقه مسائل مکان یابی قطعی است ولی مسائل مکان یابی با مانع احتمالی تنها در چند سال اخیر انجام شده است.کانبولات و وسولوسکی[31] اولین بار مسأله مکان یابی تک تسهیله را در حضور یک مانع خطی احتمالی بررسی کرد.سپس بعد از آن شیری پور و همکاران [46] مسأله مکان یابی تک تسهیله با حضور یک مانع خطی بصورت یک مسأله چند تسهیله توسعه دادند.همچنین امیری عارف و همکاران [47] نیز مسأله مکان یابی تک تسهیله با حضور یک مانع خطی را بصورت یک مسأله مرکز میانه در نظر گرفته و یک شیوه حل ارائه دادند.
3-7- رویکرد های حل مسائل در مکان یابی تسهیلات
در حل مسائل مکان یابی، رویکرد های متفاوتی جهت رسیدن به جواب بهینه یا جواب های نزدیک به جواب های بهینه ارائه شده است.رویکرد های حل مسأله را می توان به دو دسته تقسیم کرد:1- رویکردهای دقیق،2- رویکردهای تقریبی. رویکرد شاخه و کران یکی ازرویکردهای دقیق، که در حل جایابی تسهیلات استفاده می شود.کوولیس و کیم [49] یک روش شاخه و حد برای مسأله جانمایی حلقه ای ارائه کردند.ملر و همکارانش [50] رویکرد شاخه و کران را برای مسأله استقرارn وسیله مستطیل شکل در یک ناحیه مستطیلی مفروض استفاده کردند. از آنجا که روش های دقیق برای مسائل بزرگ مقیاس مناسب نیستند روش های ابتکاری و تقریبی توسعه داده شده اند.
روش های ابتکاری به دو دسته تقسیم می شوند:
روش های ابتکاری بهبود دهنده
روش های ابتکاری سازنده
روش های ابتکاری سازنده به طور متوالی و به کمک معیارهایی تسهیلات را وارد طرح استقرار می کنند تا یک طرح کامل به دست آید. روش های ابتکاری بهبود دهنده با یک طرح اولیه استقرارشروع میکنند و با تغییر چیدمان تسهیلات به کمک معیار هایی سعی دربهبود طرح دارند.الگوریتم های ابتکاری سازنده از پیچیدگی بیشتری نسبت به الگوریتم های بهبود دهنده دارند و در صورت پیشروی مناسب جواب های به بهینه نزدیک تر را ارائه می دهد.
. یکی دیگر از رویکردهای تقریبی حل مسأله روش های فرا ابتکاری می باشد.که این روش های ابتکاری به دو دسته تقسیم می شوند:
روش جستجوی کلی
از جمله این روش ها، روش فراابتکاری جستجوی ممنوع و آنلینگ شبیه سازی می توان نام برد.
رویکردهای تکاملی
از جمله این روش ها،روش فراابتکاری الگوریتم ژنتیک و اجتماع مورچگان را می توان نام برد.
با وجود پیچیدگی های زیاد در حل مکانیابی تسهیلات، هنوز راهکار دقیقی برای حل مدل های مکان یابی تسهیلات در طرح های بلوکه ای ارائه نمی شود.راهکارهای الگوریتمیک برای جانمایی تسهیلات وجود دارد، که این الگوریتم ها به طور کلی به دو دسته تقسیم می شوند:نوع سازنده و نوع بهبود دهنده. الگوریتم های سازنده مستلزم توسعه مکان یابی از صفر هستند، یعنی با شروع از یک ساختار تهی، یک واحد و یا مجموعه ای از تسهیلات را یکی پس از دیگری اضافه می کنند تا تمام تسهیلات در این ساختار، لحاظ شده باشند.رویه های بهبود دهنده گزینه های مکان تسهیلات را بر اساس طرح های موجود ارائه می دهند.
اغلب تحقیقات انجام شده تا کنون بر روی تعیین مکان تسهیلات تمرکز کرده اند.در عمل این مسائل مستقل از هم نیستند و لذا هنوز نیاز به تحقیقات بیشتر است تا روش هایی ابداع شوند که بتوان این مسائل را همزمان مدلسازی و حل کرد، نه به طور متوالی.لذا نیاز است که رویکردهای حل، عمومی تر شوند تا بتوان آنها را در نرم افزارها گنجاند و نرم افزارها را قوی تر کرد.
فصل چهارم
ارائه مدل ریاضی

پاسخ دهید

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