مساله مکانیابی تک‌وسیله ای با فاصله متعامد در حضور سه مانع خطی احتمالی
131 صفحه در قالب word
چکیده
در بسیاری از مسایل مکانیابی ضروریست که محدودیت‌های دنیای واقعی در نظر گرفته شوند. نواحی با مانع نمونه‌ای از این محدودیت‌ها هستند. در این نواحی، علاوه بر جایگذاری تسهیلات، حرکت نیز ممنوع است. در این پایاننامه، مساله مکانیابی تک‌وسیله‌ای را در حضور سه مانع خطی که در مسیرهای افقی بهطور یکنواخت توزیع شده‌اند، در نظر می‌گیریم. یک مدل برنامه‌ریزی غیرخطی ارایه میکنیم که مجموع کل فواصل متعامد با مانع انتظاری تسهیل جدید از تسهیلات موجود را کمینه می‌کند. همچنین، به منظور حل مسایل توسعه یافته، دو الگوریتم جستجوی الگو و ژنتیک ارایه و نتایج بدست آمده از آنها را مقایسه میکنیم. نتایج محاسباتی نشان میدهند که الگوریتم جستجوی الگو نسبت به الگوریتم ژنتیک، در زمانی کمتر به جواب مطلوبتری دست مییابد.
کلمات کلیدی: مکانیابی تک‌وسیله‌ای ، مانع احتمالی خطی، مساله میانه متعامد.
فهرست مطالب
فصل اول: کلیات پژوهش و ساختار پایاننامه. 1
فصل دوم: مروری بر ادبیات موضوع مسایل مکانیابی با مانع.. 6
2 – 2 مسایل مکان یابی با مانع.. 8
فصل سوم: زمینههای علمی پژوهش.... 14
3 – 2 دسته بندی مسایل مکانیابی.. 18
3 – 3 فواصل در مسایل برنامه‌ریزی تسهیلات... 20
3 – 3 – 1 فاصله متعامد یا منهتن.. 20
3 – 3 – 2 فاصله خط‌مستقیم یا اقلیدسی.. 21
3 – 3 – 3 فاصله مجذور خط‌مستقیم یا اقلیدسی.. 22
3 – 4 الگوریتمهای جستجوی مستقیم. 24
3 – 4 – 1 الگوریتم جستجوی الگو. 24
3 – 4 – 1 – 1 الگوریتم جستجوی الگوی هوک و جیوز. 27
3 – 4 – 2 الگوریتم ژنتیک... 33
3 – 4 – 2 - 1 مفاهیم کلیدی الگوریتم ژنتیک... 34
فصل چهارم: ارایه مدل ریاضی و الگوریتمهای پیشنهادی.. 43
4 – 2 – 1 محاسبه فاصله انتظاری.. 48
4 – 2 - 1 – 2 اختلاف ناحیههای X و ... 51
4 – 2 - 1 – 3 محاسبه فاصله افقی مورد انتظار در حالت . 53
4 – 2 - 1 – 4 محاسبه فاصله افقی مورد انتظار در حالت . 61
4 – 3 کران‌های بالا و پایین مساله مکانیابی با مانع.. 98
4 – 3 – 1 کران‌های پایین مساله. 98
4 – 3 – 2 کران‌های بالای مساله. 99
4 – 4 – 1 الگوریتم جستجوی الگوی هوک و جیوز. 101
4 – 4 – 1 – 2 جستجوی اکتشافی.. 102
4 – 4 – 1 – 3 معیار توقف... 102
4 – 4 – 2 الگوریتم ژنتیک... 102
4 – 4 – 2 – 1 نمایش کروموزوم. 103
4 – 4 – 2 – 5 نخبه گرایی.. 105
4 – 4 – 2 – 6 عملگر تقاطع.. 105
4 – 4 – 2 – 7 عملگر جهش.... 105
4 – 4 – 2 – 8 معیار توقف... 106
4 – 4 – 4 نتایج محاسباتی.. 108
فصل پنجم: نتیجهگیری و پیشنهادهایی برای پژوهشهای آتی.. 112
5 - 2 پیشنهادهایی برای پژوهشهای آتی.. 113
فهرست مراجع.. 115
فهرست مراجع فارسی.. 116
فهرست مراجع لاتین.. 117
1 – 1 مقدمه
در مدیریت، اقتصاد، برنامه‌ریزی تولید، طراحی سیستم‌های صنعتی و غیره، به جوانب مختلفی برمی‌خوریم که مستلزم تصمیمات مکانیابی هستند. علاوه بر کاربردهای عملی این نظریه در اتخاذ تصمیمات بهینه، نظریه مکانیابی بخش جذاب و چالش برانگیزی از ریاضیات، با مجموعه‌ای رو به فزونی از مسایل است که الزاما خاستگاهی در دنیای واقعی ندارند. [1]
واژه مکانیابی بر مدلسازی و حل مسایلی اشاره دارد که به دنبال یافتن بهترین مکان برای استقرار مراکز و تسهیلات هستند. به عبارت دیگر، مکانیابی عبارتست از انتخاب جایی برای تسهیلات جدید، بهطوریکه هزینه تولید و توزیع کالا و خدمات کمینه شود.
سال 1909 را اغلب سال تولد نظریه مکانیابی می‌دانند. آلفرد وبر یکی از نظریهپردازهایی بود که در آن سال به ارایه نظریهای در زمینه مکانیابی و کمینه سازی هزینه‌ها پرداخت [2]. هزینه هایی که او در نظر گرفته بود، عمدتاً از نوع هزینه‌های حملونقل بودند.
بعدها طیف گسترده‌ای از انواع مسایل مکانیابی متناسب با اهداف پژوهش و با توجه به شرایط متفاوت موجود در فضای مساله مطرح شدند. چند نوع از مسایلی که در ادبیات مکانیابی پیوسته مطرح شدند عبارتند از مساله میانه[1]، مساله مرکز[2] و مساله مرکز- میانه[3].
در مساله میانه، هدف قرار دادن یک تسهیل جدید در صفحه است بهطوریکه مجموع کل هزینه انتقال بین تسهیل جدید و تسهیلات موجود کمینه شود.
از طرفی تقریبا در همه‌ی موقعیت‌های دنیای واقعی با انواع محدودیت‌ها و الزامها مواجه هستیم. در مدلسازی مکانیابی محدودیت‌ها میتوانند نواحی ممنوعه[4] باشند، یعنی نواحی‌ای که قراردادن تسهیلات در آنها ممنوع، اما حمل و نقل در آنها آزاد است. پارک‌ها و سایر مناطق حفاظت شده، یا نواحی‌ای که ویژگی های جغرافیاییشان، مانند شیب تند، ساخت تسهیلات مطلوب را در آنها ناممکن می‌کند، مثال هایی از نواحی ممنوعه هستند.
همچنین اغلب نواحی‌ای وجود دارند که نه تنها قراردادن تسهیل جدید در آنها ممنوع است، بلکه حرکت در آنها هم مستلزم هزینه بیشتری است، مانند دریاچه‌هایی که با قایق می‌توان از آنها عبور کرد. این نواحی را نواحی متراکم[5] گویند.
علاوه بر این، در بسیاری مناطق حرکت نیز کاملا ممنوع یا ناممکن است. این مناطق را مانع[6] می‌نامیم. مناطق نظامی، کوهستان‌ها، دریاچه‌ها، رودخانه‌های بزرگ، بزرگراه‌ها، یا در مقیاسی کوچکتر، مناطقی که در سطح یک کارخانه با ماشین‌های حجیم و نقاله‌های حمل مواد اشغال شده‌اند، نمونه‌هایی از موانع هستند. بدون در نظر گرفتن این موانع، نمی‌توان ادعا کرد که مدلسازی واقع بینانه‌ای انجام شده است.
مطلب قابل توجه دیگر اینست که مکان قرارگیری موانع میتواند بهصورت تصادفی باشد مانند یک واگن حمل مواد که در هر لحظه ممکن است در هرجایی از مسیرش در فضای کارخانه قرار گرفته باشد. تصادف‌ها یا ساخت‌و‌ساز و تعمیرات برنامه‌ریزی نشده خیابان‌های یک شهر که باعث انحراف و تاخیر در شبکه حملونقل میشوند، نمونه‌های دیگری از موانع احتمالی هستند. این حالت در سایر زمینههای پژوهشی، از جمله دانش روباتیک، مورد توجه است، زیرا در طراحی روبات‌ها لازم است به قابلیت آنها در اجتناب از تصادف با موانعی که احتمال می‌رود در مسیرشان قرار داشته باشند، اندیشیده شود.
ما در این پایاننامه مفهوم موانع احتمالی در نظریه مکانیابی توجه میکنیم ، و به مدلسازی ریاضی مساله‌ای میپردازیم که در آن سه مانع خطی احتمالی که مسیر حرکتشان بهصورت افقی است، در صفحه موجودند. در مساله‌ی مورد بررسی، مفروضات زیر در نظر گرفته شده‌اند:
- در مساله مکانیابی میانه مورد بررسی ظرفیت تسهیل جدید برای خدمت‌دهی به تسهیلات موجود نامحدود است.
- در مدلسازی این مساله از متر متعامد برای تعیین فواصل استفاده می‌شود.
- مساله برای کل افق برنامه‌ریزی در ابتدای دوره، سیاست‌گذاری می‌کند، یعنی مساله مکانیابی ایستا است.
- هر تسهیل موجود دارای مکان ثابت با مختصات معین، قطعی و دارای وزنی نامنفی است.
- سه مانع با طول محدود در صفحه موجودند که از عرض آنها نسبت به طولشان صرف نظر شده است و بهصورت خط راست مدلسازی میشوند.
- موانع بر روی مسیرهای افقی با مختص y معین قرار دارند.
- مکان شروع موانع از توزیع یکنواخت با پارامترهای معین پیروی می‌کنند.
- تسهیلات موجود در مسیر موانع مستقر نیستند.
- تسهیل جدید نمیتواند در مسیر موانع قرار گیرد.
- تنها تسهیل جدید با تسهیلات موجود در تعامل است.
در ادامه، در فصل 2 ادبیات موضوع مسایل با مانع را بررسی میکنیم. در فصل 3، زمینههای علمی پژوهش تشریح میشوند. در فصل 4، به تشریح مساله و مدل پیشنهادی میپردازیم و در ادامه دو الگوریتم جستجوی الگو و ژنتیک برای حل مسایل مورد بررسی معرفی میکنیم. سپس، به مقایسه نتایج حاصل از آنها میپردازیم. سرانجام، پیشنهادهایی برای پژوهشهای آتی به همراه نتیجه گیری در فصل 5 ارایه میشوند.
چون فقط تکه هایی از متن برای نمونه در این صفحه درج شده است ممکن است هنگام انتقال از فایل اصلی به داخل سایت بعضی متون به هم بریزد یا بعضی نمادها و اشکال درج نشود، ولی در فایل دانلودی همه چیز مرتب و کامل می‌باشد.
متن کامل با فرمت word را که قابل ویرایش و کپی کردن می باشد، می توانید در ادامه تهیه و دانلود نمائید.
مساله مکانیابی تک‌وسیله ای با فاصله متعامد در حضور سه مانع خطی احتمالی