Câmpus de Ilha Solteira LLULEISI GRANDEZ FERNANDEZ PLANEJAMENTO DA EXPANSÃO DE SISTEMAS DE DISTRIBUIÇÃO DE ENERGIA ELÉTRICA CONSIDERANDO CONFIABILIDADE Ilha Solteira - SP 2024 Câmpus de Ilha Solteira PROGRAMA DE PÓS-GRADUAÇÃO EM ENGENHARIA ELÉTRICA LLULEISI GRANDEZ FERNANDEZ PLANEJAMENTO DA EXPANSÃO DE SISTEMAS DE DISTRIBUIÇÃO DE ENERGIA ELÉTRICA CONSIDERANDO CONFIABILIDADE Dissertação apresentada ao Programa de Pós- Graduação em Engenharia Elétrica da Facul- dade de Engenharia de Ilha Solteira da UNESP, como parte dos requisitos para a obtenção do título de Mestra em Engenharia Elétrica. Área de concentração: Automação. Prof. Dr. Rubén Augusto Romero Lázaro Orientador Prof. Dr. Leonardo Henrique Faria Macedo Possagnolo Coorientador Ilha Solteira - SP 2024 javascript:xajax_exibePagina(778,%20'idLightBox',%200,%20808);%20void(0) IMPACTO POTENCIAL DESTA PESQUISA A eficiência e confiabilidade no fornecimento de energia elétrica são pilares fundamen- tais para o desenvolvimento adequado de múltiplas atividades que dependem desse recurso es- sencial. O impacto desse trabalho se manifesta através de uma metodologia que visa aumentar a confiabilidade do sistema por meio da otimização do número de topologias radiais, que per- mitem a reposição do fornecimento elétrico em caso de falhas. Esse enfoque estratégico não apenas reduz as probabilidades de interrupções na rede, mas também se estabelece como uma valiosa ferramenta para garantir a continuidade da energia elétrica, contribuindo de maneira significativa para o funcionamento eficaz do sistema. POTENTIAL IMPACT OF THIS RESEARCH The efficiency and reliability of the electricity supply are fundamental pillars for the proper development of the many activities that depend on this essential resource. The impact of this work is manifested through a methodology that aims to increase system reliability by optimizing the number of radial topologies, which allow the electricity supply to be restored in the event of faults. This strategic approach not only reduces the likelihood of network in- terruptions, but also establishes itself as a valuable tool for guaranteeing the continuity of electricity, making a significant contribution to the effective operation of the system. AGRADECIMENTOS A Deus por me conceder vida, saúde, perseverança e por ter me acompanhado ao longo desta jornada. Minha profunda gratidão aos meus pais, Manuel Asención e María Esperanza pelo amor incondicional e pela incansável dedicação em cada decisão, motivando-me incessantemente a alcançar minhas metas e a nunca desanimar diante das adversidades da vida. Ao Professor Rubén Augusto Romero Lazaro expresso minha imensa gratidão pela ori- entação brindada, disponibilidade, apoio incansável, confiança depositada em min e pelos va- liosos ensinamentos compartilhados ao longo desta jornada de pesquisa. Ao professor Leonardo Henrique Faria Macedo Possagnolo, meus agradecimentos pela coorientação e apoio na realização deste trabalho de pesquisa. Agradeço a sua disponibilidade em partilhar o seu conhecimento e experiência ao longo deste processo. Ao Richard, pelas inúmeras ajudas e contribuições, não apenas para o desenvolvimento desta tese, mas também em minha vida. Obrigada pela dedicação, pelo afeto, pelo suporte em cada decisão tomada e por estar ao meu lado durante toda esta jornada. Aos meus irmãos Leidi, José Deiber e Juan Carlos, pelo apoio incondicional em todos os momentos, sempre me brindando palavras de incentivo e gestos de carinho. Aos meus colegas do LaPSEE – Laboratório de Planejamento de Sistemas de Energia Elétrica pela amizade, apoio e convívio. À comissão examinadora pelos comentários construtivos e valiosas sugestões que con- tribuíram para a melhoria deste trabalho. A todos os Professores que compartilharam seu co- nhecimento e aos funcionários da UNESP que contribuíram direta ou indiretamente para a rea- lização deste trabalho. O presente trabalho foi realizado com apoio da Coordenação de Aperfeiçoamento de Pessoal de Nível Superior – Brasil (CAPES) – Código de Financiamento 001 e da Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP), processo 2015/21972-6. Cada pessoa deve decidir uma vez na vida se pretende ter sucesso, arriscando tudo, ou se sentar e observar os vencedores passarem. — Thomas Alva Edison RESUMO Este trabalho aborda o problema de planejamento da expansão de sistemas de distribuição de energia elétrica (PESD), focando especialmente nos aspectos de confiabilidade. A maioria das propostas de PESD encontra apenas uma topologia ótima que é radial. Entretanto, o sistema de distribuição real tem topologia malhada onde existem ramos que devem estar ativos quando o sistema opera em condição normal e existe um conjunto geralmente reduzido de ramos que devem permanecer desligados na operação normal, mas podem estar ativos quando o sistema opera em condições não normais ou quando se pretende realizar manutenção programada do sistema. Dessa forma, o sistema ligeiramente malhado é mais confiável que um sistema apenas com topologia radial. A proposta desenvolvida neste trabalho envolve a expansão de um sistema de distribuição de 54 barras em duas etapas. Assim, inicialmente se encontra a topologia radial ótima de operação usando um modelo matemático de programação cônica de segunda ordem binário misto (PCSOBM). Posteriormente, na segunda etapa, a partir dessa topologia radial, são incorporados um número adicional de ramos de forma que o sistema malhado apresenta uma estrutura com o máximo número possível de topologias radiais. Essa segunda etapa é resolvida usando a meta-heurística VNS (do inglês Variable Neighborhood Search) nas versões VND (do inglês Variable Neighborhood Descent) e BVNS (do inglês Basic Variable Neighborhood Se- arch). Os resultados obtidos na primeira etapa incluem um custo total de planejamento de 4.788.328 USD, considerando os custos de construção de subestações, construção e reconduto- ramento de ramos. Adicionalmente na segunda etapa, foram identificados 6 ramos que geram um máximo de 138.768 topologias radiais com um custo total de construção de 54.300 USD. Esta abordagem evidencia que um sistema com uma topologia ligeiramente malhada pode ofe- recer maior confiabilidade em comparação com sistemas baseados exclusivamente em topolo- gias radiais, destacando a eficácia da metodologia combinada do sistema de expansão junto com os ramos incorporados. Palavras-chave: expansão de sistemas de distribuição; otimização; meta-heurísticas; meta- heurística VNS; topologias radiais em um grafo. ABSTRACT This work addresses the problem of planning the expansion of electric power distribution sys- tems (PESD), focusing especially on reliability aspects. Most PESD proposals find only one optimal radial topology. However, real distribution systems have a meshed topology where there are branches that must be active when the system operates under normal conditions and there is a generally reduced set of branches that should remain disconnected in normal operation but can be active when the system operates under abnormal conditions or when scheduled maintenance is intended. Therefore, a slightly meshed system is more reliable than a system with only a radial topology. The proposal developed in this work involves expanding a 54-bus distribution system in two stages. Initially, the optimal radial operating topology is found using a second-order mixed binary conic programming model (PCSOBM). Subsequently, in the sec- ond stage, from this radial topology, an additional number of branches are incorporated so that the meshed system exhibits a structure with the maximum possible number of radial topologies. This second stage is solved using the metaheuristic VNS (Variable Neighborhood Search) in the VND (Variable Neighborhood Descent) and BVNS (Basic Variable Neighborhood Search) ver- sions. The results obtained in the first stage include a total planning cost of 4,788,328 USD, considering substation construction costs, branch construction, and reconductoring costs. Ad- ditionally, in the second stage, 6 branches were identified that generate a maximum of 138,768 radial topologies with a total construction cost of 54,300 USD. This approach highlights that a system with a slightly meshed topology can offer greater reliability compared to systems based solely on radial topologies, emphasizing the effectiveness of the combined expansion system methodology with the incorporated branches. Keywords: expansion of distribution systems; optimization; metaheuristics; VNS meta-heu- ristic; radial topologies in a graph. LISTA DE FIGURAS Figura 1 – Sistema de 14 barras .............................................................................................. 44 Figura 2 – Matriz laplaciana .................................................................................................... 44 Figura 3 – Sistema de 14 barras modificado ........................................................................... 45 Figura 4 – Matriz laplaciana do sistema modificado ............................................................... 46 Figura 5 – Fluxograma do AHC aplicado ao problema de PESD ........................................... 53 Figura 6 – Idealização da forma de uma proposta de solução ................................................. 54 Figura 7 – Fluxograma do algoritmo VNS na versão VND .................................................... 59 Figura 8 – Fluxograma do algoritmo VNS na versão BVNS .................................................. 62 Figura 9 – Sistema de 54 barras – Configuração inicial e rotas factíveis propostas ............... 65 Figura 10 – Sistema de 54 barras – Resultado ........................................................................ 70 Figura 11 – Magnitudes de tensão dos subsistemas radiais formados após o planejamento .. 72 Figura 12 – Resultados obtidos da meta-heurística VNS na versão BVNS ............................ 80 Figura 13 – Sistema final com a adição dos ramos adicionais ................................................ 83 LISTA DE TABELAS Tabela 1 – Topologia base ....................................................................................................... 66 Tabela 2 – Especificações técnicas dos tipos de condutores ................................................... 67 Tabela 3 – Custos de construção e recondutoramento de ramos ............................................. 67 Tabela 4 – Dados de subestações............................................................................................. 68 Tabela 5 – Topologia radial expandida ................................................................................... 69 Tabela 6 – Custo do planejamento .......................................................................................... 71 Tabela 7 – Potência fornecida das subestações ....................................................................... 71 Tabela 8 – Ramos não construídos .......................................................................................... 73 Tabela 9 – Vetor inicial ........................................................................................................... 74 Tabela 10 – Posição dos ramos candidatos no vetor ............................................................... 74 Tabela 11 – Ramos adicionados AHC ..................................................................................... 75 Tabela 12 – Ordem dos ramos adicionados ............................................................................. 75 Tabela 13 – Posição dos ramos adicionados ........................................................................... 76 Tabela 14 – Ramos candidatos a serem construídos ............................................................... 76 Tabela 15 – Posição do ramo no vetor solução VND .............................................................. 77 Tabela 16 – Posição dos ramos solução VND ......................................................................... 77 Tabela 17 – Ramos adicionados solução VND ....................................................................... 78 Tabela 18 – Posição do ramo no vetor solução BVNS ............................................................ 79 Tabela 19 – Tipo e custo de condutor atribuído a cada ramo adicionado ............................... 81 Tabela 20 – Resultados obtidos ............................................................................................... 82 Tabela 21 – Dados do sistema de 54 barras ............................................................................. 92 Tabela 22 – Dados de ramos do sistema de 54 barras ............................................................. 93 LISTA DE ABREVIATURAS SDEE Sistema de distribuição de energia elétrica PLIM Programação linear inteira mista PNLIM Programação não linear inteira mista PESD Planejamento da expansão em sistemas de distribuição SE Subestação AMPL A mathematical programming language PCSOBM Programação cônica de segunda ordem binário mista PCSOIM Programação cônica de segunda ordem inteira mista CHA Constructive Heuristic Algorithm AHC Algoritmo heurístico construtivo VNS Variable neighborhood search SDH Steepest descent heuristic VND Variable neighborhood descent MT Média tensão BT Baixa tensão LISTA DE SÍMBOLOS Conjuntos: Ω𝑏 Conjunto de barras do sistema. Ω𝑐 Conjunto de ramos do sistema. Ω𝑎 Conjunto de tipos de condutor. Ω∪ Conjunto que representa 𝑖𝑗 ∈ Ω𝑐 união 𝑗𝑖 ∈ Ω𝑐. Parâmetros: 𝑇𝑖 𝑏 Tipo de barra (carga ou SE na barra 𝑖: carga = 0, SE = 1). 𝑃𝑖 𝐷 Potência ativa demandada na barra 𝑖. 𝑄𝑖 𝐷 Potência reativa demandada na barra 𝑖. 𝑆�̅� Capacidade da subestação na barra 𝑖. 𝑆𝑖 𝑔𝑛 Reforço de potência aparente da SE. 𝑙𝑖𝑗 Comprimento em km do ramo 𝑖𝑗. 𝑡𝑖𝑗 Tipo do ramo 𝑖𝑗 existente. 𝐶𝑡𝑖𝑗,𝑎 𝑟𝑎 Custo por km do condutor de tipo 𝑎. 𝑅𝑎 Resistência por km do condutor de tipo 𝑎. 𝑋𝑎 Reatância por km do condutor de tipo 𝑎. 𝑍𝑎 Impedância por km do condutor de tipo 𝑎. 𝐼𝑎 Limite máximo da magnitude de corrente do condutor do tipo 𝑎. 𝑉 Magnitude da tensão máxima permitida em uma barra. 𝑉 Magnitude da tensão mínima permitida em uma barra. 𝐶𝑖 𝑠 Custo fixo da construção ou ampliação de subestações na barra 𝑖. 𝛼 Número de barras do sistema. 𝛽 Número total de subestações no SDEE. Variáveis reais: 𝑉𝑖 𝑞𝑑𝑟 Quadrado da magnitude da tensão na barra 𝑖. 𝑏𝑖𝑗 Variável auxiliar usada no cálculo da queda de magnitude de tensão no ramo 𝑖𝑗 quando não é construído nenhum ramo. 𝑃𝑖 𝑆 Injeção de potência ativa de uma subestação na barra 𝑖. 𝑄𝑖 𝑆 Injeção de potência reativa de uma subestação na barra 𝑖. 𝐼𝑖𝑗,𝑎 𝑞𝑑𝑟 Quadrado da magnitude de corrente no ramo 𝑖𝑗, no condutor do tipo 𝑎. 𝑃𝑖𝑗,𝑎 Fluxo de potência ativa no ramo 𝑖𝑗, no condutor do tipo 𝑎. 𝑄𝑖𝑗,𝑎 Fluxo de potência reativa no ramo 𝑖𝑗, no condutor do tipo 𝑎. 𝑅𝑃𝑖𝑗 𝑡 Variável auxiliar para o produto de 𝑅𝑎 e 𝑃𝑖𝑗,𝑎. 𝑋𝑄𝑖𝑗 𝑡 Variável auxiliar para o produto de 𝑋𝑎 e 𝑄𝑖𝑗,𝑎. 𝑅𝐼2𝑖𝑗 𝑡 Variável auxiliar para o produto de 𝑅𝑎 e 𝐼𝑖𝑗,𝑎 𝑞𝑑𝑟 . 𝑋𝐼2𝑖𝑗 𝑡 Variável auxiliar para o produto de 𝑋𝑎 e 𝐼𝑖𝑗,𝑎 𝑞𝑑𝑟 . 𝑍2𝐼2𝑖𝑗 𝑡 Variável auxiliar para o produto de 𝑍𝑎 2 e 𝐼𝑖𝑗,𝑎 𝑞𝑑𝑟 . 𝑥𝑖𝑗 Variável binária auxiliar que indica que o fluxo no ramo 𝑖𝑗, ocorre da barra 𝑗 para a barra 𝑖, sendo a barra 𝑗 a mais próxima da subestação. Variáveis discretas: 𝑦𝑖𝑗,𝑎 Variável binária de construção de um novo ramo 𝑖𝑗 do condutor de tipo 𝑎. 𝑤𝑖 Variável binária de construção ou ampliação de uma subestação na barra 𝑖. 𝑠𝑤𝑖𝑗 Variável binária auxiliar que indica o estado operacional do ramo 𝑖𝑗, onde 𝑠𝑤𝑖𝑗 = 1 se o ramo 𝑖𝑗 está em operação no sistema e 𝑠𝑤𝑖𝑗 = 0 caso contrário. SUMÁRIO 1 INTRODUÇÃO ........................................................................................................ 17 1.1 REVISÃO BIBLIOGRÁFICA ................................................................................... 19 1.1.1 Revisão bibliográfica considerando planejamento tradicional ............................ 19 1.1.2 Revisão bibliográfica considerando heurísticas e meta-heurísticas..................... 26 1.1.3 Revisão bibliográfica considerando uma topologia ligeiramente malhada ........ 28 1.2 OBJETIVOS ............................................................................................................... 30 1.3 CONTRIBUIÇÕES .................................................................................................... 31 1.4 ESTRUTURA DO TRABALHO ............................................................................... 31 2 MODELO MATEMÁTICO PARA O PROBLEMA DE PESD .......................... 33 3 MELHORANDO A CONFIABILIDADE DO SISTEMA DE DISTRIBUIÇÃO .................................................................................................................................... 42 3.1 ESTRATÉGIA PARA ENCONTRAR O NÚMERO DE TOPOLOGIAS RADIAIS DE UM GRAFO CONEXO ....................................................................................... 43 3.2 A META-HEURÍSTICA DE BUSCA EM VIZINHANÇA VARIÁVEL ................ 47 3.3 ALGORITMO HEURÍSTICO CONSTRUTIVO PARA ENCONTRAR UMA TOPOLOGIA LIGERAMENTE MALHADA .......................................................... 50 3.4 IDEALIZAÇÃO DA APLICAÇÃO DA META-HEURÍSTICA DE BUSCA EM VIZINHANÇA VARIÁVEL ..................................................................................... 54 3.5 APLICAÇÃO DA META-HEURÍSTICA DE BUSCA EM VIZINHANÇA VARIÁVEL NA VERSÃO VND .............................................................................. 56 3.6 APLICAÇÃO DA META-HEURÍSTICA DE BUSCA EM VIZINHANÇA VARIÁVEL NA VERSÃO BVNS ............................................................................ 60 4 TESTES E RESULTADOS ..................................................................................... 64 4.1 PRIMEIRA FASE: APLICANDO O PLANEJAMENTO TRADICIONAL ............ 64 4.1.1 Sistema de distribuição de 54 barras ...................................................................... 64 4.1.2 Topologia base .......................................................................................................... 67 4.1.3 Resultados do planejamento da expansão em sistemas de distribuição .............. 68 4.2 SEGUNDA FASE: APLICANDO O AHC E VNS ................................................... 72 4.2.1 Resultados do algoritmo heurístico construtivo .................................................... 73 4.2.2 Resultados da meta-heurística VNS na versão VND ............................................ 76 4.2.3 Resultados da meta-heurística VNS na versão BVNS .......................................... 78 4.2.4 Tipo de condutor utilizado em ramos adicionais ................................................... 81 5 CONCLUSÕES E DESENVOLVIMENTOS FUTUROS .................................... 85 REFERÊNCIAS ........................................................................................................ 87 APÊNDICE A – DADOS DO SISTEMA DE DISTRIBUIÇÃO TESTADO ....... 92 17 1 INTRODUÇÃO Hoje em dia a eletricidade se tornou uma parte essencial da sociedade. O investimento contínuo em pesquisa e desenvolvimento no setor elétrico é fundamental para enfrentar os de- safios atuais e futuros relacionados à geração, transmissão e distribuição de energia elétrica. O PESD é um aspecto crítico a ser abordado, pois afeta diretamente a capacidade de atender à demanda crescente por energia de forma eficiente e confiável (Mendoza, 2010). Ao investir em pesquisas relacionadas ao PESD, podem ser desenvolvidas soluções inovadoras para otimizar a expansão das redes de distribuição, considerando aspectos como custo, qualidade do serviço e resiliência do sistema. Além disso, ao melhorar a qualidade e a confiabilidade dos serviços de energia elétrica, pode ser aumentada a eficiência energética, reduzir os custos operacionais e promover o desenvolvimento sustentável. Os sistemas de distribuição de energia desempenham um papel importante na garantia de um fornecimento confiável de eletricidade para os consumidores finais, pois são responsá- veis por levar a energia elétrica das subestações de transmissão até os consumidores finais, sejam residenciais, comerciais ou industriais. Com o aumento da demanda por energia elétrica devido ao crescimento populacional e ao desenvolvimento industrial e tecnológico, é essencial que as empresas de distribuição planejem cuidadosamente a expansão e modernização de seus sistemas. Isso envolve investir em tecnologias inteligentes de gerenciamento de rede, como medidores inteligentes, sistemas de automação de distribuição e armazenamento de energia. Essas tecnologias não só ajudam a otimizar a operação dos sistemas de distribuição, mas tam- bém permitem uma resposta mais rápida à falhas e interrupções, garantindo assim um forneci- mento mais confiável de energia para os consumidores. O processo de expansão dos sistemas de distribuição de energia elétrica (SDEE) envolve uma série de considerações financeiras e técnicas. Os custos associados à expansão podem ser significativos, incluindo investimentos em infraestrutura, construção de novas subestações, au- mento da capacidade das subestações existentes e até mesmo a necessidade de recondutora- mento de ramos já existentes (Gönen; Ramirez-Rosado, 1986). As empresas do setor elétrico precisam planejar cuidadosamente essas expansões, considerando não apenas os custos opera- cionais e de investimento, mas também a melhoria da confiabilidade e qualidade do forneci- mento. Além disso, o aumento da demanda de energia por parte dos consumidores também impulsiona a necessidade de expansão da rede de distribuição. 18 O planejamento do SDEE envolve análises técnicas e econômicas para garantir que o fornecimento de energia seja confiável e de alta qualidade, enquanto os custos sejam mantidos menores possível. Ao considerar os altos custos de investimento em novos equipamentos, cus- tos de perda de energia e outros fatores, a distribuidora precisa decidir quando e como expandir ou reforçar o seu sistema. O objetivo final é melhorar a confiabilidade e a qualidade da energia fornecida aos consumidores, analisando restrições técnicas, limites de capacidade nas subesta- ções, as quedas máximas de tensão permitidas nos ramos da rede elétrica e a radialidade do sistema (Ramírez-Rosado; Domínguez-Navarro, 2006). O PESD considera diversas funções objetivo em sua abordagem, incluindo custos de investimento envolvidos na aquisição e insta- lação de novos equipamentos, como transformadores, cabos, e outros componentes do sistema; custos operacionais dos ramos e subestações, incluindo manutenção e reparos; confiabilidade do sistema o que permite que o sistema de distribuição seja capaz de fornecer energia de forma consistente e sem interrupções indesejadas; e a minimização das perdas de energia no sistema de distribuição, que podem ocorrer devido a diversos fatores, como a resistência dos cabos e dos transformadores (Ganguly; Sahoo; Das, 2013). Os índices de confiabilidade constituem parte importante do PESD, pois fornecem mé- tricas importantes para avaliar a qualidade do serviço prestado aos usuários. Esses índices, ge- ralmente, consideram a quantidade de vezes que ocorrem interrupções no fornecimento de ener- gia durante um período de tempo específico, o qual é uma medida importante para avaliar a continuidade do fornecimento de energia em uma determinada área; a duração das interrupções de energia, o que fornece diagnóstico sobre a gravidade das interrupções e seu impacto na vida cotidiana dos usuários; e a qualidade da energia fornecida, que inclui aspectos como a tensão estável, a ausência de flutuações de tensão, a presença de harmônicos e outros parâmetros que afetam diretamente a capacidade dos equipamentos e dispositivos elétricos de operarem de ma- neira eficiente e segura (Gomez Ramirez, 2016). Ao analisar esses índices, as empresas de energia e os órgãos reguladores podem identificar áreas que precisam de melhoria na infraes- trutura elétrica, implementar estratégias eficazes de expansão e modernização, e garantir que os padrões de qualidade do serviço elétrico sejam atendidos ou superados. Finalmente, o planejamento da expansão dos SDEE desempenha um papel importante das empresas distribuidoras, na garantia de um fornecimento confiável e eficiente de energia na sociedade moderna. O PESD é uma ferramenta essencial nesse contexto, pois não só proporci- ona o projeto de redes com redução de perdas técnicas durante o transporte de energia, mas também permite identificar áreas onde quedas de tensão são mais frequentes, visando melhorar 19 a qualidade do fornecimento de energia aos consumidores. Além disso, contribui significativa- mente para a redução de custos operacionais associados ao processo de expansão da rede (Ramírez-Rosado; Domínguez-Navarro, 2006). Ao otimizar o planejamento e a gestão dos re- cursos, as empresas de energia podem economizar recursos financeiros e materiais, melhorando assim a eficiência global do sistema. Portanto, investir no desenvolvimento e implementação de estratégias de PESD é fundamental para projetar e construir um sistema de distribuição de energia mais confiável, eficiente e economicamente viável. 1.1 REVISÃO BIBLIOGRÁFICA A revisão de literatura neste trabalho é focada em problemas relacionados ao PESD. A primeira parte da revisão apresenta-se as publicações que discutem diversas estratégias de re- solução de problemas utilizando métodos tradicionais e considerando a confiabilidade do sis- tema. Na segunda parte, são apresentados trabalhos que desenvolveram diferentes métodos de planejamento baseados em heurísticas e meta-heurísticas, o que facilita a abordagem de proble- mas complexos que podem ser difíceis de resolver através de métodos tradicionais. Na terceira e última parte da revisão, trata-se de trabalhos que propõem resolver problemas considerando uma estrutura ligeiramente malhada. Todas essas investigações visam reduzir custos de operação e investimento, com o ob- jetivo de melhorar o desempenho do sistema de distribuição de energia elétrica e elevar o índice de confiabilidade do sistema. 1.1.1 Revisão bibliográfica considerando planejamento tradicional O PESD começou a ser estudado há muitos anos. Os primeiros trabalhos foram publi- cados na década de 1970. Ramirez-Rosado e Bernal-Agustin (1998) apresentam revisões bibli- ográficas detalhadas dos trabalhos realizados sobre o tema. Existe uma série de abordagens interessantes para formular e resolver o problema de PESD. Os trabalhos citados em Ponnavaikko, Rao e Venkata (1987) e Gomez et al. (2004) abordam diferentes aspectos, desde a minimização de perdas de potência e custos de construção de ramos e subestações. Ramirez-Rosado e Bernal-Agustin (1998) adotaram uma abordagem de modelagem do PESD como um problema de programação não linear inteira mista (PNLIM), visando reduzir custos operacionais e de investimento, enquanto atendem a várias restrições técnicas, como quedas de tensão e limites de fluxo permitidos nos ramos, bem como os limites de potência das subestações e as duas leis de Kirchhoff. Por outro lado, Nara et al. (1992) e 20 Goswami (1997), focam na localização e capacidade ótimas dos ramos de distribuição, levando em consideração a demanda das barras e subestações em diferentes períodos de planejamento, o que é crucial para uma expansão eficiente e sustentável do sistema. Em Agustín (1998) e Cossi et al. (2012) resolve-se o problema de PESD considerando no planejamento a construção e ampliação de subestações, construção e recondutoramento de ramos, além da alocação de chaves seccionadoras. Na função objetivo consideram os custos de instalação e operação, os custos associados à confiabilidade do sistema através da energia não fornecida. Por outro lado, em Gomez et al. (2004) o problema de PESD é modelado como um problema de PNLIM. No modelo considera-se a construção de ramos e subestações e a função objetivo está sujeita a custos operacionais e restrições técnicas. Ambas as abordagens visam otimizar o planejamento do SDEE, considerando diferentes fatores. A escolha entre os métodos pode depender das especificidades do problema em questão e das prioridades em termos de custo, confiabilidade e eficiência operacional do sistema elétrico. O PESD é uma análise importante no setor de energia elétrica, pois garante que a rede de distribuição possa responder eficaz e economicamente às exigências futuras. O planejamento implica a elaboração de um plano de expansão otimizado para diferentes períodos, conside- rando os investimentos iniciais e os custos operacionais futuros. Além disso, requer uma análise detalhada dos dados do sistema e das projeções de demanda, para determinar o momento e a forma mais adequados para expandir a infraestrutura da rede. Assim, tendo em conta as previ- sões existentes, é viável identificar onde deverão ser construídas as subestações e ramos, a quantidade que as subestações podem ser reforçadas, bem como as possibilidades de alteração das fontes de abastecimento existentes, e a alocação de reguladores de tensão. Deste modo, garante-se que o sistema proporcione um desempenho ótimo e confiável, capaz de satisfazer o crescimento previsto da demanda, ao mesmo tempo que se minimizam os custos associados à expansão e operação da rede elétrica ao longo do período de planejamento (Ault; Foote; Mcdonald, 2002) e (Willis, 2004). O modelo de programação linear inteira mista (PLIM) proposto em Hincapié, Granada e Gallego (2005), tem como objetivo principal otimizar o problema de planejamento, resol- vendo o modelo proposto de redes de distribuição elétrica. Neste modelo analisa-se a localiza- ção e o dimensionamento das novas subestações, a possibilidade de alteração ou expansão das subestações existentes, a escolha dos condutores para novos ramos, recondutoramento dos ra- mos atuais, as capacidades máximas das subestações, as restrições de radialidade do sistema, as quedas de tensão aceitáveis nos pontos de conexão, e equilíbrio nodal da rede. Ao integrar 21 todas essas ações de planejamento e restrições no modelo, procura-se identificar soluções que potencializem o desempenho da rede dentro dos parâmetros e condições estabelecidos. No artigo, Lotero e Contreras (2011), propõem uma abordagem para enfrentar o desafio do planejamento em vários horizontes de planejamento de uma rede de distribuição elétrica, utilizando um modelo de PLIM. O principal objetivo desta abordagem é minimizar os custos associados à construção ou reforço de subestações, bem como a manutenção e operação geral da rede elétrica. Em cada barra, o modelo leva em consideração três níveis de carga e duas alternativas de investimento para cada recurso adicionado, reforçado ou substituído. Conside- ram também restrições técnicas, como queda de tensão e necessidade de manutenção da radia- lidade da rede, garantindo que as soluções propostas sejam tecnicamente viáveis. Índices de confiabilidade e custos associados são calculados para cada solução. Os resultados obtidos per- mitem encontrar uma variedade de soluções ótimas que consideram aspectos tanto técnicos como econômicos, permitindo ao planejador do sistema analisar e escolher uma das soluções que melhor se adapte às necessidades específicas do sistema em questão, particularmente a confiabilidade. Em Lavorato et al. (2012), apresenta-se um modelo matemático de PNLIM, desenvol- vido para resolver de forma eficiente problemas de planejamento em redes de distribuição, li- dando com as complexidades associadas a problemas de expansão em sistemas radiais, incor- porando restrições de radialidade na estrutura de otimização. Tais restrições melhoram a otimi- zação do sistema de distribuição, assegurando que as soluções estejam alinhadas com a topolo- gia radial. Esta abordagem não só simplifica o processo de resolução de problemas, mas tam- bém garante que as soluções sejam práticas, eficientes e alinhadas com as realidades operacio- nais dos sistemas de distribuição. Os resultados são obtidos através de um algoritmo não linear de ramificação e delimitação. Em Sahoo, Ganguly e Das (2012), apresenta-se uma abordagem de planejamento mul- tiobjetivo destinada a solucionar problemas em SDEE. Essa abordagem foi projetada para mi- nimizar os custos totais de instalação e operação e, ao mesmo tempo, maximizar a confiabili- dade da rede. A otimização é realizada em duas etapas: a primeira etapa concentra-se na otimi- zação da estrutura da rede e no estado das chaves de manobras. Isto envolve identificar a con- figuração ideal da rede, abrangendo o posicionamento e o número de alimentadores e chaves de secionamento, com o objetivo de encontrar um equilíbrio entre custo e confiabilidade do sistema. Durante a segunda fase, o foco muda para a otimização dos ramos de interconexão para melhorar ainda mais o desempenho da rede. Os ramos de interligação desempenham um papel crítico na melhoria da confiabilidade do sistema, fornecendo rotas alternativas para o 22 fluxo de eletricidade, particularmente benéficas em situações de falha do sistema. O algoritmo proposto é testado em diferentes sistemas de distribuição e depois comparado com diferentes topologias de vizinhança para avaliar sua eficácia. Os resultados ilustram que a abordagem pro- posta é eficaz para o planejamento do sistema de distribuição, alcançando um equilíbrio entre custos e confiabilidade da rede. Para resolver o problema de seleção da bitola do condutor e recondutoramento ótimo em sistemas de distribuição radial, Franco et al. (2013) propõem um modelo PLIM, desenvol- vido de forma eficiente para minimizar perdas de energia e custos de investimento, e para ava- liar a operação em estado estacionário do sistema utilizam expressões lineares. Para comparar o ponto de operação em regime permanente com o obtido pelo modelo proposto, utilizaram o método de varredura de fluxo de carga, que permite analisar o fluxo de energia em sistemas de distribuição elétrica. Os resultados mostram que o modelo proposto oferece vantagens em rela- ção a outros existentes na literatura, em termos de precisão e capacidade de representar a carga de forma mais realista. Além disso, permite atender a demanda de energia projetada e com o menor custo possível, atendendo às capacidades de condução de corrente e regulação de tensão. Em Jabr (2013), o problema PESD foi formulado utilizando programação quadrática inteira mista. Neste trabalho visa-se reduzir os custos operacionais e de capital associados à expansão da rede, além de melhorar a qualidade do serviço de energia. A solução foi obtida utilizando solvers para problemas de PLIM. No planejamento considera a seleção dos condu- tores e as rotas de construção dos ramos, bem como a construção e reforço de subestações que atendam à demanda e ao mesmo tempo atendam às limitações técnicas e físicas da rede recen- temente ampliada. Além disso, incorporam restrições para evitar a geração de laços na rede de distribuição, garantindo assim uma topologia de rede radial. A aplicabilidade e eficácia do mo- delo é validada através da sua aplicação em sistemas de teste de várias dimensões, demons- trando sua capacidade de fornecer soluções ótimas de forma eficaz. Na análise realizada em Franco, Rider e Romero (2014), utilizam uma abordagem ba- seada em um modelo de programação que combina restrições quadráticas inteiras mistas, tendo como principal ênfase resolver problemas estáticos. Por outro lado, em Pozos et al. (2014) pro- põem um modelo de programação linear binária mista. Em ambos os artigos visa-se resolver o problema do PESD através da construção e reforço de subestações, a capacidade e localização das novas subestações, a construção e recondutoramento de ramos, bem como da possível mo- dificação da topologia radial do sistema. O principal objetivo é reduzir custos de investimento e operação, levando em consideração as restrições operacionais, os limites de magnitude de corrente nos ramos, a potência aparente nas subestações e a configuração radial do sistema. Os 23 resultados obtidos nos experimentos com os sistemas 23 e 54 apoiam a eficácia dos modelos propostos. Em Tabares Pozos (2015) é proposta uma abordagem dinâmica para resolver o problema de expansão SDEE, utilizando modelos de programação cônica de segundo ordem inteira mista (PCSOIM) e PLIM. No planejamento consideram-se a construção e reforço de subestações existentes, bem como a construção e recondutoramento de ramos. Da mesma forma, em Tabares et al. (2016) propõe-se um modelo para redução de custos na expansão do SDEE com planeja- mento de longo prazo do PLIM. Este modelo utiliza linearização e aborda a construção de su- bestações, aumento de capacidade das subestações existentes, alocação de reguladores de ten- são, construção de ramos e o recondutoramento de ramos existentes no sistema inicial, bem como as possíveis alterações na topologia do sistema. Por outro lado, um modelo de PNLIM é considerado em Macedo e Romero (2016) para resolver o problema de PESD. O objetivo foi determinar o melhor plano dentro da estrutura de planejamento do sistema elétrico e a técnica proposta foi aplicada a um sistema de 54 barras, alcançando uma solução viável para o pro- blema. Os artigos citados acima propõem métodos para melhorar a expansão do SDEE, com o objetivo de otimizar custos e melhorar a eficiência do sistema. Para calcular os índices de confiabilidade de redes em modelos de distribuição com res- trições de confiabilidade, Muñoz-Delgado, Contreras e Arroyo (2018) apresentam uma nova perspectiva baseada em técnicas de otimização. Em vez de utilizar a simulação tradicional, na programação linear considera-se as topologias da rede como variáveis de decisão em um pro- cesso de otimização, permitindo encontrar índices equivalentes. A contribuição mais significa- tiva envolve o desenvolvimento de um método de programação linear para avaliar a confiabili- dade de um sistema de distribuição. Ao descrever a topologia da rede por meio da otimização, esse método garante precisão matemática, propriedades de convergência comprovadas e quali- dade da solução, permitindo que abordagens não heurísticas incorporem a avaliação de confia- bilidade no planejamento do sistema de distribuição e nos modelos operacionais. Em Munoz-Delgado, Contreras e Arroyo (2018), apresenta-se um modelo PLIM que integra confiabilidade ao problema de PESD multiestágio. Esta abordagem utiliza variáveis de decisão para descrever a estrutura da rede e determinar a melhor alternativa, localização e tempo de instalação dos ativos propostos, considerando critérios econômicos e de confiabilidade. A avaliação da confiabilidade centra-se na estimativa da energia esperada não fornecida, inclu- indo a análise do possível impacto de falhas e interrupções na rede elétrica. Esta medição é essencial para avaliar o desempenho do sistema sob diversas condições operacionais e cenários de falha. Os resultados obtidos na simulação demonstram a eficácia da abordagem proposta. A 24 integração da confiabilidade como critério explícito no planejamento da expansão permite não só otimizar o investimento em infraestruturas elétricas, mas também reforçar a capacidade do sistema em manter a continuidade do serviço de fornecimento elétrico em caso de imprevistos. Com o objetivo de maximizar a utilidade e satisfazer a demanda prevista do sistema, Kaewmamuang et al. (2019) propõem uma metodologia para otimizar a expansão de subesta- ções de distribuição em várias fases. A abordagem proposta determina a localização, capaci- dade e cronograma de construção ideais vinculados às subestações. A metodologia leva em consideração uma série de fatores técnicos e operacionais, como a queda de tensão, a estrutura radial da rede e a capacidade de expansão e operação, que garantem uma rede robusta e efici- ente. O método proposto usa variáveis binárias para estabelecer a conexão entre pontos de re- carga e subestações, e variáveis inteiras para estabelecer a capacidade de expansão das subes- tações, encontrando assim soluções dentro das limitações e restrições estabelecidas. No artigo Bosisio et al. (2021), apresenta-se uma metodologia para enfrentar os desafios associados ao PESD utilizando uma abordagem baseada no modelo PLIM. O objetivo é projetar uma rede que otimize a eficiência econômica quanto à confiabilidade do sistema sob diversas condições operacionais. A estratégia incorpora limitações tanto na topologia quanto na parte elétrica, juntamente com um índice de risco que tem como principal objetivo maximizar a con- fiabilidade do sistema elétrico. A formulação matemática inclui restrições relacionadas a ramos e subestações. Estas restrições são essenciais para garantir que a rede projetada seja capaz de atender aos requisitos de carga esperados e aos padrões de segurança operacional, minimizando ao mesmo tempo os custos associados à expansão e manutenção do sistema. A ideia de abordar em conjunto a rede de média tensão (MT) e baixa tensão (BT) com o propósito de reduzir custos e investimentos é extremamente relevante, dado que ambas as redes estão interligadas e as suas eficiências são interdependentes. Em Rupolo et al. (2021), propõem um método para abordar o planejamento de redes de distribuição elétrica de grande escala, abrangendo redes de MT e BT através do uso de técnicas computacionais. A formulação matemática centra-se na alocação estratégica de subestações e ramos de MT e BT. Da mesma forma, no planejamento considera-se as perdas de energia nos cabos e subestações de distribui- ção, bem como a confiabilidade do sistema. Os resultados numéricos mostram que a metodo- logia proposta é capaz de encontrar soluções eficazes que garantam a redução dos custos asso- ciados ao planejamento. No artigo Jooshaki et al. (2022), propõe-se um modelo PLIM para integrar explicita- mente a avaliação de confiabilidade no planejamento de expansão em vários estágios de redes 25 de distribuição. A metodologia oferece uma formulação que incorpora a avaliação da confiabi- lidade, abordando os impactos das interrupções de manobras, da operação radial e dos esquemas de incentivo à confiabilidade, integrando-os diretamente nas variáveis de otimização. Esta abor- dagem PLIM é formulada com um conjunto reduzido de variáveis e restrições, garantindo de- sempenho eficiente dos algoritmos e reduzindo custos computacionais significativos sem com- prometer a precisão da solução. Os custos associados à confiabilidade são considerados com base em esquemas de incentivos e perdas causadas por falta de fornecimento de energia durante cortes de energia aos clientes. Como parte do estudo, os testes foram aplicados em redes de diferentes dimensões. Em Rastgou e Hosseini-Hemati (2022) propõe-se uma abordagem de otimização em dois níveis para o planejamento integrado de redes de distribuição de MT e BT, considerando variações na demanda. No modelo de dois níveis proposto, na fase superior busca-se minimizar o investimento e o custo operacional da rede de MT, o que envolve a tomada de decisões estra- tégicas sobre a localização e capacidade das subestações de distribuição e alimentadores de MT para satisfazer a demanda de forma eficiente. Por outro lado, no nível inferior procura-se reduzir os custos de investimento e de funcionamento da rede BT tendo em conta as perdas de potência. A solução para o problema foi encontrada através de um algoritmo genético de alta qualidade, cujos resultados demonstram a eficácia do modelo proposto, que leva a melhorias na eficiência e rentabilidade das redes de distribuição elétrica. No artigo, Tabares et al. (2022), apresenta-se um modelo matemático para resolver o problema de PESD multiestágio, onde a confiabilidade e a radialidade da rede são explicita- mente consideradas. Neste modelo visa-se minimizar o custo total de expansão da subestação, que inclui tanto os custos de investimento como os custos de operação, considerando o impacto da confiabilidade nesses custos. Uma das principais contribuições reside na inclusão explícita de uma métrica de confiabilidade, denominada energia não fornecida esperada, através do de- senvolvimento de expressões matemáticas na formulação do problema de planejamento. Além disso, na abordagem proposta leva-se em conta, com precisão, as potências ativa e reativa, uti- lizando uma aproximação linear por partes. O problema de otimização resultante foi formulado como um problema PLIM, que permite encontrar soluções ótimas. Os resultados mostram a eficácia da metodologia proposta, oferecendo soluções de alta qualidade com um esforço com- putacional razoável, o que gera planos de expansão mais econômicos que, ao mesmo tempo, melhoram a confiabilidade do sistema. 26 1.1.2 Revisão bibliográfica considerando heurísticas e meta-heurísticas A exploração de abordagens alternativas surge como resposta a dilemas altamente com- plicados que desafiam a abordagem convencional, sendo computacionalmente demorados ou mesmo inatingível encontrar uma solução ótima em um tempo razoável. Nesta revisão, são analisadas pesquisas que detalham e contrastam diferentes estratégias heurísticas e meta-heu- rísticas, avaliando sua eficácia em diversas aplicações. São abordadas conceitos-chaves, como navegação no espaço de busca e exploração de soluções. Para encontrar a solução para o problema de planejamento de redes de distribuição, que é definido como um problema de programação não linear binário misto altamente complexo, Lavorato et al. (2009) apresentam uma técnica de otimização apresentada como um algoritmo heurístico construtivo (AHC). O algoritmo busca encontrar progressivamente uma solução de alta qualidade adicionando gradualmente ramos ou subestações à rede, usando um índice de sensibilidade. O índice de sensibilidade é calculado relaxando as variáveis de decisão binárias, tratando-as posteriormente como variáveis contínuas. O principal objetivo é reduzir os custos totais, que incluem tanto os custos de construção e operação de ramos e subestações como os custos associados à perda de potência ativa nos ramos. A abordagem proposta abrange uma estratégia de ramificação destinada a prevenir situações em que as operações não sejam viáveis, bem como uma estratégia de melhoria local. Os resultados do estudo indicam a capacidade do método em identificar um plano de expansão ideal para redes de distribuição que resulte em custos totais mais baixos em comparação com outras abordagens. O problema PESD apresentado em Souza (2011) aborda a construção e recondutora- mento de ramos, construção e reforço de subestações elétricas, considerando os custos de cons- trução e operação ao longo de um horizonte de planejamento. A abordagem utilizada para en- frentar este desafio envolve a implementação de uma meta-heurística de busca em vizinhança variável (VNS), na sua versão VND (variable neighborhood descente). Esta técnica proporci- ona a capacidade de avaliar diversas configurações em diferentes estruturas vizinhas, permi- tindo uma análise detalhada de custo-benefício no sistema. Além disso, para fornecer um ponto de partida de qualidade para o VNS empregaram um AHC. Este AHC demonstra capacidade de identificar soluções viáveis de alta qualidade, melhorando assim o desempenho geral da meta- heurística. Os resultados obtidos através desta metodologia revelam topologias radiais, sendo que cada topologia radial está ligada a uma subestação. 27 No trabalho de Pereira Junior et al. (2014) propõe-se um algoritmo de busca tabu mul- tiobjetivo para resolver o problema de planejamento, em várias fases, de um sistema de distri- buição, formulado como um problema de PNLIM multiobjetivo. A função objetivo é composta pelos custos de investimento, de operação e pela confiabilidade considerando as restrições físi- cas e técnicas. Esta formulação considera a construção de novas subestações, o aumento da capacidade das subestações existentes, a construção e recondutoramento de ramos, a alocação de seccionadores, e a construção de ramos de ligação. A confiabilidade do sistema é avaliada pela energia não fornecida em situação de contingência, utilizando o critério 𝑛 − 1. Durante o processo de restabelecimento das cargas afetadas na rede de distribuição devido a fachas ou manutenção do sistema, é possível avaliar a energia não fornecida através da rede. Para o res- tabelecimento, considera-se a reconfiguração de ramos e a utilização de ramos de ligação à rede. Apresentara-se os resultados obtidos para o problema na simulação de um sistema de 54 barras. Na literatura, o foco principal do planejamento da expansão dos sistemas de distribuição está nos sistemas de MT. Existe pouca pesquisa sobre planejamento de sistemas de BT e siste- mas integrados de MT/BT. Rupolo et al. (2017) apresentam uma abordagem matemática abran- gente para o planejamento de redes de distribuição considerando os sistemas de MT e BT. O modelo é formulado como um problema de PNLIM que procura reduzir os custos de investi- mento relacionados com a construção de novos ramos de BT, bem como a substituição de ramos e a construção e o aumento de capacidade de subestações existentes. Os custos de operação e manutenção são representados pelas perdas causadas nos ramos BT e subestação, e pela confi- abilidade do sistema refletida no custo de energia não distribuída. Quanto à codificação topo- lógica do problema, baseia-se na teoria de grafos conhecida na literatura como codificação de profundidade de barra. O modelo matemático é resolvido pelo método meta-heurístico GVNS (general variable neighborhood search), que possibilita explorar o espaço de busca utilizando critérios de intensificação e diversificação. A solução encontrada permite determinar a capaci- dade das subestações, a localização apropriada para construir novos ramos de BT com seus respectivos tipos de condutores, a substituição de ramos de BT e MT com os tipos de condutores correspondentes e a topologia radial do sistema de MT e BT. Em Possagnolo (2019) é proposto um modelo PCSOIM para resolver o problema PESD, abordando aspectos econômicos e de confiabilidade, além de incorporar a restauração do for- necimento após uma falha ou manutenção do sistema. Para resolver o problema, propõem-se duas abordagens alternativas: uma baseada em uma abordagem matemática tradicional a ser resolvida usando métodos exatos, e outra a meta-heurística VNS, utilizando uma técnica de 28 busca de vizinhança para encontrar uma solução aproximada sem garantia de ser ótima, mas com considerável eficiência em termos de tempo computacional. A formulação contempla a instalação de subestações, a melhoria das subestações existentes, a construção de ramos e o recondutoramento de ramos existentes, bem como a melhoria contínua do fornecimento elétrico para aumentar a confiabilidade. Os resultados mostram que a inclusão da restauração no plane- jamento leva a soluções com maiores custos operacionais e de investimento, porém, com índice de confiabilidade de rede superior às soluções disponíveis na literatura. De Almeida, Da Rocha e De Freitas (2021) apresentam uma metodologia para o PESD de média tensão através da aplicação de um AHC. Este algoritmo é implementado em um sis- tema com múltiplas partidas com o objetivo principal de fornecer energia aos consumidores atuais e futuros. Vários fatores, como minimização de custos de construção, redução de perdas de energia e otimização de perfis de tensão, são considerados na geração de um conjunto de topologias radiais viáveis. Além disso, para resolver este problema, empregam um modelo ma- temático não linear, e a solução é obtida gradual e progressivamente através de um processo iterativo. Em cada ciclo de iteração, utilizam um indicador de sensibilidade para determinar qual ramo construir, seguido da realização de testes computacionais para analisar e medir a eficácia e desempenho do algoritmo. Os resultados da simulação apresentam soluções viáveis e de alta qualidade, indicando que a abordagem proposta é eficaz para facilitar o planejamento de expansão de sistemas de distribuição de média tensão. 1.1.3 Revisão bibliográfica considerando uma topologia ligeiramente malhada A maioria dos sistemas de distribuição de energia elétrica são inicialmente projetados com topologia radial devido à sua simplicidade e menor custo de infraestrutura e, geralmente, são expandidos considerando apenas uma topologia radial. No entanto, esta metodologia apre- senta limitações em termos de confiabilidade e capacidade de restauração rápida em caso de falhas. Isto implica que cada carga é alimentada a partir de uma única subestação através de um único caminho. Porém, as redes de distribuição possuem uma estrutura em malha, de modo que existem múltiplas rotas para alimentar cada carga. Isto significa que se uma linha ou subestação falhar, a energia pode ser redirecionada através de outras rotas para manter o fornecimento aos consumidores afetados. Em Camargo, Lavorato e Romero (2013) apresentam uma abordagem inovadora para calcular o fluxo de potência em redes de energia que não estão completamente interligadas, particularmente aquelas com uma estrutura de malha fraca. Além disso, propõem um algoritmo 29 específico para resolver o problema PESD que é formulado como um problema de PNLIM. Para o planejamento são considerados múltiplas variáveis e restrições complexas, tais como a construção e recondutoramento de ramos para diferentes tipos de condutores, e a construção e reforço de subestações. A função objetivo tem como foco a minimização dos custos totais, in- cluindo os custos de construção e operação durante um horizonte de tempo específico. Além disso, introduzem estratégias para aumentar a diversidade e melhorar a qualidade das soluções obtidas, adaptando assim o algoritmo para resolver problemas de inviabilidade durante a busca, garantindo que a grande maioria das soluções geradas sejam viáveis e aplicáveis dentro da es- trutura do sistema de energia. A maioria dos estudos que se concentram em abordar o desafio de restaurar o forneci- mento de energia nos sistemas de distribuição utilizam uma abordagem baseada num modelo de corrente contínua. O objetivo deste modelo é identificar uma topologia radial que possa operar com segurança, mínimos custos de investimento e operação. Porém, Macedo, Ortega- Vazquez e Romero (2018) propõem um modelo de otimização PCSOIM para o PESD, em vez de usar um modelo de corrente contínua. O principal objetivo desta proposta é encontrar uma topologia malhada que possibilite restaurar a carga em caso de falhas ou manutenções, ao mesmo tempo que reduza os custos de expansão. Procura também identificar topologias radiais para o funcionamento do sistema que permitam reduzir a quantidade de energia não fornecida. Na análise foram consideradas ampliações de subestações, reforço das existentes e ampliação e recondutoramento de ramos. Para testar a eficácia deste modelo, foi aplicado a um sistema de 24 barras. Os resultados obtidos mostraram que, embora os custos tenham aumentado 28,82% em relação ao método tradicional, as cargas conseguiram ser restabelecidas. Em uma rede ma- lhada, alguns ramos operam como uma rede radial e outras permanecem desconectadas. Porém, em caso de falha ou manutenção, esses ramos podem ser conectados, para permitir que a subes- tação alimente a carga. Para abordar o problema de PESD, Lin, Hu e Song (2019) apresentam uma abordagem de programação matemática que adere ao critério 𝑁 − 1. Este critério sugere estratégias de investimento ideais para configurações de ramo fechado e ramo aberto. Ao utilizar este método é possível obter soluções ótimas globais de PESD sem comprometer sua escalabilidade. Para reduzir a complexidade do modelo, primeiro relaxam-se as restrições do critério 𝑁 − 1 e, em seguida, o problema é resolvido incorporando gradualmente restrições de contingência vincu- lante, que são identificadas usando o método matemático de PLIM. Embora o PESD tenha sido amplamente explorado nos últimos anos, a maioria dos estudos centrou-se exclusivamente em 30 soluções de planejamento radial, que normalmente não são aplicáveis aos sistemas de distribui- ção reais. Para melhorar a continuidade do fornecimento de energia, é essencial que o sistema de distribuição de energia real seja projetado basicamente como um ramo fechado baseado no critério 𝑁 − 1, permitindo a transferência de carga através da reconstrução da rede. Em Jooshaki et al. (2021), os autores apresentam formulações lineares destinadas a ava- liar a confiabilidade de sistemas de distribuição elétrica através do uso de variáveis topológicas, considerando interrupções de chaveamento. Os dois modelos matemáticos propostos estão su- jeitos às restrições de confiabilidade, uma para redes radiais e outra para redes malhadas que são operadas radialmente. Estas formulações se destacam por fornecer melhor qualidade de solução, maior eficiência computacional e melhor escalabilidade em comparação aos algorit- mos de otimização heurística existentes. Além disso, podem ser facilmente integrados em vá- rios estudos de planejamento e operação de sistemas de distribuição, fornecendo métricas de confiabilidade mais precisas. Os resultados obtidos em vários estudos de casos confirmam a precisão e escalabilidade da metodologia, apoiando a sua aplicabilidade e eficácia na melhoria do planejamento e operação de redes de distribuição elétrica. As redes de distribuição urbana são projetadas para serem altamente confiáveis, sendo construídas em malha e operando como um sistema radial, permitindo a restauração do forne- cimento de eletricidade nas áreas afetadas através de ramos de conexão, alternativas aplicadas após uma falha do sistema. Para encontrar uma solução mais adequada ao projetar estas redes de distribuição, costumam-se utilizar métodos heurísticos e de simulação, embora nem sempre assegurem uma otimização global. Nesse sentido, Li et al. (2021) apresentam um novo modelo de planejamento de expansão em várias etapas para redes de distribuição em malha, que incor- pora a avaliação de confiabilidade como restrições explícitas, o que influencia diretamente as decisões de investimento e confiabilidade. A restauração da carga após a falha entre alimenta- dores, considerando os requisitos de confiabilidade tanto para redes construídas em malha quanto para redes radialmente construídas, pode levar a uma redução no custo de investimento. 1.2 OBJETIVOS O objetivo principal desta dissertação é analisar e propor uma forma diferente de expan- dir um sistema de distribuição de energia elétrica, considerando uma nova estratégia para au- mentar a confiabilidade do sistema, maximizando o número de topologias radiais em uma rede ligeiramente malhada, viabilizando a reposição eficiente do fornecimento de energia em situa- ções de falhas e/ou manutenção. 31 Entre os objetivos secundários estão os seguintes: 1. Implementar e analisar um modelo de programação cônica de segundo ordem binário misto (PCSOBM) para abordar o PESD, contemplando a construção e o reforço de su- bestações, a construção de novos ramos e o recondutoramento dos ramos existentes; 2. Desenvolver um AHC para a obtenção de uma solução inicial de boa qualidade, a partir dos resultados obtidos com o modelo matemático PCSOBM, visando melhorar a confi- abilidade do sistema, através da inclusão estratégica de certos ramos, de modo que o PESD levemente malhado forme um grafo contendo o maior número possível de topo- logias radiais; 3. Desenvolver uma meta-heurística VNS nas suas versões VND e BVNS, com o intuito primordial de aprimorar os resultados alcançados pelo AHC. 1.3 CONTRIBUIÇÕES Esta dissertação apresenta as seguintes contribuições: 1. Propor uma nova abordagem para aumentar a confiabilidade em um sistema de distri- buição, dividindo a estratégia de otimização em duas etapas (etapa determinística e etapa meta-heurística). 2. Possibilidade de incorporar um certo número ramos adicionais no sistema expandido com o intuito de melhorar a confiabilidade e manter o sistema em funcionamento em situações de falhas ou manutenções. 3. Desenvolvimento de uma topologia ligeiramente malhada do sistema para proporcionar maior flexibilidade e capacidade de enfrentar cenários de contingências, promovendo, assim, a resiliência do sistema elétrico. 1.4 ESTRUTURA DO TRABALHO O trabalho está estruturado da forma mostrada a seguir: Capítulo 1: Foi feita uma contextualização e revisão bibliográfica do problema PESD. Capítulo 2: Apresenta-se a formulação matemática de um modelo PCSOBM para o PESD, con- siderando a expansão e construção de subestações, assim como a construção e re- condutoramento de ramos cada um com seu respetivo tipo de condutor. No modelo considera-se apenas um horizonte de expansão e encontra a topologia radial ótima do sistema expandido. 32 Capítulo 3: Apresenta-se uma estratégia para adicionar ramos extras ao sistema radial expan- dido encontrado a partir da formulação matemática, de forma a encontrar uma to- pologia ligeiramente malhada com o maior número de topologias radiais existentes no sistema expandido e, portanto, melhorando a confiabilidade do sistema de dis- tribuição expandido. Capítulo 4: São apresentados e analisados os resultados obtidos pelo modelo matemático apre- sentado na primeira fase, e os resultados obtidos na segunda fase resultantes da aplicação dos ramos adicionais ao sistema expandido. Capítulo 5: Neste capítulo apresentam-se as conclusões e desenvolvimentos futuros. No Apêndice A, apresentam-se dados do sistema utilizado no teste realizado neste tra- balho. 33 2 MODELO MATEMÁTICO PARA O PROBLEMA DE PESD O problema de PESD apresentado neste trabalho é formulado como um modelo PCSOBM, no qual o modelo determina a melhor topologia radial para o funcionamento de um SDEE que foi expandido para atender às necessidades futuras em um horizonte de planejamento específico. A função objetivo do modelo, mostrada em (1), representa os custos de investimento e operação. O primeiro termo representa o custo das SE (custos de investimento), e o segundo termo corresponde ao custo associado aos ramos (custos de construção/recondutoramento que dependem do tipo de ramo e do tipo de condutor). A Variável 𝑤𝑖 é uma variável binária que assume o valor de 𝑤𝑖 = 1 quando a subestação na barra 𝑖 é construída ou reforçada, e, 𝑤𝑖 = 0, caso contrário; 𝑦𝑖𝑗,𝑎 é uma variável binária que assume o valor de 𝑦𝑖𝑗,𝑎 = 1 se um condutor do tipo 𝑎 for instalado no ramo 𝑖𝑗 e 𝑦𝑖𝑗,𝑎 = 0, caso contrário; e por último o parâmetro 𝑙𝑖𝑗 repre- senta o comprimento do ramo 𝑖𝑗 em km (Lavorato, 2010) e (Lavorato; Rider et al., 2010). minimizar ∑ 𝐶𝑖 𝑠𝑤𝑖 𝑖∈Ω𝑏| 𝑇𝑖 𝑏=1 + ∑ ∑ 𝐶𝑡𝑖𝑗,𝑎 𝑟𝑎 𝑙𝑖𝑗𝑦𝑖𝑗,𝑎 𝑎∈Ω𝑎𝑖𝑗∈Ω𝑐 , (1) As restrições que representam a operação em estado estacionário de um sistema de dis- tribuição radial são apresentadas de (2) a (15). Observa-se que as restrições (2)–(13), com ex- ceção da com exceção da (10) são representações lineares; por outro lado, as expressões (10) e (15), embora descrevam o mesmo, apresentam-se de maneira não linear devido à presença de termos quadráticos e produtos de duas variáveis. A restrição (2) e (6) representa o balanço de potência ativa e, (3) e (8) o balanço de potência reativa do sistema na barra 𝑖. As restrições (9) e (13), e (10) e (15) correspondem a restrições resultantes da aplicação da Lei das Tensões de Kirchhoff no sistema elétrico. A restrições (9) e (13) são usadas para calcular a queda de tensão no ramo 𝑖𝑗. As restrições (10) e (15) são restrições cônicas de segunda ordem que estabelecem a relação entre o fluxo de potência atual e reativa, o quadrado da magnitude da tensão (no final do ramo) e o quadrado da magnitude do fluxo de corrente no ramo 𝑖𝑗 (Franco; Rider; Romero, 2014). Entendendo que as expressões (2) e (3) simbolizam, cada uma, o equilíbrio entre as potências ativa e reativa nas barras, respectivamente. 34 ∑ ∑ 𝑃𝑗𝑖,𝑎 𝑎∈Ω𝑎𝑗𝑖∈Ω𝑐 − ∑ ∑ (𝑃𝑖𝑗,𝑎 + 𝑅𝑎𝑙𝑖𝑗𝐼𝑖𝑗,𝑎 𝑞𝑑𝑟) 𝑎∈Ω𝑎𝑖𝑗∈Ω𝑐 + 𝑃𝑖 𝑠 = 𝑃𝑖 𝐷 , ∀𝑖 ∈ Ω𝑏 (2) ∑ ∑ 𝑄𝑗𝑖,𝑎 𝑎∈Ω𝑎𝑗𝑖∈Ω𝑐 − ∑ ∑ (𝑄𝑖𝑗,𝑎 + 𝑋𝑎𝑙𝑖𝑗𝐼𝑖𝑗,𝑎 𝑞𝑑𝑟) 𝑎∈Ω𝑎𝑖𝑗∈Ω𝑐 + 𝑄𝑖 𝑠 = 𝑄𝑖 𝐷 , ∀𝑖 ∈ Ω𝑏 (3) Reformulando convenientemente a restrição (2), obtém-se a restrição (4): ∑ ∑ 𝑃𝑗𝑖,𝑎 𝑎∈Ω𝑎𝑗𝑖∈Ω𝑐 − ∑ ( ∑ 𝑃𝑖𝑗,𝑎 𝑎∈Ω𝑎 + 𝑙𝑖𝑗 ∑ 𝑅𝑎𝐼𝑖𝑗,𝑎 𝑞𝑑𝑟 𝑎∈Ω𝑎 ) 𝑖𝑗∈Ω𝑐 + 𝑃𝑖 𝑠 = 𝑃𝑖 𝐷 , ∀𝑖 ∈ Ω𝑏 (4) Onde: ∑ 𝑃𝑖𝑗,𝑎 𝑎∈Ω𝑎 = 𝑃𝑖𝑗 𝑡 ; 𝑙𝑖𝑗 ∑ 𝑅𝑎𝐼𝑖𝑗,𝑎 𝑞𝑑𝑟 𝑎∈Ω𝑎 = 𝑅𝐼2𝑖𝑗 𝑡 , ∀𝑖𝑗 ∈ Ω𝑐 (5) Ao substituir as restrições de (5) em (4), obtém-se a expressão (6): ∑ 𝑃𝑗𝑖 𝑡 𝑗𝑖∈Ω𝑐 − ∑ (𝑃𝑖𝑗 𝑡 + 𝑅𝐼2𝑖𝑗 𝑡 ) 𝑖𝑗∈Ω𝑐 + 𝑃𝑖 𝑠 = 𝑃𝑖 𝐷 , ∀𝑖 ∈ Ω𝑏 (6) De forma análoga à expressão (6), decorrem da formulação (3) as expressões matemá- ticas (7) e (8). ∑ 𝑄𝑖𝑗,𝑎 𝑎∈Ω𝑎 = 𝑄𝑖𝑗 𝑡 ; 𝑙𝑖𝑗 ∑ 𝑋𝑎𝐼𝑖𝑗,𝑎 𝑞𝑑𝑟 𝑎∈Ω𝑎 = 𝑋𝐼2𝑖𝑗 𝑡 , ∀𝑖𝑗 ∈ Ω𝑐 (7) ∑ 𝑄𝑗𝑖 𝑡 𝑗𝑖∈Ω𝑐 − ∑ (𝑄𝑖𝑗 𝑡 + 𝑋𝐼2𝑖𝑗 𝑡 ) 𝑖𝑗∈Ω𝑐 + 𝑄𝑖 𝑠 = 𝑄𝑖 𝐷 , ∀𝑖 ∈ Ω𝑏 (8) As restrições (9) e (10) correspondem às restrições resultantes da aplicação da Lei das Tensões de Kirchhoff no sistema elétrico. A restrição (9) é usada para calcular a queda de tensão no ramo 𝑖𝑗. A restrição (10) é uma restrição cônica de segunda ordem que estabelece a relação entre o fluxo de potência atual e reativa, o quadrado da magnitude da tensão (no final do ramo) e o quadrado da magnitude do fluxo de corrente no ramo 𝑖𝑗. 35 𝑉𝑖 𝑞𝑑𝑟 − 𝑉𝑗 𝑞𝑑𝑟 = ∑ [2(𝑅𝑎𝑃𝑖𝑗,𝑎 + 𝑋𝑎𝑄𝑖𝑗,𝑎)𝑙𝑖𝑗 + 𝑍𝑎 2𝑙𝑖𝑗 2 𝐼𝑖𝑗,𝑎 𝑞𝑑𝑟] 𝑎∈Ω𝑎 + 𝑏𝑖𝑗 , ∀𝑖𝑗 ∈ Ω𝑐 (9) 𝑉𝑗 𝑞𝑑𝑟 ∑ 𝐼𝑖𝑗,𝑎 𝑞𝑑𝑟 𝑎∈Ω𝑎 ≥ ( ∑ 𝑃𝑖𝑗,𝑎 𝑎∈Ω𝑎 ) 2 + ( ∑ 𝑄𝑖𝑗,𝑎 𝑎∈Ω𝑎 ) 2 , ∀𝑖𝑗 ∈ Ω𝑐 (10) Reescrevendo convenientemente a restrição (9), obtém-se surge a expressão (12): 𝑉𝑖 𝑞𝑑𝑟 − 𝑉𝑗 𝑞𝑑𝑟 = 2 (𝑙𝑖𝑗 ∑ 𝑅𝑎𝑃𝑖𝑗,𝑎 𝑎∈Ω𝑎 + 𝑙𝑖𝑗 ∑ 𝑋𝑎𝑄𝑖𝑗,𝑎 𝑎∈Ω𝑎 ) + 𝑙𝑖𝑗 2 ∑ 𝑍𝑎 2𝐼𝑖𝑗,𝑎 𝑞𝑑𝑟 𝑎∈Ω𝑎 + 𝑏𝑖𝑗 , ∀𝑖𝑗 ∈ Ω𝑐 (11) Onde: 𝑙𝑖𝑗 ∑ 𝑅𝑎𝑃𝑖𝑗,𝑎 𝑎∈Ω𝑎 = 𝑅𝑃𝑖𝑗 𝑡 ; 𝑙𝑖𝑗 ∑ 𝑋𝑎𝑄𝑖𝑗,𝑎 𝑎∈Ω𝑎 = 𝑋𝑄𝑖𝑗 𝑡 ; 𝑙𝑖𝑗 2 ∑ 𝑍𝑎 2𝐼𝑖𝑗,𝑎 𝑞𝑑𝑟 𝑎∈Ω𝑎 = 𝑍2𝐼2𝑖𝑗 𝑡 , ∀𝑖𝑗 ∈ Ω𝑐 (12) Substituindo a restrição (12) na restrição (11), obtém-se a formulação (13): 𝑉𝑖 𝑞𝑑𝑟 − 𝑉𝑗 𝑞𝑑𝑟 = 2(𝑅𝑃𝑖𝑗 𝑡 + 𝑋𝑄𝑖𝑗 𝑡 ) + 𝑍2𝐼2𝑖𝑗 𝑡 + 𝑏𝑖𝑗, ∀𝑖𝑗 ∈ Ω𝑐 (13) A partir da restrição (10), obtém-se as expressões em (14): 𝐼𝑞𝑑𝑟𝑖𝑗 𝑡 = ∑ 𝐼𝑖𝑗,𝑎 𝑞𝑑𝑟 𝑎∈Ω𝑎 ; 𝑃𝑖𝑗 𝑡 = ∑ 𝑃𝑖𝑗,𝑎 𝑎∈Ω𝑎 ; 𝑄𝑖𝑗 𝑡 = ∑ 𝑄𝑖𝑗,𝑎, 𝑎∈Ω𝑎 ∀𝑖𝑗 ∈ Ω𝑐 (14) Substituindo (14) em (10): 𝑉𝑗 𝑞𝑑𝑟𝐼𝑞𝑑𝑟𝑖𝑗 𝑡 ≥ 𝑃𝑖𝑗 𝑡 2 + 𝑄𝑖𝑗 𝑡 2 , ∀𝑖𝑗 ∈ Ω𝑐 (15) As formulações cônicas, apresentadas nas restrições (10) e (15), mostram o mesmo con- ceito, porém expresso de maneira distinta. Essas restrições, originalmente de igualdade, são transformadas em restrições cônicas ao serem convertidas em desigualdades com a finalidade de facilitar ao solver em encontrar a solução em menor tempo. A inclusão de (10) e (15) nos 36 modelos resultam em uma formulação mais manejável, em vez de lidar diretamente com o pro- blema sob a forma de restrições de igualdade, o que é mais difícil de resolver (Franco; Rider; Romero, 2014). As restrições (16) e (17) limitam a variável auxiliar 𝑏𝑖𝑗 em termos do estado operacional do ramo 𝑖𝑗. Ou seja, se o ramo estiver conectado, então 𝑏𝑖𝑗 = 0; caso contrário, 𝑏𝑖𝑗 é limitado por, 𝑉 2 − 𝑉2, que representa a queda de tensão no ramo. 𝑏𝑖𝑗 ≤ (𝑉 2 − 𝑉2) (1 − ∑ 𝑦𝑖𝑗,𝑎 𝑎∈Ω𝑎 ), ∀𝑖𝑗 ∈ Ω𝑐 (16) 𝑏𝑖𝑗 ≥ − (𝑉 2 − 𝑉2) (1 − ∑ 𝑦𝑖𝑗,𝑎 𝑎∈Ω𝑎 ), ∀𝑖𝑗 ∈ Ω𝑐 (17) Onde: 𝑠𝑤𝑖𝑗 = ∑ 𝑦𝑖𝑗,𝑎 𝑎∈Ω𝑎 , ∀𝑖𝑗 ∈ Ω𝑐 (18) A restrição (18) determina que se 𝑠𝑤𝑖𝑗 = 1, um condutor de tipo 𝑎 será instalado nesse ramo 𝑖𝑗; entretanto, caso 𝑠𝑤𝑖𝑗 = 0, nenhum tipo de condutor será instalado nesse ramo 𝑖𝑗. Substituindo a restrição (18) em (16) e (17), obtém-se a restrição (19): |𝑏𝑖𝑗| ≤ (𝑉 2 − 𝑉2) (1 − 𝑠𝑤𝑖𝑗 ), ∀𝑖𝑗 ∈ Ω𝑐 (19) Os limites para a magnitude da tensão são definidos por (20). A restrição (21) estabelece os limites para a magnitude da corrente do ramo 𝑖𝑗, relacionados a cada tipo de condutor e seu estado operacional (conectado ou desconectado). 𝑉2 ≤ 𝑉𝑖 𝑞𝑑𝑟 ≤ 𝑉 2 , ∀𝑖 ∈ Ω𝑏 (20) 𝐼𝑖𝑗,𝑎 𝑞𝑑𝑟 ≤ 𝐼𝑎 2 𝑦𝑖𝑗,𝑎, ∀𝑖𝑗 ∈ Ω𝑐, 𝑎 ∈ Ω𝑎 (21) 37 As restrições (22) e (23) mostram que os valores máximos (𝑉 𝐼𝑎) e o estado operacional de cada ramo impõem restrições aos módulos do fluxo de potência ativa e reativa. Adicional- mente, essas restrições aprimoram a eficiência computacional e a qualidade das soluções alcan- çadas. |𝑃𝑖𝑗,𝑎| ≤ 𝑉 𝐼𝑎𝑦𝑖𝑗,𝑎, ∀𝑖𝑗 ∈ Ω𝑐, 𝑎 ∈ Ω𝑎 (22) |𝑄𝑖𝑗,𝑎| ≤ 𝑉 𝐼𝑎𝑦𝑖𝑗,𝑎, ∀𝑖𝑗 ∈ Ω𝑐, 𝑎 ∈ Ω𝑎 (23) A restrição (24) representa a condição de que pelo menos um novo ramo deve ser cons- truído e formado por pelo menos uma barra de carregamento. Esta restrição não é necessária para definir o conjunto de soluções viáveis, mas é incluída no modelo para reduzir o esforço computacional necessário para sua solução. ∑ ∑ 𝑦𝑖𝑗,𝑎 𝑎∈Ω𝑎𝑖𝑗∈Ω𝑐|(𝑖=𝑘||𝑗=𝑘) ≥ 1, ∀ 𝑘 ∈ Ω𝑏| 𝑇𝑘 𝑏=0 (24) Ao substituir a restrição (18) na restrição (24), chegamos à expressão (25). ∑ 𝑠𝑤𝑖𝑗 𝑖𝑗∈Ω𝑐|(𝑖=𝑘||𝑗=𝑘) ≥ 1, ∀ 𝑘 ∈ Ω𝑏| 𝑇𝑘 𝑏=0 (25) Como o quadrado da potência aparente é igual à soma do quadrado da potência real e da potência reativa fornecida pela subestação, tem-se que o quadrado da potência aparente for- necida pela subestação é limitado por (26). O lado direito da expressão (26) representa a capa- cidade máxima inicial mais a capacidade máxima adicional proporcionada pela construção e/ou ampliação da subestação. (𝑃𝑖 𝑆) 2 + (𝑄𝑖 𝑆) 2 ≤ 𝑆𝑖 2 + (𝑆𝑖𝑆𝑖 𝑔𝑛 + 𝑆𝑖 𝑔𝑛2 ) 𝑤𝑖, ∀𝑖 ∈ Ω𝑏| 𝑇𝑖 𝑏=1 (26) A restrição de radialidade apresentada em (27), junto com as restrições de balanço de potência (2) e (3), garantem que, ao final do processo iterativo, não haja interconexão entre duas ou mais subestações. A restrição (27) estabelece que o número 𝛼 − 𝛽 de ramos existentes e em 38 construção deve ser igual ao número de 𝛼 − 𝛽 barras no sistema menos o número de subesta- ções, formando uma rede radial para cada subestação construída. Onde 𝛼 representa o número de barras no SDEE e 𝛽 = ∑ 𝑇𝑖 𝑏 𝑖∈Ω𝑏 o número total de subestações no SDEE. ∑ ∑ 𝑦𝑖𝑗,𝑎 𝑎∈Ω𝑎𝑖𝑗∈Ω𝑐 = 𝛼 − 𝛽, (27) Substituindo a restrição (18) na restrição (27) obtém-se (28). ∑ 𝑠𝑤𝑖𝑗 𝑖𝑗∈Ω𝑐 = 𝛼 − 𝛽, (28) Uma abordagem alternativa para garantir a radialidade na execução de sistemas de dis- tribuição é descrita pelas restrições (29), (30) e (31) (Jabr; Singh; Pal, 2012). Variáveis binárias auxiliares, 𝑥𝑖𝑗 e 𝑥𝑗𝑖, são atribuídas a cada ramo 𝑖𝑗, indicando a direção do fluxo no ramo. O estado operacional no ramo 𝑖𝑗 é representado por 𝑠𝑤𝑖𝑗, de modo que se 𝑠𝑤𝑖𝑗 = 1, então o ramo 𝑖𝑗 está ligado ao sistema, e desconectado em caso contrário. 𝑥𝑖𝑗 + 𝑥𝑗𝑖 = 𝑠𝑤𝑖𝑗, ∀𝑖𝑗 ∈ Ω𝑐 (29) ∑ 𝑥𝑖𝑗 𝑖𝑗∈Ω∪ ≤ 1, ∀𝑖 ∈ Ω𝑏| 𝑇𝑖 𝑏=1 (30) ∑ 𝑥𝑖𝑗 𝑖𝑗∈Ω∪ = 1, ∀𝑗 ∈ Ω𝑏| 𝑇𝑗 𝑏=0 (31) A restrição (29) estabelece que somente uma direção é viável para o fluxo no ramo 𝑖𝑗 se 𝑠𝑤𝑖𝑗 = 1, e se 𝑠𝑤𝑖𝑗 = 0, então ambas variáveis binarias auxiliares são iguais a zero para o ramo 𝑖𝑗. Se o fluxo é da barra 𝑗 para a barra 𝑖 (sendo a barra 𝑗 mais próxima da subestação), então 𝑥𝑗𝑖 = 1 se o fluxo é de 𝑖 para 𝑗 (com a barra 𝑖 mais próxima da subestação). A restrição (30) determina que as barras de passagem podem ou não ser conectadas à rede, enquanto a restrição (31) assegura que para cada barra de carga 𝑖 existe apenas um fluxo de entrada, sendo que todos os demais devem deixar essa barra. 39 O modelo PCSOBM para o PESD apresentado em (1) - (31) é resumido e apresentado nas expressões (32) - (56): minimizar ∑ 𝐶𝑖 𝑠𝑤𝑖 𝑖∈Ω𝑏| 𝑇𝑖 𝑏=1 + ∑ ∑ 𝐶𝑡𝑖𝑗,𝑎 𝑟𝑎 𝑙𝑖𝑗𝑦𝑖𝑗,𝑎 𝑎∈Ω𝑎𝑖𝑗∈Ω𝑐 , (32) Sujeito a: ∑ 𝑃𝑗𝑖 𝑡 𝑗𝑖∈Ω𝑐 − ∑ (𝑃𝑖𝑗 𝑡 + 𝑅𝐼2𝑖𝑗 𝑡 ) 𝑖𝑗∈Ω𝑐 + 𝑃𝑖 𝑠 = 𝑃𝑖 𝐷 , ∀𝑖 ∈ Ω𝑏 (33) ∑ 𝑄𝑗𝑖 𝑡 𝑗𝑖∈Ω𝑐 − ∑ (𝑄𝑖𝑗 𝑡 + 𝑋𝐼2𝑖𝑗 𝑡 ) 𝑖𝑗∈Ω𝑐 + 𝑄𝑖 𝑠 = 𝑄𝑖 𝐷 , ∀𝑖 ∈ Ω𝑏 (34) 𝑉𝑖 𝑞𝑑𝑟 − 𝑉𝑗 𝑞𝑑𝑟 = 2(𝑅𝑃𝑖𝑗 𝑡 + 𝑋𝑄𝑖𝑗 𝑡 ) + 𝑍2𝐼2𝑖𝑗 𝑡 + 𝑏𝑖𝑗, ∀𝑖𝑗 ∈ Ω𝑐 (35) ∑ 𝑃𝑖𝑗,𝑎 𝑎∈Ω𝑎 = 𝑃𝑖𝑗 𝑡 ; 𝑙𝑖𝑗 ∑ 𝑅𝑎𝐼𝑖𝑗,𝑎 𝑞𝑑𝑟 𝑎∈Ω𝑎 = 𝑅𝐼2𝑖𝑗 𝑡 , ∀𝑖𝑗 ∈ Ω𝑐 (36) ∑ 𝑄𝑖𝑗,𝑎 𝑎∈Ω𝑎 = 𝑄𝑖𝑗 𝑡 ; 𝑙𝑖𝑗 ∑ 𝑋𝑎𝐼𝑖𝑗,𝑎 𝑞𝑑𝑟 𝑎∈Ω𝑎 = 𝑋𝐼2𝑖𝑗 𝑡 , ∀𝑖𝑗 ∈ Ω𝑐 (37) 𝑙𝑖𝑗 ∑ 𝑅𝑎𝑃𝑖𝑗,𝑎 𝑎∈Ω𝑎 = 𝑅𝑃𝑖𝑗 𝑡 ; 𝑙𝑖𝑗 ∑ 𝑋𝑎𝑄𝑖𝑗,𝑎 𝑎∈Ω𝑎 = 𝑋𝑄𝑖𝑗 𝑡 ; 𝑙𝑖𝑗 2 ∑ 𝑍𝑎 2𝐼𝑖𝑗,𝑎 𝑞𝑑𝑟 𝑎∈Ω𝑎 = 𝑍2𝐼2𝑖𝑗 𝑡 , ∀𝑖𝑗 ∈ Ω𝑐 (38) 𝑉𝑗 𝑞𝑑𝑟𝐼𝑞𝑑𝑟𝑖𝑗 𝑡 ≥ 𝑃𝑖𝑗 𝑡 2 + 𝑄𝑖𝑗 𝑡 2 , ∀𝑖𝑗 ∈ Ω𝑐 (39) 𝐼𝑞𝑑𝑟𝑖𝑗 𝑡 = ∑ 𝐼𝑖𝑗,𝑎 𝑞𝑑𝑟 𝑎∈Ω𝑎 ; 𝑃𝑖𝑗 𝑡 = ∑ 𝑃𝑖𝑗,𝑎 𝑎∈Ω𝑎 ; 𝑄𝑖𝑗 𝑡 = ∑ 𝑄𝑖𝑗,𝑎, 𝑎∈Ω𝑎 ∀𝑖𝑗 ∈ Ω𝑐 (40) |𝑏𝑖𝑗| ≤ (𝑉 2 − 𝑉2) (1 − 𝑠𝑤𝑖𝑗 ), ∀𝑖𝑗 ∈ Ω𝑐 (41) 40 𝑠𝑤𝑖𝑗 = ∑ 𝑦𝑖𝑗,𝑎 𝑎∈Ω𝑎 , ∀𝑖𝑗 ∈ Ω𝑐 (42) 𝑉2 ≤ 𝑉𝑖 𝑞𝑑𝑟 ≤ 𝑉 2 , ∀𝑖 ∈ Ω𝑏 (43) 𝐼𝑖𝑗,𝑎 𝑞𝑑𝑟 ≤ 𝐼𝑎 2 𝑦𝑖𝑗,𝑎, ∀𝑖𝑗 ∈ Ω𝑐, 𝑎 ∈ Ω𝑎 (44) |𝑃𝑖𝑗,𝑎| ≤ 𝑉 𝐼𝑎𝑦𝑖𝑗,𝑎, ∀𝑖𝑗 ∈ Ω𝑐, 𝑎 ∈ Ω𝑎 (45) |𝑄𝑖𝑗,𝑎| ≤ 𝑉 𝐼𝑎𝑦𝑖𝑗,𝑎, ∀𝑖𝑗 ∈ Ω𝑐, 𝑎 ∈ Ω𝑎 (46) ∑ 𝑠𝑤𝑖𝑗 𝑖𝑗∈Ω𝑐|(𝑖=𝑘||𝑗=𝑘) ≥ 1, ∀ 𝑘 ∈ Ω𝑏| 𝑇𝑘 𝑏=0 (47) (𝑃𝑖 𝑆) 2 + (𝑄𝑖 𝑆) 2 ≤ 𝑆𝑖 2 + (𝑆𝑖𝑆𝑖 𝑔𝑛 + 𝑆𝑖 𝑔𝑛2 ) 𝑤𝑖, ∀𝑖 ∈ Ω𝑏| 𝑇𝑖 𝑏=1 (48) ∑ 𝑠𝑤𝑖𝑗 𝑖𝑗∈Ω𝑐 = 𝛼 − 𝛽, (49) 𝑥𝑖𝑗 + 𝑥𝑗𝑖 = 𝑠𝑤𝑖𝑗, ∀𝑖𝑗 ∈ Ω𝑐 (50) ∑ 𝑥𝑖𝑗 𝑖𝑗∈Ω∪ ≤ 1, ∀𝑖 ∈ Ω𝑏| 𝑇𝑖 𝑏=1 (51) ∑ 𝑥𝑖𝑗 𝑖𝑗∈Ω∪ = 1, ∀𝑗 ∈ Ω𝑏| 𝑇𝑗 𝑏=0 (52) 𝑤𝑖 ∈ {0,1} ∀𝑖𝑗 ∈ Ω𝑏 (53) 𝑦𝑖𝑗,𝑎 ∈ {0,1} ∀𝑖𝑗 ∈ Ω𝑐, ∈ Ω𝑎 (54) 𝑠𝑤𝑖𝑗 ∈ {0,1} ∀𝑖𝑗 ∈ Ω𝑐 (55) 41 𝑥𝑖𝑗 ∈ {0,1} ∀𝑖𝑗 ∈ Ω∪ (56) O modelo de PCSOBM não é uma versão aproximada do modelo PNLIM, mas é equi- valente. Isto ocorre porque a ativação da restrição de desigualdade cônica (39) leva a uma so- lução equivalente quando se considera a restrição não linear. Em termos mais simples, a transi- ção de uma restrição não linear para uma restrição cônica é uma forma de relaxar o problema, pois em vez de resolver diretamente uma formulação com uma restrição mais complexa relaci- onada à igualdade, ela é substituída por uma formulação mais convexa que utiliza uma restrição de desigualdade, que ajuda a resolver o problema. 42 3 MELHORANDO A CONFIABILIDADE DO SISTEMA DE DISTRIBUIÇÃO A maioria das propostas de otimização da expansão do sistema de distribuição de ener- gia elétrica encontra uma topologia radial que otimiza os custos de operação e de expansão do sistema de distribuição para um horizonte de planejamento. Entretanto, os sistemas de distri- buição são construídos de forma ligeiramente malhada e, portanto, em operação normal, um conjunto de ramos opera formando uma topologia radial e outro conjunto de ramos, geralmente em número reduzido, devem permanecer desligados. Os ramos desligados permitem aumentar a confiabilidade do sistema de distribuição. Dessa forma, se um ramo ou um conjunto de ramos que se encontra em operação é desligado do sistema elétrico devido a uma falta, então os ramos normalmente desligados podem ser ligados em um processo de restauração. Dessa forma, os ramos construídos, e que normalmente permanecem desligados, podem ser usados em condi- ções especiais de faltas ou de manutenção programada e, portanto, o sistema tem maior confia- bilidade. Existem poucas propostas para expandir o sistema de distribuição de forma ligeiramente malhado e que apresente confiabilidade adequada. Neste trabalho, propõe-se usar um conceito para expandir o sistema de distribuição de energia elétrica para assumir a forma ligeiramente malhada. Dessa forma, a proposta de otimização assume a seguinte estrutura. 1. Inicialmente o sistema é expandido na forma tradicional encontrando a topologia radial ótima de operação como foi apresentado no capítulo anterior. 2. Escolhe-se um número 𝑝 de ramos adicionais que devem ser construídos e que devem per- manecer desligados em operação normal. 3. A hipótese de confiabilidade é de que um sistema de distribuição é mais confiável se um sistema ligeiramente malhado construído com a adição de 𝑝 ramos adicionais gera um grafo e esse grafo contém o maior número de topologias radiais. A hipótese de confiabilidade sugerida pode ser melhor explicada usando um exemplo. Por exemplo, supor um sistema de 33 barras onde se pretende construir 37 ramos. Uma certa proposta 𝐴 de expansão com 32 ramos formando uma topologia radial e 𝑝𝐴 = 5 ramos desli- gados pode ter 50.751 topologias radiais possíveis de operação. Outra proposta de expansão 𝐵, 43 formado por outro conjunto de 32 ramos formando a topologia radial e 𝑝𝐵 = 5 ramos desliga- dos pode ter 74.578 topologias radiais possíveis de operação. Nesse contexto, a proposta 𝐵 é melhor que a proposta 𝐴 porque quando acontece uma falta, a proposta 𝐵 tem maior possibili- dade de manter o sistema operando sem corte de carga porque tem um número maior de possi- bilidades de operação em topologia radial ligando ramos que normalmente se encontram desli- gados. Neste trabalho, a partir de uma topologia radial já encontrada usando uma técnica de otimização, pretende-se identificar um conjunto adicional de 𝑝 ramos que devem ser construí- dos junto com a topologia radial de forma que o conjunto de ramos construídos forme uma rede ligeiramente malhada. Uma rede ligeiramente malhada pode gerar um conjunto diferente de topologias radiais. Dessa forma, busca-se encontrar o conjunto de ramos que devem ser cons- truídos e permanecer desligados em operação normal de forma que o grafo que representa essa rede tenha o maior número possível de topologias radiais. Em resumo, dada uma topologia radial e conhecendo um conjunto de ramos 𝑅 que pode ser construído, pretende-se identificar um subconjunto de ramos de 𝑅, chamado de conjunto 𝑃 de cardinalidade 𝑝 de forma que o conjunto total de ramos construídos permita gerar o número máximo de topologias radiais. Esse processo de identificação é um problema de otimização que deve ser resolvido usando uma meta-heurística. 3.1 ESTRATÉGIA PARA ENCONTRAR O NÚMERO DE TOPOLOGIAS RADIAIS DE UM GRAFO CONEXO Um sistema de distribuição radial pode ser considerado um grafo conexo. Para um sis- tema de distribuição de energia elétrica malhado é possível encontrar o número de topologias radiais contidas no grafo desse sistema de distribuição radial. Esse cálculo pode ser realizado usando o teorema da matriz-árvore: Teorema da Matriz-Árvore: Seja 𝐺 um grafo conexo e 𝐿 a matriz laplaciana desse grafo. Nesse contexto, o número de árvores geradoras (topologias radiais) desse grafo 𝐺 é igual ao valor de qualquer cofator 𝑙𝑖𝑗 de 𝐿. A prova desse teorema pode ser encontrada em Macedo et al. (2018), e Harris, Hirst e Mossinghoff (2008). Esse teorema permite calcular o número exato de topologias radiais que existe em um sistema de distribuição. Pode-se ilustrar a aplicação desse teorema calculando o 44 número de topologias radiais diferentes que existem no sistema de 14 barras e 16 ramos mos- trados na Figura 1. Figura 1 – Sistema de 14 barras Fonte: (Civanlar; Grainger et al., 1988) Cada elemento da matriz 𝐿 é encontrado usando a seguinte relação: 𝑙𝑖𝑗 = { 𝑔𝑟𝑎𝑢 (𝑖) Se 𝑖 = 𝑗 −1 Se 𝑖 é diferente de 𝑗 e existe um ramo entre 𝑖 e 𝑗 0 em outro caso (57) onde grau(i) indica o grau da barra 𝑖, isto é, o número de ramos conectados à barra 𝑖. Para o sistema de 14 barras, mostrado na Figura 1, a matriz 𝐿 é mostrada na Figura 2. Figura 2 – Matriz laplaciana Fonte: (Macedo; Franco et al., 2018) 45 Para encontrar o número de topologias radiais do sistema de 14 barras, deve-se calcular o determinante da matriz 𝐿 modificada eliminando uma linha e uma coluna da matriz 𝐿. Assim, o número de topologias radiais se encontra da seguinte forma: 𝑀𝐿 = |𝐷𝑒𝑡(𝐿𝑀)| (58) Para a matriz 𝐿 mostrada na Figura 2, após eliminar a primeira linha e a primeira coluna da matriz 𝐿 se encontra facilmente 𝑀𝐿 = 190 o que significa que o no sistema de 14 barras e 16 ramos existem 190 topologias radiais diferentes. Para mostrar a ideia fundamental relacionada com o número de topologias radiais exis- tentes em um grafo, pode-se realizar uma pequena alteração no grafo do sistema de distribuição da Figura 1. Após retirar dois ramos e adicionar dois ramos novos, pode-se encontrar um novo grafo desse sistema mostrado na Figura 3. Figura 3 – Sistema de 14 barras modificado Fonte: Elaborada pela autora. Para o sistema de 14 barras, mostrado na Figura 3, a matriz 𝐿 é mostrada na Figura 4. Para a matriz 𝐿 mostrada na Figura 4, após eliminar a primeira linha e a primeira coluna da matriz 𝐿 se encontra facilmente 𝑀𝐿 = 232 o que significa que o no sistema de 14 barras e 16 ramos , da Figura 3, existem 232 topologias radiais diferentes. 46 Figura 4 – Matriz laplaciana do sistema modificado Fonte: Elaborada pela autora. Os exemplos ilustrativos, apresentados anteriormente, mostram que trocando de posição alguns ramos o número de topologias radiais existentes em um grafo conexo pode mudar. Dessa forma, para um grafo que tem o mesmo número de ramos, existe um grafo que apresenta a maior número de topologias radiais e, de acordo com a hipótese aventada, o sistema de distri- buição que apresenta essa topologia seria o que apresenta maior confiabilidade perante fenô- menos que desligam uma parte do sistema devido a problemas imprevistos ou de manutenção programada. A teoria apresentada para encontrar o número de topologias radiais diferentes exis- tentes em um grafo, deve ser usada para adicionar alguns ramos adicionais na topologia radial encontrada no capítulo anterior de forma que o sistema resultante seja uma topologia malhada com o maior número de topologias radiais que podem ser gerados desse grafo ligeiramente malhado. Para adicionar esses ramos adicionais, é necessário usar uma técnica de otimização que comece com um AHC para encontrar a solução inicial. Em seguida, as versões VND e BVNS da meta-heurística de busca em vizinhança variável (VNS) são empregadas para refinar a solu- ção gerada pelo AHC. As próximas seções irão detalhar essa meta-heurística e como ela pode ser implementada no contexto do PESD. 47 3.2 A META-HEURÍSTICA DE BUSCA EM VIZINHANÇA VARIÁVEL Uma meta-heurística é uma estratégia de busca através do espaço de busca de um pro- blema complexo. A busca é realizada através de transições no espaço de busca a partir de uma proposta de solução inicial ou de um conjunto de propostas de soluções iniciais. Nesse contexto, a diferença principal entre as diferentes meta-heurísticas é a estratégia usada para realizar as transições no espaço de busca. A meta-heurística VNS (variable neigborhood search) é apenas uma generalização da heurística SDH (steepest descent heuristic) que realiza um processo de busca através do espaço de busca usando um conjunto de estruturas de vizinhança de cardina- lidade variável. A cardinalidade de uma vizinhança é o número de vizinhos da proposta de so- lução corrente que pode ser calculada após a definição ou caracterização de vizinhança. Nesse aspecto fundamental, VNS é significativamente diferente de outras meta-heurísticas. A maioria das meta-heurísticas aceitam a degradação da proposta de solução corrente (ou do conjunto de soluções correntes) como uma estratégia para sair de uma solução ótima local. O algoritmo VNS não aceita essa possibilidade. O algoritmo VNS muda a vizinhança como uma forma de sair de soluções ótimas locais. Nesse processo, a proposta de solução cor- rente também é a incumbente o que não acontece com as outras meta-heurísticas. Assim, pode- se afirmar que o algoritmo VNS realiza um conjunto de transições no espaço de busca de um problema e em cada passo a transição é realizada para uma nova solução incumbente. Se no processo de busca encontra-se um ótimo local, então o algoritmo VNS muda de vizinhança para sair desse ótimo local e passar para a nova incumbente. Como uma consequência dessa estraté- gia, se o algoritmo VNS encontra o ótimo global, então a busca fica estagnada nesse ponto de ótimo global sem possibilidade de sair desse ponto. Esse tipo de comportamento não acontece com as outras meta-heurísticas. Deve-se observar que na heurística SDH também o processo de otimização não acontece uma degradação da função objetivo e, portanto, as transições são rea- lizadas de uma solução incumbente para uma nova solução incumbente. A estratégia do algoritmo VNS é inspirada na observação de três fatos importantes: • Fato 1: Um mínimo local em relação a uma estrutura de vizinhança não necessaria- mente é ótimo local em relação a outra estrutura de vizinhança. • Fato 2: O mínimo global é um ótimo local em relação a todas as possíveis estruturas de vizinhança. • Fato 3: Para muitos problemas o mínimo local em relação a uma estrutura de vizinhança tem muita informação comum em relação a outras estruturas de vizinhança. 48 A última observação é particularmente importante na formulação de um algoritmo VNS. A observação de caráter empírica implica que uma solução ótima local fornece informação im- portante em relação ao ótimo global, especialmente, se a solução ótima local for de excelente qualidade. Existe também a observação empírica de que as soluções ótimas locais geralmente estão concentradas em regiões especificas do espaço de busca. Se as soluções ótimas locais estivessem uniformemente distribuídas no espaço de busca todas as meta-heurísticas se torna- riam ineficientes. Portanto, se for encontrado um ótimo local da região em que se encontra o ótimo global, então uma meta-heurística tipo VNS tem grande chance de encontrar esse ótimo global. Por outro lado, se o ótimo global se encontra em outra região, então a única possibilidade de encontrar o ótimo global é implementar um processo de diversificação. Por esse motivo um equilíbrio entre intensificação e diversificação no processo de busca pode ser importante em uma meta-heurística. A meta-heurística VNS é apenas uma generalização da heurística SDH. Na heurística SDH, a partir de uma proposta de solução inicial, avaliam-se todas as propostas de solução vizinhas que são ordenadas por qualidade. Se a melhor proposta de solução vizinha é de melhor qualidade, então, deve-se realizar a transição para essa proposta de solução vizinha que se trans- forma na proposta de solução corrente. Em caso contrário, deve-se terminar o processo de oti- mização. A heurística SDH apresenta a seguinte forma: 1. Passo preliminar: Montar os dados do problema. Escolher uma forma de codificação de uma proposta de solução denominada de 𝑝. Identificar uma forma de avaliar a qualidade da função objetivo ou equivalente e denominada 𝑓(𝑝). Definir a estrutura de vizinhança a ser usada, o que caracteriza o espaço de busca. 2. Encontrar uma solução inicial 𝑝𝑜 que se transforma na solução corrente 𝑝𝑐. 3. Identificar e avaliar todas as soluções vizinhas da solução corrente 𝑝𝑐 e identificar a melhor solução vizinha 𝑝𝑏𝑒𝑠𝑡. 4. Se 𝑓(𝑝𝑏𝑒𝑠𝑡) < 𝑓(𝑝) então a melhor solução vizinha é melhor que a solução corrente e, portanto, fazer 𝑝𝑐 ← 𝑝𝑏𝑒𝑠𝑡 e voltar ao passo 3. Em caso contrário, pare o processo e a solução encontrada pela heurística SDH é 𝑝𝑐 (geralmente um ótimo local). Propõe-se mostrar que a versão VND da meta-heurística VNS é apenas uma generaliza- ção da heurística SDH. Existem várias formas de implementar o algoritmo VNS e, portanto, podem ser implementados uma família de algoritmos VNS. Nesta dissertação, implementa-se 49 apenas as versões VND e BVNS. As principais versões da meta-heurística VNS são as seguin- tes: • VND (Variable neighborhood descent). • RVNS (reduced variable neighborhood search). • BVNS (basic variable neighborhood search). • GVNS (general variable neighborhood search). Deve-se observar que o VND é essencialmente determinístico, assim como o SDH, o RVNS tem uma componente estocástica e as outras versões representam estratégias mais sofis- ticadas. A meta-heurística VND apresenta a seguinte forma: 1. Passo preliminar: Montar os dados do problema. Escolher uma forma de representar uma proposta de solução denominada de 𝑝. Identificar uma forma de avaliar a qualidade da função objetivo ou equivalente e denominada 𝑓(𝑝). Definir um conjunto de estruturas de vizinhança 𝑁𝑠, 𝑠 = 1, … , 𝑠𝑚𝑎𝑥 que devem ser usados no processo iterativo; 2. Encontrar uma solução inicial 𝑝𝑜 que se transforma na solução corrente 𝑝𝑐; 3. Fazer 𝑠 ← 1; 4. Identificar e avaliar todas as soluções vizinhas da solução corrente 𝑝𝑐 para o nível de vizinhança 𝑠. Identificar a melhor proposta de solução vizinha 𝑝𝑏𝑒𝑠𝑡; 5. Se 𝑓(𝑝𝑏𝑒𝑠𝑡) < 𝑓(𝑝𝑐), então a melhor solução vizinha é melhor que a solução corrente e, portanto, fazer 𝑝𝑐 ← 𝑝𝑏𝑒𝑠𝑡 e voltar ao passo 3. Em caso contrário, ir ao passo 6; 6. Se 𝑠 = 𝑠𝑚𝑎𝑥 pare o processo e a solução encontrada pelo VND é 𝑝𝑐. Em caso contrário, fazer 𝑠 ← 𝑠 + 1 e voltar ao passo 4; Em relação ao algoritmo VND, deve-se realizar as seguintes observações: • É apenas uma generalização da heurística SDH. SDH tem apenas uma estrutura de vi- zinhança. VND tem um conjunto de 𝑠𝑚𝑎𝑥 estruturas de vizinhança, sendo cada nova estrutura de vizinhança de cardinalidade maior que a estrutura precedente. • Cada vez que a análise de uma vizinhança apre senta êxito, isto é, foi encontrada uma proposta de solução vizinha melhor que a proposta de solução corrente, então, deve-se voltar para o nível de vizinhança mais básico 𝑁1. Em caso contrário, deve-se passar para o seguinte nível de vizinhança. 50 • SDH e VND realizam transições que geram um processo da solução incumbente cor- rente para uma nova solução incumbente. • VND é essencialmente determinístico. O algoritmo VND representa a forma mais simples de formular um algoritmo VNS. Entretanto, esse tipo de algoritmo básico pode ser integrado em uma estrutura mais complexa de algoritmo VNS. Quando o algoritmo VND for usado de forma independente, deve-se prio- rizar a busca de soluções de “excelente” qualidade. Por outro lado, se o algoritmo VND é usado em estruturas mais complexas pode ser mais importante encontrar uma boa solução mais rapi- damente. A meta-heurística BVNS apresenta a seguinte estrutura: 1. Passo preliminar: Selecione o conjunto de estruturas de vizinhança 𝑁𝑠, 𝑠 = 1, … , 𝑠𝑚𝑎𝑥, que será utilizado na busca; defina um critério de parada; 2. Encontrar uma solução inicial 𝑥𝑖𝑛𝑐 que se transforma na solução corrente 𝑥𝑖; 3. Faça 𝑠 ← 1; 4. Repita os passos a seguir até 𝑠 = 𝑠𝑚𝑎𝑥: a) Gere aleatoriamente uma solução 𝑥 para o nível de vizinhança 𝑠 de 𝑥𝑖𝑛𝑐 (𝑥 ∈ 𝑁𝑠(𝑥𝑖𝑛𝑐)); b) Aplique o método de busca local com 𝑥 como solução inicial; denote por 𝑥𝑏 o ótimo local obtido por esta busca; c) Se o ótimo local 𝑥𝑏 é melhor que a solução incumbente 𝑥𝑖𝑛𝑐, faça (𝑥𝑖𝑛𝑐 ← 𝑥𝑏) e continue a busca em 𝑁1 (𝑠 ← 1); caso contrário faça 𝑠 ← 𝑠 + 1; 3.3 ALGORITMO HEURÍSTICO CONSTRUTIVO PARA ENCONTRAR UMA TOPO- LOGIA LIGERAMENTE MALHADA Inicialmente, durante a fase de PESD, é possível projetar um ou vários sistemas de dis- tribuição elétrica de forma radial, podendo incluir determinados ramos que foram considerados no plano inicial, mas que acabaram não sendo construídos. Nesse contexto específico, quando se torna necessário encontrar uma estrutura de rede ligeiramente malhada do que a atualmente em uso, que evolui a partir de uma topologia radial com o objetivo de melhorar a confiabilidade do sistema de distribuição expandido, é essencial apresentar uma sugestão de boa qualidade, embora não necessariamente ótima, em relação ao número de diferentes topologias de rede que poderiam ser construídas. Isto permitirá que a energia seja restaurada rapidamente caso surja uma falha ou seja necessária manutenção na infraestrutura do sistema. 51 A ideia principal é incorporar 𝑝 ramos adicionais à topologia encontrada anteriormente, com o objetivo de que o sistema ligeiramente malhado tenha um maior número de configura- ções radiais no grafo da rede de distribuição inicial. As informações de entrada para resolver este problema incluem os diferentes 𝑚 ramos que compõem a topologia da rede radial que foram encontrados utilizando técnicas clássicas de otimização, além de um grupo potencial de 𝑛𝑠 ramos candidatos a serem adicionados. Este problema pode ser resolvido através da aplicação de técnicas de otimização clás- sica, heurística ou meta-heurística. Neste trabalho aborda-se esta questão aplicando um AHC e a meta-heurística VNS nas suas versões VND e BVNS. Num processo de implementação de um algoritmo heurístico construtivo CHA (na forma simplificada do inglês Constructive Heuristic Algorithm), uma das decisões cruciais re- side