A reconfiguração de redes é uma técnica utilizada para alterar topologias de redes por meio da mudança dos estados das chaves normalmente aberta e normalmente fechada. Essa técnica é muito utilizada para tratar problemas relacionados ao excesso de perdas ôhmicas em uma rede elétrica. Tais perdas representam um custo considerável no faturamento das empresas distribuidoras. O problema de redução de perdas via reconfiguração de redes pode ser modelado como um problema de otimização combinatória, em que se deve determinar a combinação de estados de chaves que correspondem a configuração radial da rede com menor nível de perdas. De modo a lidar com esse problema por reconfiguração da redes, diversas técnicas computacionais têm sido propostas. Dentre essas técnicas, estruturas de dados eficientes, como a Representação nó-profundidade (RNP), viabilizam a modelagem radial dos sistemas de distribuição (SDs) e o uso combinado com métodos de otimização possibilitam uma redução do espaço de busca de soluções consequentemente pode-se obter melhores soluções. Para otimizar a capacidade de processamento, este trabalho propõe tratar o problema de redução de perdas em SDs via reconfiguração de redes em aceleradores de hardware utilizando da arquitetura de hardware paralelizada em FPGA baseada na RNP (HP-RNP) proposta em (GOIS, 2011). Assim, um problema combinatório é tratado em aceleradoras de hardware reduzindo significativamente o custo computacional devido ao alto grau de paralelismo no processo de busca por soluções. Nesse sentido, foi proposto neste trabalho a extensão da HP-RNP, a partir de modificações no barramento de comunicação da arquitetura original para o envio e recebimentos dos dados que representam os SDs de forma mais eficiente. Além disso, o problema de redução de perdas por reconfiguração de redes foi mapeado em um problema de floresta geradora mínima com restrição de grau (dc-MSFP), a partir de uma aproximação que faz uso de uma heurística de pesos, em que informações relacionadas com grandezas elétricas e características topológicas da rede são transformadas em pesos. A partir da extensão da HP-RNP e do mapeamento do problema em um dc-MSFP, foi possível obter soluções de qualidade (próximas da ótima) em tempo significativamente reduzido quando comparado às outras abordagens. / Network reconfiguration is a technique used to change network topologies by changing the normally open and normally closed switches states. This technique is widely used to problems related to the excess of ohmic losses in distribution companies. Such losses represent a considerable cost in the distribution companies. The problem of network reconfiguration can be modeled as a combinatorial optimization problem, in which the combination of switches states that represent the configuration of the network with the lowest level of losses must be determined. To deal with these problems by network reconfiguration, several computational techniques have been proposed. Among these techniques, efficient data structures, such as the Node-Depth Encoding (NDE), enable the radial modeling of the distribution systems and the combined use of the NDE with optimization methods allow the reduction of the search space of the solutions. In order to optimize the processing capacity, this work proposes to deal with the loss minimization problem in Distribution Systems (DSs) by network reconfiguration using the Hardware Parallelized NDE (HP-NDE) proposed in (GOIS, 2011) to accelerate the network reconfiguration. Thus, a combinatorial problem is addressed in hardware accelerators, reducing significantly the computational cost due to the high degree of the parallelism in the process of search of the solution search. In this context, it was proposed the extension of the HP-NDE, from modifications in the communication bus of the original HP-NDE to send and receive more efficiently the data that represent the DSs. Moreover, the problem of loss reduction was mapped in a minimum spanning forest problem with degree constraint (dc-MSFP), by using an approximation that use a weights heuristic based on the information of the electrical magnitudes and topological characteristics of the network. From the extension of the HP-RNP and the mapping of the problem in a dc-MSFP, it was possible to obtain solutions of the good quality (close to optimal) in a time significantly reduced when compared to the other approaches.

A reconfiguração de redes é uma técnica utilizada para alterar topologias de redes por meio da mudança dos estados das chaves normalmente aberta e normalmente fechada. Essa técnica é muito utilizada para tratar problemas relacionados ao excesso de perdas ôhmicas em uma rede elétrica. Tais perdas representam um custo considerável no faturamento das empresas distribuidoras. O problema de redução de perdas via reconfiguração de redes pode ser modelado como um problema de otimização combinatória, em que se deve determinar a combinação de estados de chaves que correspondem a configuração radial da rede com menor nível de perdas. De modo a lidar com esse problema por reconfiguração da redes, diversas técnicas computacionais têm sido propostas. Dentre essas técnicas, estruturas de dados eficientes, como a Representação nó-profundidade (RNP), viabilizam a modelagem radial dos sistemas de distribuição (SDs) e o uso combinado com métodos de otimização possibilitam uma redução do espaço de busca de soluções consequentemente pode-se obter melhores soluções. Para otimizar a capacidade de processamento, este trabalho propõe tratar o problema de redução de perdas em SDs via reconfiguração de redes em aceleradores de hardware utilizando da arquitetura de hardware paralelizada em FPGA baseada na RNP (HP-RNP) proposta em (GOIS, 2011). Assim, um problema combinatório é tratado em aceleradoras de hardware reduzindo significativamente o custo computacional devido ao alto grau de paralelismo no processo de busca por soluções. Nesse sentido, foi proposto neste trabalho a extensão da HP-RNP, a partir de modificações no barramento de comunicação da arquitetura original para o envio e recebimentos dos dados que representam os SDs de forma mais eficiente. Além disso, o problema de redução de perdas por reconfiguração de redes foi mapeado em um problema de floresta geradora mínima com restrição de grau (dc-MSFP), a partir de uma aproximação que faz uso de uma heurística de pesos, em que informações relacionadas com grandezas elétricas e características topológicas da rede são transformadas em pesos. A partir da extensão da HP-RNP e do mapeamento do problema em um dc-MSFP, foi possível obter soluções de qualidade (próximas da ótima) em tempo significativamente reduzido quando comparado às outras abordagens. / Network reconfiguration is a technique used to change network topologies by changing the normally open and normally closed switches states. This technique is widely used to problems related to the excess of ohmic losses in distribution companies. Such losses represent a considerable cost in the distribution companies. The problem of network reconfiguration can be modeled as a combinatorial optimization problem, in which the combination of switches states that represent the configuration of the network with the lowest level of losses must be determined. To deal with these problems by network reconfiguration, several computational techniques have been proposed. Among these techniques, efficient data structures, such as the Node-Depth Encoding (NDE), enable the radial modeling of the distribution systems and the combined use of the NDE with optimization methods allow the reduction of the search space of the solutions. In order to optimize the processing capacity, this work proposes to deal with the loss minimization problem in Distribution Systems (DSs) by network reconfiguration using the Hardware Parallelized NDE (HP-NDE) proposed in (GOIS, 2011) to accelerate the network reconfiguration. Thus, a combinatorial problem is addressed in hardware accelerators, reducing significantly the computational cost due to the high degree of the parallelism in the process of search of the solution search. In this context, it was proposed the extension of the HP-NDE, from modifications in the communication bus of the original HP-NDE to send and receive more efficiently the data that represent the DSs. Moreover, the problem of loss reduction was mapped in a minimum spanning forest problem with degree constraint (dc-MSFP), by using an approximation that use a weights heuristic based on the information of the electrical magnitudes and topological characteristics of the network. From the extension of the HP-RNP and the mapping of the problem in a dc-MSFP, it was possible to obtain solutions of the good quality (close to optimal) in a time significantly reduced when compared to the other approaches.