Ilha SolteiraIlha Solteira UNIVERSIDADE ESTADUAL PAULISTA “ JÚLIO DE MESQUITA FILHO” Câmpus de Ilha Solteira - SP VERA LÚCIA VIEIRA DE CAMARGO ALGORITMO GENÉTICO ESPECIALIZADO APLICADO AO PLANEJAMENTO DA EXPANSÃO DE SISTEMAS DE DISTRIBUIÇÃO DE ENERGIA ELÉTRICA Ilha Solteira 2014 VERA LÚCIA VIEIRA DE CAMARGO ALGORITMO GENÉTICO ESPECIALIZADO APLICADO AO PLANEJAMENTO DA EXPANSÃO DE SISTEMAS DE DISTRIBUIÇÃO DE ENERGIA ELÉTRICA Tese apresentada à Faculdade de Engenha- ria do Campus de Ilha Solteira - UNESP como parte dos requisitos para obtenção do título de Doutora em Engenharia Elétrica. Especialidade: Automação. Prof. Dr. Rubén Augusto Romero Lázaro Orientador Profa. Dra. Marina Lavorato de Oliveira Co-orientadora Ilha Solteira 2014 FICHA CATALOGRÁFICA Desenvolvido pelo Serviço Técnico de Biblioteca e Documentação Camargo, Vera Lúcia Vieira de. C173a Algoritmo genético especializado aplicado ao planejamento da expansãode sistemas de distribuição de energia elétrica / Vera Lúcia Vieira de Camargo. - - Ilha Solteira : [s.n.], 2014 175 f.:il. Tese (doutorado) - Universidade Estadual Paulista. Faculdade de Engenharia de Ilha Solteira. Área de Conhecimento: Automação, 2014 Orientador: Rubén Augusto Romero Lázaro Co-orientadora: Marina Lavorato de Oliveira Inclui bibliografia 1. Planejamento de sistemas de distribuição de energia elétrica. 2. Algoritmo genético. 3. Programação não linear inteiro misto. 4. Otimização de sistemas de potência. DEDICO Aos meus pais, ao meu esposo, aos meus irmãos, aos meus filhos e minha neta. AGRADECIMENTOS • A Deus nosso pai, força maior do Universo, pela força concedida para superar os desa- fios que foram surgindo durante esta jornada da vida profissional e pela oportunidade de vivenciar este processo que me possibilitou compreender e perceber os valores das múl- tiplas dimensões da existência humana. Obrigada também Senhor, pela vida e por sua graça sempre presente em minha vida. • Ao Professor Dr. Rubén Augusto Romero Lázaro, orientador deste trabalho, pela opor- tunidade, pela orientação, pelas ideias criativas trocadas durante a elaboração do trabalho e, também pelo grande empenho e dedicação na implantação e execução do Doutorado Interinstitucional - DINTER no Estado de Mato Grosso. • À Dra. Marina Lavorato de Oliveira, co-orientadora deste trabalho, pelo acompanha- mento, ajuda e atenção recebida durante o desenvolvimento deste trabalho. • Aos professores do DINTER Anna Diva Plasencia Lotufo, Antonio Padilha Feltrin, José Roberto Mantovani e Rubén Augusto Romero Lázaro pela dedicação e contribuições em nossa formação. • Aos professores das bancas do exame de qualificação e de defesa: Carlos R. M. da Rocha, Fábio B. Leão, John Fredy Franco Baquero, José Roberto Mantovani e Roberto C. Lotero pelas valiosas sugestões e contribuições para o trabalho. • Aos meus pais João Arlindo de Camargo e Clotilde Vieira de Camargo pela vida, pelo carinho, pela dedicação e pelos ensinamentos; verdadeiros anjos incumbidos por Deus para nos conduzir e preparar para as jornadas e desafios da vida. • Um agradecimento especial a quem sempre me encorajou e incentivou em todos os aspec- tos de minha vida, meu esposo Jocimal Galdino Delgado, pelo carinho, pelo amor, pela força, pela compreensão, pelo apoio e pela longa espera durante a realização dos cursos de pós-graduação. • Aos meus filhos, Ariadne C. P. de Camargo, Matheus P. de Camargo Silva, André Luís P. de Camargo pelo carinho, incentivo e compreensão de minhas frequentes ausências ao longo destes anos. • Ao André Luís, pelo seu auxílio na construção das figuras deste trabalho. • Aos meus irmãos pelo carinho, pela torcida e também pela oportunidade de juntos com- partilharmos experiências durante a nossa vivência que se tornaram lições para a vida em sociedade. • A todos os colegas do DINTER, em especial a Adriana S. Resende, Diego Piasson, Do- nizete Ritter, Emivan F. da Silva, Inédio Arcari, Marinez Cargnin-Stieler, Márcia Cristina Dal Toé, Milton L. N. Pereira, Minéia C. Fagundes, Rogério dos R. Gonçalves, Silvio C. G. Granja e Suzan G. B. de Pádua pelo apoio mútuo e pela amizade. • À Márcia C. Dal Toé, amiga especial que esteve próxima durante toda a trajetória do dou- torado, pela grande amizade, pelo carinho, pelo companheirismo, pelo incentivo, pelos estudos em grupo e por ter me dado tanta força em momentos cruciais ao longo deste processo. • Aos amigos Rogério dos Reis Gonçalves e Milton Luiz Neri Pereira, amigos de trabalho e do doutorado, pelo companheirismo nas viagens que juntos realizamos, pelas parcerias e incentivo nos estudos em grupo, pelo apoio e pela grande amizade construída ao longo destes anos. • À Suzan G. B. de Pádua, pela atenção dispensada e pela sua disponibilidade para trocar ideias sobre a pesquisa. • Ao Jeferson B. Vanderlinde pelo auxílio nas instalações dos programas e pela atenção dispensada. • Aos professores e colegas do LaPSEE (Laboratório de Planejamento de Sistema de Ener- gia Elétrica), pela oportunidade de nossa convivência que foi fundamental para o desen- volvimento da pesquisa. • À Universidade do Estado de Mato Grosso (UNEMAT), pelo apoio financeiro e incentivo no processo de qualificação de seu quadro docente. • À Universidade Estadual Paulista de Ilha Solteira, pela oportunidade oferecida ao estabe- lecer parceria com outras universidades. • Aos funcionários do DEE-FEIS-UNESP, pela atenção e apoio. • À CAPES (Coordenação de Aperfeiçoamento de Pessoal de Nível Superior do Brasil), pelo apoio financeiro para execução do DINTER. ”O aumento do conhecimento é como uma esfera dilatando-se no espaço: quanto maior a nossa com- preensão, maior o nosso contacto com o desconhe- cido.” Blaise Pascal RESUMO No presente trabalho foi proposto o desenvolvimento de uma técnica de solução para resolver o problema de planejamento de expansão do sistema de distribuição de energia elétrica (PSDEE) modelado como um problema de programação não linear inteiro misto (PNLIM) mono-objetivo e multiestágio (dinâmico), com o objetivo de encontrar um plano de expansão do sistema de distribuição de energia elétrica com custos de investimentos e de operação mínimos sujeitos a restrições físicas e operacionais e restrições que estabelecem os limites dos indicadores de continuidade DIC, FIC, DEC e FEC. A função objetivo do modelo é igual ao valor presente líquido dos custos com construção e/ou recondutoramento de circuitos, com construção e/ou ampliação de subestações, com perdas resistivas anuais e com operação das subestações. Para atingir o objetivo proposto foi desenvolvido um algoritmo genético especializado, adaptado da proposta de Chu-Beasley em conjunto com técnicas heurísticas especializadas para resolver o problema de PSDEE. Para avaliar a viabilidade e flexibilidade da proposta foram testados sistemas da literatura, que foram organizadas em três etapas com objetivos distintos: na pri- meira foi realizado o planejamento estático considerando somente as restrições operacionais do sistema (sistemas de 23 e 136 barras); na segunda o planejamento multiestágio dinâmico considerando as mesmas restrições da etapa anterior (sistemas de 54 e 417 barras) e a terceira o planejamento multiestágio dinâmico considerando tanto as restrições operacionais como as relacionadas com a confiabilidade do sistema (sistema de 27 barras). Pelos resultados obtidos o algoritmo mostrou-se eficiente e versátil, pois dos sistemas que foram possíveis estabelecer uma comparação, o algoritmo conseguiu encontrar resultado melhor (para o sistema de 54 barras), igual (para os sistemas de 23 e 136 barras) e próximo para o sistema de 417 barras. Palavras-chave:Planejamento de sistemas de distribuição de energia elétrica. Algoritmo ge- nético. Programação não linear inteiro misto. Otimização de sistemas de potência. ABSTRACT In this paper, it was proposed the development of a solution technique to solve the expansion planning problem of electricity distribution system (PEDS) modeled as a problem of mixed integer nonlinear programming (MINP) mono-objective and multi-stage (dynamic), with the goal to find an expansion plan from electricity distribution system with minimum investment costs and operation subject to physical and operational constraints and restrictions that esta- blish the limits of continuity indicators DIC, FIC, DEC and FEC . The model objective function is equal to the costs present value net with construction and/ or reconductoring of circuits with construction and/or substations expansion with annual resistive losses and with substations ope- ration. In order to achieve the objective proposed a specialized genetic algorithm adapted by Chu-Beasley was developed in conjunction with specialized heuristics techniques to solve the problem of PEDS. To assess the feasibility and flexibility of proposed literature, systems which they were tested organized in three stages with different goals: the first it was performed the static planning considering only the system operating constraints (systems 23 and 136 bus); the second it was performed the dynamic multistage planning considering the same restrictions from the previous stage (systems 54 and 417 bus) and the third it was performed the dynamic multistage planning considering as much operating restrictions as related to reliability of system (system 27 bus). According to the results, the algorithm was efficient and versatile because of the systems that were possible to reach a comparison, the algorithm was able to find best result (for system 54 bus) equal (for systems 23 and 136 bus) and next to system of 417 bus. Keywords: Planning of electricity distribution system. Genetic algorithm. Mixed integer non- linear programming. Optimization of power systems. LISTA DE FIGURAS Figura 1 Sistema de 14 barras antes da ordenação . . . . . . . . . . . . . . . . 49 Figura 2 Sistema de 14 barras ordenado. . . . . . . . . . . . . . . . . . . . . . 49 Figura 3 Ramo k-m de um sistema de distribuição radial . . . . . . . . . . . . . 50 Figura 4 Exemplo de codificação para o planejamento estático. . . . . . . . . . 56 Figura 5 Exemplo de codificação para o planejamento multiestágio. . . . . . . . 57 Figura 6 Diagrama de blocos da heurística de geração da população inicial . . . 61 Figura 7 Diagrama de blocos da heurística utilizada na fase de recombinação . . 66 Figura 8 Ilustração da recombinação entre duas soluções no planejamento estático 67 Figura 9 Vetor codificação da recombinação ilustrada na Figura 8 . . . . . . . . 67 Figura 10 Vetor codificação da recombinação do planejamento multiestágio entre duas soluções . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 Figura 11 Ilustração da mutação de uma solução candidata. . . . . . . . . . . . . 69 Figura 12 Diagrama de blocos da Melhoria de Qualidade I. . . . . . . . . . . . . 71 Figura 13 Diagrama de blocos da Melhoria de Qualidade II. . . . . . . . . . . . 72 Figura 14 Diagrama de blocos da Heurística I. . . . . . . . . . . . . . . . . . . . 75 Figura 15 Diagrama de blocos da Melhoria de Factibilidade. . . . . . . . . . . . 77 Figura 16 Diagrama de blocos da sub-rotina utilizada na etapa de substituição do AG-ESP. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 Figura 17 Diagrama de blocos do Algoritmo Genético Especializado implemen- tado. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 Figura 18 Custos x confiabilidade . . . . . . . . . . . . . . . . . . . . . . . . . 84 Figura 19 Níveis hierárquicos utilizados nos estudos da confiabilidade . . . . . . 84 Figura 20 Ilustração de um alimentador . . . . . . . . . . . . . . . . . . . . . . 89 Figura 21 Efeitos de cada falha sobre os demais blocos . . . . . . . . . . . . . . 90 Figura 22 Número de interrupções ocorridas nos blocos com as falhas . . . . . . 90 Figura 23 Interrupções-consumidor afetado . . . . . . . . . . . . . . . . . . . . 91 Figura 24 Duração das interrupções dos blocos . . . . . . . . . . . . . . . . . . 92 Figura 25 Duração das interrupções dos blocos - consumidores afetados . . . . . 93 Figura 26 Fluxograma para o cálculo dos índices de confiabilidade . . . . . . . . 95 Figura 27 Rotas propostas para o sistema de 23 barras . . . . . . . . . . . . . . 98 Figura 28 Topologia da melhor solução encontrada pelo AG-ESP - Sistema de 23 barras (Teste 1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 Figura 29 Gráfico dos valores da incumbente ao longo das gerações - Sistema de 23 barras - Teste 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 Figura 30 Topologia da melhor solução - Sistema de 23 barras (Teste 2) . . . . . 101 Figura 31 Gráfico dos valores da solução incumbente - Sistema de 23 barras - Teste 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 Figura 32 Sistema de 136 barras - Circuitos existentes e propostos. . . . . . . . . 102 Figura 33 Topologia da melhor solução encontrada pelo AG-ESP para o Sistema de 136 barras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 Figura 34 Gráfico dos valores da incumbente ao longo das gerações - Sistema de 136 barras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 Figura 35 Sistema de 54 barras inicial . . . . . . . . . . . . . . . . . . . . . . . 105 Figura 36 Configuração da melhor solução encontrada no estágio 3 - Sistema de 54 barras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 Figura 37 Gráfico do perfil de tensão das barras do estágio 3 da solução obtida pelo AG-ESP - Sistema de 54 barras . . . . . . . . . . . . . . . . . . 107 Figura 38 Gráfico dos valores da incumbente ao longo das gerações - Sistema de 54 barras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 Figura 39 Configuração da melhor solução encontrada no estágio 3 - Sistema de 417 barras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 Figura 40 Gráfico do perfil de tensão das barras da solução no estágio 3 - Sistema de 417 barras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 Figura 41 Gráfico dos valores da incumbente ao longo das gerações - Sistema de 417 barras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 Figura 42 Sistema de 27 barras inicial . . . . . . . . . . . . . . . . . . . . . . . 119 Figura 43 Configuração da melhor solução encontrada no estágio 3 - Sistema de 27 barras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 Figura 44 Gráfico do perfil de tensão nas barras do estágio 3 da melhor solução - Sistema de 27 barras - Caso I . . . . . . . . . . . . . . . . . . . . . . 121 Figura 45 Comportamento da incumbente ao longo das gerações - Sistema de 27 barras - Caso I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 Figura 46 Configuração da melhor solução encontrada no estágio 3 - Sistema de 27 barras - Caso II . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 Figura 47 Gráfico do comportamento da incumbente ao longo das gerações - Caso II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 Figura 48 Topologias da melhores soluções encontradas pelo AG-ESP - Sistema de 27 barras - Casos I e II . . . . . . . . . . . . . . . . . . . . . . . . 130 Figura 49 Gráfico do perfil da magnitude de tensão do estágio 3 - Casos I e II . . 131 LISTA DE TABELAS Tabela 1 Custos da melhor solução encontrada pelo AG-ESP para o sistema de 23 barras - Teste 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 Tabela 2 Comparativo dos resultados obtidos na literatura para o sistema de 23 barras - Teste 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 Tabela 3 Custos da melhor solução encontrada pelo AG-ESP para o Sistema de 23 barras - Teste 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 Tabela 4 Custos da melhor solução encontrada pelo AG-ESP para o sistema de 136 barras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 Tabela 5 Custos da melhor solução encontrada pelo AG-ESP para o Sistema de 54 barras (103 R$) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 Tabela 6 Capacidade de potência máxima e demandada das subestações da so- lução obtida pelo AG-ESP - Sistema de 54 barras. . . . . . . . . . . . 106 Tabela 7 Tipos de condutores dos circuitos da melhor solução encontrada pelo AG-ESP- Sistema de 54 barras . . . . . . . . . . . . . . . . . . . . . 108 Tabela 8 Comparativo do resultado obtido pelo AG-ESP com o da literatura - Sistema de 54 barras. . . . . . . . . . . . . . . . . . . . . . . . . . . 108 Tabela 9 Custos do indivíduo de melhor qualidade da população inicial e da solução obtida pelo AG-ESP . . . . . . . . . . . . . . . . . . . . . . 109 Tabela 10 Custos da melhor solução encontrada pelo AG-ESP para o Sistema de 417 barras (103 R$) . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 Tabela 11 Capacidade de potência máxima e demandada das subestações - Sis- tema de 417 barras. . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 Tabela 12 Tipos de condutores dos circuitos - Sistema de 417 barras . . . . . . . 112 Tabela 13 Comparativo do resultado encontrado pelo AG-ESP com o da literatura - Sistema de 417 barras (103 R$). . . . . . . . . . . . . . . . . . . . . 117 Tabela 14 Comparativo entre os custos do indivíduo de melhor qualidade da po- pulação inicial e melhor solução obtida pelo AG-ESP (103 R$) . . . . 118 Tabela 15 Custos da melhor solução encontrada pelo AG-ESP para o Sistema de 27 barras (103 U$) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 Tabela 16 Capacidade de potência máxima e demandada das subestações - Sis- tema de 27 barras - Caso I . . . . . . . . . . . . . . . . . . . . . . . . 121 Tabela 17 Tipos de condutores dos circuitos da melhor solução - Sistema de 27 barras - Caso I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 Tabela 18 Custos do indivíduo de melhor qualidade da população inicial obtido pelo AHC e melhor solução obtida pelo AG-ESP . . . . . . . . . . . . 122 Tabela 19 Índices de confiabilidade das barras do sistema da melhor solução - Sistema de 27 barras - Caso I . . . . . . . . . . . . . . . . . . . . . . 124 Tabela 20 Índices de Confiabilidade por grupo de consumidores - Sistema de 27 barras - Caso I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 Tabela 21 Custos da melhor solução do sistema de 27 barras - Caso II (103 U$) . 126 Tabela 22 Capacidade de potência máxima e demandada das subestações - Sis- tema de 27 barras - Caso II . . . . . . . . . . . . . . . . . . . . . . . 126 Tabela 23 Tipos de condutores dos circuitos da melhor solução obtida - Sistema de 27 barras - Caso II . . . . . . . . . . . . . . . . . . . . . . . . . . 127 Tabela 24 Índices de Confiabilidade das barras - Sistema de 27 barras - Caso II . 128 Tabela 25 Índices de Confiabilidade por grupo de consumidores - Sistema de 27 barras - Caso II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 Tabela 26 Custos das melhores soluções dos Casos I e II (103 U$) . . . . . . . . 129 Tabela 27 Dados de barra do sistema de 23 barras . . . . . . . . . . . . . . . . . 145 Tabela 28 Dados de ramo do Sistema de 23 barras . . . . . . . . . . . . . . . . . 145 Tabela 29 Dados de condutores do Sistema de 23 barras. . . . . . . . . . . . . . 146 Tabela 30 Dados de subestação existente do sistema de 23 barras - Teste 1 . . . . 146 Tabela 31 Dados de subestação existente do sistema de 23 barras - Teste 2 . . . . 146 Tabela 32 Dados de subestação proposta do sistema de 23 barras - Teste 2 . . . . 146 Tabela 33 Dados de barra do sistema de 136 barras . . . . . . . . . . . .. . . . 147 Tabela 34 Dados de ramo do sistema de 136 barras . . . . . . . . . . . . . . . . 148 Tabela 35 Dados dos condutores do sistema de 136 barras . . . . . . . . . . . . 150 Tabela 36 Dados das subestações existentes do sistema de 136 barras . . . . . . 150 Tabela 37 Dados de ramo do sistema de 54 barras . . . . . . . . . . . . . . . . . 151 Tabela 38 Dados de barra do sistema de 54 barras (continua) . . . . . . . . . . . 152 Tabela 39 Dados de condutores do sistema de 54 barras . . . . . . . . . . . . . . 153 Tabela 40 Dados de subestações existentes do sistema de 54 barras . . . . . . . . 154 Tabela 41 Dados de subestações propostas do sistema de 54 barras . . . . . . . . 154 Tabela 42 Custo com recondutoramento (103 R$) - Sistema de 54 barras . . . . . 154 Tabela 43 Dados de barra do sistema de 417 barras. . . . . . . . . . . . . . . . . . 155 Tabela 44 Dados de ramo do Sistema de 417 barras . . . . . . . . . . . . . . . . 165 Tabela 45 Dados de condutores do sistema de 417 barras . . . . . . . . . . . . . 170 Tabela 46 Dados de subestações existentes do sistema de 417 barras . . . . . . . 171 Tabela 47 Dados de subestação proposta do sistema de 417 barras . . . . . . . . 171 Tabela 48 Custo com recondutoramento (103 R$) - Sistema de 417 barras . . . . 171 Tabela 49 Dados de barra do sistema de 27 barras . . . . . . . . . . . . . . . . . 173 Tabela 50 Custos dos circuitos por tipo de condutor instalado (103 US$) . . . . . 174 Tabela 51 Dados de condutores do sistema de 27 barras . . . . . . . . . . . . . . 175 Tabela 52 Dados de subestações existentes do sistema de 27 barras . . . . . . . . 175 Tabela 53 Dados de subestação proposta do sistema de 27 barras . . . . . . . . . 175 LISTA DE ABREVIAÇÕES E SIGLAS AG Algorítimo Genético AFC Algorítimo de Fluxo de Carga AGCB Algorítimo Genético de Chu-Beasley AG-ESP Algoritmo Genético Especializado AHC Algoritmo Heurístico Construtivo B&B Branch and Bound ANEEL Agência Nacional de Energia Elétrica DEC Duração Equivalente de Interrupção por Unidade Consumidora DIC Duração de Interrupção por Unidade Consumidora FEC Frequência Equivalente de Interrupção por Unidade Consumidora FIC Frequência de Interrupção por Unidade Consumidora PSDEE Planejamento da Expansão do Sistema de Distribuição de Energia Elétrica PL Programação Linear PLIM Programação Linear Inteiro Misto PNLIM Programação Não-Linear Inteiro Misto PRODIST Procedimentos de Distribuição de Energia Elétrica no Sistema Elétrico Nacional SAIFI System Average Interruption Frequency Index SAIDI System Average Interruption Duration Index VNS Busca em Vizinhança Variável LISTA DE SÍMBOLOS bi j,a Susceptância do ramoi j de condutor do tipoa. Bi j Elemento da matriz susceptância nodal. ci j ,a Custo do circuitoi j com condutor do tipoa que pode ser adicionado ou substituído em unidade monetária/km. cop Custo de operação da subestação em (unidade monetária/kVA2h). csi,b Custo de subestação adicionada ao sistema ou repotenciada em unidade mo- netária. ce Custo de perdas de energia em unidade monetária/kWh. DECk,t Duração Equivalente de Interrupção por Unidade Consumidora do alimenta- dork no estágiot. DECp Limite estipulado para o índice DEC no estágiot. DICi,t Duração de Interrupção por Unidade Consumidora da barrai no estágiot. DICp Limite estipulado para o índice DIC no estágiot. FECk,t Frequência Equivalente de Interrupção por Unidade Consumidora do ali- mentadork no estágiot. FECp Limite estipulado para o índice FEC no estágiot. FICp Limite estipulado para o índice FIC no estágiot. FICi,t Frequência de Interrupção por Unidade Consumidora da barrai no estágiot. gi j ,a Condutância do ramoi j do condutor do tipoa. Gi j Elemento da matriz condutância nodal. I taxa de juros. Imaxa Corrente máxima permitida no condutor do tipoa. l i j Comprimento do ramoi j emkm. mi,b,t Variável binária que indica construção/repotenciação de subestação do tipo b na barrai no estágiot. np(t) Duração em anos do estágiot. nb Número de barras do sistema. nbs Número de barras com subestação (existentes e propostas). ni j ,a,t variável binária que indica se o circuitoi j é construído ou recondutorado com condutor do tipoa no estágiot. nr Número de ramos (candidatos e propostos). PDi,t Potência ativa demandada pela barrai no estágiot. PSi,t Potência ativa fornecida pela subestação da barrai no estágiot. Pi,t Potência ativa calculada na barrai no estágiot. Pi j,a,t Fluxo de potência ativa no condutor do tipoa que sai da barrai e vai para a barra j no estágiot. p(t) Ano de início do estágiot a partir de um referencial adotado como base (ano zero). QDi,t Potência reativa demandada pela barrai no estágiot. QSi,t Potência reativa fornecida pela subestação da barrai no estágiot. Qi,t Potência reativa calculada na barrai no estágiot. Qi j ,a,t Fluxo de potência reativa no condutor do tipoa que sai da barrai e vai para a barra j no estágiot. Si,b Limite máximo da potência aparente da subestação da barrai do tipob . Si j ,a,t Fluxo de potência aparente no ramoi j com condutor do tipoa no estágiot. Si j,a Fluxo de potência aparente máxima no ramoi j com condutor do tipoa. Vi,t Magnitude da tensão na barrai no estágiot. Vmax Magnitude de tensão máxima permitida no sistema. Vmin Magnitude de tensão mínima permitida no sistema. T Número de estágios do planejamento. T ′ {1,2, ...,T}. αi,b,t Variável binária que indica se a subestação do tipob da barrai está ativa no estágiot. β i j ,a,t Variável binária que indica se o ramo com condutor do tipoa entre as barrasi e j está ativo no estágio t. θi j ,t Diferença angular entre as barrasi e j no estágiot. λi Estimativa da taxa de ocorrência de falha que provoca a interrupçãoi. φl Fator de perdas dos circuitos. φs Fator de perdas das subestações. Ωl Conjunto de ramos (existentes e propostos) do sistema. Ωa Conjunto dos tipos de condutores. Ωal Conjunto de alimentadores do sistema. Ωb Conjunto de barras do sistema. Ωbs Conjunto de barras com subestações (existentes e propostas) comΩbs⊂Ωb. Ωts Conjunto do tipo de subestações. 8760 Número de horas em um ano. SUMÁRIO 1 INTRODUÇÃO 29 2 REVISÃO BIBLIOGRÁFICA SOBRE O PSDEE 33 2.1 PLANEJAMENTO DA EXPANSÃO DO SISTEMA DE DISTRIBUIÇÃO DE ENERGIA ELÉTRICA 33 2.2 MODELOS DE PSDEE 34 2.3 TÉCNICAS DE SOLUÇÃO DO PSDEE 35 2.3.1 Técnicas Clássicas de Otimização 35 2.3.2 Técnicas Heurísticas 36 2.3.3 Metaheurísticas 36 2.4 REVISÃO BIBLIOGRÁFICA 37 3 MODELO MATEMÁTICO PARA O PROBLEMA DO PSDEE 43 3.1 PLANEJAMENTO DA EXPANSÃO DO SISTEMA DE DISTRIBUIÇÃO DE ENERGIA ELÉTRICA 43 3.2 MODELO MATEMÁTICO DO PSDEE 44 3.3 ESTRATÉGIAS UTILIZADAS PARA RESOLVER O MODELO MATEMÁ- TICO DO PSDEE 48 3.3.1 Fluxo de Carga 48 3.3.1.1 Renumeração das barras 49 3.3.1.2 Etapa Backward (varredura das correntes): 50 3.3.2 Etapa Forward (varredura de tensões) 50 3.3.2.1 Cálculo das Perdas 51 4 ALGORITMO GENÉTICO ESPECIALIZADO APLICADO AO PSDEE 53 4.1 ALGORITMO GENÉTICO TRADICIONAL E ALGORITMO GENÉTICO MO- DIFICADO DE CHU-BEASLEY 53 4.2 ALGORITMO GENÉTICO ESPECIALIZADO PARA RESOLVER O PROBLEMA DE PSDEE 55 4.2.1 Codificação do Problema 56 4.2.1.1 Planejamento Estático 56 4.2.1.2 Planejamento Multiestágio 57 4.2.2 População Inicial 57 4.2.2.1 Processo de Seleção de Subestações 58 4.2.2.2 Processo construtivo dos circuitos que comporão a topologia da solução 59 4.2.3 Manipulação das Infactibilidades e Função Objetivo 60 4.2.4 Seleção 63 4.2.5 Recombinação 64 4.2.6 Mutação 68 4.2.7 Fase de Melhoria Local 69 4.2.7.1 Melhoria de qualidade 69 4.2.7.2 Melhorias da Factibilidade 74 4.2.8 Substituição 78 5 CONFIABILIDADE NO SISTEMA DE DISTRIBUIÇÃO DE ENERGIA ELÉTRICA 83 5.1 NOÇÕES BÁSICAS 83 5.2 INDICADORES DE CONTINUIDADE DO SERVIÇO DE DISTRIBUIÇÃO DE ENERGIA ELÉTRICA 86 5.2.1 Indicadores de continuidade adotados no Brasil 86 5.2.1.1 FIC - Frequência de Interrupção por Unidade Consumidora 86 5.2.1.2 DIC - Duração de Interrupção por Unidade Consumidora 86 5.2.1.3 FEC - Frequência Equivalente de Interrupção por Unidade Consumidora 87 5.2.1.4 DEC - Duração Equivalente de Interrupção por Unidade Consumidora 87 5.2.2 Indicadores de Continuidade Internacionais 87 5.2.2.1 SAIDI - System Average Interruption Duration Index 88 5.2.2.2 SAIFI - System Average Interruption Frequency Index 88 5.3 METODOLOGIA UTILIZADA PARA O CÁLCULO DOS ÍNDICES DE CON- FIABILIDADE 88 5.3.1 Cálculo do FIC e FEC 90 5.3.2 Cálculo do DIC e DEC 92 6 TESTES E RESULTADOS 97 6.1 PSDEE ESTÁTICO 97 6.1.1 Sistema de 23 Barras 97 6.1.1.1 Sistema de 23 Barras - Teste 1 98 6.1.1.2 Sistema de 23 Barras - Teste 2 100 6.1.2 Sistema de 136 Barras 101 6.2 PSDEE MULTIESTÁGIO DINÂMICO 104 6.2.1 Sistema de 54 Barras 104 6.2.2 Sistema de 417 Barras 109 6.3 PSDEE MULTIESTÁGIO CONSIDERANDO AS RESTRIÇÕES DE CONFIA- BILIDADE 118 6.3.1 Sistema de 27 Barras 118 6.3.1.1 Sistema 27 Barras - Caso I 119 6.3.1.2 Sistema de 27 Barras - Caso II 125 7 CONSIDERAÇÕES FINAIS 133 REFERÊNCIAS 137 APÊNDICE A - TRABALHO PUBLICADO 143 ANEXO A - DADOS DO SISTEMA DE 23 BARRAS 145 ANEXO B - DADOS DO SISTEMA DE 136 BARRAS 147 ANEXO C - DADOS DO SISTEMA DE 54 BARRAS 151 ANEXO D - DADOS DO SISTEMA DE 417 BARRAS 155 ANEXO E - DADOS DO SISTEMA DE 27 BARRAS 173 29 1 INTRODUÇÃO A literatura especializada mostra que nas últimas décadas vêm sendo desenvolvidos vários trabalhos propondo novas metodologias para resolver o problema do planejamento da expansão do sistema de distribuição de energia elétrica (PSDEE), cujo objetivo clássico é o de minimizar custos de investimentos e de operação do sistema satisfazendo um conjunto de restrições físicas, operacionais e financeiras. A relevância de pesquisas nesta área se justifica à medida que é nesta parte do sistema que ocorre frequentemente o aumento de demanda de energia elétrica e se encontra a maior parte dos consumidores e uma parcela significativa de perdas técnicas. Nessa perspectiva, o desenvolvimento de modelos matemáticos de otimização e de técnicas de solução, aliadas a ferramentas computacionais, são de grande relevância para que o sistema de distribuição de energia seja projetado de forma a atender as exigências técnicas impostas pelos órgãos reguladores e pela sociedade, bem como forneça energia ao consumidor com qua- lidade e confiabilidade com o menor custo possível. O problema de planejamento do sistema de distribuição (PSDEE) é um problema clássico de otimização cujo modelo matemático é de Programação Não Linear Inteiro Misto (PNLIM) de grande porte. Sendo assim, o objetivo é otimizar uma função não linear, sujeita a restrições lineares e não lineares, em que uma parcela das variáveis são inteiras e as demais são contínuas (KAGAN et al., 2009). Este problema é de natureza combinatória, com vasto espaço de busca, estrutura multimodal, com uma infinidade de soluções ótimas locais (COSSI et al., 2012). Outro aspecto importante é que o modelo do PSDEE tem uma característica flexível que pode se adaptar às necessidades do planejamento que se pretenda desenvolver (OLIVEIRA, 2010). Os estudos do problema de PSDEE teve início desde a década de 1960 e vem sendo desen- volvido até os dias atuais, com diferenciados modelos e técnicas de solução. Quanto às opções metodológicas para resolver o problema de PSDEE são várias as apresentadas na literatura, com destaque às técnicas clássicas de otimização, técnicas heurísticas e as metaheurísticas. Desde o final da década de 1980, tem se intensificado o uso de metaheurísticas para resolver problemas complexos de sistema de energia elétrica, pela facilidade em considerar restrições e funções objetivo não lineares e inserir aspectos específicos de acordo com a natureza do pro- blema, como por exemplo a confiabilidade, perdas, dentre outras, apesar de não haver garantias de que a solução ótima do problema seja obtida (HAFFNER et al., 2006). As metaheurísticas utilizadas para resolver o problema de PSDEE presentes na literatura consultada são: Algoritmos Genéticos,Tabu Search,Simulated Annealing, Colonia de Formi- 30 1 INTRODUÇÃO gas,Particle swarm optimization(PSO), Busca em Vizinhança Variável e Busca Dispersa. Por outro lado, no contexto dos trabalhos desenvolvidos sobre planejamento dos sistemas de transmissão de energia elétrica como em Silva et al. (2006), Negrete (2010) e Gallego et al. (2012), foi utilizado o Algoritmo Genético Modificado de Chu-Beasley (AGCB) que vem demonstrando ser uma eficiente técnica de otimização para resolver problemas complexos de sistemas de energia elétrica com vasto espaço de busca e várias restrições. Este algoritmo possui modificações estratégicas do Algoritmo Genético tradicional (AG) que foram implementadas no trabalho de Chu e Beasley (1997) para resolver o problema de alocação de tarefas. As principais diferenças do AGCB, em relação ao AG, estão na forma como são tratadas as infactibilidades; como ocorre a substituição em cada ciclo geracional e a inserção de uma etapa de melhorias da solução após a aplicação dos operadores genéticos. De acordo com a revisão bibliográfica realizada durante a pesquisa, o AG já foi bastante utilizado como técnica de solução nas pes- quisas sobre PSDEE, no entanto, o algoritmo genético com as modificações estratégicas de Chu-Beasley ainda não foi apresentado pela literatura para resolver este problema. Assim sendo, esta pesquisa teve como objetivo aplicar o Algoritmo Genético Modificado de Chu-Beasley associado às técnicas heurísticas para resolver o problema do PSDEE, mode- lado como um problema de PNLIM mono-objetivo, estático ou multiestágio (dinâmico), com o objetivo de encontrar um plano de expansão do sistema de distribuição de energia elétrica com custo mínimo, sujeitos às restrições físicas, operacionais e restrições que estabelecem os limites dos indicadores de continuidade DIC, FIC, DEC e FEC. A função objetivo do modelo utilizado é o valor presente líquido dos custos com construção e/ou recondutoramento de circuitos, com construção e/ou ampliação de subestações, com perdas resistivas anuais e operação das subestações. Como auxiliar no processo de obtenção do ponto de operação e avaliação das infactibilidades das soluções geradas foi utilizado um fluxo de carga para sistemas radiais, que orientou todo o processo para o cálculo do custo das perdas e avaliação das infactibilidades operacionais. Os índices de continuidade considerados como restrição no modelo de PSDEE é um fator de grande relevância tanto para a sociedade, que possui uma forte dependência com a energia elé- trica, como para as concessionárias que tem a avaliação da qualidade de seus serviços prestados prejudicada, haja vista que o número e duração das interrupções ocorridas em um determinado período de tempo são convertidos em índices cujos valores máximos são estipulados pelo órgão regulador e quando estes valores são violados as concessionárias são penalizadas. Por outro lado, inserir o comportamento das falhas no problema eleva sobremaneira o nível de complexidade do estudo, uma vez que se trata de um fenômeno aleatório que depende tanto de eventos internos como externos ao contexto estudado. Para esta questão uma das alternativas é que a confiabilidade do sistema possa ser tratada em uma etapa seguinte a do planejamento por meio de alocação de dispositivos de controle e proteção e instalação de ramais de interconexão 1 INTRODUÇÃO 31 de forma independente. Outra é desenvolver modelos ou metodologias no problema de PSDEE que favoreçam condições para que o sistema opere com níveis desejáveis de continuidade de energia elétrica, tendência presente em muitas pesquisas da literatura especializada que são dis- cutidas no Capítulo 2. Nessa perspectiva, foi proposto um modelo em que foram acrescentadas como restrições os limites dos índices de continuidade DIC, FIC, DEC e FEC. Este trabalho está organizado da forma descrita a seguir: No Capítulo 2 são apresentadas as principais características dos modelos e técnicas de so- lução utilizados para resolver o PSDEE presentes na literatura especializada e uma revisão bibliográfica dos trabalhos consultados que abordam o assunto. No Capítulo 3 é apresentado o modelo matemático do PSDEE proposto para o desenvolvi- mento da pesquisa. É abordado também como o modelo apresentado é resolvido pelo algoritmo genético especializado e o fluxo de carga de varredura utilizado no trabalho. No Capítulo 4 são abordados os aspectos teóricos relacionados aos Algoritmos Genéticos de Chu-Beasley e a metodologia utilizada para implementação do algoritmo desenvolvido para resolver o problema de PSDEE. No Capítulo 5 é apresentado um texto introdutório sobre confiabilidade no sistema de ener- gia elétrica, as definições e metodologia utilizada para os cálculos dos índices de continuidade DIC, FIC, DEC e FEC. No Capítulo 6 são apresentados os resultados obtidos pela metologia proposta em três eta- pas: Na primeira os resultados obtidos com o planejamento estático considerando somente as restrições operacionais do sistema (Sistema de 23 e 136 barras); na segunda os resultados do planejamento multiestágio dinâmico considerando as mesmas restrições da etapa anterior (sistemas de 54 e 417 barras) e a terceira os resultados obtidos ao se realizar o planejamento multiestágio dinâmico considerando tanto as restrições operacionais como as relacionadas com a confiabilidade do sistema (sistema de 27 barras). Finalmente, no Capítulo 6, são apresentadas as considerações sobre o desenvolvimento da pesquisa e perspectivas de trabalhos futuros. No Apêndice A é apresentada a referência do artigo publicado em anais de um evento internacional relacionado à pesquisa desenvolvida. Nos Anexos B, C, D, E e F são apresentados os dados dos sistemas testes utilizados para o desenvolvimento do trabalho. 32 1 INTRODUÇÃO 33 2 REVISÃO BIBLIOGRÁFICA SOBRE O PSDEE Neste capítulo são apresentadas as principais características dos modelos matemáticos e das técnicas de solução presentes na literatura especializada para resolver o problema do PSDEE e uma revisão bibliográfica dos trabalhos consultados para o desenvolvimento da pesquisa. 2.1 PLANEJAMENTO DA EXPANSÃO DO SISTEMA DE DISTRIBUIÇÃO DE ENERGIA ELÉTRICA Em termos gerais, o planejamento da expansão de sistemas de distribuição de energia elé- trica (PSDEE) tem como objetivo projetar um sistema que atenda de forma confiável a crescente demanda de energia elétrica em um determinado período de tempo, com o mínimo custo pos- sível, sendo respeitadas as condições físicas, operacionais, financeiras e as particularidades do contexto em que está sendo planejado. Nesse sentido, a solução do PSDEE deve indicar onde, quando e quais modificações devem ser realizadas nos ramos e subestações de um sistema ao longo do horizonte de planejamento. Para atingir tais objetivos muitas são as pesquisas desen- volvidas na área de planejamento de sistemas de distribuição de energia elétrica e diferenciados modelos e técnicas de solução podem ser encontrados na literatura especializada sobre o tema. O problema de PSDEE clássico considera que a topologia inicial e os dados de demandas futuras em cada barra de consumo são conhecidos. Assim, resolver este problema consiste em determinar, entre um conjunto pré-definido de ramos e subestações candidatas, quando e quais construções, substituições e ampliações devem ser realizadas de forma a minimizar os custos de investimento e de operação para um determinado tempo satisfazendo um conjunto de restrições operacionais, físicas e financeiras (OLIVEIRA, 2010). Por outro lado, as pesquisas da literatura disponível sobre PSDEE mostram uma tendência na formulação de modelos e metodologias que visam encontrar um plano de expansão otimizado com características que favoreçam as condições de confiabilidade do sistema. Estas caracterís- ticas estão presentes em trabalho como: Skok, Krajcar e Skrlec (2005) que propôs um plane- jamento com configurações com malhas abertas estruturadas, para possibilitar a reconfiguração em situações de contingência; em Lotero e Contreras (2011) que realizou a avaliação dos índi- ces de continuidade da rede de um conjunto de soluções encontradas na etapa de planejamento, adotando como conhecidas as taxas do número e duração de interrupções; em Souza (2013) que desenvolveu uma metodologia para a alocação de chaves para realizar a restauração da rede em condições de contingências; em Miranda, Ranito e Proença (1994) e Miguez et al. (2002) que inseriram os custos associados com o grau de confiabilidade na função objetivo; em Carrano et 34 2 REVISÃO BIBLIOGRÁFICA SOBRE O PSDEE al. (2006), que também propôs um modelo multiobjetivo em que as funções custos com investi- mento e operação e custo com faltas são tratados simultaneamente; em Bernal-Agustín (1998), Ramirez-Rosado e Bernal-Agustin (2001), Cossi (2008), Pereira-Junior (2014) e Pádua (2014) que desenvolveram modelos multiobjetivo que tratam o problema de planejamento em conjunto com a confiabilidade mensurada com base no custo de energia não suprida. 2.2 MODELOS DE PSDEE Os modelos mais frequentemente utilizados na literatura tem como objetivo minimizar os custos com investimentos e custos operacionais. Os custos com investimentos geralmente estão associados com a construção e/ou recondutoramento de circuitos e construção e/ou ampliação de subestações. Podem ser encontrados na literatura vários trabalhos que tem como foco princi- pal somente a alocação e dimensionamento de circuitos, sendo conhecidas à priori a localização e a potência da subestação, como em Adams e Laughton (1974). Outros trabalhos centram es- forços na alocação e dimensionamento de subestações como em Crawford e Holt (1974). Os custos operacionais mais frequentemente utilizados na literatura consideram as perdas resistivas anuais, mas há trabalhos como o de Oliveira (2010) e Souza (2011) que em conjunto com os custos com perdas são considerados também os custos com operação das subestações (proporcional ao quadrado da potência aparente fornecida pela subestação ao sistema). Outros elementos considerados na função objetivo para avaliar os custos de cada proposta de solução para o PSDEE, adicionados aos custos usuais encontrados na literatura, são: custo da alocação de chaves de manobras e ramais de interconexão entre alimentadores, custo da energia não suprida, custo de banco de capacitores, reguladores de tensão e geração distribuída. O planejamento da expansão pode ser realizado em um único período (planejamento es- tático), como pode ser dividido em várias etapas de acordo com o crescimento gradativo da demanda (planejamento multiestágio). No planejamento estático é encontrado o plano otimi- zado de expansão em uma única etapa e a previsão de demanda corresponde à do final do período de planejamento. No planejamento multiestágio as ações do planejamento são realiza- das em diferentes estágios ao longo do horizonte de planejamento, de acordo com a previsão de demanda para cada período considerado e pode serdinâmicoou pseudodinâmico. O planeja- mentodinâmicoconsidera que as ações do planejamento ocorrem de forma coordenada entre os estágios, enquanto o planejamentopseudodinâmico, resolve o problema do planejamento para cada estágio como se fosse estático e o próximo estágio é inicializado com a solução do estágio anterior (COSSI, 2008). É importante destacar que, como o planejamento é realizado para um horizonte de tempo que pode ser de vários anos, os valores da função objetivo que se pretende otimizar devem ser atualizados ao valor presente utilizando as taxas de juros do mercado. Diante das características das restrições e dos custos com perdas, geralmente modelado 2.3 TÉCNICAS DE SOLUÇÃO DO PSDEE 35 como proporcional ao quadrado da corrente que passa pelos circuitos, o problema de PSDEE é um PNLIM. Se os custos com perdas forem linearizados, este modelo simplificado permite a solução do modelo equivalente com menor esforço computacional em relação à solução dos modelos não lineares. Em Souza (2013) e Lotero e Contreras (2011) são obtidos modelos apro- ximados dos modelos não lineares e o problema é resolvido como um problema de programação linear inteiro misto (PLIM) por umsoftwarecomercial. As restrições do problema de PSDEE, segundo Oliveira (2010), podem ser classificadas como físicas, operacionais e de investimento: - Restrições físicas: Estas restrições estão relacionadas à capacidade dos componentes do sis- tema, como: limite de fluxo de potência aparente nos circuitos, potência máxima fornecida pela subestação, dentre outras. - Restrições operacionais:São determinadas pela operação do sistema, tais como: limite de tensão nos nós, duplicidade de circuitos no mesmo ramo, radialidade etc. - Restrições de Investimento:Restrições impostas pela empresa em função do orçamento, ca- pacidade de subestações etc. As restrições usualmente utilizadas no modelo do PSDEE são: balanço de potência ou de cor- rente nas barras, limite de tensão nas barras, capacidade de potência dos circuitos e das subes- tações, condições de radialidade, condições de escolha de uma única opção para as variáveis de decisão. Outro aspecto diferenciado nos trabalhos refere-se ao número de funções objetivo utilizadas no modelo (mono ou multiobjetivo). O modelo mono-objetivo possui uma única função obje- tivo, enquanto o modelo multiobjetivo é composta por mais de uma função objetivo que são otimizadas simultaneamente. Na otimização mono-objetivo se trabalha no espaço das variáveis e se encontra uma única solução otimizada no espaço dos objetivos, enquanto na multiobjetivo se trabalha no espaço das variáveis e dos objetivos e como solução pode ser encontrado um conjunto de soluções (RENDÓN; ZULUAGA; OCAMPO, 2008). 2.3 TÉCNICAS DE SOLUÇÃO DO PSDEE As metodologias utilizadas para se resolver o problema de PSDEE podem ser agrupadas em: técnicas de otimização clássicas, técnicas heurísticas e metaheurísticas. A seguir, são apresentadas as principais característica destas técnicas de solução e as respectivas pesquisas desenvolvidas na área presentes na literatura. 2.3.1 Técnicas Clássicas de Otimização Os métodos clássicos de otimização utilizados no PSDEE estão baseados em técnicas de programação matemática com destaque para a programação linear inteiro misto (PLIM), a pro- 36 2 REVISÃO BIBLIOGRÁFICA SOBRE O PSDEE gramação não-linear (PNL) e a programação linear (PL). Segundo Haffner et al. (2006) a abordagem do problema na perspectiva da PLIM tem se revelado atrativa, pois reduz o esforço computacional comparada com os modelos não lineares e ainda garante a otimalidade do modelo correspondente. Dentre as técnicas mais utilizadas na literatura destaca-se o algoritmoBranch and Bound, que é um algoritmo enumerativo utilizado para resolver problemas combinatoriais deste tipo. O algoritmo B&B resolve um problema de PLIM utilizando um conjunto de subproblemas de programação linear, relaxando as condições de integralidade das variáveis do problema (OLIVEIRA, 2010). Este algoritmo foi utilizado em Adams e Laughton (1974), Gönen e Foote (1981), Boardman e Meckiff (1985), Paiva et al. (2005), Haffner et al. (2006), Haffner et al. (2008a) e Haffner et al. (2008b). Outro algoritmo desenvolvido na última década e utilizado em Oliveira (2010) é o B&B não linear que resolve diretamente os problemas de PNLIM. 2.3.2 Técnicas Heurísticas As técnicas heurísticas são algoritmos que utilizam procedimentos simples e rápidos e en- contram soluções de boa qualidade com esforço computacional relativamente pequeno. As heurísticas consideradas construtivas são técnicas que escolhem sequencialmente cada elemento para compor uma solução e o critério de escolha de cada elemento depende da função de avalia- ção adotada. Como exemplo podemos citar o chamado algoritmo guloso (greedy), que consiste em escolher em cada passo o elemento que produz o maior benefício local, orientado por uma função gulosa que escolhe o benefício da inserção de cada elemento na solução (RENDÓN; ZULUAGA; OCAMPO, 2008). Nas pesquisas da área de PSDEE, os Algoritmos Heurísticos Construtivos (AHC) são fre- quentemente utilizados como auxiliares ou como pontos de partida para a implementação de outras técnicas, pois geralmente são soluções de boa qualidade, porém dificilmente encontram o ótimo global do problema, principalmente em problemas de grande porte de sistemas elétricos de potência. Na literatura, Lavorato et al. (2010) propõe um AHC para o problema de PSDEE e em Souza (2011) é utilizado um AHC para gerar uma solução inicial para posteriormente aplicar uma metaheurística. Outro algoritmo heurístico utilizado em Goswami (1997) e Miguez et al. (2002) para resolver o problema de PSDEE é obranch-exchange, que em termos gerais consiste na técnica de troca de ramos. 2.3.3 Metaheurísticas As metaheurísticas são algoritmos que possuem estratégias que evitam a convergência pre- matura em ótimos locais no processo de busca da melhor solução de um problema de otimi- zação. Estas técnicas são utilizadas para resolver problemas combinatoriais complexos e ga- 2.4 REVISÃO BIBLIOGRÁFICA 37 nharam espaço nas pesquisas nas últimas décadas pela facilidade em tratar os problemas não lineares e inserir novas restrições ao modelo, embora não seja garantida a otimalidade da so- lução obtida. Em especial, os algoritmos de busca através da vizinhança, como oSimulated Annealing(SA), Tabu Search(TS) e GRASP, partem de uma solução inicial e usando um me- canismo de transição adequado, passam de uma solução atual para a melhor solução vizinha. O processo é repetido de acordo com a lógica de cada algoritmo até ser satisfeito o critério de parada. Durante este processo, a melhor solução (incumbente) vai sendo armazenada e ao final esta é a solução obtida pelo algoritmo para o problema. Na literatura foram encontrados vários trabalhos que utilizaram as metaheurísticas para resolver o problema de PSDEE, dentre eles podemos citar: • Algoritmos Genéticosem Bernal-Agustín (1998), Miranda, Ranito e Proença (1994), Car- rano et al. (2006), Najafi et al. (2009) e Camargo, Lavorato e Romero (2013); • Simulated Annealingem Jonnavithula e Billinton (1996), Parada et al. (2004) e Nahman e Peric (2008); • Colonia de Formigasem Gomez et al. (2004); • Tabu Searchem Baykasoglu, Owen e Gindy (1999), Cossi (2008), Baquero (2012) e Pereira-Junior (2014); • Particle swarm optimization(PSO) em Ganguly, Sahoo e Das (2009); • Busca em Vizinhança Variável(VNS) em Souza (2011); • Busca Dispersaem Pádua (2014). 2.4 REVISÃO BIBLIOGRÁFICA De acordo com Bernal-Agustín (1998) o primeiro trabalho sobre PSDEE registrado na li- teratura foi o de Knight (1960) que propôs a utilização da programação inteira para resolver o problema. Em Bernal-Agustín (1998) pode ser encontrada uma revisão bibliográfica dos traba- lhos desenvolvidos sobre o assunto até o ano de 1997. Diante da quantidade expressiva de estudos relacionados ao PSDEE encontrados na lite- ratura, são apresentados a seguir, resumidamente, somente os trabalhos consultados durante o desenvolvimento da presente pesquisa. Em Adams e Laughton (1974) foi proposto um modelo de programação linear inteira mista mono-objetivo para o PSDEE para obter a alocação e dimensionamento dos circuitos, sendo co- nhecidas a localização e a potência da subestação. A função objetivo a ser minimizada consiste nos custos com construção de circuitos e perdas resistivas. A função que representa as perdas 38 2 REVISÃO BIBLIOGRÁFICA SOBRE O PSDEE é não linear, a qual é linearizada e o modelo resultante é resolvido pelo AlgoritmoBranch & Bound. Na literatura há vários trabalhos que tomam a subestação como elemento principal do PS- DEE, como em Crawford e Holt (1974) que propôs um modelo mono-objetivo para obter a melhor localização, dimensão e a região de serviço das subestações. O trabalho em referência utilizou um modelo de programação inteira para minimizar a soma dos produtos das distâncias das subestações até os pontos de carga pela respectiva potência fornecida para este ponto pela subestação. A partir da década de 1990 são encontradas com bastante frequência na literatura especiali- zada as heurísticas e metaheurísticas como técnica de solução para resolver o planejamento do sistema de distribuição de energia elétrica. Em Miranda, Ranito e Proença (1994) foi utilizado o algoritmo genético para resolver o problema do PSDEE modelado como um PNLIM mono-objetivo e multiestágio. O modelo visa minimizar os custos com investimentos, perdas e custos associados com o grau de confiabilidade e desvio de tensão das barras do sistema. O horizonte de planejamento foi dividido em três estágios de planejamento, sendo classificado pela literatura comopseudodinâmico. O modelo e o algoritmo são testados em um sistema de 54 barras, o qual foi posteriormente utilizado em várias pesquisas presentes na literatura. No trabalho de Goswami (1997) o problema de PSDEE foi modelado como um PNLIM cujo objetivo foi minimizar os custos com investimentos e com as perdas resistivas do sistema. Para resolver o problema foi utilizado uma técnica heurística denominada deBranch Exchange. Inicialmente é gerada uma solução de topologia radial por meio de conexões uma a uma das barras às subestações previamente determinadas, seguindo critérios associados com a distância entre cada barra e as subestações. A técnica de troca de ramos, consiste em adicionar um ramo não pertencente a uma topologia radial que resulta na formação de uma malha na configuração presente e a seguir é escolhido um ramo para ser retirado do sistema e produzir soluções de melhor qualidade. As trocas de ramos ocorrem em duas etapas: realizando troca de ramos entre ramos ligados na mesma subestação (intrazona) e entre ramos ligados em subestações adjacentes (interzona). Em Bernal-Agustín (1998) foi utilizado o Algoritmo Genético para resolver o problema do PSDEE mono e multiobjetivo, numa formulação não linear, com o objetivo de minimizar os custos de investimentos e operação da rede e adicionalmente foram incluídos os custos com confiabilidade, por meio da avaliação da energia não suprida (ENS). A codificação do trabalho é inteira, com duas sequências de caracteres, a primeira se relaciona aos circuitos e a segunda às subestações, que permite a inserção de vários tipos de condutores e capacidades de subestações. Com o modelo proposto foi possível realizar tanto o planejamento estático como o multiestágio. 2.4 REVISÃO BIBLIOGRÁFICA 39 Em Miguez et al. (2002) foi proposta uma versão melhorada da técnica heurística deBranch Exchange, com o objetivo de obter a configuração ideal dos alimentadores de média tensão e a potência instalada nas subestações, sendo conhecidas a localização geográfica dos pontos de carga e das subestação e a demanda de potência dos consumidores. O problema foi modelado como um PNLIM que teve como objetivo minimizar os custos de investimento com infraes- trutura e com perdas de potência ativa, bem como os custos com a confiabilidade mensurado com base no somatório dos produtos entre o coeficiente do custo com confiabilidade, o fluxo de corrente em cada circuito e seus respectivos comprimentos. Os cálculos de confiabilidade foram feitos considerando apenas o disjuntor colocado na saída da subestação. As restrições consideradas para o problema são: limite da queda de tensão ocorrida nos ramos, a radialidade e o número máximo anual de interrupções permitidas. Em Ramirez-Rosado e Bernal-Agustin (2001) foi proposta uma metodologia de otimização multiobjetivo não linear inteiro misto, para minimizar os custos com investimentos (fixos e variáveis) e confiabilidade do sistema, simultaneamente. Para mensurar a confiabilidade do sistema foi utilizado o conceito de subestações e alimentadores fictícios que fornecem a energia não suprida no caso de falta no sistema. A técnica de solução utilizada para resolver o problema é um algoritmo evolutivo multiobjetivo. Em Skok, Krajcar e Skrlec (2005) foi proposto um planejamento multiestágio com malhas abertas estruturadas, incluindo geração distribuída conectada à rede sob condições de incerteza. Como técnica de solução foram utilizados dois algoritmos evolucionários interdependentes (um mestre e outro escravo) para resolver simultaneamente o problema com custos usualmente uti- lizados no planejamento e com a confiabilidade alcançada. A confiabilidade foi tratada no mo- delo de forma explícita com base na avaliação econômica dos índices de confiabilidade ENS, FEC e DEC e de forma implícita na escolha da configuração que indica os locais ideais para se alocar os ramais de reserva para atingir o melhor grau de confiabilidade com menor custo de investimento e operação. A metodologia foi testada em um sistema baseado nos dados reais de distribuição de uma cidade. Em Carrano et al. (2006) foi apresentado um modelo matemático multiobjetivo para o pro- blema de PSDEE, com duas funções objetivo, a primeira está relacionada com os custos mo- netários com investimentos com circuitos e subestações, manutenção e operação e a segunda com os custos com as interrupções (número e tempo de duração). Para resolver o problema foi utilizado um algoritmo genético multiobjetivo e os conceitos da fronteira ótima de Pareto. Em Cossi (2008) foi proposto um planejamento integrado do sistema de distribuição pri- mário (média tensão) e secundário (baixa tensão). O modelo de planejamento do sistema de distribuição primário foi abordado como um problema de programação não linear inteiro misto (PNLIM) estático multi-objetivo, com duas funções objetivos, uma relacionada com custos com construção/recondutoramento dos circuitos, ampliação/construção de subestações, alocação de 40 2 REVISÃO BIBLIOGRÁFICA SOBRE O PSDEE chaves e ramais de interconexão entre os alimentadores e perdas resistivas e a outra com a confi- abilidade do sistema por meio dos custos de energia não suprida. Como técnica de solução para o problema foi utilizado um algoritmo Tabu Search (TS) reativo em que os múltiplos objetivos são considerados utilizando os conceitos de soluções não dominadas para encontrar a fronteira ótima de Pareto. Para o planejamento dos circuitos secundários o modelo é formulado também como um (PNLIM) resolvido por um algoritmo TS, em três etapas: a primeira refere-se ao ba- lanceamento das cargas nas fases do circuito, a segunda está relacionada a alocação, capacidade e quantidade de transformadores que comporão a rede e a terceira define as rotas e o tipo dos condutores dos circuitos secundários. Para integrar o planejamento dos sistemas de média e baixa tensão foi utilizada uma técnica heurística orientada por um conjunto de regras usual- mente utilizadas para se realizar as conexões entre a rede primária e a secundária do sistema de distribuição de energia elétrica. Em Oliveira (2010) foi apresentado um modelo de planejamento do sistema de distribuição de energia elétrica estático integrado com instalação de capacitores e reguladores de tensão, com o objetivo de minimizar os custos com: construção/repotenciação de subestações, cons- trução/recondutoramento de circuitos, perdas ativas, operação das subestações, instalação de banco de capacitores fixos e de reguladores de tensão. O problema é modelado como um PN- LIM e para resolvê-lo foram implementados um AHC e um AlgoritmoBranch and Boundnão linear. Em Lotero e Contreras (2011) foi apresentado uma formulação para o problema de PSDEE multiestágio. A função objetivo a ser minimizada é o valor presente líquido dos custos com adi- ção/recondutoramento de circuitos e instalação/ampliação de subestações, operação associado as perdas resistivas nos circuitos e subestação e manutenção da rede. A função não linear foi aproximada em partes por uma função linear, resultando em um modelo linear inteiro misto que é resolvido usando osolver(GAMS/CPLEX). O modelo encontra um conjunto de soluções para o PSDEE e em seguida são determinados os índices de confiabilidade CIF (Customer Interrup- tion Frequency), CID (Customer Interruption Duration), EENS (Expected Energy Not Served), SAIFI (System Average Interruption Frequency Index), SAIDI (System Average Interruption Duration Index), ASAI (Average System Availability Index) para cada estágio do horizonte de planejamento das soluções encontradas. São calculados os custos associados à violação dos valores dos referidos indicadores tomando como referência os limites estabelecidos pelo órgão regulador. Em Souza (2011) foi apresentado um modelo que visa minimizar os custos com investi- mento fixos (adição/recondutoramento de circuitos e ampliação/construção de subestações) e investimentos variáveis (perdas e operação da subestação) para o problema de PSDEE em uma única etapa no horizonte de planejamento, sujeito às restrições físicas e operacionais. Para obter o plano otimizado de expansão o processo de solução inicia com uma solução de boa qualidade 2.4 REVISÃO BIBLIOGRÁFICA 41 obtida por um AHC e a seguir é aplicada a metaheurística de Buscaem Vizinhança Variável (VNS). A metodologia foi testada para os sistemas de 23, 54, 136, 202 e 417 barras. Em Baquero (2012) foi proposta uma metodologia para resolver o problema de PSDEE baseada em uma estratégia de decomposição em subproblemas de seleção das subestações, so- lução de problemas de reconfiguração e seleção de condutores dependentes. O problema foi modelado como um PNLIM mono-objetivo que permite realizar tanto o planejamento estático como o multiestágio (pseudodinâmico e dinâmico). Para resolver o modelo foi utilizada a me- taheurísticaBusca Tabuem conjunto com algoritmos heurísticos especializados desenvolvidos para cada subproblema. As ações previstas para o planejamento são: construção e/ou ampliação de capacidade das subestações, alocação e dimensionamento dos circuitos. O modelo utilizado teve como objetivo minimizar os custos com construção e/ou recondutoramento de circuitos, ampliação e/ou construção de subestações e custos anuais com perdas de energia resistiva aten- dendo as restrições físicas e operacionais. Foram testados os sistemas de 54 e 417 barras na perspectiva do planejamento estático, pseudodinâmico e dinâmico. A estratégia de decomposi- ção em subproblemas permitiu o uso de programação paralela que reduziu significativamente o tempo computacional usualmente utilizado para resolver problemas desta natureza. Em Pereira-Junior (2014) foram propostos modelos de planejamentos da expansão a curto e a longo prazo modelados como um PNLIM multiobjetivo. O modelo de curto prazo utilizado considera as ações usualmente utilizadas pelas concessionárias, isto é, a alocação de banco de capacitores, reguladores de tensão e recondutoramento dos circuitos existentes. Este modelo é composto por duas funções objetivo, a primeira busca manter o mais próximo possível os níveis de tensão das barras da tensão de referência e a segunda está relacionada com custos com instalação de banco de capacitores, reguladores de tensão, recondutoramento de circuitos existentes e custos com as perdas de energia. Como técnica de solução foi utilizado o Algoritmo Genético multiobjetivo especializado. As ações ao longo prazo consideradas são: a reponteciação e/ou construção de subestações, construção e/ou recondutoramento de circuitos, possibilidade de reconfiguração da rede; alo- cação de chaves de manobras, construção de ramais de interconexão e alocação de geradores distribuídos. O horizonte de planejamento foi dividido em estágios, que foi resolvido na pers- pectiva do planejamento multiestágio dinâmico. Foram consideradas duas funções objetivo, a primeira está relacionada com os custos de investimento fixos e variáveis relacionada às ações ao longo prazo e a segunda se refere à confiabilidade do sistema com base no custo de ener- gia não suprida. Este modelo foi resolvido por meio do algoritmo Busca Tabu multiobjetivo utilizando os conceitos de soluções não dominadas para encontrar a fronteira ótima de Pareto. Em Souza (2013) foi apresentada uma metodologia para resolver o problema de PSDEE uti- lizando sequencialmente dois modelos formulados como de programação linear binária mista, que são resolvidos por técnicas de otimização clássica. Na primeira etapa foi encontrado o me- 42 2 REVISÃO BIBLIOGRÁFICA SOBRE O PSDEE lhor plano de expansão para os custos relacionados com investimentos e operação e na segunda etapa, visando garantir um bom nível de confiabilidade do sistema, buscou-se o melhor plano de expansão considerando os custos com energia não distribuída, custos com alocação de chaves e ramais de interconexões entre alimentadores para realizar a restauração da rede em condições de contingências. Em Pádua (2014) foi utilizado o Algoritmo Busca Dispersa para resolver três modelos do PSDEE formulados como PNLIM. O primeiro modelo realiza o planejamento a curto prazo permitindo ações como construção e/ou recondutoramento dos circuitos e instalação e /ou am- pliação de capacidade das subestações. Este modelo é estático mono-objetivo e visa definir quais circuitos serão construídos e/ou recondutorados e quais subestações serão construídas e/ou terão sua capacidade ampliada com menor custo sujeito a um conjunto de restrições físi- cas, operacionais e econômicas. O segundo modelo também é mono-objetivo e o planejamento realizado é multiestágio dinâmico sendo que as ações consideradas são as mesmas do primeiro modelo com o adicional que define quando estas ações serão realizadas. O terceiro modelo formulado é multiestágio (dinâmico) e multiobjetivo com o objetivo de inserir a confiabilidade no problema mensurada com base nos custos da energia não suprida. Os modelos propostos são resolvidos por meio da metaheurística Busca Dispersa e foram testados os sistemas de 54 e 417 barras. Neste capítulo foram apresentadas as principais referências pesquisadas durante o desen- volvimento deste trabalho. A revisão da literatura realizada permitiu caracterizar como as pes- quisas realizadas até o momento vêm tratando os modelos e técnicas de solução para resolver o problema de PSDEE. No próximo capítulo é apresentado o modelo matemático utilizado neste trabalho. 43 3 MODELO MATEMÁTICO PARA O PROBLEMA DO PSDEE Neste capítulo é apresentado o modelo matemático do planejamento multiestágio da expan- são do sistema de distribuição de energia elétrica que foi utilizado para o desenvolvimento deste trabalho, bem como os mecanismos que serão utilizados para resolvê-lo. Adicionalmente são abordados os conceitos teóricos referentes ao fluxo de carga de sistemas radiais de varredura. 3.1 PLANEJAMENTO DA EXPANSÃO DO SISTEMA DE DISTRIBUIÇÃO DE ENERGIA ELÉTRICA O problema do PSDEE visa determinar as alterações que devem ser realizadas no sistema para atender as condições de demanda futura, satisfazendo aos critérios técnicos de operação e segurança com o mínimo custo econômico (BAQUERO, 2012). Dada a sua natureza, o problema de PSDEE é modelado como um problema de PNLIM, cujo objetivo é minimizar os custos de investimentos e de operação do sistema, sujeito a um conjunto de restrições lineares e não lineares relacionados às condições físicas, operacionais e de confiabilidade do sistema. O modelo de planejamento proposto neste trabalho é multiestágio do tipo dinâmico que indica onde, quando e quais ações de planejamento devem ser realizadas ao longo do hori- zonte especificado. Este tipo de planejamento permite dividir o horizonte de planejamento em várias etapas para que os investimentos sejam distribuídos de acordo com a demanda prevista para cada período, o que resulta em tomadas de decisões de forma coordenada entre estágios diferentes. As variáveis inteiras representam a construção/recondutoramento de circuitos e a construção/repotenciação de subestações e as variáveis contínuas estão associadas às variáveis relacionadas ao estado de operação da rede de energia elétrica. Como o processo é realizado ao longo do horizonte de planejamento, os custos são atualizados em valores equivalentes numa mesma data de referência para que seja possível compará-los. As possibilidades de alterações nos ramos e subestações em qualquer um dos estágios do horizonte de planejamento são: construção de novos circuitos ou recondutoramento ou desco- nexão de circuitos existentes, ampliação de capacidade de subestações existentes ou construção de novas subestações. Esta formulação foi elaborada baseando-se nos trabalhos de Oliveira (2010), Baquero (2012), Haffner et al. (2006) e Bernal-Agustín (1998) no que se refere a função objetivo e às restrições técnicas e operacionais. Como diferencial deste trabalho, foram acrescentadas ao modelo usual 44 3 MODELO MATEMÁTICO PARA O PROBLEMA DO PSDEE as restrições relacionadas com a confiabilidade expressas pelas Equações (14) a (17) por meio da avaliação dos índices de continuidade do sistema. 3.2 MODELO MATEMÁTICO DO PSDEE O modelo utilizado para resolver o problema de PSDEE apresentado a seguir, é composto pela função objetivo representada pela Equação (1) sujeitas as restrições de (2) a (17). min f = T ∑ t=1 1 (1+ I)p(t) ︸ ︷︷ ︸ TVP                ∑ i j∈Ωl ∑ a∈Ωa ( ci j ,a,t ni j ,a,t l i j ) ︸ ︷︷ ︸ IC + ∑ i∈Ωbs ∑ b∈Ωts ( csi,b mi,b,t ) ︸ ︷︷ ︸ IS + δlt ∑ i j∈Ωl ∑ a∈Ωa βi j ,a,t gi j ,a ( V2 i,t + V2 j,t − 2Vi,t Vj,t cosθi j ,t ) ︸ ︷︷ ︸ CP + δst ∑ i∈Ωbs αi,b,t ( P2 Si,t +Q2 Si,t ) ︸ ︷︷ ︸ CO                (1) s.a. Pi,t−PSi,t +PDi,t = 0 ∀ i ∈Ωb, ∀ t ∈ T ′ (2) Qi,t−QSi,t +QDi,t = 0 ∀ i ∈Ωb, ∀ t ∈ T ′ (3) Vmin≤Vi,t ≤Vmax ∀ i ∈Ωb, ∀ t ∈ T ′ (4) P2 Si,t +Q2 Si,t ≤ ( mi,b,tSi,b )2 ∀ i ∈Ωbs, ∀b∈Ωts, ∀ t ∈ T ′ (5) P2 i j ,a,t +Q2 i j ,a,t ≤ ( βi j ,a,tSi j,a )2 ∀ i j ∈Ωl , ∀a∈Ωa, ∀ t ∈ T ′ (6) ∑ a∈Ωa ni j ,a,t ≤ 1 ∀ i j ∈Ωl , ∀ t ∈ T ′ (7) ∑ b∈Ωts mi,b,t ≤ 1 ∀ i ∈Ωbs, ∀ t ∈ T ′ (8) ni j ,a,t ∈ {0,1} ∀ i j ∈Ωl ,∀a∈Ωa, ∀ t ∈ T ′ (9) mi,b,t ∈ {0,1} ∀ i ∈Ωbs, ∀b∈Ωts ∀ t ∈ T ′ (10) ∑ i j∈Ωl ∑ a∈Ωa βi j ,a,t = nb−nbs ∀ t ∈ T ′ (11) βi j ,a,t ≤ t ∑ h=1 ni j ,a,h ∀ i j ∈Ωl ,∀a∈Ωa,∀ t ∈ T ′ (12) αi,b,t ≤ t ∑ h=1 mi,b,h ∀ i ∈Ωbs, ∀b∈Ωts, ∀ t ∈ T ′ (13) FICi,t ≤ FICp ∀ i ∈Ωb, ∀ t ∈ T ′ (14) DICi,t ≤ DICp ∀ i ∈Ωb, ∀ t ∈ T ′ (15) FECk,t ≤ FECp ∀k∈Ωal, ∀ t ∈ T ′ (16) DECk,t ≤ DECp ∀k∈Ωal, ∀ t ∈ T ′ (17) 3.2 MODELO MATEMÁTICO DO PSDEE 45 A função objetivo (1) corresponde a minimização do valor presente líquido dos custos fi- xos referentes aos investimentos com construção/recondutoramento de circuitos (IC) e constru- ção/repotenciação de subestações (IS), mais os custos de operação que estão relacionados aos custos de perdas ativas nos ramos (CP) e de operação nas subestações (CO), considerando osT estágios do horizonte de planejamento. O fator (TVP) atualiza os custos de investimentos e de operação de cada estágiot ao valor presente, sendoI a taxa de juros ep(t) o ano de início do estágiot a partir de um referencial adotado como base. As variáveis de decisãoni j ,a,t e mi,b,t indicam respectivamente, as alterações ocorridas nos ramos do sistema (construção de novos ou recondutoramento de ramos pré-existentes) e nas barras do sistema (construção ou ampliação de capacidade de subestações). As variáveisαi,b,t e βi j ,a,t são as variáveis que indicam respectivamente, se a subestaçãoi e o ramoij estão ativos no estágiot. Os valores deδlt e δst são determinados respectivamente, pelas Equações (18) e (19) apre- sentadas a seguir: δlt = ceφl 8760 np(t) ∑ p=1 1 (1+ I)p (18) δst = copφs8760 np(t) ∑ p=1 1 (1+ I)p (19) sendoce o custo do kWh,np(t) a duração em anos do estágiot, I a taxa de juros,cop o custo do kVA2h e os fatores de perdasφl e φs são determinadas com a relação entre as perdas médias e as perdas máximas, em um determinado período de tempo (OLIVEIRA, 2010). Quanto às restrições de natureza técnica e operacionais do modelo, as restrições (2) e (3) representam as equações de balanço de potência ativa e reativa, em quePi,t e Qi,t no estágiot calculadas pelas equações (20) e (21), respectivamente. Pi,t =Vi,t ∑ j∈Ωb Vj,t βi j ,a,t ( Gi j cosθi j ,t +Bi j senθi j ,t ) (20) Qi,t =Vi,t ∑ j∈Ωb Vj,t βi j ,a,t ( Gi j senθi j ,t−Bi j cosθi j ,t ) (21) SendoVi,t a magnitude da tensão da barrai no estágio t,θi j ,t=θi,t−θ j,t representa a diferença do ângulo de fase entre as barrasi e j no estágiot eGi j eBi j são respectivamente, os elementos de condutância e susceptância que formam a matriz de admitância nodal do sistema. A restrição (4) representa os limites da magnitude de tensão das barrasi permitidos. A res- trição (5) representa o limite máximo da potência aparente fornecida ao sistema pela subestação do tipob da barrai no estágiot. A restrição (6) representa o fluxo de potência aparente máximo no circuitoi j em que os fluxos de potência ativa e reativaPi j ,t e Qi j ,t no circuitoi j no estágiot 46 3 MODELO MATEMÁTICO PARA O PROBLEMA DO PSDEE são determinados por: Pi j,t =V2 i,t gi j ,a βi j ,a,t − Vi,t Vj,t βi j ,a,t ( gi j ,a cosθi j ,t + bi j ,a senθi j ,t ) (22) Qi j ,t =−V2 i,t bi j ,a βi j ,a,t − Vi,tVj,t βi j ,a,t ( gi j ,a senθi j ,t − bi j ,a cosθi j ,t ) (23) sendogi j ,a e bi j ,a a condutância e susceptância do ramoi j do condutor do tipoa, respectiva- mente. As restrições (7) e (8) garantem a escolha de somente uma alternativa de alteração para os ramos e subestações, respectivamente. As restrições (9) e (10) indicam a natureza binária das variáveis de decisão para cada estágio em análise. A restrição (11) é uma condição neces- sária para que o sistema possua uma topologia radial, isto é, permite que todas as barras com carga estejam conectadas e que não haja laços no sistema. A restrição (11) em conjunto com as restrições (2) e (3) asseguram a radialidade do sistema, como discutido em Lavorato et al. (2012). As restrições (14), (15), (16) e (17) relacionadas com a confiabilidade do sistema garantem que os valores dos índices de continuidade FIC (Frequência de Interrupção por Unidade Con- sumidora ), DIC (Duração de Interrupção por Unidade Consumidora) de cada barrai e o FEC (Frequência Equivalente de Interrupção por Unidade Consumidora) e DEC (Duração Equiva- lente de Interrupção por Unidade Consumidora) do conjunto de consumidoresk não tenham seus limites ultrapassados. Notação: bi j ,a Susceptância do ramoi j de condutor do tipoa. Bi j Elemento da matriz susceptância nodal. ci j ,a Custo do circuitoi j com condutor do tipoa que pode ser adicionado ou substituído em unidade monetária/km. cop Custo de operação da subestação em unidade monetária/kVA2h. csi,b Custo da subestação que é adicionada ao sistema ou repotenciada. ce Custo de perdas de energia em unidade monetária/kWh. DECk,t Duração Equivalente de Interrupção por Unidade Consumidora do alimenta- dork no estágiot. DECp Limite estipulado para o índice DEC no estágiot. DICi,t Duração de Interrupção por Unidade Consumidora da barrai no estágiot. DICp Limite estipulado para o índice DIC no estágiot. FECk,t Frequência Equivalente de Interrupção por Unidade Consumidora do ali- mentadork no estágiot. FECp Limite estipulado para o índice FEC no estágiot. FICp Limite estipulado para o índice FIC no estágiot. FICi,t Frequência de Interrupção por Unidade Consumidora da barrai no estágiot. 3.2 MODELO MATEMÁTICO DO PSDEE 47 gi j,a Condutância do ramoi j do condutor do tipoa. Gi j Elemento da matriz condutância nodal. Imaxa Corrente máxima permitida no condutor do tipoa. I Taxa de juros. l i j Comprimento do ramoi j . mi,b,t Variável binária que indica construção/repotenciação de subestação do tipo b na barrai no estágiot. nbs Número de barras com subestação (existentes e propostas). ni j ,a,t Variável binária que indica se o circuitoi j é construído ou recondutorado com condutor do tipoa no estágiot. nb Número de barras do sistema. np(t) Duração em anos do estágiot. PDi,t Potência ativa demandada pela barrai no estágiot. PSi,t Potência ativa fornecida pela subestação da barrai no estágiot. Pi,t Potência ativa calculada na barrai no estágiot. Pi j ,a,t Fluxo de potência ativa no condutor do tipoa que sai da barrai e vai para a barra j no estágiot. p(t) Ano de início do estágiot a partir de um referencial adotado como base (ano zero). QDi,t Potência reativa demandada pela barrai no estágiot. QSi,t Potência reativa fornecida pela subestação da barrai no estágiot. Qi,t Potência reativa calculada na barrai no estágiot. Qi j ,a,t Fluxo de potência reativa no condutor do tipoa que sai da barrai e vai para a barraj no estágiot. Si,b Limite máximo da potência aparente da subestação da barrai do tipob . Si j ,a,t Fluxo de potência aparente no ramoi j com condutor do tipoa no estágiot. Si j,a Fluxo de potência aparente máxima no ramoi j com condutor do tipoa. Vi,t Magnitude da tensão na barrai no estágiot. Vmax Magnitude de tensão máxima permitida no sistema. Vmin Magnitude de tensão mínima permitida no sistema. T Número de estágios do planejamento. T ′ {1,2, ...,T}. αi,b,t Variável binária que indica se a subestação do tipob da barrai está ativa no estágiot. βi j ,a,t Variável binária que indica se o ramo com condutor do tipoa entre as barras i e j está ativo no estágio t. θi j ,t Diferença angular entre as barrasi e j no estágiot. φl Fator de perdas dos circuitos. φs Fator de perdas das subestações. 48 3 MODELO MATEMÁTICO PARA O PROBLEMA DO PSDEE Ωl Conjunto de ramos (existentes e propostos) do sistema. Ωa Conjunto dos tipos de condutores. Ωal Conjunto de alimentadores do sistema. Ωb Conjunto de barras do sistema. Ωbs Conjunto de barras com subestações (existentes e propostas) comΩbs⊂Ωb. Ω f Conjunto de direções de fluxo de potência aparente. Ωts Conjunto do tipo de subestações. 8760 número de horas em um ano. 3.3 ESTRATÉGIAS UTILIZADAS PARA RESOLVER O MODELO MATEMÁTICO DO PSDEE O modelo do PSDEE resultante apresentado na Seção 3.2 é resolvido por meio de um Al- goritmo Genético Especializado (AG-ESP), cuja metodologia está detalhada no Capítulo 4, em conjunto com um Algoritmo de Fluxo de Carga para Sistemas de Distribuição Radiais (AFC). O AG-ESP, através de seus operadores genéticos e heurísticas associadas, geram soluções candidatas indicando os respectivos valores das variáveis de decisão binárias do problema. Para avaliar a factibilidade da solução gerada em relação às restrições operacionais é resolvido o problema do fluxo por meio do AFC que determina o estado da rede (tensão e ângulo de fase nas barras), valores das correntes nos ramos e o valor da potência fornecida pelas subestações ao sistema. Estes resultados também orientam a heurística de seleção e troca de condutores, a etapa de melhoria local e ainda fornece o valor das perdas resistivas para o cálculo de seus custos. A seguir é apresentado os conceitos teóricos do fluxo de carga utilizado neste trabalho. 3.3.1 Fluxo de Carga Considerando que a topologia do sistema de distribuição é radial e que a relação reatân- cia/resistência depende do tipo de condutor de cada ramo, optou-se para o desenvolvimento deste trabalho o fluxo de carga de varredura similar ao utilizado em (SHIRMOHAMMADI et al., 1988), que é uma aplicação das leis de Kirchhoff de tensões e correntes. Este algoritmo é simples e eficaz, pois apresenta bom comportamento em relação à convergência e não requer muita memória computacional para a solução do problema (BAQUERO, 2012). O processo é iniciado escolhendo-se um valor de tensão para as barras, usualmente o mesmo valor de tensão da subestação. O método consiste em duas etapas, abackwarde a forward. No processobackwardsão calculadas as correntes nas barras e nos ramos, partindo das barras finais em direção à subestação. No processoforwardas tensões são atualizadas com as correntes 3.3 ESTRATÉGIAS UTILIZADAS PARA RESOLVER O MODELO MATEMÁTICODO PSDEE 49 calculadas na etapabackward, partindo da subestação em direção às barras mais distantes. Estes passos são repetidos até que se obtenha a convergência do método. 3.3.1.1 Renumeração das barras Como o método de fluxo de carga de varredura percorre da barra mais distante da subes- tação para as mais próximas na etapabackwarde vice-versa na etapaforward, então torna-se necessário enumerar os ramos por camadas a medida que vão se afastando da barra principal. A Figura 1 ilustra a disposição das barras a partir da subestação para o sistema de 14 barras e a Figura 2 apresenta as barras devidamente renumeradas para a utilização do método. Figura 1 - Sistema de 14 barras antes da ordenação 14 13 9 4 81112 7 3 2 10 6 5 1 Fonte: Da própria autora Figura 2 - Sistema de 14 barras ordenado. 1 2 3 4 765 8 9 10 11 12 13 14 Fonte: Da própria autora A seguir é apresentada a formulação matemática utilizada pelo método. 50 3 MODELO MATEMÁTICO PARA O PROBLEMA DO PSDEE 3.3.1.2 Etapa Backward (varredura das correntes): Nesta etapa são determinadas as injeções de corrente nas barras e a corrente nos ramos. Seja a tensãȯVj e a potência aparente da cargaṠj da barraj, as injeções de correntei j em cada barraj podem ser determinadas por: i j = ( Ṡj V̇j )∗ (24) Calculadas as injeções de corrente em cada barra, os fluxos de corrente nos ramoskmpodem ser determinados pela Eq. (25): ˙Ikm= ˙Idm+ ∑ j∈Ωm ˙I jm (25) onde: ˙Ikm: fasor da corrente no ramokm. ˙Idm: fasor da corrente demandada na barram. Ωm: conjunto de barras ligadas à barrama sua jusante. 3.3.2 Etapa Forward (varredura de tensões) Seja o ramok-mde um sistema de distribuição radial ilustrada pela figura 3. Figura 3 - Ramo k-m de um sistema de distribuição radial • • • • • • k m Ikm • Zkm k • V • mV •• Fonte: Da própria autora Sendo conhecida a tensão na barrak, a tensão da barrampode ser determinada pela equação a seguir: V̇m = V̇k− ˙Ikm(rkm+ jxkm) (26) sendo: V̇k: fasor da tensão na barra inicial do ramokm. V̇m: fasor da tensão na barra final do ramokm. 3.3 ESTRATÉGIAS UTILIZADAS PARA RESOLVER O MODELO MATEMÁTICODO PSDEE 51 ˙Ikm: fasor da corrente no ramokm. rkm: resistência do ramokm. xkm: reatância do ramokm. 3.3.2.1 Cálculo das Perdas Sendo ˙Skmp as perdas no ramo k-m da Figura 3, as perdas ativa e reativa do sistema podem ser obtidas da seguinte forma: ˙Skmp = ∆ ˙Vkm( ˙Ikm) ∗ = ˙Zkm( ˙Ikm)( ˙Ikm) ∗ Sendo: ˙Zkm= rkm+ jxkm ˙Skmp = (rkm+ jxkm)( ˙Ikm)( ˙Ikm) ∗ ˙Skmp = (rkm+ jxkm)(Ikm) 2 ˙Skmp = rkm(Ikm) 2+ jxkm(Ikm) 2 Como ˙Skmp = Pkmp + jQkmp, então as perdas ativas e reativas no sistema podem ser calculadas utilizando as equações (27) e (28) respectivamente: Pt = ∑ (k,m)∈Ωb rkmI2 km (27) Qt = ∑ (k,m)∈Ωb xkmI2 km (28) sendo: Pkmp: Perdas ativa do ramo k-m. Qkmp: Perdas reativa do ramo k-m. Pt : Perdas ativas totais do sistema. Qt : Perdas reativas totais do sistema. Apresentada a formulação matemática que são utilizadas pelo método, após realizada a or- denação das barras, o Algoritmo de Fluxo de Carga Radial de Varredura, pode ser resumido nos seguintes passos: 1. Fixar as tensões nas barra como sendo a tensão da barra de referência e assumirPper1 = 0 e escolher a tolerânciaε. 2. Iniciando das barras extremas, calcular as correntes das barras e dos ramos através das 52 3 MODELO MATEMÁTICO PARA O PROBLEMA DO PSDEE Equações (24) e (25) respectivamente (etapa backward). 3. Calcular as perdas ativas do sistema usando a Eq. (27) e assumirPper2 = Pt . 4. Se ∣ ∣Pper2−Pper1 ∣ ∣≤ ε, pare porque foi atingida a convergência. Em caso contrário, fazer Pper1 = Pper2 e passe ao passo seguinte. 5. Partindo da subestação, atualizar os valores das tensões usando os valores das correntes dos ramos determinados anteriormente (etapa forward). Volte ao passo ii. Neste capítulo foi apresentado o modelo do problema de PSDEE utilizado neste trabalho. No próximo capítulo é apresentada a técnica de solução utilizada para resolvê-lo. 53 4 ALGORITMO GENÉTICO ESPECIALIZADO APLICADO AO PSDEE Neste capítulo são abordados inicialmente os aspectos teóricos do Algoritmo Genético Tra- dicional (AG) e do Algoritmo Genético Modificado de Chu-Beasley (AGCB) que deram susten- tação teórica-metodológica para o desenvolvimento deste trabalho. Posteriormente é apresen- tada de forma detalhada a metodologia utilizada para a implementação do Algoritmo Genético Especializado (AG-ESP) para resolver o problema de PSDEE. 4.1 ALGORITMO GENÉTICO TRADICIONAL E ALGORITMO GENÉTICO MODIFI- CADO DE CHU-BEASLEY O Algoritmo Genético faz parte das técnicas evolutivas propostas nos anos de 1950 sendo originalmente idealizado por Holland na década de 1970. Fundamenta-se na analogia com processos naturais de evolução, na qual, dada uma população inicial, os indivíduos com carac- terísticas genéticas melhores têm mais chance de sobrevivência e de transmitirem seu código genético para os descendentes que serão cada vez mais adaptados, enquanto os piores tendem a desaparecer (RENDÓN; ZULUAGA; OCAMPO, 2008). Na aplicação do AG em problemas de otimização, o processo inicia gerando uma população inicial composta por um conjunto de indivíduos (possíveis soluções candidata para o problema a ser otimizado), geralmente utilizando funções aleatórias. Cada solução candidata da popu- lação inicial é mensurada por uma função de adaptação que indica o seu grau de qualidade para o problema a ser otimizado. A seguir, são selecionados os indivíduos que poderão repro- duzir, sendo que os melhores (mais adaptados) têm maior chance de participarem desta etapa. Para a próxima etapa, os operadores genéticos, como a recombinação (crossover) e a mutação, são aplicados, com o objetivo de que as características de adaptação adquirida pelas gerações anteriores sejam transmitidas e que os indivíduos gerados sejam diversificados para favorecer condições para uma eficiente exploração do espaço de busca, evitando assim convergência pre- matura. Assim, os algoritmos genéticos são estratégias que utilizam combinações e acumula um conhecimento histórico produzido pelos resultados que vão sendo obtidos ao longo do processo e que orienta a exploração do espaço de busca. Resumidamente, o AG é composto das seguintes etapas: 1. Especificar os parâmetros de controle (tamanho da população, taxas de recombinação e de mutação, dentre outras); 54 4 ALGORITMO GENÉTICO ESPECIALIZADO APLICADO AO PSDEE 2. Apresentar as especificidades do problema tais como: tipo de codificação e de seleção, maneira de estruturar a população inicial e manipular infactibilidades etc.; 3. Obter uma população inicial que se torna a população corrente; 4. Determinar o valor da função objetivo (fitness) de cada elemento da população corrente e atualizar a incumbente (melhor solução encontrada); 5. Avaliar se o critério de parada foi satisfeito, caso positivo, parar, caso contrário, ir ao passo 6; 6. Realizar a seleção; 7. Realizar a recombinação; 8. Realizar a mutação; 9. Recompor a população corrente para a próxima geração e voltar ao passo 4. Uma modificação estratégica do AG tradicional foi proposta no trabalho de Chu e Beas- ley (1997) para resolver o problema de alocação den tarefas param agentes denominado de Generalized Assignment Problem, com geralmenten >> m. Trata-se de um problema linear inteiro binário multirestrito que gera muitas soluções infactíveis em função dos operadores ge- néticos e da geração da população inicial. Resumidamente, o (AGCB) pode ser implementado da seguinte maneira: 1. Especificar os parâmetros de controle (tamanho da população, taxas de recombinação e de mutação, dentre outras); 2. Apresentar as especificidades do problema tais como: tipo de codificação e de seleção, maneira de estruturar a população inicial e manipular infactibilidades etc.; 3. Obter uma população inicial de forma aleatória que se torna a população corrente; 4. Determinar os valores da função objetivo (fitness) e da infactibilidade (unfitness) dos in- divíduos da população corrente; 5. Atualizar a incumbente (melhor solução encontrada); 6. Realizar a seleção e escolher somente duas soluções geradoras; 7. Realizar a recombinação e preservar somente um descendente; 8. Realizar a mutação do descendente preservado; 9. Implementar uma fase de melhoria local; 4.2 ALGORITMO GENÉTICO ESPECIALIZADO PARA RESOLVER O PROBLEMA DE PSDEE 55 10. Verificar se o descendente melhorado pode entrar na população, caso positivo, substituir um elemento da população corrente e atualizar a incumbente, caso contrário, descartar a solução gerada; 11. Avaliar se o critério de parada foi satisfeito, caso positivo, parar, caso contrário, ir para o passo 6. As principais diferenças do AGCB em relação ao AG, consiste em: • As infactibilidades são tratadas de forma diferenciada. Os valores da funçãofitnessob- tidos pela função objetivo e da funçãounfitnessque quantifica a infactibilidade de cada solução testada, são tratados separadamente. Os valores dafitnesssão usados na fase de seleção e substituição e os daunfitnessna fase de substituição na troca de uma solução gerada infactível por outra de pior qualidade. • Somente um indivíduo é substituído na população corrente em cada ciclo geracional, se este for diferente de todos os demais e melhor que o de pior qualidade da população corrente. • Prevê uma fase de melhoria local que permite tratar o descendente antes de decidir se o indivíduo vai ou não substituir um elemento da população atual. Esta fase permite melhorar a qualidade do descendente e tratar as infactibilidades das soluções geradas pelos operadores genéticos. Segundo Rendón, Zuluaga e Ocampo (2008), as modificações proposta no AGCB o tornou muito mais competitivo para avaliar sistemas de grande porte e complexidade. 4.2 ALGORITMO GENÉTICO ESPECIALIZADO PARA RESOLVER O PROBLEMA DE PSDEE Neste trabalho, baseando-se no AGCB, foi implementado um Algoritmo Genético Especi- alizado (AG-ESP) para resolver o problema de PSDEE. Considerando as particularidades do problema tratado, algumas modificações e adaptações foram inseridas na metodologia original do trabalho de Chu-Beasley como: a forma como é gerada a população inicial; as estratégias de melhoria local do descendente e a maneira empregada para a realização do controle da di- versidade na população, dentre outros. A seguir são apresentadas detalhadamente cada uma das etapas de implementação do AG-ESP. 56 4 ALGORITMO GENÉTICO ESPECIALIZADO APLICADO AO PSDEE 4.2.1 Codificação do Problema 4.2.1.1 Planejamento Estático A codificação do problema é inteira para que cada solução possa retratar de forma clara e adequada as especificidades dos condutores dos circuitos a serem instalados e as capacidades escolhidas das subestações do sistema. A proposta de solução é representada por um vetor com duas sequências de caracteres, a primeira parte de tamanhonr , representa os ramos propostos e existentes do sistema e a segunda de tamanhonbs as subestações (candidatas e existentes). Para a primeira parte da representação da solução os números inteiros maiores que zero são utilizados para indicar o tipo de condutor a ser instalado no respectivo ramo e 0 indica que o circuito não está ativo. Os condutores novos são numerados de 1 ao número de alternativas de condutores propostos que são categorizados pela capacidade de conduzir corrente. Para os condutores pré-existentes é escolhido o tipo de condutor e acrescido de 100 para distinguí- los dos novos. Por exemplo um condutor novo do tipo 2 será representado por 2, enquanto o existente será representado por 102. Para a segunda sequência do vetor codificação o número inteiro maior que zero indica que a subestação está ativada e zero que não. As subestações são categorizadas de acordo com suas capacidades de fornecer potência. As candidatas à construção são representadas de 1 ao número de alternativas do problema, enquanto que as subestações existentes são representadas por múltiplos de 10. A subestação existente sem alteração de capacidade é representada por 10 e as que foram ampliadas em sua capacidade serão 20, 30 e assim por diante, conforme o número de alternativas de ampliação da capacidade do sistema. Para ilustrar a codificação do planejamento estático a Figura 4 representa uma proposta de solução que indica que no ramo 1 há um condutor existente do tipo 1, nos ramos 3 e 6 foram construídos com condutor do tipo 1 e os ramos 2 e 8 foram construídos ou recondutorados com condutores do tipo 3 e 2, respectivamente e o 4, 5 e 7 não estão ativos. Em relação às subestações, SE1 corresponde a uma subestação existente que não foi repotenciada e SE2 foi construída utilizando a alternativa com capacidade do tipo 2. Figura 4 - Exemplo de codificação para o planejamento estático. Fonte: Adaptado de Bernal-Agustín (1998) 4.2 ALGORITMO GENÉTICO ESPECIALIZADO PARA RESOLVER O PROBLEMA DE PSDEE 57 4.2.1.2 Planejamento Multiestágio Para o planejamento da expansão multiestágio a proposta de solução é representada por uma matriz de dimensão (nest x nt), sendonest o número de estágios ent = nr +nbs, sendonr o número de ramos enbs o número de barras com subestações (propostas e existentes). A Figura 5 ilustra uma proposta de solução de três estágios de planejamento, sendo que o ramo 1 pré- existente permaneceu com o condutor do tipo 1 nos três estágios. O ramo 8 foi construído no segundo estágio com o condutor do tipo 1 e recondutorado no terceiro com condutor do tipo 2. A subestação SE1 existente permaneceu com a mesma capacidade nos três estágios, enquanto SE2 permaneceu com a capacidade da subestação existente nos dois primeiros estágios e no terceiro foi repotenciada. A subestação SE3 foi construída no primeiro estágio com capacidade do tipo 1 e SE4 foi construída no segundo estágio com a capacidade do tipo 2. Os ramos não construídos ou desativados são representados por 0 Figura 5 - Exemplo de codificação para o planejamento multiestágio. 101 1 1 0 0 0 0 0 8 10 10 1 0 101 1 0 8 0 0 2 8 10 20 1 2 1 2 3 4 5 6 7 8 9 10 11 12 13 SE1 SE2 SE3 SE4 Estágio 1 Estágio 30 . 101 1 1 1 1 1 0 8 10 10 1 2 Estágio 21 ... ... ... ... ... ... ... ... ... ... ... ... Fonte: Da própria autora 4.2.2 População Inicial O AG e o AGCB sugerem gerar a população inicial de forma aleatória. No entanto, para os problemas complexos de engenharia elétrica a geração de uma população aleatória pode au- mentar muito o tempo computacional para se encontrar soluções de qualidade e além disso, a quantidade de soluções infactíveis a serem incorporadas na população inicial podem ser nume- rosas e muito distantes da factibilidade. Considerando estas situações foi implementado para o desenvolvimento deste trabalho um Algoritmo Heurístico Construtivo para gerar os indivíduos da população inicial com características desejáveis e que levem em conta as restrições do pro- blema. O AHC implementado primeiro seleciona as subestações que farão parte da solução e a seguir, a cada passo, vai acrescentando um ramo ao sistema. Para a escolha de cada ramo, inici- almente é selecionada qual a subestação que este será ligado, usando como critério de seleção a que possui o maior valor de potência aparente disponível (em percentuais). A seguir, são iden- tificados os ramos candidatos e um deles é selecionado aleatoriamente para ser acrescentado ao sistema. O processo se repete até que todas as barras do sistema estejam conectadas ao sistema. As subestações de cada solução candidata são selecionadas segundo critérios específicos, 58 4 ALGORITMO GENÉTICO ESPECIALIZADO APLICADO AO PSDEE conforme detalhado na Seção 4.2.2.1 e estas informações são armazenadas em dois vetores denominados neste trabalho deSUB-1e SUB-2. Foram gerados dois conjuntos distintos de subestações que fazem parte de cada solução, porque as melhores soluções testadas dos sis- temas pertencem ao primeiro grupo de subestações e, consequentemente, a busca de soluções nas regiões deste grupo foram intensificadas. Assim sendo, os primeiros 70% dos indivíduos da população inicial serão selecionados aleatoriamente dentre as alternativas de estruturas de subestações do ConjuntoSUB-1e o restante do ConjuntoSUB-2. Depois de escolhidas as su- bestações da solução, é realizado um processo construtivo para se obter os circuitos que farão parte da solução. Obtida a topologia da solução, é feita a seleção de condutores, cuja metodo- logia está detalhada na subseção 4.2.7.1. 4.2.2.1 Processo de Seleção de Subestações Para a seleção das subestações foi realizado inicialmente um pré-processamento para iden- tificar as subestações existentes e as que devem estar obrigatoriamente presentes no sistema para que todos as barras possam estar conectadas ao sistema. As especificações destas subesta- ções são armazenadas em um vetor denominado de SUB-Ex de dimensão igual ao número de barras com subestações. É apresentada a seguir a maneira como foram obtidos os elementos dos Conjuntos SUB-1 e SUB-2. Conjunto SUB-1 Cada elemento do conjuntoSUB-1é composto pelas subestações que farão parte das so- luções candidatas. Parte-se das informações de SUB-Ex e a seguir, os elementos que com- porão o conjunto SUB-1 é o resultado de todas as combinações de alternativas de constru- ção/repotenciação de subestações com capacidade de fornecimento mínimo para atender a po- tência demandada pelos nós de consumo mais as perdas no sistema. No caso do planejamento multiestágio, as informações das subestações no primeiro estágio assume SUB-Ex. Posteriormente é avaliado se a potência total fornecida pelas subestações é maior ou igual à potência demandada do referido estágio, caso positivo, inicia-se a seleção das subestações para o estágio seguinte, caso contrário, faz-se todas as possíveis combinações de seleção de subestações de forma a atender a demanda deste estágio. As subestações de cada estágio recebe inicialmente a estrutura de subestação do estágio anterior e o processo se repete até que as subestações sejam selecionadas para todos os estágios. Conjunto SUB-2 As estruturas de subestações deste conjunto são obtidas de forma aleatória, de acordo com os passos apresentados a seguir. 1. Inicia-se com SUB-2 =∅. 4.2 ALGORITMO GENÉTICO ESPECIALIZADO PARA RESOLVER O PROBLEMA DE PSDEE 59 2. SUB-k← SUB-Ex. 3. Para cada subestação um número aleatório é sorteado para decidir se a subestação sofrerá modificação, isto é, se será construída ou repotenciada. Caso positivo, sorteia-se qual a alternativa (tipo) daquela subestação será selecionada. 4. SUB-k é atualizada recebendo as informações das escolhas feitas no passo anterior. 5. Avalia-se se a potência total fornecida pelas subestações é suficiente para atender a de- manda, caso positivo, segue-se ao passo 6, caso negativo, a estrutura obtida é descartada e retorna-se ao passo 2. 6. Avalia-se se a estrutura de subestação SUB-k é repetida, caso positivo, esta é descartada, caso contrário uma nova estrutura é obtida e SUB-2← SUB-2 + SUB-k. O processo se repete até que um número definido de iterações seja executada. No caso do planejamento multiestágio, para o primeiro estágio inicia-se com SUB-Ex e a partir dela são feitos os sorteios de ampliação ou não de potência das subestações. Para os demais estágios inicia-se com a estrutura de subestação do estágio anterior e