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: बहु-स्रोत वितरण नेटवर्क के लिए एक व्यवहार्य रेडियल पुनर्विन्यास एल्गोरिदम

मूल जानकारी

पेपर ID: 2510.08785
शीर्षक: FORWARD: A Feasible Radial Reconfiguration Algorithm for Multi-Source Distribution Networks
लेखक: Joan Vendrell Gallart (UC Irvine), Russell Bent (Los Alamos National Laboratory), Solmaz Kia (UC Irvine)
वर्गीकरण: math.OC (अनुकूलन और नियंत्रण)
प्रकाशन समय/सम्मेलन: 9 अक्टूबर 2025 को arXiv पर प्रस्तुत, 2025 American Control Conference में प्रारंभिक संस्करण प्रकाशित
पेपर लिंक: 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: क्षमता-जागरूक किनारे विनिमय
सैद्धांतिक ढांचा: संयोजी व्यवहार्यता प्रमेय (Theorem 5) और इष्टतमता-संरक्षण उपफल (Corollary 6) स्थापित किए, जो ग्राफ अपघटन विधि की सैद्धांतिक शुद्धता को साबित करते हैं
प्रदर्शन सफलता: बड़े पैमाने के नेटवर्क परीक्षण में वाणिज्यिक MINLP सॉल्वर से काफी बेहतर, पारंपरिक तरीकों के विफल होने या घंटों की आवश्यकता के मामलों में, 400-नोड नेटवर्क को कुछ सेकंड में पूरा कर सकता है

विधि विवरण

कार्य परिभाषा

वितरण नेटवर्क 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. Pre-Processor घटक

कार्य: नेटवर्क में लटकते नोड्स की पहचान और प्रसंस्करण
एल्गोरिदम: डिग्री 1 के नोड्स को पुनरावृत्ति से संसाधित करता है, 
           उनकी मांग/आपूर्ति को पैरेंट नोड को स्थानांतरित करता है
जटिलता: O(n + m)
आउटपुट: 2-core सबग्राफ GP और नमूना किए गए किनारों का सेट S

2. Islander घटक

कार्य: जोड़ बिंदुओं पर 2-core सबग्राफ को अपघटित करता है
रणनीति: केवल स्रोत जोड़ बिंदुओं पर विभाजन, कम्प्यूटेशनल जटिलता को कम करता है
संतुलन: विभाजन नोड्स के नोड मान को समायोजित करके 
         प्रत्येक सबग्राफ इनपुट-आउटपुट संतुलन सुनिश्चित करता है
आउटपुट: L संतुलित सबग्राफ {G1, G2, ..., GL}

3. Net-Concad घटक

कार्य: दोहरे ग्राफ संघनन, लालची एल्गोरिदम की अदूरदर्शिता समस्या को हल करता है
विधि:
- नमूना किए गए बहु-वृक्षों को सुपर "नमूना किए गए" नोड में मर्ज करता है
- अनमूना किए गए जुड़े घटकों को सुपर "अनमूना किए गए" नोड में मर्ज करता है
- अर्ध-द्विपक्षीय ग्राफ संरचना Ḡℓ का निर्माण करता है

4. Sampler घटक

कार्य: नमूनाकरण के लिए इष्टतम किनारों को भार-आधारित चयन करता है
भार फ़ंक्शन: wi,j = pi/(Ri,j · d²j + f̂(Ri_k))
प्राथमिकता:
1. लटकते सुपर अनमूना किए गए नोड्स
2. पर्याप्त क्षमता वाले किनारे
3. भार अवरोही क्रम में

5. Rewire घटक

कार्य: किनारे विनिमय के माध्यम से क्षमता बाधा से उत्पन्न अव्यवहार्यता को हल करता है
रणनीति:
- अपूर्ण आपूर्ति नोड्स और अतिरिक्त आपूर्ति पथों की पहचान करता है
- रणनीतिक किनारे विनिमय निष्पादित करता है
- रेडियल संरचना को बनाए रखता है

तकनीकी नवाचार बिंदु

1. ग्राफ अपघटन सिद्धांत

नवाचार: संयोजी व्यवहार्यता प्रमेय को साबित किया, मूल समस्या और अपघटित सबप्रॉब्लम्स के बीच समतुल्यता स्थापित की लाभ: समानांतर प्रसंस्करण का समर्थन करता है, साथ ही इष्टतमता को बनाए रखता है

2. दोहरे ग्राफ संघनन तकनीक

नवाचार: Net-Concad फ़ंक्शन अर्ध-द्विपक्षीय ग्राफ संरचना के निर्माण के माध्यम से लालची चयन की अदूरदर्शिता को दूर करता है तंत्र: जटिल बहु-स्रोत बहु-सिंक समस्या को सुपर नोड्स के बीच सरल कनेक्शन समस्या में परिवर्तित करता है

3. क्षमता-जागरूक किनारे विनिमय

नवाचार: Rewire फ़ंक्शन रणनीतिक किनारे विनिमय के माध्यम से क्षमता बाधाओं को हल करता है सिद्धांत: अतिरिक्त आपूर्ति क्षेत्रों से प्रवाह को अपूर्ण आपूर्ति नोड्स में पुनः वितरित करता है, अतिरिक्त उत्पादन संसाधनों की आवश्यकता के बिना

प्रयोगात्मक सेटअप

डेटासेट

IEEE मानक परीक्षण प्रणाली:

IEEE 13 (2 स्रोत नोड्स)
IEEE 18 (2 स्रोत नोड्स)
IEEE 33 (3 स्रोत नोड्स)

छोटी दुनिया नेटवर्क:

WS 120 (10 स्रोत नोड्स)
WS 240 (10 स्रोत नोड्स)
WS 400 (20 स्रोत नोड्स)

मूल्यांकन मेट्रिक्स

विद्युत हानि: किलोवाट (kW) में
कम्प्यूटेशन समय: CPU निष्पादन समय (सेकंड)
व्यवहार्यता: क्या व्यवहार्य समाधान मिला

तुलना विधियां

Knitro: Artelys कंपनी का वाणिज्यिक MINLP सॉल्वर
पारंपरिक MINLP विधि: शाखा और बाउंड जैसी सटीक एल्गोरिदम

कार्यान्वयन विवरण

प्लेटफॉर्म: MacBook Air M3 चिप, 24GB RAM
प्रोग्रामिंग भाषा: Julia
ढांचा: PowerDistributionModel (PMD)
समय सीमा: 3 घंटे का टाइमआउट सेटिंग

प्रयोगात्मक परिणाम

मुख्य परिणाम

नेटवर्क	Knitro विद्युत हानि(kW)	Knitro समय(s)	FORWARD विद्युत हानि(kW)	FORWARD समय(s)
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) समाधान गुणवत्ता में काफी सुधार करता है
समानांतर प्रसंस्करण लाभ: ग्राफ अपघटन रणनीति प्रभावी समानांतर कम्प्यूटिंग को सक्षम करती है

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

सैद्धांतिक योगदान: पहली बार साबित किया कि व्यवहार्य रेडियल विन्यास निर्माण कमजोर 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 एल्गोरिदम न केवल एक महत्वपूर्ण इंजीनियरिंग समस्या को हल करता है, बल्कि बड़े पैमाने के नेटवर्क अनुकूलन के लिए एक नया सैद्धांतिक ढांचा और व्यावहारिक उपकरण भी प्रदान करता है। कुछ सीमाओं के बावजूद, इसकी नवाचारिता और व्यावहारिक मूल्य इसे इस क्षेत्र का एक महत्वपूर्ण योगदान बनाता है।