عنوان پایان‌نامه
ارزیابی الگوریتم های Facility Location
- رشته تحصیلی
- مهندسی کامپیوتر- آلگوریتم ها و محاسبات
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه پردیس یک فنی شماره ثبت: 36..;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 55219
- تاریخ دفاع
- ۲۹ بهمن ۱۳۹۰
- دانشجو
- سارا روحانی
- استاد راهنما
- علی معینی
- چکیده
- در این پژوهش انواع گونه های مسئله ی مکان یابی تسهیلات مورد پژوهش قرار گرفته است. مکان یابی تسهیلات مسئله ای است که در پنجاه سال اخیر مورد بررسی و تحقیق پژوهشگران بوده است. این مسئله در حوزه ی تحقیق در عملیات جای می گیرد و راه حل هایی چون جستجوی محلی، برنامه ریزی خطی، الگوریتم های تقریبی و الگوریتم های مکاشفه ای و انواع دیگر الگوریتم ها به آن اعمال شده است. تمرکز اصلی ما بر روی بهبود گونه ای از الگوریتم ها به نام الگوریتم حریصانه و الگوریتم حریصانه ی معکوس در این زمینه می باشد. ما الگوریتم بهبود یافته ی حریصانه معکوس را بر مسائل مکان یابی تسهیلات استاندارد و k میانه اعمال کرده ایم. در الگوریتم حریصانه ی معکوس پارامتر تصمیم گیری حریصانه را تغییر داده ایم. در الگوریتم جدید سعی در ساختن پارامتر حریصانه ی جدید بر اساس فواصل و هزینه های متوسط و به دست آوردن ضریبی برای میزان اشتراک هر تقاضا در هزینه ها و تصمیم گیری بر این اساس داشته ایم. در هر دوی این مسائل نتایج آزمایشات را در گروه های تصادفی که بر اساس انحراف معیار هزینه ی راس ها و یال ها دسته بندی شده اند، ارائه کرده ایم. اگر انحراف از معیار کم باشد، جواب به جواب بهینه نزدیک است. با زیاد شدن انحراف معیار از جواب بهینه دور می شویم. در هر دو مورد زمان انجام الگوریتم نسبت به نمونه ی قبلی خود بهبود یافته است و با انتخاب آرایش مناسبی در برخی پارامترهای مسئله و توزیع های یکنواخت لطمه ای به جواب ها نرسیده است. همچنین نوعی از مسئله به نام k تقاضا که تا کنون بررسی نشده است، پیشنهاد داده ایم و الگوریتم حریصانه ی مستقیم با ساختن پارامتر متوسط را بر آن اعمال کرده ایم. علاوه بر این به تحلیل مسئله ی مکان یابی تسهیلات وزن دار پرداخته ایم و ثابت کرده ایم که سخت تر از مسئله ی مکان یابی تسهیلات استاندارد نیست. در آخر با مدل سازی و بررسی نمونه ی واقعی مراکز آتش نشانی در منطقه ای از شهر تهران میزان بهینگی آن را اندازه گرفته ایم که نزدیک 5/1 برابر مقدار بهینه می باشد.
- Abstract
- In this thesis different variants of Facility Location Problem (FLP) has been investigated. FLP as a subject of the field of Operation Research has been studied widely in recent fifteen years by researchers. Many approaches have been applied to FLP, such as: Local Search, Linear Programming, Approximation Algorithms, Heuristic Algorithms and many others. Our focus is on improvement of Greedy Algorithms and reverse Greedy Algorithms for FLP. We have applied the improved Reverse Greedy Algorithm on FLP and K-Median Problem. In Reverse Greedy Algorithm, we have changed the greedy decision parameter. In our new algorithm, we have tried to determine the greedy decision parameter according to average service costs and distances, and make decision according to the coefficient of the part of any request in whole costs. In both problems, we have presented the results of our tests in the groups, classified by the standard deviation of the cost of nodes and edges. In groups with lower standard deviation, the results are near to optimal solution. The growth in standard deviation causes the difference between results and optimal solution. In both problems, the time of running the algorithms has got better than the previous version. Because of our good choice in proper parameters, in uniform distributions the results are good. We have proposed a problem named K-Request that has never been studied before. We have applied the Greedy Algorithm with average parameter on it. We have studied the Weighted FLP and proved that it is as difficult as Standard FLP. We have studied and modeled a fire station in a region of Tehran, and measured its optimality. In our results, it was 1.5 times the optimal.
