چکیدهاین تحقیق مسأله مکان یابی تک تسهیله را در حضور یک مانع آرکی شکل که در یک مسیر دایره ای شکل بطور یکنواخت در حال رفت و برگشت می باشد، را در نظر میگیرد. فواصل در نظر گرفته شده در این کار متعامد می باشد. ابتدا الگوریتمی برای تشخیص شرایط پدیداری برای مسأله تعریف می شودکه رویکردی جامع و قابل استفاده برای تمامی مسائل مکانیابی با شکلهای متفاوت مانع می باشد.بعلاوه یک مدل برنامه ریزی غیر خطی ارائه شده است که، مکان تسهیل جدید را بگونه ای می یابد که مجموع کل فواصل انتظاری با مانع وزن دهی شده تسهیل جدید با تسهیلات موجود حداقل شوند.برای درک مدل ارائه شده و اثبات کارایی آن مثال کوچک ارائه شده است و همچنین به علت پیچیدگی حل مدل در ابعاد بزرگ الگوریتم ابتکاری نیز ارائه شده است.کلمات کلیدی:مکان یابی تک تسهیله؛ مانع دایره ای احتمالی؛ فاصله متعامد؛ الگوریتم ابتکاری مانع دایرهای متحرک. AbstractIn this paper we consider the single facility location problem with respect to a given set of existing facilities in the presence of an arc- shaped barrier which moving in a circular route and having the starting point of the barrier uniformly distributed. The objective is to locate this single facility such that the sum of the weighted expected rectilinear distances from the facility to the demand points is minimized. In this paper first a general algorithm for specifying visible and shadow conditions which is used for any shape barrier is structured. A mixed-integer nonlinear programming model is designed for the proposed problem. Test problems are presented to illustrate the application of the proposed model.Becuase of complication in solution of model we construcedexact and heuristic solution procedures based on optimization methods.Keywords:Single-facility location problem; Probabilistic Circular barrier; Rectilinear distance; heuristic algorithm. فهرست مطالبعنوان صفحهفصل اول : كليات تحقيق و ساختار پايان نامه........................................................................................11-1 مقدمه....................................................................................................................................21-2ساختار پايان نامه...................................................................................................................5فصل دوم : مروري بر ادبيات موضوعي مسائل مكان يابي با مانع.........................................................62-1 مقدمه...................................................................................................................................72-2 مسايل مكان يابي همراه با موانع..........................................................................................92-3مسايل مكان يابي تک تسهيله............................................................................................17فصل سوم : زمينه هاي عامي تحقيق......................................................................................................203-1 مقدمه..................................................................................................................................213-2 دسته بندي كلي مسايل برنامه ريزي تسهيلات....................................................................223-3 دسته بندي مسايل مكان يابي با نگرش سنتي.....................................................................233-4 فواصل در مسايل برنامه ريزي تسهيلات.........................................................................243-4-1 فاصله خط مستقيم يا اقليدسي..........................................................................243-4-2 فاصله مجذور خط مستقيم يا اقليدسي.............................................................253-4-3 فاصله منهتن يا متعامد.......................................................................................263-4-4 فاصله چبي شف...............................................................................................273-5 مسايل مكان يابي ميانه تک تسهیله با انواع فاصله.......................................................................283-5-1 مسايل مكان يابي ميانه تک تسهیله با فاصله متعامد.......................................................293-5-2 مسايل مكان يابي ميانه تک تسهیله با مربع فاصله اقلیدسی...........................................323-5-3 مسايل مكان يابي ميانه تک تسهیله با مربع فاصله اقلیدسی...........................................323-6 رویکردهای نوین در مکان یابی تسهیلات...................................................................................333-7 رویکرد های حل مسائل در مکان یابی تسهیلات........................................................................35فصل چهارم : ارائه مدل ریاضی...........................................................................................................384-1 مقدمه.............................................................................................................................................394-2 ساختار مسأله................................................................................................................................414-2-1 وضعیت پدیداری..........................................................................................................464-2-2 محاسبه فاصله انتظاری.................................................................................................644-2-3 مدل ریاضی پیشنهادی..................................................................................................834-2-3-1 مثال...........................................................................................................................924-3 روش پیشنهادی حل......................................................................................................................944-4 مسائل نمونه...................................................................................................................................994-4-1 روش کاروش- کاهن- تاکر.........................................................................................974-5 نتایج محاسباتی.............................................................................................................................99فصل پنجم : نتیجه گیری و پیشنهادات آتی.......................................................................................1065-1 نتیجه گیری....................................................................................................................1075-2 پیشنهادات آتی...............................................................................................................108مراجع....................................................................................................................................................109مراجع فارسی..........................................................................................................................110مراجع لاتین............................................................................................................................111 فهرست جداولعنوان صفحهفصل دوم :جدول (2-1). مروریاجمالي بر مسايل مكان يابي تسهيلات در حضور موانع........................................8فصل چهارم :جدول (4-1). اطلاعات تسهیلات موجود..............................................................................................93جدول (4-2). اوزان مابین تسهیل موجود و جدید................................................................................3 9جدول (4-3) . مختصات مکان بهینه تسهیل جدید در مثال نمونه..........................................................93جدول (4-4). مختصات تسهیلات موجود.............................................................................................99جدول (4-5). تسهیلات درون و بیرون مسیر دایره ای.........................................................................100جدول (4-6). نقاط پایداری حاصل ازK.K.Tدر ترکیب تکی ربع.......................................................101جدول (4-7). نقاط پایداری حاصل ازK.K.Tدر ترکیب دو تایی ربع ها.............................................101جدول (4-8). نقاط پایداری حاصل ازK.K.Tدر ترکیب سه تایی ربع ها............................................107جدول (4-9). نقاط پایداری حاصل ازK.K.Tدر ترکیب چهار تایی ربع ها........................................102جدول (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فصل اولكليات تحقيق و ساختار پايان نامه 1-1- مقدمهبرنامه ریزی تسهیلات دو بخش عمده جایابی و طراحی را شامل میشود که مهمترین بخش طراحی، استقرار یا جانمایی تسهیلات میباشد.منظور از تسهیلات،هر مجموعه، شامل کارخانه، بیمارستان، دانشگاه ... است. با افزایش میزان هزینه حمل و نقل و هزینههای تحویل،مساله مکانیابی تسهیلات نقش مهمی در محیطهای صنعتی ایفا میکند.نظریه مکانیابی به عنوان شاخهای از تحقیق در عملیات از یک سو در جایابی تسهیلات و از سوی دیگر در تصمیم گیری های مدیریتی ،اقتصادی و برنامه ریزی تولید تاثیرگذار است و فواید بسیاری برای واحد های صنعتی از جمله سرمایه کمتر و بازدهی بیشتر، زمان بازگشت سرمایه کمتر و سود بیشتر به دنبال خواهد داشت.انتخاب مکان بهینه و متعاقبا مسیر بهینه کاری پیچیده و دارای فرایند تکراری می باشد.مکان بهینه همچنین باید بتواند پاسخگوی حجم تردد در محیط صنعتی باشد.مطالعه پیرامون مکان بهینه از دیدگاه جغرافی دانان و علمای اقتصادی هموراه دارای اهمیت بوده و در محاسبات خود مد نظر قرار می دهند [1].مراکز صنعتی و کارخانجات برای تعیین مکان احداث کارخانه، استقرار تجهیزات و دپارتمانهای خود در کارخانه، استقرار دفاترشان در سطح شهر، تعیین مراکز توزیع محصولات و ... با چنین مسائلی سر و کار دارند.در مسایل مکان یابی دو نوع محیط پیوسته و گسسته در نظر گرفته میشود.از جمله مسایل مکانیابی پیوسته میتوان به مسایل مکان یابی میانه ، و مساله مرکز میانه نام برد. تصمیمات مکانیابی اهداف مختلفی را دنبال می کند.برای مثال کمینه کردن مجموع وزنی فاصلههای بین تسهیل جدید و سایر تسهیلات موجود و کمینه کردن بیشترین فاصله بین تسهیل جدید و سایر تسهیلات موجود از این نوع هستند. در مساله میانه هدف، پیدا کردن مکان وسیله (تسهیل) جدید می باشد، بطوری که مجموع فواصل وزندهی شده بین تسهیل جدید و تسهیلات موجود ، حداقل گردد.چنین مساله به مساله مکانیابی کمینه[1] مجموع شهرت دارد.نوع دیگر طبقه بندی مسایل مکانیابی بر اساس نوع فاصله مورد نظرمی باشد.فواصل مورد محاسبه میتواند بصورت متعامد یا اقلیدسی باشد. مساله کمینه مجموع با فاصله اقلیدسی از ابتدایی ترین و قدیمی ترین مسایل مکان یابی تسهیلات می باشد.در این نوع مکان یابی با محدودیت در قرار گیری و یا حرکت در مسیر مواجه می شویم.در دسته ای از این مسایل ،نواحی وجود دارد که تسهیل جدید نه می تواند در آنجا استقرار یابد و نه مي تواند از ميان آن عبور كند. اين نواحي ، نواحي بامانع[2] ناميده مي شوند. درياچه ها، كوهستان ها، مناطق نظامي، رودخانه ها و بزرگ راه ها و در مقياس كوچكتر، ماشين آلات و واگن هاي حمل مواد در كارخانجات، مثال هايي از اين نواحي مي باشند.در حقیقت مساله مکان یابی با مانع در واقعیت نقش مهمتری را ایفا می کند. اين مسايل در مقايسه با مسايل مكانيابي كلاسيك خيلي عملي تر و نزديك تر به دنياي واقعي مي باشند، اما به علت پيچيدگي محاسباتي كه اين نوع مسايل دارند، تنها در چند دهه اخير مورد بررسي قرار گرفتند و کمتر در محاسبات و مدل های مکان یابی تسهیلات به حضور مانع پرداخته شده است.کارهای ابتدایی که در زمینه مکان یابی با مانع مورد بررسی قرار گرفت همه زمانی که مانع ساکن باشند مورد بررسی قرار گرفت.بعد ازآن ان بعلت بالا بودن حجم محاسبات به روش های حل متفاوت برای مسایل مکان یابی با مانع پرداخته شد. اما از سوی دیگر موانع احتمالي بطور طبيعي در دنياي واقعي وجود دارد، يعني موانع مي توانند داراي موجوديت تصادفي، مكان تصادفي و يا اندازه تصادفي باشند.بعبارتی دیگر اجسام متحرک نقش بیشتر وواقعی تر در مسایل روزمره دارندو همچنین وجود همین موانع متحرک نقش اثر گذاری را در محاسبات ایفا می کنند و در نهایت بر روی میزان هزینه تاثیر گذار هستند. يك مثال ساده آن يك واگن در يك كارخانه مي باشد كه در يك مسير ثابت در رفت و آمد مي باشد.یا مساله یافتن مسیر بهینه برای یک ربات در نظر بگیرید که به عنوان یکی از مهمترین مسایل روز دنیای صنعت می باشد.یک ربات جهت جابجایی از یک نقطه به نقطه دیگر ، با توجه به رقابت های موجود در کاهش زمان ،نیازمند یافتن کوتاهترین مسیر می باشد که در طول پیمودن مسیر خود با موانع بسیار متحرک و ثابت برخورد می کند.بنابراین برنامه ریزی آن باید بصورتی باشد که بتواند با موانع موجود مسیر بهینه خود را بیابد. مدل پيشنهادي اين تحقيق، يك مساله ميانه با فواصل متعامد مي باشد، بطوري كه در ناحيه پيوسته يك مانع آرکی شکل وجود دارد كه در مسير دایره ای حركت خود، از توزيع احتمال يكنواخت با پارامتر معين پيروي مي كند. فرضيات مساله پيشنهادي بقرار زير در نظر گرفته مي شوند:1- با مساله مكان يابي پيوسته ميانه متعامد تک تسهيله با ظرفيت نامحدود سروكار داريم، يعني هدف يافتن مكان تک تسهيل نقطه اي در ميان يك تعداد متناهي تسهيلات موجود متناهي مي باشد، بطوريكه ظرفيت تسهيل جديدبراي خدمت دهي نامحدود مي باشد.2- مساله براي كل افق برنامه ريزي در ابتداي دوره، سياست گذاري مي كند، يعني مساله مكان يابي ايستا مي باشد.3- هر تسهيل موجود داراي مكان ثابت با مختصات معين، قطعي و داراي وزن غيرمنفي مي باشد.4- با مساله مكان يابي محدود با يك مانع آرکی شکل احتمالی سر و كار داريم که در یک مسیر دایره ای شکل در حال رفت و برگشت می باشد.5- مكان شروع مانع آرکی شکل، از توزيع يكنواخت با پارامترهاي معين پيروي مي كند.6- تسهيلات موجود در مسير مانع مستقر نيستند.7- تسهيل جديد بر روي مسير مانع آرکی شکل نمي توانند استقرار يابد.8- تعامل مابين تسهيل جديد و موجود برقرار است.1-2- ساختار پايان نامهدر ادامه در فصل 2، ادبيات موضوعي مسايل با مانع و مسايل مكان يابي تک تسهيله[3] را مورد بررسي قرار خواهيم داد. در فصل 3 زمينه هاي علمي تحقيق شامل دسته بندي مسايل مكان يابي، انواع توابع فاصله، مساله مكان يابي كلاسيك، الگوريتم ابتکاری بطور مفصل تشريح خواهند شد. در فصل 4 به تشريح مساله و مدل پيشنهادي مي پردازيم. در ادامه اين فصل به منظور درك بهتر رفتار مدل، يك مثال نمونه اي ارائه خواهيم داد، اما با توجه به پيچيدگي هاي مدل پيشنهادي در مقياس هاي بزرگ، الگوريتم ابتكاري نتايج محاسبات مربوط به اين الگوريتم را مورد بررسي قرار خواهيم داد. در نهايت تعدادي از توسعه هاي آتي به همراه نتيجه گيري در فصل 5 مورد بررسي قرار گرفتند.