Estratégia de verificação de radialidade de um subgrafo usado na otimização de sistemas de distribuição de energia elétrica - Romero Reynoso, César Augusto [UNESP] (Universidade Estadual Paulista (Unesp), 2024)
Em problemas relacionados com a otimização do planejamento da expansão e da operação de sistemas de distribuição radiais, existe a necessidade de verificar se uma proposta de solução é radial ou não. Essa necessidade de verificação é imprescindível quando são usadas algumas meta-heurísticas no processo de otimização do problema de distribuição, onde pode haver casos em que é necessário realizar milhares ou dezenas de milhares de verificações desse tipo. A proposta mais usada na literatura especializada consiste em calcular o determinante da matriz de incidência nó-arco da candidata à topologia radial. Nesse tipo de proposta, o tempo de processamento pode ser elevado. Adicionalmente, a topologia gerada é descartada se for verificada que não é radial. Neste trabalho, apresentam-se duas propostas para verificar se um subgrafo de um grafo conexo é árvore geradora (topologia radial). Essas propostas foram idealizadas usando as propriedades de grafos relacionadas com a caracterização de uma árvore geradora (topologia radial) e os conceitos existentes no algoritmo de Prim usado para resolver o problema de árvore geradora mínima de um grafo conexo. Além disso, apresenta-se também uma estratégia que pode ser mais interessante que as anteriores. Nessa estratégia, em um processo único, verifica-se se um subgrafo é uma topologia radial e, caso não seja, encontra-se a topologia radial mais próxima. Os testes mostram que as propostas apresentadas são rápidas e eficientes.

In problems related to the optimization of the expansion planning and of the operation of radial distribution systems, there is a need to verify if a solution proposal is radial or not. This verification is indispensable when some metaheuristics are used in the optimization process of the distribution problem, where may be cases which is necessary to perform this verification thousands or tens of thousand times. In the specialized literature, the most used proposal consists of calculating the determinant of the node-edge incidence matrix of the candidate to radial topology. In that proposal, the processing time can be high. Besides, the generated topology is discarded if it is verified as not being radial. In this work, two proposals are presented to verify if a subgraph from a connected graph is a spanning tree (radial topology). These proposals were idealized using the properties of graphs related with the caracterization of a spanning tree (radial topology) and the existing concepts in the Prim's Algorithm used to solve the minimal spanning tree problem of a connected graph. Furthermore, it is also presented a proposal which may be more interesting than the previous ones. In this proposal, in a single process, is verified if a subgraph is a radial topology and, if not, is generated the closer radial topology from the previous subgraph. The tests demonstrate that the presented proposals are fast and efficient.
Strategy to check the radiality of a subgraph used in the optimization of electrical energy distribution systems
Keywords: Algoritmo de Prim; Árvore geradora mínima; Otimização de sistemas de distribuição; Topologia radial; Minimal spanning tree; Optimization of distribution systems; Prim’s algorithm; Radial topology