توصيفگر ها :
بهينەسازي تركيبياتي , الگوريتمهاي دقيق براي حل مسائل NP-سخت , رويكرد شاخەو كران , رويكرد شاخەو هزينه , برنامەريزي خطي عدد صحيح , مسئله p-مركز , مسئله p-مركز بعدي , مسئله α-همسايگي p-مركز
چكيده فارسي :
مسئله مكانيابي مركز يا p-مركز يكي از مسائل كلاسيك و كاربردي در حوزه بهينهسازي تركيبياتي و مكانيابي تسهيلات است. اين مسئله در كاربردهاي متنوعي نظير طراحي ايستگاههاي اورژانس، مكانيابي پناهگاهها، يا تعيين محلهاي توزيع كالا مورد استفاده قرار ميگيرد. هدف نسخهي كلاسيك p-مركز، انتخاب p مركز از ميان نقاط كانديد و تخصيص ساير نقاط به نزديكترين مركز است بهگونهاي كه حداكثر فاصلهي يك نقطه تقاضا تا مركز نظيرش كمينه شود. با اين حال، اين نسخه در برابر اختلالاتي مانند خرابي يا از دسترس خارجشدن يك مركز، مقاوم نيست. به همين دليل، نسخههاي مقاوم در برابر خطايي نظير p-مركز بعدي و α-همسايگي p-مركز معرفي شدهاند كه با در نظر گرفتن مراكز پشتيبان براي هر مشتري، تخصيص را در شرايط اضطراري نيز حفظ ميكنند.
تاكنون، براي حل اين مسائل، رويكردهاي دقيق و غيردقيق متعددي ارائه شدهاست. روشهاي غيردقيق مانند الگوريتمهاي ابتكاري و فراابتكاري، اغلب سريع هستند اما بهينگي جواب را تضمين نميكنند. در مقابل، روشهاي دقيق كه معمولاً بر پايه برنامهريزي خطي عدد صحيح (ILP) طراحي ميشوند، با وجود هزينه محاسباتي بيشتر، جوابهايي بهينه را برميگردانند. در اين پژوهش، با توجه بر مزيتهاي فرمولبندي مسائل در بستر برنامهريزي خطي عدد صحيح، براي هر يك از مسائل p-مركز و p-مركز بعدي، دو فرمولبندي ILP فشرده جديد ارائه شدهاست. همچنين، براي نسخهي α-همسايگي p-مركز، يك فرمولبندي ILP فشرده جديد طراحي گرديدهاست. تمامي فرمولبنديها بهصورت مستقيم توسط حلكنندههاي تجاري يا متنباز موجود قابل حل هستند. در 4 مورد از 5 فرمولبندي ارائه شده، تعداد محدوديتها نسبت به تعداد نقاط تقاضا از مرتبهي خطي است. لذا ميتوان براي حل اين فرمولبنديها از چارچوب قدرتمند شاخهوهزينه بهره گرفت. براي 3 مورد از فرمولبنديهاي ارائه شده، چند خانواده از نابرابريهاي معتبر نيز ارائه گرديده است كه بهرهگيري از آنها ميتواند فرايند حل را تسريع كند.
نتايج حاصل از شبيهسازي نشان ميدهد كه بهرهگيري از فرمولبنديهاي پيشنهادي امكان حل نمونههاي بزرگ مقياس از سه مسئله فوقالذكر را در زمان منطقي مهيا ميسازد.
چكيده انگليسي :
The facility location problem, particularly the p-center problem, is a classical and widely studied problem in combinatorial optimization. It is used in various applications such as designing emergency stations, locating shelters, or determining distribution points for products. The goal of the classic p-center problem is to select p centers from candidate points and assign each demand point to its nearest center so that the maximum distance between a demand point and its assigned center is minimized. However, this version is not robust against disruptions, such as the failure or unavailability of a center. To address this, fault-tolerant variants like the p-next center and the α-neighborhood p-center have been introduced. By considering backup centers for each customer, these variants preserve assignments even under emergency situations.
Numerous exact and heuristic approaches have been proposed to solve these problems. Heuristic methods, such as metaheuristics, are often fast but do not guarantee optimality. In contrast, exact methods, typically based on integer linear programming (ILP), provide optimal solutions despite higher computational costs. In this research, considering the advantages of ILP formulations, two new compact ILP formulations are introduced for the p-center and p-next center problems, respectively. Additionally, a new compact ILP formulation is designed for the α-neighbor p-center problem.
All formulations can be directly solved using existing commercial or open-source solvers. In four out of the five proposed formulations, the number of constraints is linear in terms of the number of demand points, making them suitable for powerful branch-and-price frameworks. For three of the proposed formulations, several families of valid inequalities are also presented, which can accelerate the solution process. Simulation results demonstrate that the proposed formulations enable solving large-scale instances of the three aforementioned problems within reasonable computation times.
