Rapid radiality testing methods for accelerating the optimization of reconfigurable power grids

As distribution networks evolve toward smart, active, and increasingly decentralized architectures, driven by the integration of distributed energy resources, electric vehicles, and microgrids, grid reconfiguration has become a key tool for optimal operation. A critical step in grid reconfiguration is evaluating the radiality of every potential solution proposed by the optimization algorithm in each iteration; in a reconfiguration case, this test alone accounted for more than 80% of the population-preparation time of a given metaheuristic algorithm. Alternatives for this evaluation include Prim’s algorithm—the most widespread—eigenvalue analysis with the Fiedler theorem, Depth-First Search (DFS), and the zero-eigenvalue multiplicity in the Laplacian matrix. This work first proposes efficient alternatives to calculate the Fiedler value and evaluate matrix multiplicity, and then evaluates the performance of these four strategies in MATLAB and in a dedicated micro-computer under a Processor-in-the-Loop scheme representative of on-site smart grid controllers. In MATLAB, DFS was faster with a mean self-time of 0.003 s—nearly an order of magnitude below Prim’s (0.026 s)—while Multiplicity (0.004 s) marginally outperformed DFS below 50 buses. On the embedded device, DFS again led with a mean of 0.064 s, about three times faster than Prim’s (0.175 s), and Multiplicity 0.071 s. Fiedler roughly halved Prim’s time in MATLAB (0.011 s) but remained slower than both DFS and Multiplicity in both environments. Accuracy of the algorithms over 10,000 random grids was exact for Prim’s and DFS, 100% for Fiedler and 99.97% for Multiplicity.