DOI: https://doi.org/10.1016/j.knosys.2026.115579
تاريخ النشر: 2026-02-18
المؤلف: Sergio Salazar وآخرون
الموضوع الرئيسي: تحديد مواقع المنشآت وإدارة الطوارئ
نظرة عامة
تتناول ورقة البحث مشكلة الوسيط p المحفزة مع التحديثات (IpMU)، وهي نوع معقد من مشكلة الوسيط p الكلاسيكية ضمن مشاكل تحديد مواقع المنشآت (FLPs). تفصل هذه المشكلة بشكل فريد بين تكلفة النقل والوقت كمعايير متميزة وتدمج ميزانية لتحديث حواف الرسم البياني، مما يعزز الطرق بين الوسائط والعملاء. يقترح المؤلفون خوارزمية ميتاهيرستية تعتمد على إجراء البحث العشوائي التكيفي الجشع (GRASP)، باستخدام استراتيجية حل من مرحلتين تتناول بشكل مستقل مشكلات اختيار الوسيط والتحديث. تظهر نهجهم تحسينات كبيرة في وقت التنفيذ، حيث تحقق حلولًا مثالية في أكثر من 99% من 1,230 حالة تم اختبارها، مع أداء يتجاوز نماذج البرمجة الرياضية الحالية.
تشير النتائج إلى أن الطريقة المعتمدة على GRASP لا تحقق فقط أفضل النتائج المعروفة في 1,226 حالة، ولكنها تعمل أيضًا بوقت تنفيذ مخفض بمقدار ترتيب مقارنة بالنماذج المتطورة. يدعم اختبار إحصائي بايزي فعالية الخوارزمية المقترحة، حيث يظهر احتمالًا أعلى للحصول على نتائج مثالية مقارنة بالطرق التقليدية. تستكشف الدراسة أيضًا تعقيد حالات المشكلة، كاشفة أن تلك التي تحتوي على المزيد من الأمثل المحلية تشكل تحديات أكبر. تهدف الأعمال المستقبلية إلى تحسين أداء الخوارزمية من خلال تحسينات هيوريستية وتوسيع المنهجية لتشمل مشاكل تحسين أخرى ضمن مجال FLP، مما يساهم في نهج أكثر رسمية لتحسين التوافقيات.
مقدمة
تناقش مقدمة ورقة البحث هذه أهمية مشاكل تحديد مواقع المنشآت (FLPs) في بحوث العمليات، مع تسليط الضوء على تحليلها الرياضي وتطبيقاتها العملية في سيناريوهات مثل وضع المنشآت الطبية خلال جائحة COVID-19 والموقع الاستراتيجي لمخازن الذخيرة بعد النزاع. من بين مختلف FLPs، يتم التأكيد بشكل خاص على مشاكل تحديد مواقع المنشآت الصحية (HCFLPs)، مع الإشارة إلى حالات محددة مثل مشكلة تحديد الموقع القصوى ومشكلة تحديد مواقع المنشآت المزعجة المتعددة لصلتها بإدارة الكوارث والاهتمامات البيئية.
تقدم الورقة مشكلة الوسيط p المحفزة مع التحديث (IpMU)، التي تركز على تحسين لوجستيات التجارة الإلكترونية والنقل الحضري من خلال تحديد موقع p وسائط في رسم بياني ثنائي الوزن. تفصل هذه المشكلة بشكل فريد بين وقت السفر والتكلفة، مما يسمح بتخصيص الميزانية نحو تحديث أقواس الشبكة لتقليل تكاليف السفر. يقترح المؤلفون نهجًا ميتاهيرستيًا جديدًا يعتمد على إجراء البحث العشوائي التكيفي الجشع (GRASP) لتعزيز الكفاءة الحسابية مقارنة بأساليب البرمجة الرياضية التقليدية. تظهر النتائج التجريبية فعالية الخوارزمية المقترحة، حيث تحقق حلولًا مثالية في وقت تنفيذ مخفض بشكل كبير مقارنة بالطرق المتطورة الحالية. توضح الورقة هيكلها، مشيرة إلى أن الأقسام التالية ستتناول مراجعة الأدبيات، الوصف الرسمي للمشكلة، النهج الخوارزمي، التجارب الحسابية، والاستنتاجات.
طرق
في هذا القسم، يقدم المؤلفون خوارزمية جديدة لمشكلة IpMU، بناءً على نماذج خطية متطورة وتوظيف نهج من مرحلتين يعتمد على إجراء البحث العشوائي التكيفي الجشع (GRASP). تفصل الخوارزمية بين مشكلات اختيار الوسيط وتحديث الحواف، مما يسمح بفضاء بحث توافقي يسرع من إيجاد الحلول مقارنة بأساليب المجال المستمر. يتم تعريف مشكلة تحديث الحواف من خلال إجراء سريع يعمل على تخفيف تكاليف الرسم البياني بشكل مثالي نظرًا لمجموعة من الوسائط. كما يوضح المؤلفون إعداد التجربة، بما في ذلك توليد 960 حالة عبر مجموعتين (P و R) مع معلمات متغيرة، وضبط معلمات الخوارزمية باستخدام أداة irace لتحسين الأداء.
تظهر النتائج التجريبية أن خوارزمية GRASP المقترحة تتفوق بشكل كبير على نموذج FL1 من الأدبيات، لا سيما من حيث وقت التنفيذ وجودة الحل. على سبيل المثال، تحقق GRASP حلولًا مثالية لجميع الحالات في المجموعة R مع انحراف متوسط ضئيل، بينما تواجه FL1 صعوبة مع الحالات الأكبر، وغالبًا ما تتجاوز حدود الوقت. تكشف التحليلات أن GRASP تحافظ على وقت تنفيذ ثابت عبر أحجام الحالات المتغيرة، بينما تتدهور أداء FL1 مع زيادة عدد العقد. بالإضافة إلى ذلك، يؤكد تحليل بايزي أداء GRASP المتفوق، مع احتمال أعلى لتحقيق نتائج أفضل من FL1 ومنهجية كوين-هامبورغ، التي تنتج باستمرار حلولًا أقل جودة. يختتم القسم بتحليل صعوبة الحالات، مشيرًا إلى أن العلاقة بين تكلفة النقل والوقت تؤثر على تعقيد فضاء الحل، حيث تقدم الحالات غير المرتبطة المزيد من الأمثل المحلية وبالتالي تحديات حسابية أكبر.
نقاش
في هذا القسم النقاشي، يقدم المؤلفون مراجعة شاملة لمشكلة الوسيط p المحفزة مع التحديثات (IpMU) ضمن السياق الأوسع لمشاكل تحديد مواقع المنشآت (FLPs). يصنفون FLPs إلى مشاكل أحادية المستوى ومتعددة المستويات، مع تسليط الضوء على التمييز بين التحسين المنفصل والمستمر. يؤكد المؤلفون على هيمنة طرق الحل الرياضية، مثل الفرع والحد، وظهور الأساليب الهيوريستية والميتاهيرستية، لا سيما للحالات الأكبر. بشكل ملحوظ، يحددون مشكلة تحديد مواقع المنشآت غير المحدودة (UFLP) ومشكلة تحديد مواقع المنشآت المحدودة (CFLP) كمجالات رئيسية للدراسة، مع تفضيل التطورات الأخيرة للخوارزميات التطورية الهيوريستية لتحسين الأداء على مجموعات البيانات الأكبر.
يؤكد المؤلفون أن مشكلة IpMU تدمج ميزات من كل من عائلات مشاكل الشبكة الثنائية والتحديث، حيث تركز الأدبيات الحالية بشكل أساسي على النماذج الرياضية. يقترحون نهجًا ميتاهيرستيًا جديدًا لمعالجة IpMU، يجمع بين خوارزمية جشعة لتحديث الحواف مع إجراء البحث العشوائي التكيفي الجشع (GRASP) لاختيار الوسيط. تظهر نتائجهم التجريبية أن هذا النهج يتفوق على الأساليب المتطورة، حيث يحقق حلولًا مثالية في أكثر من 99.67% من الحالات المختبرة بينما يقلل بشكل كبير من وقت التنفيذ. علاوة على ذلك، يؤكد تحليل إحصائي بايزي قوة نتائجهم، مشيرًا إلى احتمال أعلى للحصول على أفضل النتائج مقارنة بالنماذج الحالية. يستكشف المؤلفون أيضًا تعقيد حالات المشكلة، كاشفين أن تلك التي تحتوي على المزيد من الأمثل المحلية تقدم تحديات أكبر، مما قد يوجه تحسينات خوارزمية مستقبلية.
DOI: https://doi.org/10.1016/j.knosys.2026.115579
Publication Date: 2026-02-18
Author(s): Sergio Salazar et al.
Primary Topic: Facility Location and Emergency Management
Overview
The research paper addresses the Induced p-Median Problem with Upgrades (IpMU), a complex variation of the classical p-Median problem within facility location problems (FLPs). This problem uniquely separates transport cost and time as distinct metrics and incorporates a budget for upgrading graph edges, thereby enhancing routes between medians and customers. The authors propose a metaheuristic algorithm based on the Greedy Randomized Adaptive Search Procedure (GRASP), employing a two-phase resolution strategy that independently tackles the median selection and upgrading problems. Their approach demonstrates significant improvements in execution time, achieving optimal solutions in over 99% of the 1,230 tested instances, with a performance that surpasses existing mathematical programming models.
The findings indicate that the GRASP-based method not only yields the best-known results in 1,226 instances but also operates with an execution time reduced by an order of magnitude compared to state-of-the-art models. A Bayesian statistical test further supports the efficacy of the proposed algorithm, showing a higher probability of obtaining optimal results compared to traditional methods. The study also explores the complexity of the problem instances, revealing that those with more local optima pose greater challenges. Future work aims to refine the algorithm’s performance through heuristic enhancements and to extend the methodology to other optimization problems within the FLP domain, ultimately contributing to a more formalized approach to combinatorial optimization.
Introduction
The introduction of this research paper discusses the significance of Facility Location Problems (FLPs) in Operations Research, highlighting their mathematical analysis and practical applications in scenarios such as the placement of medical facilities during the COVID-19 pandemic and the strategic location of ammunition depots post-conflict. Among the various FLPs, Healthcare Facility Location Problems (HCFLPs) are particularly emphasized, with specific cases like the Maximum Covering Location Problem and the Multiple Obnoxious Facility Location Problem being noted for their relevance to disaster management and environmental concerns.
The paper introduces the Induced p-Median Problem with Upgrading (IpMU), which focuses on optimizing e-commerce logistics and urban transportation by determining the location of p medians in a dual-weight binetwork graph. This problem uniquely separates travel time and cost, allowing for budget allocation towards upgrading network arcs to minimize travel costs. The authors propose a novel metaheuristic approach based on the Greedy Randomized Adaptive Search Procedure (GRASP) to enhance computational efficiency compared to traditional mathematical programming methods. Experimental results demonstrate the effectiveness of the proposed algorithm, achieving optimal solutions in a significantly reduced execution time compared to existing state-of-the-art methods. The paper outlines its structure, indicating subsequent sections will cover literature review, formal problem description, algorithmic approach, computational experiments, and conclusions.
Methods
In this section, the authors present a novel algorithm for the IpMU problem, building on state-of-the-art linear models and employing a two-phase approach based on the Greedy Randomized Adaptive Search Procedure (GRASP). The algorithm separates the median selection and edge-upgrading problems, allowing for a combinatorial search space that accelerates solution finding compared to continuous domain methods. The edge-upgrading problem is defined through a rapid procedure that optimally relaxes graph costs given a set of medians. The authors also detail the experimental setup, including the generation of 960 instances across two sets (P and R) with varying parameters, and the tuning of algorithm parameters using the irace tool to optimize performance.
The experimental results demonstrate that the proposed GRASP algorithm significantly outperforms the FL1 model from the literature, particularly in terms of execution time and solution quality. For instance, GRASP achieves optimal solutions for all instances in set R with a negligible average deviation, while FL1 struggles with larger instances, often exceeding time limits. The analysis reveals that GRASP maintains a consistent execution time across varying instance sizes, while FL1’s performance deteriorates with increased node counts. Additionally, a Bayesian analysis confirms GRASP’s superior performance, with a higher probability of achieving better results than FL1 and the Kuehn-Hamburguer heuristic, which consistently yields poorer solutions. The section concludes with a hardness analysis of the instances, indicating that the correlation between transport cost and time affects the complexity of the solution space, with non-correlated instances presenting more local optima and thus greater computational challenges.
Discussion
In this discussion section, the authors provide a comprehensive review of the Induced p-Median Problem with Upgrades (IpMU) within the broader context of Facility Location Problems (FLPs). They categorize FLPs into unilevel and multilevel problems, highlighting the distinction between discrete and continuous optimization. The authors emphasize the predominance of mathematical resolution methods, such as Branch and Bound, and the emergence of heuristic and metaheuristic approaches, particularly for larger instances. Notably, they identify the Uncapacitated Facility Location Problem (UFLP) and the Capacitated Facility Location Problem (CFLP) as key areas of study, with recent advancements favoring heuristic evolutionary algorithms for improved performance on larger datasets.
The authors assert that the IpMU problem integrates features from both bi-network and upgrading problem families, with existing literature primarily focusing on mathematical models. They propose a novel metaheuristic approach to address the IpMU, which combines a greedy algorithm for edge upgrades with a Greedy Randomized Adaptive Search Procedure (GRASP) for median selection. Their experimental results demonstrate that this approach outperforms state-of-the-art methods, achieving optimal solutions in over 99.67% of the tested instances while significantly reducing execution time. Furthermore, a Bayesian statistical analysis confirms the robustness of their results, indicating a higher probability of obtaining the best outcomes compared to existing models. The authors also explore the complexity of problem instances, revealing that those with more local optima present greater challenges, which may inform future algorithmic improvements.