Skip to main content
SUPERVISOR
Naser MollaverdiIsfahani,Ali Shahandeh nookabadi
ناصر ملاوردي اصفهاني (استاد راهنما) علي شاهنده نوک آبادي (استاد مشاور)
 
STUDENT
Kasra Gholamrezaei
کسري غلامرضائي

FACULTY - DEPARTMENT

دانشکده مهندسی صنایع
DEGREE
Master of Science (MSc)
YEAR
1388

TITLE

Developing and solving a New Model for Set Covering Problem in Continous Space
Abstarct Facility location is one of the most important problems in strategic decisions of private firms and governmental organizations. Covering problem is one of the most useful problems in the field of facility location. In this thesis, two new models in the field of covering problems in continous space are presented. The first model is called Continous Set Covering Problem (CSCP) which is based on a continous two dimentional space instead of network space, with the aim of minimizing the number of located facilities, so that all customer points will be covered. The second model is called Continous Set Covering Problem with Demand (CSCPD) which adds customer demands and capacity of facilities suppositions to the first model, with the aim of minimizing the number of located facilities, so that the demand of all customer points will be fully covered. These two models are in the form of mixed integer nonlinear programming (MINLP). Using an innovative approximation, the models will be converted to the form of mixed integer linear programming (MILP). A three step heuristic algorithm called Compass is presented to solve the CSCP model. This heuristic algorithm is based on a theorem according to it, customer points that have a joint covering zone, are palced in distinct sets and each set is assigned one facility. The heuristic algorithm is validated by solving 20 random sample problems with different dimensions and comparing its solutions with the GAMS software solutions. Average of difference between the final goal value of heuristic algorithm and GAMS software for the sample problems with dimensions up to 50 customer points with 2650 variables including 2550 binary variables and 40100 constraints is equal to about 3% and this shows that the heuristic solutions are close to optimal solutions. Solving time for the heuristic algorithm is much less than GAMS software, so that the heuristic algorithm solves problems with dimensions up to 300 customer points with 90900 variables including 90300 binary variables and 1440600 constraints in a time duration which is about 50 seconds. Unlike the GAMS software presents only one point for each customers set, the heuristic algorithm presents several candidate point to locate the facilities, and this gives more alternatives to decision maker to choose the location points.
چکيده مکان‌يابي تسهيلات يکي از مهمترين مسائل مطرح در تصميمات استراتژيک شرکت‌هاي خصوصي و سازمان‌هاي دولتي مي‌باشد. مسئله پوشش يکي از مسائل مطرح در زمينه مکان‌يابي تسهيلات مي‌باشد. در اين پايان‌نامه دو مدل جديد در زمينه مسائل پوشش در فضاي پيوسته ارائه مي‌شود. مدل اول مسئله پوشش مجموعه پيوسته (CSCP) نام دارد که به جاي فضاي شبکه‌اي، بر روي فضاي پيوسته دو بعدي پياده‌سازي مي‌شود و هدف آن مينيمم کردن تعداد تسهيلات مستقر شده است، به طوري که تمامي نقاط مشتري پوشش داده شود. مدل دوم مسئله پوشش مجموعه پيوسته با در نظر گرفتن تقاضا (CSCPD) نام دارد که فرض تقاضاي مشتريان و ظرفيت تسهيلات را به مدل اول اضافه مي‌کند و هدف آن مينيمم کردن تعداد تسهيلات مستقر شده است، به طوري که تقاضاي تمامي نقاط مشتري به طور کامل پوشش داده شود. اين دو مدل به فرم برنامه‌ريزي غير خطي مختلط (MINLP) مي‌باشند که با يک تقريب ابتکاري به فرم برنامه‌ريزي خطي مختلط (MILP) تبديل مي‌شوند و کاهش چشميگري در زمان حل اين دو مدل با نرم‌افزار GAMS حاصل مي‌شود. يک الگوريتم ابتکاري سه مرحله‌اي به نام Compass براي حل مدل CSCP ارائه مي‌شود. اساس اين الگوريتم لمي است که بر مبناي آن نقاط مشتري که ناحيه پوشش مشترک دارند در يک دسته قرار مي‌گيرند و به هر دسته يک تسهيل اختصاص داده مي‌شود. اعتبار اين الگوريتم با حل 20 مسئله نمونه تصادفي در ابعاد مختلف و مقايسه جواب‌ آن‌‌ها با نرم‌افزار GAMS مورد سنجش قرار مي‌گيرد. جواب نهايي الگوريتم ابتکاري تا مسائلي با ابعاد 50 گره با 2650 متغير شامل 2550 متغير 0 و 1 و 40100 محدوديت، با جواب نهايي نرم‌افزار GAMS اختلافي معادل 3% دارد و اين نشان‌دهنده نزديکي جواب‌هاي الگوريتم به جواب بهينه است. زمان حل الگوريتم ابتکاري به شدت کمتر از نرم‌افزار GAMS مي‌باشد، به طوري که اين الگوريتم مسائلي تا ابعاد 300 گره با 90900 متغير شامل 90300 متغير 0 و 1 و 1440600 محدوديت را در مدت زماني معادل 50 ثانيه حل مي کند. الگوريتم ابتکاري بر خلاف نرم‌افزار GAMS که براي هر دسته از مشتريان تنها يک نقطه استقرار ارائه مي دهد، چند نقطه کانديد براي استقرار پيشنهاد مي دهد و اين امر باعث مي شود تا تصميم‌گيرنده آلترناتيوهاي بيشتري براي انتخاب داشته باشد .

ارتقاء امنیت وب با وف بومی