فرمول بندي برنامه ريزي خطي عدد صحيح براي مسئله ي p- مركز و دو نسخه ي مقاوم در برابر خطا از آن

اصفهان : دانشگاه صنعتي اصفهان

كامپيوتر

كارشناسي ارشد

مسئله مكان‌يابي مركز يا p-مركز يكي از مسائل كلاسيك و كاربردي در حوزه بهينه‌سازي تركيبياتي و مكان‌يابي تسهيلات است. اين مسئله در كاربردهاي متنوعي نظير طراحي ايستگاه‌هاي اورژانس، مكان‌يابي پناهگاه‌ها، يا تعيين محل‌هاي توزيع كالا مورد استفاده قرار مي‌گيرد. هدف نسخه‌ي كلاسيك p-مركز، انتخاب p مركز از ميان نقاط كانديد و تخصيص ساير نقاط به نزديك‌ترين مركز است به‌گونه‌اي كه حداكثر فاصله‌ي يك نقطه تقاضا تا مركز نظيرش كمينه شود. با اين حال، اين نسخه در برابر اختلالاتي مانند خرابي يا از دسترس خارج‌شدن يك مركز، مقاوم نيست. به همين دليل، نسخه‌هاي مقاوم در برابر خطايي نظير p-مركز بعدي و α-همسايگي p-مركز معرفي شده‌اند كه با در نظر گرفتن مراكز پشتيبان براي هر مشتري، تخصيص را در شرايط اضطراري نيز حفظ مي‌كنند. تاكنون، براي حل اين مسائل، رويكردهاي دقيق و غيردقيق متعددي ارائه شده‌است. روش‌هاي غيردقيق مانند الگوريتم‌هاي ابتكاري و فراابتكاري، اغلب سريع هستند اما بهينگي جواب را تضمين نمي‌كنند. در مقابل، روش‌هاي دقيق كه معمولاً بر پايه برنامه‌ريزي خطي عدد صحيح (ILP) طراحي مي‌شوند، با وجود هزينه محاسباتي بيشتر، جواب‌هايي بهينه را برمي‌گردانند. در اين پژوهش، با توجه بر مزيت‌هاي فرمول‌بندي مسائل در بستر برنامه‌ريزي خطي عدد صحيح، براي هر يك از مسائل p-مركز و p-مركز بعدي، دو فرمول‌بندي ILP فشرده جديد ارائه شده‌است. همچنين، براي نسخه‌ي α-همسايگي p-مركز، يك فرمول‌بندي ILP فشرده جديد طراحي گرديده‌است. تمامي فرمول‌بندي‌ها به‌صورت مستقيم توسط حل‌كننده‌هاي تجاري يا متن‌باز موجود قابل حل هستند. در 4 مورد از 5 فرمول‌بندي ارائه شده، تعداد محدوديت‌ها نسبت به تعداد نقاط تقاضا از مرتبه‌ي خطي است. لذا مي‌توان براي حل اين فرمول‌بندي‌ها از چارچوب قدرتمند شاخه‌و‌هزينه بهره گرفت. براي 3 مورد از فرمول‌بندي‌هاي ارائه شده، چند خانواده از نابرابري‌هاي معتبر نيز ارائه گرديده است كه بهره‌گيري از آنها مي‌تواند فرايند حل را تسريع كند. نتايج حاصل از شبيه‌سازي نشان مي‌دهد كه بهره‌گيري از فرمول‌بندي‌هاي پيشنهادي امكان حل نمونه‌هاي بزرگ مقياس از سه مسئله فوق‌الذكر را در زمان منطقي مهيا مي‌سازد.

236912

نرم افزار

مهندسي برق و كامپيوتر

دانشگاه صنعتي اصفهان