Service restoration and switch allocation in power distribution networks : bounds and algorithms

A melhora da confiabilidade em redes de distribuição de energia elétrica é um tema importante para as indústrias de fornecimento de eletricidade, devido aos regulamentos estritos em muitos países. Depois de uma falha na rede, algumas chaves são usadas para isolar a falha, enquanto outras restauram a energia a alguns consumidores. A ótima seleção das chaves que serão abertas ou fechadas para restaurar a energia é conhecido como o problema de restauração de serviço. A instalação de chaves em posições estratégicas pode reduzir o tempo de parada, e assim melhorar a confiabilidade da rede. A seleção ótima de posições para instalar chaves é conhecido como o problema de alocação de chaves. Estes dois problemas estão relacionados estreitamente. Esta dissertação estuda o problema de alocação de chaves, considerando o problema de restauração de serviço como um subproblema. Dois métodos são propostos para estimar a confiabilidade de uma rede de distribuição com um conjunto dado de chaves instaladas. O foco principal está nas heurísticas para resolver o problema composto. Propõe-se aqui métodos como busca tabu, procedimento de busca gulosa adaptativa aleatória (sigla em inglês: GRASP), e procedimento iterativo de construção por amostras com reconexão de caminhos. Também estuda-se o benefício dos métodos de construção gulosa, semigulosa, aleatória e por amostras, e estuda-se o desempenho das estratégias de busca local por amostras, primeira melhoria e melhor melhoria. Os diferentes métodos são comparados e analisados. Os resultados mostram que os métodos por amostras são baratos e levam a soluções de boa qualidade. O procedimento iterativo de construção por amostras com reconexão de caminhos é o melhor método proposto para resolver o problema composto que é proposto nesta dissertação.The improvement of reliability in electrical power distribution networks is an important issue for electricity supply industries, due to strict regulations in many countries. After a failure in the network, some switches are used to isolate the failure, while others restore the energy to some consumers. The optimal selection of the switches to open or close to restore energy is called the service restoration problem. The installation of switches in strategic places may reduce the outage time in case of blackouts, and thus improve the reliability of the network. The optimal selection of places to install switches is called the switch allocation problem. These two problems are closely related. This dissertation studies the switch allocation problem, considering the service restoration problem as a sub-problem. Two methods are proposed to estimate the reliability of a distribution network with a given set of installed switches. The main focus is in heuristics to solve the joint problem. It proposes methods like tabu search, greedy randomized adaptive search procedure, and iterated sample construction with path relinking. It also studies the benefit of greedy, semigreedy, random, and sample construction methods, and studies the performance of sample, first improvement and best improvement local search strategies. The different methods are compared and analyzed. The results show that sample approaches are inexpensive and lead to solutions of good quality. Iterated sample construction with path relinking is the best method to solve the joint problem that is proposed in this dissertation