چکیدهمسائل مکانیابی بر روی سطح, در حضور یک مانع خطی یا چند مانع, مساله ای می باشد که هم استقرار تسهیل جدید و هم تردد از میان این موانع, ممنوع می باشد. مسئله بررسی شده در این تحقیق, از نوع مکانیابی پیوسته با ظرفیت نامحدود می باشد. یعنی هدف یافتن مکان چند تسهیل نقطه ای در میان یک تعداد متناهی تسهیلات موجود با وزن معین, قطعی و دارای وزن غیر منفی می باشد.در این تحقیق, مدل پیشنهادی ارائه شده یک مسئله میانه با فواصل متعامد می باشد, بطوری که در ناحیه پیوسته یک مانع خطی وجود دارد که در مسیر افقی حرکت خود, از توزیع احتمالی با تابع چگالی احتمال نرمال با پارامتر های معین و ثابت پیروی می کند.همچنین از عرض مانع در این تحقیق صرفه نظر شده است.استقرار تسهیلات موجود در سیستم به گونه ای می باشد که امکان استقرار مولفه محور yها بر روی مسیر مانع خطی وجود ندارد و به صورت مشابه امکان استقرار تسهیلات جدید بر روی مسیر مانع خطی امکان پذیر نمی باشد.همچنین تعریفی از فاصله بین دو نقطه در حضور مانع ارائه شده و برای مسئله مورد بحث با توزیع نرمال, فاصله بین دو نقطه مفروض را فرموله نمودیم. با توجه به پیچیده بودن مسئله مدل بدست آمده, از الگوریتم فراابتکاری ژنتیک در این مسئله استفاده شده و نتایج این روش با روش دقیق مقایسه گشته است. 1- فهرست رئوس مطالبفصل اول- مقدمه و کلیات تحقیق1-1 مقدمه ............................................................................................................................... 101-2 کلیات تحقیق و ساختار پایان نامه .....................................................................................13فصل دوم- ادبیات و پیشینه تحقیق2-1 مقدمه ............................................................................................................................... 152-2 ادبیات موضوعی ...............................................................................................................162-3 پیشینه تحقیقات انجام شده ..............................................................................................172-3-1 روند تحقیقات انجام شده ................................................................................................21فصل سوم- روش تحقیق3-1 مقدمه ........................................................................................................................... 253-2 فواصل در مسائل برنامه ریزی تسهیلات ..................................................................... 263-2-1 فاصله خط مستقیم یا اقلیدسی ..................................................................................... 263-2-2 فاصله مجذور خط مستقیم یا اقلیدسی ........................................................................ 273-2-3 فاصله منهتن یا متعامد ................................................................................................. 283-2-4 فاصله چبیشف ........................................................................................................... 293-2-5 کوتاهترین مسیر ......................................................................................................... 303-3 مسائل مکانیابی میانه با انواع فاصله ........................................................................... 313-4 فرآیند تحقیق ............................................................................................................. 343-4-1 تعریف ساده ای از مساله .......................................................................................... 343-4-2 وضعیت دو نقطه نسبت به هم در حضور مانع ......................................................... 353-4-3 کوتاهترین فاصله بین دو نقطه در حضور مانع ......................................................... 383-4-3-1 مانع به صورت ثابت ......................................................................................... 383-4-3-2 مانع به صورت متحرک ..................................................................................... 40فصل چهارم- محاسبات و یافته های تحقیق4-1 مقدمه .................................................................................................................... 444-2 محاسبه امید فاصله بین دو نقطه در حالت shadow ........................................... 454-3 محاسبه امید فاصله بین دو نقطه در حضور مانع احتمالی در حالت کلی ............. 484-4 متغییر های واسط ................................................................................................. 514-5 مدل ریاضی مسئله ............................................................................................... 544-6 محدوده امید فاصله بین دو نقطه در مدل ............................................................ 554-7 وارد نمودن انتگرال به لینگو ............................................................................... 574-8 الگوریتم ژنتیک ................................................................................................... 594-8-1 تعریف الگوریتم ژنتیک ................................................................................ 594-8-2 مزایا و برتریهای الگوریتم ژنتیک ................................................................. 614-8-3 معایب الگوریتم ژنتیک ................................................................................ 644-8-4 گذری بر ژنتیک طبیعی ................................................................................ 654-8-5 واژگان الگوریتم ژنتیک ................................................................................ 704-8-6 ساختار کلی الگوریتم ژنتیک ........................................................................ 714-8-7 کروموزوم ..................................................................................................... 734-8-8 ایجاد جمعیت اولیه ....................................................................................... 754-8-9 اعمال ژنتیک ................................................................................................. 764-8-9-1 عملگر جهشی ....................................................................................... 774-8-9-2 عملگر تقاطعی .......................................................................................794-8-10 انتخاب چرخه رولت ................................................................................... 814-8-11 استراتژی برخورد با محدودیت ها .............................................................. 824-9 مثال ................................................................................................................. 83فصل پنجم- نتیجه گیری و پیشنهادات5-1 نتیجه گیری ....................................................................................................... 875-2 پیشنهادات آتی .................................................................................................. 88پیوست – فهرست منابع و مواخذ .................................................................................. 89چکیده انگلیسی .............................................................................................................. 91 2- فهرست جداولجدول 1-1 روند تحقیقات علمی و مقالات انجام شده در زمینه مکانیابی در حضور مانع .......21جدول 4-1 مختصات تسهیلات موجود ................................................................... 83جدول 4-2 وزن بین تسهیلات موجود با جدید ........................................................83جدول 3-4 وزن بین تسهیلات جدید با جدید .........................................................83جدول 4-4 داده های مانع خطی ............................................................................. 83جدول 4-5 مقایسه نتایج الگوریتم ژنتیک ............................................................... 84جدول 4-6 نتیجه حل مثال ..................................................................................... 84 3- فهرست تصاویر و نمودارهاشکل 3-1 فاصله اقلیدسی در صفحه .........................................................................26شکل 3-2 مسیر های مختلف متعامد بین x و xi .................................................... 29شکل 3-3 وضعیت های مختلف دو نقطه نسبت به هم در حضور مانع خطی .........36شکل 3-4 فاصله بین دو نقطه در حالت shadow ................................................... 39شکل 3-5 تابع فاصله در حضور مانع خطی در حالت xj > xi ............................... 42شکل 3-6 تابع فاصله در حضور مانع خطی در حالت xj < xi ............................... 42شکل 4-1 دو نقطه در حالت shadow ..................................................................... 47شکل 4-2 مدل تئوری داروین ................................................................................. 71شکل 4-3 ساختار کروموزوم ................................................................................... 76شکل 4-4 عملگر Mutation ......................................................................................81شکل 4-5 عملگر Crossover ....................................................................................82شکل 4-6 مکان استقرار تسهیلات مثال 4-9 ........................................................... 87 فصل اول – مقدمه و کلیات تحقيق 1-1 مقدمهمسالة مكانيابي[1](جایابی) واستقرار تسهيلات یکی از مسائل مهمی می باشد که در طراحی سیستم های صنعتی مورد توجه قرار فراوان می گیرد. در ادبيات موضوعي، معمولاً چند حالت از مسایل مكانيابي پيوسته، مورد بحث قرار گرفتند، مانند مساله ميانه[2]، مساله مركز[3] و مساله مركز-ميانه[4]. در مساله میانه هدف، پیدا کردن مکان وسیله (تسهیل) جدید میباشد، بطوریکه مجموع فواصل وزندهی شده بین تسهیل جدید و تسهیلات موجود، حداقل گردد. این مساله، در تئوری مکانیابی به مساله وِبِر[5] و مساله کمینه مجموع[6] نیز شهرت دارد. مسایل مکانیابی بر اساس نوع تابع فاصله نیز تقسیمبندی میشوند، مانند فاصله اقلیدسی و متعامد. مساله میانه با فواصل اقلیدسی یکی از قدیمی ترین مسایل مکانیابی تسهیلات میباشد. برای حل بهینه این نوع مساله، روشهای حل مختلفی پیشنهاد شدهاست که مشهورترین آن روش تکراریی میباشد.بسیاری از مسائل مکان یابی تسهیلات وجود دارند که در عمل جنبه واقعی تری پیدا می کنند. این دسته مکان یابی تسهیلات در حضور مانع صورت می پذیرد. در واقع در گونهاي از مسایل میانه با محدوديت در قرار گيري[7] و يا حركت[8] مواجه هستيم. در دستهای از این نوع مسایل، نواحی وجود دارند كه تسهيل (یا تسهیلات) جديد نه مي‌تواند در آنجا استقرار يابد و نه مي‌تواند از ميان آن عبور كند. این نواحي، نواحي بامانع[9] ناميده مي‌شوند. درياچه‌ها، كوهستانها، مناطق نظامي، رودخانه‌ها و بزرگراهها ودر مقياس كوچكتر، ماشینآلات و واگنهای حمل مواد در كارخانجات، مثالهايي از اين نواحي مي‌باشند. این مسایل در مقایسه با مسایل مكانيابي كلاسيك خيلي عمليتر ونزديك‌تر به دنياي واقعي مي‌باشند، اما بهعلت پيچيد‌گي محاسباتي که اين نوع مسایل دارند، تنها در چند دهه اخير مورد بررسی قرار گرفتند. موانع احتمالی بطور طبیعی در دنیای واقعی وجود دارد، یعنی موانع میتوانند دارای موجودیت تصادفی، مکان تصادفی و یا اندازه تصادفی باشند. یک مثال ساده آن یک واگن در یک کارخانه میباشد که در یک مسیر ثابت در رفت و آمد میباشد.مثال دیگر از این دسته که کاربرد نظامی دارد اعزام دسته هایی از نیروهای نظامی به مناطق نظامی است در صورتی که چندین دسته از نیروهای خودی در محل حاضر می باشند و در بسیاری از این مناطق به دلیل وجود دریاچه، کوه و یا ... امکان استقرار این نیروهای نظامی وجود ندارد.در این تحقیق، مدل پیشنهادی ارائه شده یک مساله میانه با فواصل متعامد میباشد، بطوریکه در ناحیه پیوسته یک مانع خطی وجود دارد که در مسیر افقی حرکت خود، از توزیع احتمالی با تابع چگالی احتمال نرمال[10] با پارامترهای معین و ثابت پیروی میکند.فرضیاتی که برای مسئله تعریف می نماییم به قرار زیر می باشد:1- مسئله از نوع مکان یابی پیوسته با ظرفیت نامحدود می باشد. یعنی هدف یافتن مکان چند تسهیل نقطهای در میان یک تعداد متناهی تسهیلات موجود متناهی میباشد، بطوریکه ظرفیت تسهیلات جدید برای خدمتدهی نامحدود میباشد.2- مسئله از نوع مکان یابی پیوسته میانه متعامد در حالت چند تسهیله می باشد.3- هر تسهیل موجود دارای مکان ثابت با مختصات معین، قطعی و دارای وزن غیرمنفی میباشد.4- مساله برای کل افق برنامهریزی در ابتدای دوره، سیاستگذاری میکند، یعنی مساله مکانیابی ایستا میباشد.5- با مساله مکانیابی محدود با یک مانع خطی سر و کار داریم، بطوریکه از عرض مانع صرفنظر میشود.6- مانع بر روی یک مسیر افقی حرکت میکند.7- مکان شروع مانع خطی، از توزیع نرمال با میانگین و انحراف معیار مشخص و ثابت پیروی میکند.8- تسهیلات موجود در مسیر حرکت مانع مستقر نمی باشند.9- تسهیلات جدید بر روی مسیر مانع خطی نمیتوانند استقرار یابند.10- تعامل هم مابین تسهیلات جدید و موجود ، و هم ما بین تسهیلات جدید و جدید برقرار است. 1-2 كلياتتحقيق و ساختار پایان نامهساختار پایان نامه به گونه ای می باشد که در ادامه و در فصل 2، ادبیات موضوعی مسائل بامانع ومسائلمکان‌یابی چند تسهیله[11] را مورد بررسی قرار خواهیم داد. در فصل 3 زمینههای علمی تحقیق شامل دستهبندی مسایل مکانیابی، انواع توابع فاصله، مساله مکانیابی کلاسیک و الگوریتم ژنتیک[12] بطور مفصل تشریح خواهند شد. در فصل 4 به تشریح مساله و مدل پیشنهادی می پردازیم. در ادامه این فصل به منظور درک بهتر رفتار مدل، یک مثال نمونهای ارائه خواهیم داد، اما با توجه به پیچیدگیهای مدل پیشنهادی در مقیاس های بزرگ، یک الگوریتم فراابتکاری[13] (الگوریتم ژنتیک) را معرفی و نتایج محاسبات مربوط به این الگوریتمها را مورد بررسی و مقایسه قرار خواهیم داد. در نهایت، تعدادی از توسعههای آتی بههمراه نتیجهگیری در فصل 5 مورد بررسی قرار گرفتند و معرفی خواهند شد. فصلدوم – ادبیاتوپیشینه تحقيق 2-1 مقدمهیکی از مسائل مهم و پیچیده در علم مهندسی صنایع مکان یابی تسهیلات می باشد. بسیار مشاهده شده است که در بسیاری از کارخانه ها ، به علت عدم چیدمان مناسب تسهیلات ، هر ساله نیاز به تغییر مکان تسهیلات گرفته این می شود. لیکن تنها دلیل تغییر چیدمان در کارخانه ،چیدمان نامناسب اولیه نمی باشد.در بسیاری از موارد به دلایلی نظیر توسعه محصولات کارخانه، افزایش ظرفیت تولید، تغییر نوع محصولات، افزایش و کاهش در بنای کارخانه، نیاز به استفاده از تکنولوژی جدید و دستگاه های بروز و ... نیاز به مکان یابی مجدد تسهیلات و یا مکان یابی تسهیلات موجود می باشد. مبحث مورد بحث ما مکان یابی تسهیلاتی جدید در میان تسهیلات موجود در کارخانه می باشد. مسایل مكانيابي تک وسیلهای (تک تسهیله) پيوسته در سطح، يكي از حوزه‌هاي گسترده در مدل سازي رياضي، در دنياي واقعي مي‌باشند، كه دراین مسایل يك تسهيل جديد (تسهیل عرضه) به مجموعهاي از تسهيلات موجود ( تسهیلات متقاضی)، با توجه به تقاضاهايشان، سرويس میدهد. 2-2 ادبیات موضوعیدر ادبيات موضوعي، معمولاً چند حالت از مسایل مكانيابي پيوسته، مورد بحث قرار میگیرد، مانند مساله ميانه، مساله مركز و مساله مركز-ميانه.در مساله میانه كلاسيك ( که غالبا مساله وبِر، مسالهفرمارت اشنایدر وبر[14] و مساله حداقل مجموع [15] نیز نامیده ميشود)، در صدد یافتن مكان تسهيل جديد هستيم، بطوريكه مجموعه فواصل وزن دهي شده[16] با تسهيلات موجود، حداقل گردد. در گونهاي از مسایلمیانه، با محدوديت در قرارگيري و يا حركت مواجه هستيم. در ادبيات موضوعي اين نوع مسایل، معمولاً سه دسته از اين مسایل مورد مطالعه قرار گرفتهاند. اولين دسته، نواحي ممنوعه[17] نامیده می شوند كه در این نواحی تسهيلات نمي‌توانند در آنجا قرار گيرند اما حركت در ميان اين نواحي بلامانع و بدون جريمه مي‌باشد (مانند مناطق و پاركهاي حفاظت شده و یا مناطقی که مشخصههای جغرافیای از قبیل شیب تند زمین از ایجاد تسهیل مورد نظر ممانعت میکند).براي مطالعه بروي مسایل مكانيابيمیانه و مرکز در نواحی ممنوعه به هاماخر و نیکل [5] مراجعه كنيد.دسته دوم به عنوان نواحي متراکم[18]شناخته میشوند كه در اين نواحي قرارگيري يك تسهيل ممنوع بوده اما حركت از ميان آن با جريمه [19] همراه مي‌باشد(مانند درياچه‌اي كه، با قايق بتوان از دو طرف آن عبور و مرور كرد. برای نمونه، مسایل مکانیابی با نواحی متراکم، با سرعت و هزینههای سفر مختلف، در بوت و کاوالیر [6] مورد بحث و بررسی قرار گرفتهاند.دسته سوم نواحی هستند كه تسهيل جديد نه مي‌تواند در آنجا استقرار يابد و نه مي‌تواند از ميان آن عبور كند. این نواحي، نواحي با مانع ناميده مي‌شوند. درياچه‌ها، كوهستانها، مناطق نظامي، رودخانه‌ها و بزرگراهها ودر مقياس كوچكتر، نوار نقاله‌ها،ماشینآلات موجود در كارخانجات، مثالهايي از اين نواحي مي‌باشند. 2-3 پیشینه تحقیقات انجام شدهمکان یابی تسهیلات در سطح همراه با مانع با مقاله ای توسطکاتز و کوپرآغاز گردید[1]. این مقاله اولین مقاله ای بود که مسئله وبر را در حالت متعامد و در حضور یک مانع بررسی می نمود. بعضی از موارد و خصوصیات این مقاله از جمله فضای شدنی مسئله بعد ها در مقاله ای توسط کلامورت توسعه داده شد[2].