–273


عضو شوید


نام کاربری
رمز عبور

:: فراموشی رمز عبور؟

عضویت سریع

نام کاربری
رمز عبور
تکرار رمز
ایمیل
کد تصویری
براي اطلاع از آپيدت شدن وبلاگ در خبرنامه وبلاگ عضو شويد تا جديدترين مطالب به ايميل شما ارسال شود




تبادل لینک هوشمند

برای تبادل لینک ابتدا ما را با عنوان پایان نامه ها و آدرس k-thesis.LXB.ir لینک نمایید سپس مشخصات لینک خود را در زیر نوشته . در صورت وجود لینک ما در سایت شما لینکتان به طور خودکار در سایت ما قرار میگیرد.







نام :
وب :
پیام :
2+2=:
(Refresh)
پرش به محتوای اصلیرفتن به نوارابزار پیشخوان خانه به‌روزرسانی‌ها 2 نوشته‌ها همه‌ی نوشته‌ها افزودن نوشته دسته‌ها برچسب‌ها بگرد و جایگزین کن! تمام گشتن ها اضافه کردن رسانه کتابخانه افزودن برگه‌ها همه‌ی برگه‌ها افزودن برگه دیدگاه‌ها 1 نمایش پوسته‌ها سفارشی‌سازی ابزارک‌ها فهرست‌ها سربرگ پس‌زمینه Random Backgrounds تنظیمات پوسته ویرایشگر افزونه‌ها افزونه‌های نصب‌شده افزودن ویرایشگر Random Banners کاربران همه کاربران افزودن شناسنامه شما ابزارها ابزارهای دردسترس درون‌ریزی برون‌بری Search & Replace تنظیمات همگانی نوشتن خواندن گفت‌و‌گو‌ها رسانه پیوندهای یکتا Shortcode any widget Auto Limit Posts Header and Footer WP Rocket XML-Sitemap Random Thumbnails کوتاه کردن پست فونت ماندگار فونت پیشخوان فونت پوسته انتقادات و پیشنهادات Related Posts تنظیمات پارسی جمع کردن فهرست درباره وردپرس پایان نامه های ایران داک 22 به‌روزرسانی پوسته 11 دیدگاه در انتظار مدیریت است تازه WP Rocket سلام 92 بیرون رفتن راهنما تنظیمات صفحه نوشته‌ی تازه Easy Image Display is supported through Patreon. If you find it useful, please consider a small donation. Thanks! | Hide Notice وردپرس پارسی فعال شد! برای کارکردن افزونه نیاز به پیکربندی آن دارید. برگه‌ی پیکربندی – بی‌خیال WP Rocket بعد از فعال یا غیرفعال سازی ویژگی یا افزونه پا کردن کش ضروری است پاک کردن کش WP Rocket: برای درست کار کردن افزونه به پیوند یکتا بروید و ساختار دلخواه را انتخاب کنید ، رفتن به پیوند یکتا عنوان را اینجا وارد کنید پیوند یکتا: http://abbas-jadidi.ir/?p=3132&preview=true تغییر پیوندهای یکتا افزودن پرونده چندرسانه‌ایدیداریمتن bilinkb-quotedelinsimgulollicodemoreبستن برچسب‌هاجهت متن سرویس وبلاگدهی وردپرسی

پایان نامه ارشد مدیریت (سایت اصلی)

نمونه سوال ارشد (تست ها)

پایان نامه ارشد حقوق (سایت اصلی)

دانلود پایان نامه ارشد -همه رشته ها

پایان نامه حسابداری (سایت اصلی)

پایان نامه ادبیات

پایان نامه برق

پایان نامه (ارشد فایل)

پایان نامه ارشد روانشناسی (بلاگ اسکای)

پایان نامه مدیریت

پایان نامه ارشد (پارسی بلاگ)

روانشناسی (لوکس بلاگ)

پایان نامه (رزبلاگ)

فروش فایل سنجش و دانش

آرتین فایل

پایان نامه (بلاگ اسکای)

پایان نامه های پارسی بلاگ 2

پایان نامه و تز (فورکیا)

پایان نامه (نیلوبلاگ)

دانلود پایان نامه ارشد مدیریت (لوکس بلاگ)

پایان نامه ارشد رشته حقوق (میهن بلاگ)

پایان نامه ارشد حقوق (بلاگ اسکای)

هما تز

دانلود پایان نامه رشته حقوق (رز بلاگ)

پایان نامه حقوق (نیلو بلاگ)

عناوین پایان نامه مدیریت

پایان نامه های حقوق (لوکس بلاگ)

پایان نامه تربیت بدنی

پایان نامه مدیریت صنعتی

پایان نامه ارشد مدیریت (بلاگ اسکای)

پایان نامه علم یار

پایان نامه روانشناسی (فورکیا)

پایان نامه ارشد

پایان نامه حقوق (رزبلاگ)

آوا فایل

دانلود پایان نامه ها (رزبلاگ 3)

دانلود متن کامل پایان نامه (رزبلاگ)

پایان نامه حقوق جزا

ارشد حقوق

بهار فایل

پایان نامه ها (پارسا بلاگ)

پایان نامه حسابداری

پایان نامه بورس

پایان نامه حسابداری دولتی

پایان نامه ها (سایت بیان)

پایان نامه مدیریت مالی

پایان نامه ارشد جغرافی (جغرافیا)

فوکا-لینک های مفید سایت دانلود

پایان نامه مدیریت انسانی

پایان نامه ارشد صنایع

پایان نامه مدیریت مالی صنعتی

پایان نامه الهیات

پایان نامه عمران

پایان نامه ارشد (میهن بلاگ)

متن کامل پایان نامه (رزبلاگ 4)

پایان نامه و تحقیق

پایان نامه مدیریت عمران

پایان نامه فرمت ورد( لوکس بلاگ)

پایان نامه ارشد ( لوکس بلاگ)

پایان نامه ارشد دانلود ( لوکس بلاگ)

دانلود پایان نامه ها (پارسا بلاگ)

پایان نامه (جوان بلاگ)

پایان نامه ارشد و کارشناسی

پایان نامه کارشناسی ارشد (لاین بلاگ)

دسترسی پایان نامه ارشد

دانلود رایگان پایان نامه

تعداد واژه‌ها: 290 پیش‌نویس در زمان 2:17:43 ب.ظ ذخیره شد. تغییر وضعیت پنل: انتشار انتشار ذخیره پیش‌نویس پیش‌نمایش (باز شدن در پنجره تازه) وضعیت: پیش‌نویس ویرایش ویرایش وضعیت نمایانی: عمومی ویرایش تغییر میدان دید انتشار فوری ویرایش ویرایش تاریخ و زمان پاک کردن کش انتقال به زباله‌دانانتشار تغییر وضعیت پنل: ساختار ساختار ساختارهای نوشته استاندارد حاشیه پیوند گفتاورد تغییر وضعیت پنل: دسته‌ها دسته‌ها همه دسته‌ها بیشتر استفاده شده پایان نامه ها دسته شماره 2 + افزودن دسته تازه تغییر وضعیت پنل: برچسب‌ها برچسب‌ها افزودن برچسب افزودن برچسب‌ها را با ویرگول لاتین (,) جدا کنید انتخاب از برچسب‌های بیشتر استفاده شده تغییر وضعیت پنل: Cache Options Cache Options Activate these options on this post: Images LazyLoad Iframes & Videos LazyLoad HTML Minification CSS Minification JS Minification شبکه تحویل محتوا Note: These options aren't applied if you added this post in the "Never cache the following pages" option. تغییر وضعیت پنل: Header and Footer Header and Footer Disable top injection Disable bottom injection سپاسگزاریم از اینکه سایت خود را با وردپرس ساخته‌اید. نگارش 4.8.1 پیوند درج شد. هیچی پیدا نشد.

Please enter banners and links.

مزایا و برتریهای الگوریتم ژنتیک ……………………………………………………….. 61
معایب الگوریتم ژنتیک …………………………………………………………………….. 64
گذری بر ژنتیک طبیعی …………………………………………………………………….. 65
واژگان الگوریتم ژنتیک …………………………………………………………………….. 70
ساختار کلی الگوریتم ژنتیک ……………………………………………………………… 71
کروموزوم ……………………………………………………………………………………….. 73
ایجاد جمعیت اولیه …………………………………………………………………………… 75
اعمال ژنتیک ……………………………………………………………………………………. 76
عملگر جهشی …………………………………………………………………………… 77
عملگر تقاطعی ……………………………………………………………………………79
انتخاب چرخه رولت ……………………………………………………………………….. 81
استراتژی برخورد با محدودیت ها …………………………………………………….. 82
مثال ………………………………………………………………………………………………….. 83
فصل پنجم- نتیجه گیری و پیشنهادات
نتیجه گیری …………………………………………………………………………………………. 87
پیشنهادات آتی …………………………………………………………………………………….. 88
پیوست – فهرست منابع و مواخذ ………………………………………………………………………. 89
چکیده انگلیسی ……………………………………………………………………………………………….. 91
فهرست جداول
جدول 1-1 روند تحقیقات علمی و مقالات انجام شده در زمینه مکانیابی در حضور مانع …….21
جدول 4-1 مختصات تسهیلات موجود …………………………………………………………. 83
جدول 4-2 وزن بین تسهیلات موجود با جدید ………………………………………………..83
جدول 3-4 وزن بین تسهیلات جدید با جدید …………………………………………………83
جدول 4-4 داده های مانع خطی ………………………………………………………………….. 83
جدول 4-5 مقایسه نتایج الگوریتم ژنتیک ……………………………………………………… 84
جدول 4-6 نتیجه حل مثال …………………………………………………………………………. 84
فهرست تصاویر و نمودارها
شکل 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
فصل اول – مقدمه و کلیات تحقيق
مقدمه
مسالة مكان‌يابي (جایابی) و استقرار تسهيلات یکی از مسائل مهمی می باشد که در طراحی سیستم های صنعتی مورد توجه قرار فراوان می گیرد. در ادبيات موضوعي، معمولاً چند حالت از مسایل مكانيابي پيوسته، مورد بحث قرار گرفتند، مانند مساله ميانه، مساله مركز و مساله مركز-ميانه. در مساله میانه هدف، پیدا کردن مکان وسیله (تسهیل) جدید میباشد، بطوریکه مجموع فواصل وزندهی شده بین تسهیل جدید و تسهیلات موجود، حداقل گردد. این مساله، در تئوری مکانیابی به مساله وِبِر و مساله کمینه مجموع نیز شهرت دارد. مسایل مکانیابی بر اساس نوع تابع فاصله نیز تقسیمبندی میشوند، مانند فاصله اقلیدسی و متعامد. مساله میانه با فواصل اقلیدسی یکی از قدیمی ترین مسایل مکانیابی تسهیلات میباشد. برای حل بهینه این نوع مساله، روشهای حل مختلفی پیشنهاد شدهاست که مشهورترین آن روش تکراریی میباشد.
بسیاری از مسائل مکان یابی تسهیلات وجود دارند که در عمل جنبه واقعی تری پیدا می کنند. این دسته مکان یابی تسهیلات در حضور مانع صورت می پذیرد. در واقع در گونهاي از مسایل میانه با محدوديت در قرار گيري و يا حركت مواجه هستيم. در دستهای از این نوع مسایل، نواحی وجود دارند كه تسهيل (یا تسهیلات) جديد نه مي‌تواند در آنجا استقرار يابد و نه مي‌تواند از ميان آن عبور كند. این نواحي، نواحي بامانع ناميده مي‌شوند. درياچه‌ها، كوهستانها، مناطق نظامي، رودخانه‌ها و بزرگ‌راه‌ها ودر مقياس كوچكتر، ماشینآلات و واگنهای حمل مواد در كارخانجات، مثالهايي از اين نواحي مي‌باشند. این مسایل در مقایسه با مسایل مكانيابي كلاسيك خيلي عمليتر ونزديك‌تر به دنياي واقعي مي‌باشند، اما بهعلت پيچيد‌گي محاسباتي که اين نوع مسایل دارند، تنها در چند دهه اخير مورد بررسی قرار گرفتند. موانع احتمالی بطور طبیعی در دنیای واقعی وجود دارد، یعنی موانع میتوانند دارای موجودیت تصادفی، مکان تصادفی و یا اندازه تصادفی باشند. یک مثال ساده آن یک واگن در یک کارخانه میباشد که در یک مسیر ثابت در رفت و آمد میباشد.مثال دیگر از این دسته که کاربرد نظامی دارد اعزام دسته هایی از نیروهای نظامی به مناطق نظامی است در صورتی که چندین دسته از نیروهای خودی در محل حاضر می باشند و در بسیاری از این مناطق به دلیل وجود دریاچه، کوه و یا … امکان استقرار این نیروهای نظامی وجود ندارد.
در این تحقیق، مدل پیشنهادی ارائه شده یک مساله میانه با فواصل متعامد میباشد، بطوریکه در ناحیه پیوسته یک مانع خطی وجود دارد که در مسیر افقی حرکت خود، از توزیع احتمالی با تابع چگالی احتمال نرمال با پارامترهای معین و ثابت پیروی میکند.
فرضیاتی که برای مسئله تعریف می نماییم به قرار زیر می باشد:
مسئله از نوع مکان یابی پیوسته با ظرفیت نامحدود می باشد. یعنی هدف یافتن مکان چند تسهیل نقطهای در میان یک تعداد متناهی تسهیلات موجود متناهی میباشد، بطوریکه ظرفیت تسهیلات جدید برای خدمتدهی نامحدود میباشد.
مسئله از نوع مکان یابی پیوسته میانه متعامد در حالت چند تسهیله می باشد.
هر تسهیل موجود دارای مکان ثابت با مختصات معین، قطعی و دارای وزن غیرمنفی میباشد.
مساله برای کل افق برنامهریزی در ابتدای دوره، سیاستگذاری میکند، یعنی مساله مکانیابی ایستا میباشد.
با مساله مکانیابی محدود با یک مانع خطی سر و کار داریم، بطوریکه از عرض مانع صرفنظر میشود.
مانع بر روی یک مسیر افقی حرکت میکند.
مکان شروع مانع خطی، از توزیع نرمال با میانگین و انحراف معیار مشخص و ثابت پیروی میکند.
تسهیلات موجود در مسیر حرکت مانع مستقر نمی باشند.
تسهیلات جدید بر روی مسیر مانع خطی نمیتوانند استقرار یابند.
تعامل هم مابین تسهیلات جدید و موجود ، و هم ما بین تسهیلات جدید و جدید برقرار است.
كليات تحقيق و ساختار پایان نامه
ساختار پایان نامه به گونه ای می باشد که در ادامه و در فصل 2، ادبیات موضوعی مسائل بامانع و مسائل مکان‌یابی چند تسهیله را مورد بررسی قرار خواهیم داد. در فصل 3 زمینههای علمی تحقیق شامل دستهبندی مسایل مکانیابی، انواع توابع فاصله، مساله مکانیابی کلاسیک و الگوریتم ژنتیک بطور مفصل تشریح خواهند شد. در فصل 4 به تشریح مساله و مدل پیشنهادی می پردازیم. در ادامه این فصل به منظور درک بهتر رفتار مدل، یک مثال نمونهای ارائه خواهیم داد، اما با توجه به پیچیدگیهای مدل پیشنهادی در مقیاس های بزرگ، یک الگوریتم فراابتکاری (الگوریتم ژنتیک) را معرفی و نتایج محاسبات مربوط به این الگوریتمها را مورد بررسی و مقایسه قرار خواهیم داد. در نهایت، تعدادی از توسعههای آتی بههمراه نتیجهگیری در فصل 5 مورد بررسی قرار گرفتند و معرفی خواهند شد.
فصل دوم – ادبیات و پیشینه تحقيق
2-1 مقدمه
یکی از مسائل مهم و پیچیده در علم مهندسی صنایع مکان یابی تسهیلات می باشد. بسیار مشاهده شده است که در بسیاری از کارخانه ها ، به علت عدم چیدمان مناسب تسهیلات ، هر ساله نیاز به تغییر مکان تسهیلات گرفته این می شود. لیکن تنها دلیل تغییر چیدمان در کارخانه ،چیدمان نامناسب اولیه نمی باشد.
در بسیاری از موارد به دلایلی نظیر توسعه محصولات کارخانه، افزایش ظرفیت تولید، تغییر نوع محصولات، افزایش و کاهش در بنای کارخانه، نیاز به استفاده از تکنولوژی جدید و دستگاه های بروز و … نیاز به مکان یابی مجدد تسهیلات و یا مکان یابی تسهیلات موجود می باشد. مبحث مورد بحث ما مکان یابی تسهیلاتی جدید در میان تسهیلات موجود در کارخانه می باشد. مسایل مكانيابي تک وسیلهای (تک تسهیله) پيوسته در سطح، يكي از حوزه‌هاي گسترده در مدل سازي رياضي، در دنياي واقعي مي‌باشند، كه دراین مسایل يك تسهيل جديد (تسهیل عرضه) به مجموعهاي از تسهيلات موجود ( تسهیلات متقاضی)، با توجه به تقاضاهايشان، سرويس میدهد.
2-2 ادبیات موضوعی
در ادبيات موضوعي، معمولاً چند حالت از مسایل مكانيابي پيوسته، مورد بحث قرار میگیرد، مانند مساله ميانه، مساله مركز و مساله مركز-ميانه. در مساله میانه كلاسيك ( که غالبا مساله وبِر، مساله فرمارت اشنایدر وبر و مساله حداقل مجموع نیز نامیده ميشود)، در صدد یافتن مكان تسهيل جديد هستيم، بطوريكه مجموعه فواصل وزن دهي شده‌ با تسهيلات موجود، حداقل گردد. در گونهاي از مسایل میانه، ‌با محدوديت در قرارگيري و يا حركت مواجه هستيم. در ادبيات موضوعي اين نوع مسایل، معمولاً سه دسته از اين مسایل مورد مطالعه قرار گرفتهاند. اولين دسته، نواحي ممنوعه نامیده می شوند كه در این نواحی تسهيلات نمي‌توانند در آنجا قرار گيرند اما حركت در ميان اين نواحي بلامانع و بدون جريمه مي‌باشد (مانند مناطق و پاركهاي حفاظت شده و یا مناطقی که مشخصههای جغرافیای از قبیل شیب تند زمین از ایجاد تسهیل مورد نظر ممانعت میکند). براي مطالعه بروي مسایل مكانيابي میانه ‌و مرکز در نواحی ممنوعه به هاماخر و نیکل [5] مراجعه كنيد.
دسته دوم به عنوان نواحي متراکم شناخته میشوند كه در اين نواحي قرارگيري يك تسهيل ممنوع بوده اما حركت از ميان آن با جريمه همراه مي‌باشد (مانند درياچه‌اي كه، با قايق بتوان از دو طرف آن عبور و مرور كرد. برای نمونه، مسایل مکانیابی با نواحی متراکم، با سرعت و هزینههای سفر مختلف، در بوت و کاوالیر [6] مورد بحث و بررسی قرار گرفتهاند.
دسته سوم نواحی هستند كه تسهيل جديد نه مي‌تواند در آنجا استقرار يابد و نه مي‌تواند از ميان آن عبور كند. این نواحي، نواحي با مانع ناميده مي‌شوند. درياچه‌ها، كوهستانها، مناطق نظامي، رودخانه‌ها و بزرگراه‌ها و در مقياس كوچكتر، نوار نقاله‌ها، ماشینآلات موجود در كارخانجات، مثالهايي از اين نواحي مي‌باشند.
2-3 پیشینه تحقیقات انجام شده
مکان یابی تسهیلات در سطح همراه با مانع با مقاله ای توسط کاتز و کوپر آغاز گردید [1]. این مقاله اولین مقاله ای بود که مسئله وبر را در حالت متعامد و در حضور یک مانع بررسی می نمود. بعضی از موارد و خصوصیات این مقاله از جمله فضای شدنی مسئله بعد ها در مقاله ای توسط کلامورت توسعه داده شد[2].
اگر چه مسایل مكانيابي با مانع، در مقایسه با مسایل مكانيابي كلاسيك خيلي عمليتر و نزديك‌تر به دنياي واقعي مي‌باشند اما به علت پيچيدگي محاسباتي که اين نوع مسایل دارند، تنها در چند دهه اخير، وارد ادبيات موضوعي شده‌اند.
نويسندگان يك مساله وبر صفحهای را با فواصل اقليدسي و يك مانع دايره‌اي در نظر گرفتند. همچنين آنها، نشان دادند كه چنين مسایلی دارای تابع هدف غيرمحدب هستند و در ادامه براي حل آن يك روش ابتکاری مبتني بر تکنیک کمینه سازی متوالی بدون محدودیت پيشنهاد دادند.
انجا و پارلر [7] براي مسایل میانه در سطح و در حضور موانع چندوجهي، روشهای ابتکاریی را توسعه دادند. انجا و پارلر [7] بر مبناي مفهوم پدیداری و با بکارگیری الگوريتم كوتاهترين مسير دایجسترا براي مساله مكان‌يابي در حضور موانع چند وجهي (نه لزوما محدب) تحت شرایطی که تابع فاصله از نوع اقليدسي باشد، به کمک الگوریتم فرا ابتکاری شبیه سازی تبرید (SA)، حل بهينه تخميني را بدست آوردند. بوت و کاوالیر [8] حالت خاص مساله انجا و پارلر [7] را كه موانع چند وجهي محدب بودند را درنظر گرفتند. نویسندگان با استفاده از گراف پدیداری و با پیشنهاد يك روش ابتکاری، مساله وِبِر محدودیت دار ‌را به مساله بدون وِبِر محدودیت در هر تکرار الگوریتم، تبدیل کردند، سپس بر اساس شرط توقف معرفي شده، الگوريتم منجر به حل بهینه موضعی شد.
مکگاروی و کاوالیر [9] از روش اصلاح شده «مربع بزرگ مربع کوچک (BSSS)»، براي مساله مکانیابی میانه در حضور موانع چندوجهی و فواصل اقليدسي بهره بردند. روش BSSS يك الگوريتم هندسی شاخه و كران مي‌باشد كه توسط هانسن و همکاران [10] پيشنهاد شد. روش BSSS در ابتدا برای حل مسایل مکانیابی تسهیلات ناخوشایند پیشنهاد شد. اين الگوريتم براي مسایل مكانيابي پيوسته به اين صورت طراحي شد كه از طريق گسسته سازي‌، یک سطح یا صفحه پيوسته ناحيه شدني را به يك تعداد زير منطقه مربعي شکل تقسيم مي‌كند.
فریث و همکاران [11] یک مساله مکانیابی مرکز را در حضور موانع چندوجهی همراه با تابع فاصله اقلیدسی در نظر گرفتند. نویسندگان با استفاده از رويكرد انتشار امواج راديويي دايره‌اي ، كوتاهترين فاصله بین نقاط را تعيين كردند و سپس يك آزمايش تجربي مورد بررسی قرار داده و يك شبيه سازي كامپيوتري براي فواصل اقليدسي و متعامد، ارائه کردند.
در حالت خاص از فاصله منهتن (متعامد)، نتایج گسسته سازی توسط لارسون و صدیق [12] برای مساله وِبِر با اشكال دلخواه موانع بررسی شد. نويسندگان با ايجاد ساختار شبكه‌اي (شبكه موازاييكي) از گره و يال و با تعيين مجموعه متناهي مسلط و با بکارگیری مساله p-median، مشخص كردند كه این شبکه حاوي حداقل يك حل بهينه مي‌باشد.
مقاله فوق زمينهای برای توسعه و تحقيقات مشابه شد. باتا و همکاران [13]، دو مساله مكانيابي سطحي با فاصله متعامد را هم براي نواحي ممنوعه و هم موانع با اشکال دلخواه در نظر گرفتند. نويسنگان ابتدا يك مساله p-median و سپس يك مساله صف احتمالی میانه را در حضور موانع با اشکال دلخواه بررسي كردند.
گسسته سازي مشابه با لارسون و صدیق [12]، توسط هاماخر و کلامروس [14] براي مساله وِبِر با موانع و فواصل بلوکی، انجام گرفت. كارايي محاسباتي روشهاي فوق‌الذكر، توسط دیرینگ و سگراس [16-15] بطور قابل ملاحضه ای بهبود داده شد. نويسندگان نشان دادند که يك مجموعه مسلط کاهیده شده براي اين مساله کافی و مناسب مي‌باشد
دسته‌اي ديگر از تحقيقات، در ادامهی مطالعات لارسون و صدیق [12] و باتا و همکاران [13] توسط ساواش و همکاران [17]‌ آغاز شد. نويسندگان مدلي براي قرارگيري تسهيلات با اندازه متناهی توسعه دادند كه ممکن است اندازهشان براي خودشان به عنوان مانع عمل کنند. وانگ و همکاران [18]، مساله مكانيابي تك تسهيله را در جانمایی کف یک فروشگاه با فواصل متعامد مورد مطالعه قرار دادند. در اين مقاله، با توجه به نقاط ورودی و خروجی تسهيلاتِ تقاضایِ مستطيلي شكل با مکان ثابت‌، حداقل هزينه‌ي مسافتِ كل، از تسهيل عرضه، كه به اين تسهيلات سرويس مي‌دهد، بدست آمد. گسترشي از کار ساواش و همکاران [17] توسط کلاچنکاتیو و همکاران [19]، انجام شده است. نویسندگان استقرار يك تسهيل با اندازه محدود را در چیدمان در صورتي كه تسهيل جديد و دپارتمانهاي موجود مستطيل شكل و فواصل ازنوع نرم 1l‌ باشند، در نظر گرفتند. آنها بواسطه اينكه تسهيل جديد بعلت برخي محدوديتها نمي‌تواند در مكان بهينه استقرار يابد، از خطوط كانتور به منظور یا فتنِ مكان مناسب جايگزين برای دپارتمان جديد، استفاده كردند.
ناندیکوندا و همکاران [20] مساله مكانيابي مرکز ‌را در حضور موانع با اشکال دلخواه و فواصل منهتن بررسي كردند. نویسندگان از تكنيك تجزيه سازي ناحيه شدني به سلولها كه توسط لارسون و صدیق [12] مطرح شده بود را براي اين مساله توسعه دادند. گسترشی از مطالعه ناندیکوندا و همکاران [20]، توسط سرکار و همکاران [21] كه مكانيابي يك تسهیل با اندازه محدود و شکل دلخواه ‌را در حضور موانع با اشکال دلخواه و تابع هدف مرکز و تابع فاصله متعامد در نظر گرفتند، انجام شد. همچنين نویسندگان، بر خلاف ساواش و همکاران [17] ‌بجاي مساله میانه‌، مساله مرکز را و همينطور فقط رابطه ميان تسهيل جديد و تسهیلات موجود را در نظر گرفتند.
در ادبيات موضوعي مسایل وِبِر علاوه بر موانع چندوجهی و دایرهای، يك مانع خطي، همراه با تعدادي گذرگاه توسط کلامروس [15] براي هر نوع فاصله دلخواه، معرفي شد. در ادامه کلامروس و ویچک [19] مدل فوق را براي مساله دو هدفه میانه بررسي كردند.
موانع احتمالی بطور طبیعی در برخی موارد از دنیای واقعی اتفاق میافتد. موانع ممکن است، دارای موجودیت تصادفی، مکان تصادفی و یا اندازه تصادفی باشند. برای مثال، در چیدمان تسهیلات، واگنهای که می توان از عرض آن نسبت به طول آن صرفنظر کرد و در روی ریل برای حمل داخل کارخانه بطور مداوم در حرکتند، برای جریان مواد داخل کارخانه تداخل ایجاد میکنند را میتوان، یک نمونه از این موانع خطی با مکان احتمالی برشمرد. کانبولات و وسولوسکی [3] برای اولین بار، بطور رسمی بروی موانع احتمالی بحث کردند.
پس از آن شیری پور و همکاران [4] مقاله ای در زمینه ی بهبود مقاله ی کانبولات و وسولوسکی [3] ارائه کردند که در این مقاله ، مسئله را از حالت تک تسهیله به مکان یابی چند تسهیله تغییر دادند. نتیجه بدست آمده جواب بهینه همراه با ارائه دو الگوریتم ابتکاری(الگوریتم ژنتیک و الگوریتم رقابت استعماری) می باشد.
2-3-1 روند تحقیقات انجام شده
جدول 1-1 روند مقالات علمی وتحقیقات انجام شده در زمینه مکان یابی تسهیلات در حضور مانع را نشان می دهد[3].
جدول SEQ Table \* ARABIC 1-1 روند تحقیقات علمی و مقالات انجام شده در زمینه مکان یابی در حضور مانع
Result Barrier type Barrier shape Facility shape Interaction Objective Distance Heuristic Fixed Circular Point User–facility Minisum Euclidean Katz and Cooper (1981)
Optimal Fixed Arbitrary Point User–facility Minisum Rectilinear Larson and Sadiq (1983)
Optimal Fixed Arbitrary Point User–facility Minisum Rectilinear Batta et al. (1989)
Heuristic (SA) Fixed Arbitrary Point User–facility Minisum Euclidean Aneja and Parlar (1994)
Local optimal Fixed Convex polygonal Point User–facility Minisum Euclidean Butt and Cavalier (1996)
Optimal Fixed Convex polygonal Point User–facility Minisum Block Hamacher and Klamroth
(2000)
Optimal Fixed Convex polygonal Point User–facility Minisum or
center Any Klamroth (2001a)
Optimal Fixed Line with
passages Point User–facility Minisum Euclidean Klamroth (2001b)
Optimal Fixed Convex polygonal Point User–facility Center Rectilinear Dearing et al. (2002)
Optimal Fixed Arbitrary Point User–facility Minisum or
Center Rectilinear Dearing and Segars (2002a)
Optimal Fixed Arbitrary Point User–facility Minisum or
center Rectilinear Dearing and Segars (2002b)
Pareto optimal Fixed Line with
passages Point User–facility Minisum Any Klamroth and Wiecek
(2002)
Heuristic Variable Arbitrary Finite User–user and user –facility Minisum Rectilinear Savas et al. (2002)
Optimal Fixed Rectangular Finite or
point User–facility Minisum Rectilinear Wang et al. (2002)
Optimal Fixed Convex polygonal Point User–facility Minisum Euclidean McGarvey and Cavalier
(2003)
Optimal Fixed Arbitrary Point User–facility Center Rectilinear Nandikonda et al. (2003)
Optimal Fixed Circular Point User–facility Minisum Euclidean Klamroth (2004)
Optimal Fixed Convex polygonal Point User–facility Minisum or
center Block Dearing et al. (2005)
Optimal (experimental) Fixed Convex polygonal Point User–facility Center Euclidean Frieß et al. (2005)
Heuristic (GA) Fixed Convex polygonal Point User–facility Minisum Euclidean Bischoff and Klamroth
(2007
Multiple optimal Variable Rectangular Rectangular User–user and user –facility Minisum Rectilinear Kelachankuttu et al. (2007)
Optimal Variable Arbitrary Finite User–facility Center Rectilinear Sarkar et al. (2007)
Optimal Probabilistic Line Point User–facility Minisum Rectilinear Canbolat & wesolowsky(2008)
Optimal Probabilistic Uniform Line Point User–user and user –facility Minisum Rectilinear Shiripour, et al
(2012)
Optimal Probabilistic
Normal Line Point User–user and user –facility Minisum Rectilinear This paper
پایان نامه ارائه شده در جهت بهبود مقاله ارائه شده توسط شیری پور و همکاران [4] اقدام نموده است. دستاورد این پایان نامه بهبود مقاله ارائه شده از سوی شیری پور و همکاران [4] می باشد.
این پایان نامه در مقایسه با شیری پور و همکاران [4] علاوه بر تغییر نوع توزیع حرکت مانع خطی , در روش حل صورت پذیرفته در الگوریتم ژنتیک کاملا متفاوت عمل نموده و همچنین تابع هدف و محدودیت های کاملا متفاوتی را ایجاد نموده است و این مطلب تنها به خاطر پیچیده بودن انتگرال توزیع نرمال می باشد که باعث تغییر در میزان فاصله بین دو نقطه در مقایسه با توزیع یکنواخت نموده است.
اگرچه با انجام این تغییر بر روی مسئله پیچیدگی مسئله به مراتب بسیار بیشتر از حالت توزیع مانع در حالت یکنواخت می باشد، لیکن کاربردیتر شدن مسئله از حیث استفاده از آن در صنایع تولیدی ، نظامی و… به لحاظ ساختار خاص توزیع نرمال، این امر را توجیه پذیر می نماید. نکته مثبت دیگر استفاده از توزیع پیچیده نرمال در مسئله این است که با تحقیقات انجام شده در این پایان نامه، استفاده از سایر توزیع ها و به کار گرفتن آنها در مسئله برای هر نوع توزیع پیوسته , به صورت مشخص امکان پذیر گشته است. زیرا روند جایگزینی سایر توزیع ها بجای توزیع نرمال از روند این پایان نامه پیروی می نماید و با دنبال کردن روند کار صورت پذیرفته در این پایان نامه, می توان هر نوع توزیع پیوسته دیگری را جایگزین نوع توزیع مانع خطی نمود.
فصل سوم – روش تحقيق
3-1 مقدمه
همانطور که در فصل دوم ملاحظه فرمودید, روند پیشرفت کارهای گذشته به گونه ای بوده است که مسئله را در حالت مکان یابی چند تسهیله در حضور مانع خطی با توزیع احتمال یکنواخت فرموله کرده و نتایج قابل قبولی بدست آمده بود.
پس از مطالعه و بررسی انجام شده روی مقاله ارائه شده از سوی شیری پور و همکاران [4] و مشاهده پیشنهادات ارائه شده، یکی از پیشنهادات در جهت بهبود مسئله کاربردی تر به نظر می رسید. فرض نرمال گرفتن حرکت مانع خطی یکی از پیشنهادات بسیار کاربردی در این زمینه می باشد که با توجه به این مهم, تحقیق در این زمینه صورت پذیرفت.
3-2 فواصل در مسایل برنامهريزي تسهيلات
چنان چه مختصات تسهیل جديدX=(x,y) و وسيله موجود Xi=(xi,yi) در صفحه دوبعدی باشند، آنگاه فواصل زير را مي‌توانيم تعريف كنيم.
3-2-1 فاصله خط مستقيم يا اقليدسي
فاصله اقليدسي بين X و Xi به صورت زير تعريف مي‌شود :
(3-1) d2X,Xi=x-xi2+y-yi2 .
فاصله اقليدسي براي برخي از مسایل جايايي شبكه شامل نقاله و سفر هوايي به كار مي‌رود. برخي از مسایل سيم‌كشي الكتريكي و مسایل طراحي لوله‌كشي نيز نمونه‌ها‌يي از مسایل فاصله اقليدسي هستند. شکل (3-1) مسیر حاصل از این فاصله را بين X و Xi با خط تیره مشخص میسازد.

شکل 3-1 فاصله اقلیدسی در صفحه
3-2-2 فاصله مجذور خط مستقيم يا اقليدسي
در برخي مسایل جايايي تسهيلات، هزينه تابع درجه اول فاصله نيست. به عنوان مثال، انتظار مي‌رود هزينه مرتبط با عكس‌العمل يك ماشين آتش‌نشاني با فاصله غيرخطي باشد. فرض كنيد، هزينه با مربع فاصله اقليدسی بين X و Xi متناسب باشد. فاصله اقليدسي بين X و Xiبه صورت زير تعريف مي‌شود:
(3-2) dESX,Xi=x-xi2+y-yi2. اين نوع فاصله بیشتر در مسایل خدمات اورژانس و آتشنشانی و به طور کل مسائلی که فاصله بین خدمت دهنده و خدمت گیرنده عاملی بسیار می باشد كاربرد دارد.
3-2-3 فاصله منهتن یا متعامد
در غالب مسائل مکانیابی ماشين، فاصله در مجمو‌عهاي از راهروهايي پيموده مي‌شود كه در الگويي مستطيلي و موازي با ديو‌ارهاي ساختمان هستند. در چنين وضعيتي، فاصله متناسب به صورت متعامد مستطيلي، كلان شهر‌ي يا منهتن است (گاهی اوقات فاصله خطی شکسته، پلهای و راهرویی نیز نامیده میشود). فاصله متعامد بين X و Xiرا بصورت زير تعريف ميكنيم‌‌:
(3-3) d1X,Xi=x-xi+y-yi. فاصله متعامد بر‌اي تحليل‌هاي جايابي شهري مناسب است كه در آن سفر در امتداد مجموعه محدبي از خيابان‌ها اتفاق مي‌افتد.
شکل (3-2) مسیرهای متعامد مختلف بین X و Xiرا نشان میدهد که فواصل متعامد یکسان دارند.

شکل 3- 2 مسیرهای مختلف متعامد بین X و Xi
3-2-4 فاصله چبيشف فاصله چبيشف بين دو نقطه بین X و Xi با علامت t(X, Xi) نمايش داده ميشود و به صورت زیر تعريف ميگردد:
tX,Xi=maxx-xi,y-yi(3-4)
در حالي كه فاصله متعامد برابر مجموع فواصل افقي و عمودي دو نقطه است. فاصله چبي‌شف بر‌‌ابر حداکثر فواصل ‌افقي و عمودي دو نقطه است.
از جمله كاربردهاي اين فاصله این است كه حركت مواد در كارخانه به كمك جرثقيل‌هاي مجهز‌‌‌ به دو موتور انجام مي‌شود كه موتور سبب حركت در جهت محور x‌ ها و ديگري سبب حركت در محورy ها است. همچنين در مسایل انتخاب سفارش نيز اين فاصله كاربرد دارد.
3-2-5 كوتاه‌ترين مسير
در مسایل مكان‌يابي روي شبكه از آن‌جا كه معمولاً بيش از يك مسير بين هر دو گره وجود دارد، روش كوتا‌هترين مسير براي تعيين فاصله بين دو گروه مورد استفاده قرار مي گيرد‌.
3-3 مسایل مکانیابی میانه با انواع فاصله
در اين بخش، مساله تعيین مكان چند وسيله جديد نسبت به يك تعداد وسيله موجود مورد بررسي قرار مي‌گيرد. مكانهای كه به دنبال آنها هستيم، جايي است كه يك تابع هزينه كل تعريف شده را حداقل ميكند و هز ينه كل مذ‌كور متناسب با فاصله در نظر گرفته مي‌شود.
تعدادي از مسایل مکانیابی چند تسهيله جالب وجود دارند كه براي نمونه تعيين مكان تسهيلات زير قابل ارائه است:
انبارهای جديد بر‌اي تسهيلات توليدي و مشتريان،
ماشينهای تراش جديد در يك مكان توليدي،
بيمارستان، ايستگاه آتشنشاني، اداره پليس يا كتابخانه در يك كلانشهر،
ساختمانهای كلاس درس جديد در زمين يك دانشكده،
مناطق هوايي جديد كه براي تامين تعدادي پايگاه‌هاي نظامي استفاده مي‌شود،
جرثقيل در بخشي از بزرگراه براي پيش‌بيني تصادفات ترافيكي،
سكوهاي بارگيري در يك انبار،
اسبابهای جديد در يك آشپزخانه،
منابع آب در يك ساختمان
نمونه خيلي ساده از مساله مکانیابی چند تسهيله، تسهیلات جديد مي‌تواند كارخانههایی باشد كه تامين كننده انبارهايي است كه تسهيلات موجودند وهزينه‌هاي حمل ونقل متناسب با فاصله بين كارخانه وانبار‌ها هستند؛ wij مي تواند هزينه كل حمل ونقل به ازاي هر واحد فاصله بين كارخانه j-ام و انبار i-ام باشد، و همچنین vjk مي تواند هزينه كل حمل ونقل به ازاي هر واحد فاصله بين كارخانههای جدید j-ام و k-ام باشد. در نمونه ديگر، وسايل جديد مي‌توانند ماشينهایی جديد باشند كه قرار است در يك طرح استقرار ماشين‌آلات جايابي شوند. از آنجا كه محصولات بين ماشين‌هاي جديد و موجود به عقب و جلو سفر ميكنند، هزينهها متناسب با فاصله هستند.
سوال اين است كه «يك فاصله متناسب» به چه معنا است؟
در بيشتر مسایل جايابي ماشين، فاصله در مجموعهاي از راهروهايي پيموده ميشود كه الگويي مستطیلي و موازي با ديوارهاي ساختمان هستند. در چنين وضعيتي، فاصله متناسب به صورت متعامد، مستطيلي، يا منهتن است. چنانچه از فاصله متعامد بين Xj، j=1,…n و Xi، i=1,…m، استفاده كنيم تابع هزینه کل، به صورت زير در مي‌آيد:
(3-5) f(X)=i=1mj=1nwijxj-xi+yj-yi+j=1nk=1k>jnvjkxj-xk+yj-yk. فاصله متعامد براي برخي تحليل‌هاي جايابي شهري مناسب است كه در آن سفر در امتداد مجموعه محدبي از خيابان‌ها اتقاق مي‌افتد. به علاوه، تعدادي از ادار‌ات، مجموعه‌اي از راهروها و تالارهاي متعامد را براي حركت پرسنل به كار مي‌برند. در اين حالت هزينه تابع خطي درجه اول از فاصله است.
در برخي مسایل جايابي تسهيلات، هزينه، تابع خطي درجه اول نيست. به عنوان مثال، انتظار مي‌رود هزينه مرتبط با عكس‌العمل يك ماشين آتش‌نشاني با فاصله غير خطي متناسب باشد، بنابر‌اين در مساله جايابي f(x) ميتواند فرمول بندي‌هاي متفا‌وتي داشته باشد.
يكي از شكل‌هاي f(x) غيرخطي هنگامي است كه فاصله به صورت خط مستقيم يا اقليدسي باشد. اگر مختصات تسهیلات جديد Xj=(xj,yj) و براي وسيله موجود Xi=(xi,yi) باشند، رابطه هزينه کل برای فواصل اقلیدسی بهشرح زیر میباشد:
(3-6) f(X)=i=1mj=1nwij2(xj-xi)2+(yj-yi)2+j=1nk=1k>jnvjk2(xj-xk)2+(yj-yk)2. فاصله اقليدسي براي برخي از مسایل جايابي شبكه، شامل نقاله‌‌ها وسفر هوايي به كار مي‌رود. برخي از مسایل سيم‌كشي الكتر‌يكي و مسایل طراحي لوله‌كشي نيز نمونه‌هايي از مسایل فاصله اقليدسي هستند.
يكي ديگر از شكل‌هاي f(x) غيرخطي كه در اين قسمت بررسي مي‌شود، مساله مركز ثقل یا مربع اقلیدسی است. فرض كنيد هزينه با مربع فاصله اقليدسي بين Xj، j=1,…n و Xi، i=1,…m، متناسب باشد. بنابر‌اين، رابطه هزينه به صورت زير در مي‌آيد:
(3-7) f(X)=i=1mj=1nwij(xj-xi)2+(yj-yi)2+j=1nk=1k>jnvjk(xj-xk)2+(yj-yk)2.مسایل جايابي كه فرمول‌بندي داده شده در رابطه فوق را دارند به مسایل مركز ثقل تعبير مي‌شوند.
3-4 فرآیند تحقیق
به منظور توضیح هر چه بیشتر در خصوص روش تحقیق به عمل آمده، در ابتدا می بایست تعریف ساده و صحیحی از مسئله ارائه دهیم.
3-4-1 تعریف ساده ای از مسئله
فرض کنید در محیطی به مساحتی دلخواه، تعدادی تسهیل موجود به صورت دلخواه (از نظر تعداد) ولی محدود داریم. تسهیلات موجود در سیستم ثابت فرض می شوند. بدین معنی که امکان جابجایی تسهیلات موجود در سیستم مقدور نمی باشد و همچنین هر تسهیل موجود دارای مکان ثابت با مختصات معین، قطعی و دارای وزن غیرمنفی میباشد.
مسئله موجود از نوع مکان یابی پیوسته میانه متعامد در حالت چند تسهیله می باشد و همچنین در ابتدای دوره برای کل افق برنامهریزی در ابتدای دوره، سیاستگذاری میکنیم، یعنی مساله مکانیابی ایستا میباشد.
حال فرض کنید تعدادی تسهیل جدید(بیشتر از یک عدد) را می خواهیم مکان یابی نمائیم به گونه ای که کل هزینه کمینه گردد. تسهیلات جدید دارای وزن غیر منفی و ثابت با تسهیلات موجود و با سایر تسهیلات جدید می باشند.
دشواری کار زمانی می باشد که یک مانع وجود دارد که به صورت خطی در جهت محور x ها حرکت می نماید. مانع به گونه ای می باشد که از عرض آن صرفه نظر می گردد. حرکت این مانع به گونه ای می باشد که دارای توزیع نرمال با میانگین و انحراف معیار مشخص و ثابت می باشد. همچنین حرکت بین نقاط تنها به صورت اقلیدسی امکان پذیر می باشد.
حال می بایست تسهیلات را به گونه ای مکان یابی نمائیم که کمترین هزینه برای ما ایجاد گردد. همچنین امکان استقرار تسهیلات بر روی مسیر حرکت مانع نیز وجود ندارد.
3-4-2 وضعیت دو نقطه نسبت به هم در حضور مانع
دو نقطه را یک سطح دو بعدی در نظر بگیرید. حال فرض کنیم در این بین مانعی خطی نیز وجود داشته باشد. با توجه به نحوه ی قرار گرفتن دو نقطه و وضعیت دو نقطه نسبت به هم و همچنین مکان استقرار مانع خطی و وضعیت آن نسبت به نقاط، می توانیم سه حالت را برای فاصله بین دو نقطه در نظر گرفت.(دقت شود حرکت بین نقاط تنها به صورت فاصله اقلیدسی امکان پذیر می باشد).

شکل 3-3 وضعیت های مختلف دو نقطه نسبت به هم در حضور مانع خطی

اجازه دهید قبل از توضیح حالات فوق به سه نکته مهم اشاره نماییم:
در این پایان نامه همواره بجای صحبت از “فاصله بین دو نقطه” از لفظ “میانگین فاصله بین دو نقطه” استفاده می شود. این مطلب به این دلیل می باشد که در مسئله مورد بررسی، مانع دارای توزیع احتمالی می باشد و می بایست به ناچار امید فاصله را محاسبه نمود.
وجود مانع برای نقاط یک نوع محدودیت در فاصله به همراه دارد. فلذا می توان گفت میانگین فاصله بین دو نقطه در حالت بدون وجود هرگونه مانع، حتما بیشتر از میانگین فاصله در حالت وجود مانع نخواهد شد. در واقع حتما کوچکتر مساوی خواهد شد.
در هر سه حالت شکل فوق، وجود مانع هیچ گونه تاثیری بر روی فاصله y ها نخواهد گذاشت. این مطلب را کانبولات و وسولوسکی [3] به اثبات رسانده اند. دلیل این اثبات را می توان به صورت خلاصه ” فرض ناچیز بودن عرض مانع ” بیان نمود.
میزان امید فاصله بین دو نقطه i وj در هر سه حالت در جهت محور y ها برابر است با yi-yj. بنابراین در توضیحاتی که در ادامه ارائه می شود تنها امید فاصله بین دو نقطه را در جهت محور x ها مورد بررسی قرار خواهیم داد.
حال با توجه به موارد عنوان شده ، به بررسی سه حالت شکل 3-1 می پردازیم.
حالت الف :
در این حالت دو نقطه در یک طرف مانع قرار دارند. به وضوح مشخص می باشد که در این حالت مانع هیچ گونه تاثیری بر روی میزان فاصله نمی گذارد. بنابراین امید فاصله میان دو نقطه i وj برابر است با : xi-xj.
حالت ب :
در حالت ب اگرچه نقاط i وj هر کدام در دو طرف مانع می باشند، لیکن مجدداً مشاهده می گردد که وجود مانع هیچ گونه تاثیری بر روی میزان امید فاصله میان دو نقطه i وj نمی گذارد و امید فاصله میان دو نقطه i وj مجددا” برابر است با : xi-xj.
با کمی دقت می توان دریافت دلیل این امر بیشتر بودن میزان فاصله xi-xj از اندازه طول مانع( xs-xf ) می باشد که در ادامه در این مورد بحث خواهد شد.
حالت ج :
حالت ج حالتی می باشد که در آن مانع بر روی میزان امید فاصله میان دو نقطه i وj تاثیر می گذارد و آن چنان که در قبل ذکر شد، در این صورت قطعا” میزان امید فاصله میان دو نقطه i وj بیشتر از مقدار xi-xj خواهد شد.
سه حالت عنوان شده در فوق و نحوه قرارگیری دو نقطه و مانع در آن را نسبت به هم می توان در دسته بندی دیگری نیز قرار داد که سهولت بیشتری در فرموله کردن مسئله می نماید که از نتیجه موارد زیر در فصل چهارم استفاده خواهیم نمود.
در شکل 3-1 حالت الف و ب را حالت visible و حالت ج را Shadow می نامند.
در حالت visible ، مانع تاثیری بر روی میزان امید فاصله میان دو نقطه i وj ندارد و حالت Shadow مربوط به زمان تاثیر مانع بر روی میزان امید فاصله میان دو نقطه می باشد.
نتیجه گرفته شده از عبارت فوق که می تواند در فرموله کردن مسئله کمک زیادی نماید ،این است که برای ایجاد حالت Shadow می بایست لزوما :
دو نقطه در دو طرفِ مختلفِ دو نیم صفحه ی ایجاد شده توسط مانع قرار داشته باشند.
xi-xj < xs-xf
در صورت عدم وجود حتی یکی از این دو شرط، حالت visible بین دو نقطه i وj برقرار می گردد.(البته حرکت مانع را به صورت افقی در این حین نیز می بایست مدنظر داشت)

3-4-3 کوتاهترین فاصله بین دو نقطه در حضور مانع
3-4-3-1 مانع به صورت ثابت
کوتاهترین فاصله بین دو نقطه (با توجه به نکته 4 بخش 3-4-3 ) را کانبولات و وسولوسکی [3] محاسبه نموده اند و اثبات کرده اند.ما نیز به دلیل استفاده از مطالب، آنها زا ذکر کرده و توضیحات جامع تری پیرامون آن ذکر خواهیم نمود.
همانطور که در پیش عنوان شد، به طور کلی دو حالت visible و Shadow در چگونگی قرارگیری مانع و دو نقطه ایجاد خواهد. در حالت visible همانطور که در قبل نیز عنوان شد امید فاصله به مانع بستگی نداشته و برابر xi-xj می باشد.
در حالت Shadow مانع تاثیر مهمی روی فاصله خواهد گذاشت و مقدار آنرا بیشتر خواهد نمود.حال این مقدار به چه میزان می باشد؟

شکل 3-4 فاصله بین دو نقطه در حالت Shadow
با دقت در شکل بالا می توان میزان فاصله بین دو نقطه را پیدا کرد. کانبولات و وسولوسکی [3] این مقدار را محاسبه نموده اند.
فاصله میان دو نقطه i وj را در حالت Shadow با نماد llB نمایش می دهیم و برابر است با : llB=Min(xj+xi-2xs,2xs+2l-xj-xi)(3-8)
برای فهم بهتر فرمول (3-8) ، شکل 3-4 را مشاهده نمایید. چنانچه بخواهیم از نقطه A در نیم صفحه پایین به نقطه B در نیم صفحه بالا برویم، با توجه به اینکه نوع حرکت ما اقلیدسی می باشد، دو مسیر داریم. یا می بایستی از سمت چپ نقطه A حرکت نماییم یا از راست. چنانچه از سمت چپ (فلش های کشیده شده به رنگ سرمه ای) حرکت نماییم ،مسافت طی شده به صورت زیر می باشد:
(xi-xs)+xj-xs=xj+xi-2xsو چنانچه از سمت راست(فلش های کشیده شده به رنگ سبز) حرکت نماییم:
(xf-xi)+xf-xj=2xf-xj-xiبدین دلیل که می خواهیم براساس xs فرمول بندی نماییم، لذا از عبارت xf=xs+l استفاده می نماییم و در نهایت با جایگذاری خواهیم داشت :
2xf-xj-xi=2*(xs+l)-xj-xiحال هر کدام از این دو که کمتر بود ( با توجه به نحوه ی قرار گیری مانع) می تواند انتخاب شود.
دقت شود محاسبات فوق مربوط به حالتی می باشد که مانع ثابت بوده و لذا محاسبات برای حالت قطعی می باشد نه احتمالی. بنابراین در بجای لغت “امید فاصله” واژه “فاصله” بکار رفته است.
3-4-3-1 مانع به صورت متحرک
این مطلب را کانبولات و وسولوسکی [3] اثبات نموده اند و ما تنها شرح مختصری از آن می دهیم. صرفه نظر از نوع توزیعی که مانع دارد، صرف حرکت مانع به تنهایی باعث به وجود آمدن حالت های visible و Shadow می شود. برای آنالیز حالت های مختلف می بایستی فضای مسئله را به دو حالت کلی تقسیم کرد.
حالت الف) Xi<Xj برای فهم بهتر مسئله اینطور می توان تصور کرد. نقاطxi وxj ثابت می باشند و مانعی به طول ثابت l که نقطه ی ابتدایی آن xs و نقطه ی انتهایی آن xf می باشد با توزیع مشخصی(صرف نظر از نوع توزیع)وارد می شود. مانع به گونه ای وارد فضا می شود که قابلیت ایجاد حالت Shadow را داشته باشد.یعنی مطابق شکل 3-4 مقدار عرض مانع که ما با y=b نمایش می دهیم بین عرض نقاط i وj قرار گیرد. با این تصور در خواهیم یافت شرط اول برای ایجاد حالت Shadow برقرار شده است. با حرکت مانع در جهت مثبت محور x ها، زمانی که xi-xj < xs-xf شد، یا به عبارت ساده تر xi<xs,xf<xj قرار گرفت حالت Shadow اتفاق می افتد. در ابتدای ورود مانع به حالت Shadow میزان کمی اضافه مسیر طی می گردد و این میزان تا نقطه ای که xs به xj+xi-l2 برسد، همواره افزایش می یابد و سپس از این نقطه به بعد روند کاهش تا زمانی که نقطه xs به xi برسد ادامه پیدا می کند و با ادامه حرکت مانع در جهت مثبت محور x ،از حالت Shadow (به علت فقدان شرط دوم آن) خارج می شویم.
شکل های 3-5 و 3-6 به خوبی این مطلب را نشان می دهند.

شکل 3-5 تابع فاصله در حضور مانع خطی در حالت xi<x j
حالت ب) Xi>Xjبه طریق مشابه نیز می توان نموداری در این حالت ترسیم نمود.شکل 3-6 این مطلب را نشان می دهد.
شکل 3-6 تابع فاصله در حضور مانع خطی در حالت xi>x j
دقت شود در حالات فوق نوع توزیع حرکت مانع تاثیری بر روی شکل ها نخواهد گذاشت. این مطلب به سبب وجود موقعیت نسبی بین دو نقطه و خط می باشد و نوع توزیع تنها زمان حضور بیشتر یا کمتر مانع در یک مکان خاص را نشان خواهد داد. (البته به شرطی که توزیع تعریف شده شامل محدوده حرکتی که ایجاد حالت Shadow نماید، باشد و مقادیر ممکن برای متغییر آن قابلیت ایجاد حالت Shadow را داشته باشد)
فصل چهارم – محاسبات و یافته های تحقيق
4-1 مقدمه
درفصل سوم تعریف ساده و دقیقی از مسئله بیان گردید. حال در این فصل قصد داریم تا مواردی که نیاز به اثبات دارند و همچنین مواردی که به صورت عملیات ریاضی می باشند را توضیح دهیم.
همچنین در این فصل الگوریتم پیشنهادی را ارئه خواهیم نمود. این الگوریتم را سپس با انجام یک مثال مورد امتحان قرار خواهیم داد. همانطور که در ادامه مشاهده خواهید کرد، خواهیم دید که مسئله دارای پیچیدگی محاسبات می باشد و همچنین تابع مسئله به صورت غیر خطی برنامه ریزی می شود. لذا به منظور بهینه سازی مسئله ، الگوریتم فراابتکاری ژنتیک نیز ارائه می شود و مقایسه میان این دو انجام می پذیرد.
4-2 محاسبه امید فاصله بین دو نقطه در حالت Shadow
در فصل قبلی فاصله میان دو نقطه i وj در حالت Shadow و در حضور مانع ثابت، محاسبه گردید. دشواری کار زمانی می شود که مانع دارای حرکت احتمالی باشد. قبل از محاسبه امید فاصله بین دو نقطه در حالت Shadow ، فرضیات زیر را مطرح می نماییم:
مانع دارای حرکت احتمالی با توزیع نرمال با میانگین ثابت و معلوم µ و انحراف معیار ثابت و معلوم σ می باشد.
Xs~ N(μ , σ)hxs=1σ2πe-xs-μ22σ2طول مانع ثابت و برابر مقدار معلوم l می باشد.
E1 امید فاصله بین دو نقطه i وj در حالتی که Xi<Xj و E2 امید فاصله بین دو نقطه i وj در حالتی که Xi>Xj می باشد.بدیهی است در حالت Xi=Xj دو مقدار E1, E2 برابر خوهند شد.
چنانچه دو نقطه و مانع حالت Shadow را ایجاد کنند، فضای حالت ایجاد شده را φ می نامیم و چون محاسبات ما بر اساس Xs می باشد به صورت Xs∈φنمایش می دهیم.
حال امید فاصله بین دو نقطه A و B را در شکل 4-1 به صورت زیر محاسبه می نماییم:

شکل 4-1 دو نقطه در حالت Shadow

برای این منظور فضا را به دو قسمت visible و Shadow تقسیم می نماییم. همچنین برای دو حالت Xi<Xj و Xi>Xj نیز جداگانه امید ریاضی با نام E1 و E2 را محاسبه می نماییم. بنابراین طبق تعریف امید ریاضی مشروط داریم:
E1=ELbfXi,XjXs∈ φ , Xi<Xj=xj-lxj+xi-l22xs+2l-xj-xiPxj-l≤Xs≤xi hxsdxs+xj+xi-l2xixj+xi-2xsPxj-l≤Xs≤xi hxsdxs =xj-lxj+xi-l22xs+2l-xj-xixj-lxi1σ2πe-xs-μ22σ2dxs ×1σ2πe-xs-μ22σ2dxs+xj+xi-l2xixj+xi-2xsxj-lxi1σ2πe-xs-μ22σ2dxs ×1σ2πe-xs-μ22σ2dxsE2=ELbfXi,XjXs∈ φ , Xi>Xj=xi-lxj+xi-l22xs+2l-xj-xiPxi-l≤Xs≤xj hxsdxs+xj+xi-l2xjxj+xi-2xsPxi-l≤Xs≤xj hxsdxs =xi-lxj+xi-l22xs+2l-xj-xixi-lxj1σ2πe-xs-μ22σ2dxs ×1σ2πe-xs-μ22σ2dxs+xj+xi-l2xjxj+xi-2xsxi-lxj1σ2πe-xs-μ22σ2dxs ×1σ2πe-xs-μ22σ2dxs4-3 محاسبه امید فاصله بین دو نقطه در حضور مانع احتمالی در حالت کلی
دقت کنید که در قسمت قبلی تنها امید فاصله بین دو نقطه i وj در حالت Shadow محاسبه شد. مطابق آنچه در قسمت 3-4-2 عنوان شد، امید فاصله در حالت visible برابر xi-xj می باشد.
حال می بایست این دو حالت Shadow و visible را به صورت یکجا و در قالب یک امید ریاضی از فاصله وارد مسئله نمائیم.
برای رسیدن به این منظور ابتدا می بایست احتمال حضور مانع در محدوده ی خاصی که شرط دوم برای برقرای حالت Shadow می نماید را محاسبه نماییم. با این کار تاثیر حالت احتمالی مانع را وارد مسئله نموده ایم.
به همین منظور αXj را به صورت زیر تعریف می نماییم:
برای حالت Xi<Xj :
αxj=xj-lxi1σ2πe-xs-μ22σ2dxs=Pxj-l≤Xs≤xi=Pxj-l-μσ≤Xs-μσ≤xi-μσ=Pxj-l-μσ≤Z≤xi-μσ=PZ≤xi-μσ-PZ≤xj-l-μσ=Φxi-μσ-Φxj-l-μσبرای حالت Xi>Xj :
αxj=xi-lxj1σ2πe-xs-μ22σ2dxs=Pxi-l≤Xs≤xj=Pxi-l-μσ≤Xs-μσ≤xj-μσ=Pxi-l-μσ≤Z≤xj-μσ=PZ≤xj-μσ-PZ≤xi-l-μσ=Φxj-μσ-Φxi-l-μσدر جایی که αXj تابعی از Xj می باشد که تاثیر حالت احتمالی را برقرار می نماید. در واقع تابع αXj حالتی را که مانع در برای ما حالت Shadow را مشخص می نماید، نشان می دهد. همانطور که در فصول قبل نیز عنوان شد ما متغییر اصلی خود را Xs انتخاب می نماییم.
حال توضیح بیشتری در مورد فرمول بالا ارائه می دهیم. کانبولات و وسولوسکی [3] اثبات نموده اند که چنان چه دو محدودیت
X s≤Xj≤Xf X s≤Xi≤Xfتواما” برقرار شود،آنگاه
maxXj-L , Xi-L<Xs<minXj,Xiبنابراین می توان گفت شرط دوم برای برقرای حالت Shadow ایجاد شده است. به عبارت ساده تر چنان چه نقاط i وj درون ناحیه محصور شده توسط مانع قرار گیرند(از جهت محور x ها) حالت Shadow برقرار شده است.
حال چنان چه دو شرط فوق برقرار شوند و بخواهیم این مطلب را برای حالت Xi<Xj بیان نماییم به گونه ای که بر حسب X s بیان کرده باشیم، به صورت زیر می توان عنوان کرد:
α1Xj=PmaxXj-L , Xi-L<Xs<minXj,Xi=Pxj-l≤Xs≤xixj-lxi1σ2πe-xs-μ22σ2dxs=Pxj-l≤Xs≤xi=Pxj-l-μσ≤Xs-μσ≤xi-μσ=Pxj-l-μσ≤Z≤xi-μσ=PZ≤xi-μσ-PZ≤xj-l-μσ=Φxi-μσ-Φxj-l-μσبه طریق مشابه نیز می توان α2Xj را برای حالت Xi>Xj اثبات نمود.
حال امید فاصله بین دو نقطه i وj در حالت کلی مکان یابی با تابع احتمالی نرمال رامحاسبه می نماییم. فضا را به دو قسمت تقسیم می نماییم و برای هر کدام محاسبه می نماییم:
حالت اول: Xi<XjE3=ELbfXi,Xj=α1Xj×E1+1-α1Xj×Xi-Xj=Φxi-μσ-Φxj-l-μσ×xj-lxj+xi-l22xs+2l-xj-xixj-lxi1σ2πe-xs-μ22σ2dxs ×1σ2πe-xs-μ22σ2dxs+xj+xi-l2xixj+xi-2xsxj-lxi1σ2πe-xs-μ22σ2dxs ×1σ2πe-xs-μ22σ2dxs+1-Φxi-μσ-Φxj-l-μσ×Xi-Xjحالت دوم: Xi>XjE4=ELbfXi,Xj=α2Xj×E2+1-α2Xj×Xi-Xj=Φxj-μσ-Φxi-l-μσ×xi-lxj+xi-l22xs+2l-xj-xixi-lxj1σ2πe-xs-μ22σ2dxs ×1σ2πe-xs-μ22σ2dxs+xj+xi-l2xjxj+xi-2xsxi-lxj1σ2πe-xs-μ22σ2dxs ×1σ2πe-xs-μ22σ2dxs+1-Φxj-μσ-Φxi-l-μσ×Xi-Xj4-4 متغییر های واسط
حال با محاسبه مقادیر E3 و E4، می توانیم تابع هدف مسئله را تکمیل نماییم. اما پیش از اینکه به معرفی تابع هدف و همچنین محدودیت های مسئله بپردازیم، لازم است تا پارامتر هایی را که در مدل مورد استفاده قرار می گیرند را تعریف نماییم.
برای اینکه نشان دهیم بین دو نقطه در صفحه در جهت مخالف هم هستند یا خیر، به چهار متغییر احتیاج داریم. این متغییرها به صورت زیر تعریف می شوند:
Si=1 , yi>b0 , اینصورت غیر در ∀iZj=1 , yj>b0 , اینصورت غیر در ∀jtij=1, باشند صفحه مختلف طرف دو در j جدید تسهیل و i موجود تسهیل اگر0 , اینصورت غیر در ∀i,j
uij=1, باشند صفحه مختلف طرف دو در k جدید تسهیل و j جدید تسهیل اگر0 , اینصورت غیر در ∀j,k

Related posts:




:: بازدید از این مطلب : 236
|
امتیاز مطلب : 0
|
تعداد امتیازدهندگان : 0
|
مجموع امتیاز : 0
ن : پایان نامه ها
ت : یک شنبه 12 شهريور 1396
مطالب مرتبط با این پست
می توانید دیدگاه خود را بنویسید


(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){ (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o), m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m) })(window,document,'script','//www.google-analytics.com/analytics.js','ga'); ga('create', 'UA-52170159-2', 'auto'); ga('send', 'pageview');