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 که برای هر دسته از مشتریان تنها یک نقطه استقرار ارائه می دهد، چند نقطه کاندید برای استقرار پیشنهاد می دهد و این امر باعث می شود تا تصمیم‌گیرنده آلترناتیوهای بیشتری برای انتخاب داشته باشد .

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