GRASP com path relinking aplicado ao problema de reconfiguração de sistemas de distribuição de energia elétrica - Yamamoto, Rafael Yuki de Souza [UNESP] (Universidade Estadual Paulista (Unesp), 2023)
Esta dissertação apresenta uma nova abordagem para resolver o problema de reconfiguração de sistemas de distribuição de energia elétrica utilizando o greedy randomized adaptive search procedure (GRASP) com o path relinking (PR), sendo a busca local de ambos realizados pela heurística steepest descent heuristic. Esta estratégia foi utilizada para resolver o modelo matemático aproximado através de formulações de programação cônica de segunda ordem inteira mista. Nesta proposta todos os circuitos estão inicialmente fechados e, através da solução de alguns problemas de fluxos de carga para redes levemente malhadas, os circuitos são abertos de forma que o sistema ao final da fase construtiva seja radial e conexo. Para auxiliar na geração das soluções, foram implementados dois pré-processamentos, onde o primeiro tem a função de reduzir o espaço de busca e o segundo garante a factibilidade topológica na geração da solução. As soluções geradas pelo GRASP variam de acordo com o valor do parâmetro α, onde é possível optar por uma geração variando de gulosa para uma totalmente aleatória. Após a geração de duas soluções de qualidade, é realizado o PR entre elas, onde uma é escolhida como solução inicial e, a outra, como solução guia. A melhor solução encontrada é utilizada junto à próxima solução gerada pelo GRASP em um novo PR. Este processo se repete até atender o critério de parada, que será após o GRASP gerar um certo número de soluções. Foram utilizados os métodos forward e backward para verificar qual disposição das soluções apresenta melhor resultado. Neste estudo, também se compara a eficiência do solver GUROBI com as meta-heurísticas GRASP e GRASP-PR para os sistemas de 84, 118, 136 e 415 barras. Além disso, verifica-se as diferenças obtidas pelas disposições forward e backward. Os algoritmos e seus pré-processamentos propostos foram implementados em linguagem AMPL.

This dissertation introduces a novel approach to address the reconfiguration problem in electrical power distribution systems using the greedy randomized adaptive search procedure (GRASP) with path relinking (PR), with the local search for both being performed by the steepest descent heuristic. This strategy was employed to solve the approximate mathematical model through mixed-integer second-order cone programming formulations. In this approach, all circuits are initially closed, and by solving power flows for weakly meshed grids, the circuits opens so that the system becomes radial and connected at the end of the constructive phase. To aid in the generation of solutions, two preprocessing algorithms were implemented, where the first aimed to reduce the search space, and the second ensured the topological feasibility of the solution. The solutions generated by GRASP vary depending on the value of the parameter α, allowing for a choice ranging from a greedy approach to random. After generating two solutions, a PR is performed between them, with one chosen as the initial solution and the other as the guiding solution. The best solution found is used alongside the next solution generated by GRASP in a new PR. This process repeats until the stopping criterion is met, which is typically after GRASP generates a certain number of solutions. The forward and backward methods were employed to assess which arrangement of solutions yields superior outcomes. In this study, the efficiency of the GUROBI solver was also compared with the GRASP and GRASP-PR metaheuristics using the 84-, 118-, 136-, and 415-node test systems. Furthermore, the differences resulting from the forward and backward arrangements were examined. The proposed algorithms and their preprocessing were implemented in the AMPL language.
GRASP with path relinking applied to the problem of reconfiguration of electrical distribution systems
Keywords: GRASP; Path relinking; Reconfiguração de sistemas de distribuição de energia elétrica; Meta-heurística; Reconfiguration of distribution networks; Metaheuristic