عنوان پایان‌نامه
الگوریتم های بهبود یافته برای مساله مکان یابی تسهیلات سیار وبرخی گونه های دیگر مساله
- رشته تحصیلی
- مهندسی کامپیوتر- آلگوریتم ها و محاسبات
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه پردیس یک فنی شماره ثبت: 22..;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 47861
- تاریخ دفاع
- ۰۷ اسفند ۱۳۸۹
- دانشجو
- عبدالحمید قدس الهی
- استاد راهنما
- علی معینی
- چکیده
- در این پایان نامه یکی از مسائل کلیدی و محوری در مبحث تحقیق در عملیات، یعنی مساله مکان یابی تسهیلات مورد توجه قرار گرفته است. گونه استاندارد این مساله از دهه شصت میلادی مورد بررسی محققین قرار گرفته است و تاکنون تحقیقات وسیعی روی گونه های مختلف این مساله انجام گرفته و راه حل های متنوعی برای آنها ارائه شده است. محققین از تکنیک های برنامه ریزی خطی گرفته، روش های جستجوی محلی تا جستجوی های مکاشفه ای، برای حل انواع مختلف این مساله بهره گرفته اند. ما توجه خود در این پایان نامه را به گونه برخط بعضی از انواع مساله مکان یابی تسهیلات معطوف کرده ایم. در فصل 4، گونه برخط مساله مکان یابی تسهیلات سیار در حد ارائه مدل و الگوریتم مورد توجه قرار گرفته است. تمرکز اصلی این تحقیق بر روی گونه برخط مساله مکان یابی تسهیلات با اندکی تغییر نسبت به گونه استاندارد آن واقع شده است. در واقع یک سناریو در بدترین حالت برای مساله مکان یابی برخط تسهیلات مورد تحلیل قرار می دهیم. در این سناریو، یک رقیب قوی تقاضاها را در حالت برخط، یک به یک برای اخذ خدمت وارد می کند. الگوریتم رقابتی ما باید هنگام ورود یک تقاضا تصمیم بگیرد که یک تسهیل باز(موجود) را به تقاضای تازه رسیده نسبت دهد یا اینکه تسهیل جدیدی را ایجاد/بهره برداری کند. تصمیم گیری الگوریتم رقابتی باید به نحوی باشد که نسبت هزینه کل به هزینه الگوریتم بهینه مقدار قابل قبولی باشد. تقاضاهای رسیده در هر نقطه ای از گراف می توانند قرار گیرند. الگوریتم رقابتی ما هیچ اطلاع قبلی نسبت به ترتیب تقاضاهای وارد شده یا مکان قرارگیری آنها ندارد. الگوریتم رقابتی و قطعی ارائه شده برای مسائل مکان یابی تسهیلات در هر فضای متری و حالتی که تسهیلات در نقاط معینی از گراف قرار گرفته اند(مدل مکانی ثابت که پوششی عمومی برای انواع مدلهای قرارگیری تسهیلات در گراف است)، کار می کند. هزینه ایجاد/بهره برداری تسهیلات، غیر یکسان فرض می شود. نسبت هزینه کل الگوریتم رقابتی فوق به هزینه کل الگوریتم بهینه یک فاکتور لگاریتمی است.
- Abstract
- In this thesis, we consider facility location problem(FLP) that is an important and pivotal problem in the field of operations research. Standard version of this problem has studied since the early 1960's and the researchers have extended many variants of the standard version and presented many different solutions for them. They have used linear programming techniques, local search methods, and heuristics to solve the different types of FLP. We focus our attention on online version of some type of FLP. In chapter 4, online version of mobile facility location problem is considered and we present an algorithm for it. The main contribution of this thesis is presentation a general model for online facility location problem (OFLP) and a feasible solution for it. We study a worst case scenario in OFLP where an adversary adaptively brings the demands one at a time and we should decide to either open a new facility or use an existing open facility for a coming demand right when it comes. The demands arrive one at a time and can locate at any points in the region. There is no prior information on the input order and the location of the demands. Our algorithm is deterministic and competitive for the fixed location model in every metric space and general case of non-uniform facility costs. We have achieved a competitive ratio of logarithmic order.
