2025-11-24T14:52:17.958368

FORWARD: A Feasible Radial Reconfiguration Algorithm for Multi-Source Distribution Networks

Gallart, Bent, Kia

This paper considers an optimal radial reconfiguration problem in multi-source distribution networks, where the goal is to find a radial configuration that minimizes quadratic distribution costs while ensuring all sink demands are met. This problem arises in critical infrastructure systems such as power distribution, water networks, and gas distribution, where radial configurations are essential for operational safety and efficiency. Optimal solution for this problem is known to be NP-hard. In this paper, we prove further that constructing a feasible radial distribution configuration is weakly NP-complete, making exact solution methods computationally intractable for large-scale networks. We propose FORWARD (Feasibility Oriented Random-Walk Inspired Algorithm for Radial Reconfiguration in Distribution Networks), a polynomial-time algorithm that leverages graph-theoretic decomposition and random walk principles to construct feasible radial configurations. Our approach introduces novel techniques including strategic graph partitioning at articulation points, dual graph condensation to address greedy shortsightedness, and capacity-aware edge swapping for infeasibility resolution. We provide rigorous theoretical analysis proving feasibility guarantees and establish a compositional framework enabling parallel processing while preserving optimality properties. Comprehensive numerical evaluation on networks ranging from IEEE standard test systems to 400-node small-world networks demonstrates that FORWARD consistently outperforms commercial MINLP solvers, achieving optimal or near-optimal solutions in seconds where traditional methods require hours or fail entirely. The algorithm's polynomial-time complexity and scalability make it particularly suitable for real-time distribution network management and as an effective initialization strategy for iterative optimization solvers.

academic

FORWARD: خوارزمية إعادة تكوين شعاعية قابلة للتنفيذ للشبكات الموزعة متعددة المصادر

المعلومات الأساسية

معرّف الورقة: 2510.08785
العنوان: FORWARD: A Feasible Radial Reconfiguration Algorithm for Multi-Source Distribution Networks
المؤلفون: Joan Vendrell Gallart (جامعة كاليفورنيا، إيرفاين)، Russell Bent (مختبر لوس ألاموس الوطني)، Solmaz Kia (جامعة كاليفورنيا، إيرفاين)
التصنيف: math.OC (التحسين والتحكم)
تاريخ النشر/المؤتمر: تم تقديمها إلى arXiv في 9 أكتوبر 2025، نسخة أولية منشورة في مؤتمر التحكم الأمريكي 2025
رابط الورقة: https://arxiv.org/abs/2510.08785v1

الملخص

تبحث هذه الورقة عن مشكلة إعادة التكوين الشعاعي الأمثل في الشبكات الموزعة متعددة المصادر، بهدف إيجاد تكوين شعاعي يقلل من تكاليف التوزيع التربيعية مع تلبية احتياجات جميع عقد الاستهلاك. تظهر هذه المشكلة في أنظمة البنية التحتية الحرجة مثل توزيع الكهرباء وشبكات المياه وتوزيع الغاز الطبيعي، حيث يكون التكوين الشعاعي ضروريًا لسلامة التشغيل والكفاءة. يثبت المؤلفون أن بناء تكوين توزيع شعاعي قابل للتنفيذ هو مشكلة NP كاملة ضعيفة، ويقترحون خوارزمية FORWARD - وهي خوارزمية زمن متعدد الحدود تستخدم تحليل نظرية الرسوم البيانية ومبادئ المشي العشوائي لبناء تكوينات شعاعية قابلة للتنفيذ. تُظهر التقييمات العددية الشاملة على أنظمة الاختبار القياسية IEEE وحتى شبكات صغيرة العالم بـ 400 عقدة أن FORWARD يتفوق باستمرار على حلول MINLP التجارية، حيث يحصل على حلول مثلى أو قريبة من المثلى في ثوانٍ قليلة في الحالات التي تتطلب فيها الطرق التقليدية ساعات أو تفشل تمامًا.

الخلفية البحثية والدافع

تعريف المشكلة

المشكلة الأساسية التي تعالجها هذه الورقة هي مشكلة إعادة التكوين الشعاعي الأمثل في الشبكات الموزعة متعددة المصادر. بشكل محدد، بالنظر إلى شبكة توزيع تحتوي على عقد مصادر متعددة وعقد استهلاك، يجب إيجاد تكوين شعاعي (هيكل شجري بدون حلقات) بحيث:

تلبية احتياجات جميع عقد الاستهلاك
تقليل تكاليف التوزيع التربيعية في الشبكة
الامتثال لقيود السعة

أهمية المشكلة

تتمتع هذه المشكلة بأهمية كبيرة في عدة مجالات للبنية التحتية الحرجة:

الأنظمة الكهربائية: يضمن التكوين الشعاعي استقرار النظام والتشغيل الآمن، مع تقليل خسائر الطاقة
شبكات المياه: ضمان سلامة وكفاءة إمدادات المياه
توزيع الغاز الطبيعي: ضمان النقل الآمن والتحكم في التكاليف

قيود الطرق الموجودة

تعاني الطرق التقليدية بشكل أساسي من المشاكل التالية:

التعقيد الحسابي العالي: تنمو أوقات الحساب لطرق MINLP بشكل أسي على الشبكات الكبيرة
قابلية التوسع الضعيفة: غالبًا ما تفشل الحلول التجارية عند التعامل مع شبكات بـ 400+ عقدة
عدم كفاية الوقت الفعلي: لا يمكن تلبية متطلبات إدارة الشبكة في الوقت الفعلي
صعوبة التهيئة: يصعب على الطرق الاستكشافية إيجاد نقطة ابتدائية داخل المنطقة القابلة للتنفيذ

الدافع البحثي

ينبع الدافع البحثي للمؤلفين من:

إثبات التعقيد الحسابي لمشكلة بناء الحل القابل للتنفيذ (NP كاملة ضعيفة)
تطوير خوارزمية يمكنها إيجاد حل قابل للتنفيذ في زمن متعدد الحدود
توفير حل فعال مناسب لإدارة الشبكة في الوقت الفعلي

المساهمات الأساسية

المساهمة النظرية: إثبات أول مرة أن بناء تكوين شعاعي قابل للتنفيذ في شبكات موزعة متعددة المصادر هو مشكلة NP كاملة ضعيفة، مما يوفر أساسًا نظريًا لصعوبة الحساب لهذه المشكلة
الابتكار الخوارزمي: اقتراح خوارزمية FORWARD بتعقيد زمني متعدد الحدود O(n²log n)، تتضمن خمسة مكونات أساسية:
- المعالج المسبق (Pre-Processor): تبسيط هيكل الشبكة
- عازل الجزر (Islander): تحليل الرسم البياني والمعالجة المتوازية
- محكم الشبكة (Net-Concad): تقنية تكثيف الرسم البياني الثنائي
- أداة الأخذ (Sampler): أخذ العينات من الحواف بناءً على الأوزان
- إعادة الأسلاك (Rewire): تبديل الحواف مع الوعي بالسعة
الإطار النظري: إنشاء نظرية الجدوى التوليفية (النظرية 5) ونتيجة الحفاظ على الأمثلية (النتيجة 6)، مما يثبت صحة طريقة تحليل الرسم البياني من الناحية النظرية
اختراق الأداء: تفوق ملحوظ على حلول MINLP التجارية في اختبارات الشبكات الكبيرة، حيث يحصل على حلول في ثوانٍ قليلة في الحالات التي تفشل فيها الطرق التقليدية أو تتطلب ساعات

شرح الطريقة

تعريف المهمة

بالنظر إلى شبكة التوزيع GD = G(VD, ED)، حيث:

المدخلات: N عقدة، m حافة، ng مجموعة عقد مصادر Vg، nc مجموعة عقد استهلاك Vc
القيود: متجه الإدخال g، متجه الإخراج d، قيود السعة x̄، مع تحقيق ∑gi = ∑di
المخرجات: تكوين شعاعي S وتوزيع تدفق x، يقلل من دالة الهدف:

$\min \sum_{(i,j) \in S} C_{i,j} \cdot x_{i,j}^2$

تحت القيود:

G(VD,S) ∈ F (قيد التكوين الشعاعي)
0 ≤ x(S) ≤ x̄(S) (قيد السعة)
A(S)x(S) = g - d (قيد حفظ التدفق)

معمارية النموذج

1. مكون المعالج المسبق

الوظيفة: تحديد ومعالجة العقد المعلقة في الشبكة
الخوارزمية: معالجة تكرارية للعقد بدرجة 1، نقل احتياجاتها/إمداداتها للعقدة الأب
التعقيد: O(n + m)
المخرجات: الرسم البياني الفرعي 2-core GP ومجموعة الحواف المأخوذة S

2. مكون عازل الجزر

الوظيفة: تحليل الرسم البياني الفرعي 2-core عند نقاط المفاصل
الاستراتيجية: التقسيم فقط عند نقاط المفاصل المصدرية، مما يقلل التعقيد الحسابي
التوازن: تعديل قيم العقد المنفصلة لضمان توازن الإدخال والإخراج لكل رسم بياني فرعي
المخرجات: L رسم بياني فرعي متوازن {G1, G2, ..., GL}

3. مكون محكم الشبكة

الوظيفة: تكثيف الرسم البياني الثنائي، حل مشكلة قصر النظر في الخوارزمية الجشعة
الطريقة:
- دمج الأشجار المتعددة المأخوذة في عقدة "مأخوذة" فائقة
- دمج المكونات المتصلة غير المأخوذة في عقدة "غير مأخوذة" فائقة
- بناء هيكل شبه ثنائي الرسم البياني Ḡℓ

4. مكون أداة الأخذ

الوظيفة: اختيار الحواف المثلى للأخذ بناءً على الأوزان
دالة الوزن: wi,j = pi/(Ri,j · d²j + f̂(Ri_k))
الأولويات:
1. عقد فائقة معلقة غير مأخوذة
2. حواف بسعة كافية
3. ترتيب تنازلي للأوزان

5. مكون إعادة الأسلاك

الوظيفة: حل عدم الجدوى الناجم عن قيود السعة من خلال تبديل الحواف
الاستراتيجية:
- تحديد العقد غير المزودة ومسارات الإمداد الزائد
- تنفيذ تبديل حواف استراتيجي
- الحفاظ على الهيكل الشعاعي

نقاط الابتكار التقني

1. نظرية تحليل الرسم البياني

الابتكار: إثبات نظرية الجدوى التوليفية، إنشاء علاقة تكافؤ بين المشكلة الأصلية والمشاكل الفرعية المحللة المزايا: دعم المعالجة المتوازية مع الحفاظ على الأمثلية

2. تقنية تكثيف الرسم البياني الثنائي

الابتكار: تحل دالة Net-Concad مشكلة قصر النظر في الاختيار الجشع من خلال بناء هيكل شبه ثنائي الرسم البياني الآلية: تحويل مشكلة معقدة متعددة المصادر والمصارف إلى مشكلة اتصال أبسط بين العقد الفائقة

3. تبديل الحواف مع الوعي بالسعة

الابتكار: تحل دالة Rewire اختناقات السعة من خلال تبديل حواف استراتيجي المبدأ: إعادة توزيع التدفق من مناطق الإمداد الزائد إلى العقد غير المزودة، دون الحاجة إلى موارد توليد إضافية

إعداد التجارب

مجموعات البيانات

أنظمة الاختبار القياسية IEEE:

IEEE 13 (عقدتا مصدر)
IEEE 18 (عقدتا مصدر)
IEEE 33 (ثلاث عقد مصادر)

شبكات صغيرة العالم:

WS 120 (10 عقد مصادر)
WS 240 (10 عقد مصادر)
WS 400 (20 عقدة مصدر)

مؤشرات التقييم

خسائر الطاقة: بوحدة الكيلوواط (kW)
وقت الحساب: وقت تنفيذ وحدة المعالجة المركزية (ثانية)
الجدوى: ما إذا تم إيجاد حل قابل للتنفيذ

طرق المقارنة

Knitro: حل MINLP تجاري من شركة Artelys
طريقة MINLP التقليدية: خوارزميات دقيقة مثل فرع وحد

تفاصيل التنفيذ

المنصة: MacBook Air M3، 24GB RAM
لغة البرمجة: Julia
الإطار: PowerDistributionModel (PMD)
حد المهلة الزمنية: إعداد انتهاء المهلة 3 ساعات

نتائج التجارب

النتائج الرئيسية

الشبكة	خسائر Knitro (kW)	وقت Knitro (ثانية)	خسائر FORWARD (kW)	وقت FORWARD (ثانية)
IEEE 13	360.183	4.189	360.183	0.033
IEEE 18	175.821	123.416	175.821	0.229
IEEE 33	318.568	3,345.67*	919.783	0.066
WS 120	TL	TL	1,428.72	0.361
WS 240	TL	TL	4,393.17	1.016
WS 400	TL	TL	28,345.7	3.090

*يشير إلى الإنهاء اليدوي، TL يشير إلى انتهاء المهلة الزمنية بدون حل

تحليل الأداء

1. الكفاءة الحسابية

الشبكات الصغيرة: FORWARD أسرع من Knitro بـ 100-500 مرة
الشبكات الكبيرة: فشل Knitro تمامًا، أكمل FORWARD شبكة بـ 400 عقدة في 3 ثوانٍ

2. جودة الحل

الأمثلية: تحقيق الحل الأمثل على IEEE 13 و 18
التقريب: توفير حلول تقريبية معقولة على الشبكات الكبيرة

3. قابلية التوسع

النمو الخطي: ينمو وقت الحساب بشكل تقريبي خطي مع حجم الشبكة
كفاءة الذاكرة: تعقيد المساحة متعدد الحدود

النتائج التجريبية

قيود الطرق التقليدية: غالبًا ما يفشل التهيئة الاستكشافية للحلول التجارية على الشبكات الكبيرة
فعالية الأوزان المدركة فيزيائيًا: تحسن دالة الوزن بناءً على الخصائص الكهربائية (الصيغة 2) جودة الحل بشكل كبير
مزايا المعالجة المتوازية: تحقق استراتيجية تحليل الرسم البياني معالجة متوازية فعالة

الأعمال ذات الصلة

الاتجاهات البحثية الرئيسية

1. طرق التجميع الطيفي

الأعمال الممثلة: [19]29 استخدام التجميع الطيفي متبوعًا بالبحث الجشع المحلي
القيود: افتقار إلى ضمانات الجدوى، كفاءة برامج الإصلاح منخفضة

2. طرق التدفق الأقصى

الأساس النظري: بناءً على خوارزمية Ford-Fulkerson 17
المشكلة: تحويل القيد الشعاعي للمشكلة إلى NP صعبة

3. طرق الشجرة الممتدة الدنيا

الطريقة التقليدية: خوارزميات Kruskal و Prim
القيود: فقدان الأمثلية في الحالات متعددة المصادر، MSF ليست بالضرورة مجموعة فرعية من MST

مزايا هذه الورقة

الضمانات النظرية: توفير إثبات صارم للجدوى
تعقيد متعدد الحدود: تعقيد زمني O(n²log n)
الجدوى العملية: مناسبة لإدارة الشبكة في الوقت الفعلي

الخلاصة والمناقشة

الاستنتاجات الرئيسية

المساهمة النظرية: إثبات أول مرة أن بناء تكوين شعاعي قابل للتنفيذ هو مشكلة NP كاملة ضعيفة
اختراق الخوارزمية: تحقيق خوارزمية FORWARD لبناء حل قابل للتنفيذ في زمن متعدد الحدود
القيمة العملية: تفوق ملحوظ على الطرق الموجودة على الشبكات الكبيرة

القيود

نموذج التكلفة: ينطبق فقط على دوال التكلفة التربيعية
طوبولوجيا الشبكة: مصممة بشكل أساسي للشبكات الموزعة الخفيفة
فجوة الأمثلية: افتقار إلى تحليل نظري لفجوة الأمثلية

الاتجاهات المستقبلية

القيود غير الخطية: التوسع إلى نماذج قيود فيزيائية أكثر تعقيدًا
تحليل الأمثلية: توصيف رسمي لفجوة الأمثلية
توسيع التطبيقات: التوسع إلى مشاكل تحسين الشبكات الأخرى مثل الاتصالات وسلسلة الإمداد

التقييم المتعمق

المزايا

1. ابتكار الطريقة

العمق النظري: يملأ إثبات اكتمال NP الضعيف فراغًا نظريًا
تصميم الخوارزمية: معمارية المكونات الخمسة مصممة بدقة، كل منها يؤدي دوره
الاختراق التقني: تحل تقنية تكثيف الرسم البياني الثنائي بفعالية العيب الكامن في الخوارزمية الجشعة

2. كفاية التجارب

تنوع مجموعات البيانات: تغطي أنظمة الاختبار القياسية والشبكات المولدة عشوائيًا
نطاق الحجم الواسع: اختبار شامل من 13 عقدة إلى 400 عقدة
عدالة المقارنة: المقارنة المباشرة مع الحلول التجارية لها قوة إقناع

3. الصرامة النظرية

إثبات كامل: جميع النظريات لها إثبات رياضي صارم
تحليل التعقيد: تحليل تفصيلي لتعقيد الوقت
ضمان الجدوى: ضمان نظري لصحة الخوارزمية

أوجه القصور

1. قيود الطريقة

تقيد دالة التكلفة: ينطبق فقط على التكاليف التربيعية، مما يحد من نطاق التطبيق
افتراضات الشبكة: قد لا تنطبق افتراضات الشبكة الخفيفة على جميع السيناريوهات العملية
معالجة السعة: قد يؤثر تعقيد مكون Rewire على التطبيقات الكبيرة

2. إعداد التجارب

طرق المقارنة الفردية: المقارنة بشكل أساسي مع Knitro، افتقار إلى المقارنة مع طرق استكشافية أخرى
حساسية المعاملات: افتقار إلى تحليل حساسية معاملات الخوارزمية
الدلالة الإحصائية: افتقار إلى التحليل الإحصائي لعمليات تشغيل متعددة

3. عمق التحليل

فجوة الأمثلية: عدم توفير حدود نظرية لفجوة الأمثلية
حالات الفشل: افتقار إلى تحليل حالات فشل الخوارزمية
المعنى الفيزيائي: يمكن أن يكون التفسير الفيزيائي لدالة الوزن أعمق

التأثير

1. المساهمة الأكاديمية

القيمة النظرية: لإثبات اكتمال NP الضعيف أهمية كبيرة لنظرية التحسين
قيمة المنهجية: يمكن تطبيق إطار تحليل الرسم البياني على مشاكل تحسين الشبكات الأخرى
الإلهام: توفير أفكار جديدة لتحسين الشبكات الكبيرة

2. القيمة العملية

التطبيق الصناعي: ينطبق مباشرة على إدارة الشبكات الكهربائية في الوقت الفعلي
تحسين الكفاءة: تحسين كبير في كفاءة حل الشبكات الكبيرة
قابلية التوسع: توفير دعم للتطبيقات الناشئة مثل الشبكات الكهربائية الذكية

3. قابلية التكرار

فتح الكود: يوفر المؤلفون تنفيذًا مفتوح المصدر
تفاصيل التنفيذ: وصف الخوارزمية مفصل، مما يسهل التكرار
مجموعات البيانات القياسية: استخدام أنظمة الاختبار القياسية IEEE يضمن القابلية للمقارنة

السيناريوهات المعمول بها

1. التطبيق المباشر

الأنظمة الكهربائية: إعادة تكوين الشبكات الموزعة والإدارة في الوقت الفعلي
شبكات المياه: تحسين تصميم أنظمة إمدادات المياه
شبكات الغاز الطبيعي: تخطيط شبكات الأنابيب

2. التطبيق الموسع

شبكات الاتصالات: تحسين طوبولوجيا الشبكة
سلسلة الإمداد: تصميم شبكات التوزيع
تخطيط النقل: تحسين تصميم شبكات الطرق

3. تطبيق المنهجية

استراتيجية التهيئة: توفير نقطة بداية جيدة لخوارزميات التحسين التكرارية
إطار التحليل: استراتيجية فرق تسد لمشاكل التحسين الكبيرة
نموذج الحوسبة المتوازية: نموذج معالجة متوازية لتحسين الشبكات

المراجع

تستشهد هذه الورقة بـ 32 مرجعًا مهمًا، تغطي بشكل أساسي:

نظرية إعادة تكوين الشبكات: العمل الرائد لـ Merlin & Back (1975)
أساسيات نظرية الرسوم البيانية: نظرية الرسوم البيانية الحديثة لـ Bollobás
خوارزميات التحسين: خوارزمية التدفق الأقصى Ford-Fulkerson
نظرية التعقيد: اكتمال NP لمشكلة التقسيم
تطبيقات الأنظمة الكهربائية: أنظمة الاختبار القياسية IEEE والحالات التطبيقية الفعلية

التقييم الإجمالي: هذه ورقة بحثية عالية الجودة في مجال خوارزميات التحسين، تُظهر أداءً ممتازًا من حيث المساهمات النظرية والابتكار المنهجي والتحقق التجريبي. لا تحل خوارزمية FORWARD مشكلة هندسية مهمة فحسب، بل توفر أيضًا إطارًا نظريًا جديدًا وأداة عملية لتحسين الشبكات الكبيرة. على الرغم من وجود بعض القيود، فإن قيمتها الابتكارية والعملية تجعلها مساهمة مهمة في هذا المجال.