Orientador: Rubén Augusto Romero Lázaro / Banca: Anna Diva Plasencia Lotufo / Banca: Marcos Julio Rider Flores / Resumo: Neste trabalho é realizada uma análise teórica, a formulação conceitual e a implementação computacional de um algoritmo de vizinhança variável aplicado ao problema de planejamento a longo prazo de sistemas de transmissão de energia elétrica. O problema de planejamento de sistemas de transmissão é um problema muito complexo de resolver porque o modelo matemático é um problema de programação não linear inteiro misto. Por outro lado, a metaheurística de vizinhança variável é uma técnica de otimização que provou excelente desempenho na resolução de problemas complexos no campo da pesquisa operacional. Assim, neste trabalho é desenvolvido um algoritmo de vizinhança variável para o problema de planejamento de sistemas de transmissão. Um conceito importante na implementação desse algoritmo é a definição de vizinhança em relação a caminhos e a técnica de redução do tamanho da vizinhança. Testes realizados mostraram um excelente desempenho do algoritmo VNS, encontrando as melhores soluções conhecidas e mostradas na literatura especializada / Abstract: In this work a theoretical analysis is carried through, the conceptual formularization and the computational implementation of an applied algorithm of variable neighborhood to the problem of planning in the long run of systems of transmission of electric energy. The problem of planning of transmission systems is a very complex problem from solve because the mathematical model is a programming problem not linear. On the other hand, the metaheuristic of variable neighborhood is one technique of optimization that proved excellent performance in the resolution of complex problems in the field of the operational research. Thus, in this work is developed an algorithm of variable neighborhood for the problem of planning of transmission systems. An important concept in the implementation of this algorithm is the definition of neighborhood in relation the paths and the technique of reduction of the size of the neighborhood. Tests carried through had shown to an excellent performance of algorithm VNS, finding the best solutions known and shown in specialized literature / Mestre

Made available in DSpace on 2014-06-11T19:22:33Z (GMT). No. of bitstreams: 0 Previous issue date: 2009-11-30Bitstream added on 2014-06-13T18:08:29Z : No. of bitstreams: 1 martins_wa_me_ilha.pdf: 616652 bytes, checksum: e8d6346d5cc6774ab31d1538b90cb349 (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Neste trabalho é realizada uma análise teórica, a formulação conceitual e a implementação computacional de um algoritmo de vizinhança variável aplicado ao problema de planejamento a longo prazo de sistemas de transmissão de energia elétrica. O problema de planejamento de sistemas de transmissão é um problema muito complexo de resolver porque o modelo matemático é um problema de programação não linear inteiro misto. Por outro lado, a metaheurística de vizinhança variável é uma técnica de otimização que provou excelente desempenho na resolução de problemas complexos no campo da pesquisa operacional. Assim, neste trabalho é desenvolvido um algoritmo de vizinhança variável para o problema de planejamento de sistemas de transmissão. Um conceito importante na implementação desse algoritmo é a definição de vizinhança em relação a caminhos e a técnica de redução do tamanho da vizinhança. Testes realizados mostraram um excelente desempenho do algoritmo VNS, encontrando as melhores soluções conhecidas e mostradas na literatura especializada / In this work a theoretical analysis is carried through, the conceptual formularization and the computational implementation of an applied algorithm of variable neighborhood to the problem of planning in the long run of systems of transmission of electric energy. The problem of planning of transmission systems is a very complex problem from solve because the mathematical model is a programming problem not linear. On the other hand, the metaheuristic of variable neighborhood is one technique of optimization that proved excellent performance in the resolution of complex problems in the field of the operational research. Thus, in this work is developed an algorithm of variable neighborhood for the problem of planning of transmission systems. An important concept in the implementation of this algorithm is the definition of neighborhood in relation the paths and the technique of reduction of the size of the neighborhood. Tests carried through had shown to an excellent performance of algorithm VNS, finding the best solutions known and shown in specialized literature

O principal objetivo deste estudo é propor uma nova metodologia para lidar com o problema de Planejamento da Expansão de Redes de Transmissão de Energia Elétrica com Múltiplos Cenários de Geração (PERTEEG). Com a metodologia proposta neste trabalho almeja-se construir planos de expansão de redes de transmissão de energia elétrica que sejam capazes de, no menor custo de investimento possível, satisfazer às novas exigências dos sistemas elétricos modernos, tais como construção de redes de transmissão livres de congestionamento e robustas à incerteza em relação aos cenários de geração futuros. Através de estudos realizados na literatura do problema, verificou-se que novos modelos e metodologias de abordagem do PERTEEG se fazem necessários. Ao se modelar o PERTEEG visando construir redes de transmissão que contornem as incertezas em relação aos cenários de geração futuros e concomitantemente minimizar o custo de investimento para a expansão do sistema, o planejador se depara com um problema de otimização multiobjetivo. Existem na literatura da pesquisa operacional diversos algoritmos que visam lidar com problemas multiobjetivos. Nesta tese, foram aplicados dois desses algoritmos: Nondominated Sorting Genetic Algorithms-II (NSGA-II) e SPEA2: Strength Pareto Evolutionary Algorithm (SPEA2). Em primeira análise, se destacou uma das maiores dificuldade de lidar com o PERTEEG, a saber, o esforço computacional elevado. Por isso, vislumbrou-se que uma possível solução para contornar esta dificuldade esteja na computação paralela. Para se confirmar esta suspeita, nesta tese foram implementadas versões paralelas dos algoritmos sequenciais testados. A qualidade das soluções encontradas pelos algoritmos foram bastante superiores às soluções encontradas pelos algoritmos sequenciais. Neste trabalho também será mostrado que as soluções ótimas clássicas considerando somente o objetivo de m´mínimo custo são incapazes de atender às novas necessidades dos sistemas elétricos de potência. Testes computacionais foram realizados e analisados neste trabalho. Considerando as metodologias conhecidas na literatura para medição da qualidade das soluções encontradas por algoritmos multiobjetivo, se pode afirmar de que a proposta de abordagem do problema de PERTEEG pode ser viável tanto do ponto de vista de engenharia como do ponto de vista da computação matemática. / The main objective of this study is to propose a new methodology to deal with the long-term transmission system expansion planning with multiple generation dispatch scenarios problem (TEP-MDG). With the methodology proposed in this thesis we aim to build expansion plans with minimum investment cost and also capable of meeting the new demands of modern electrical systems, such as uncertainty about the future generation scenarios and congestion in the transmission systems. By modeling the TEP-MDG aiming to build transmission networks that circumvent the uncertainties regarding the future generation scenarios and simultaneously minimize the cost of investment for transmission networks expansion, the planner faces a multiobjective optimization problem. One can find various algorithms that aim to deal with multiobjective problems in the literature of operations research. In this thesis, we apply two of these algorithms: Nondominated Sorting Genetic Algorithms-II (NSGA-II) and SPEA2: Strength Pareto Evolutionary Algorithm (SPEA2). In a first analysis, we have found that the most critical issue with the TEP-MOG is the high computational demand. Therefore, in order to circumvent this difficulty we have implemented parallel versions of the sequential algorithms tested. In performed tests, the parallel algorithms have found solutions of superior quality than the solutions found by the sequential algorithms. In this thesis we also show that optimal solutions considering only the classical least cost objective are unable to meet the electric power systems new demands. Tests have been performed and analyzed in this work. By considering the methods known in the literature convinced to measure the quality of solutions found by multiobjective algorithms, we concluded that the proposed approach to TEP-MDG may be feasible from the point of view of both engineering and computational mathematics.

O principal objetivo deste estudo é propor uma nova metodologia para lidar com o problema de Planejamento da Expansão de Redes de Transmissão de Energia Elétrica com Múltiplos Cenários de Geração (PERTEEG). Com a metodologia proposta neste trabalho almeja-se construir planos de expansão de redes de transmissão de energia elétrica que sejam capazes de, no menor custo de investimento possível, satisfazer às novas exigências dos sistemas elétricos modernos, tais como construção de redes de transmissão livres de congestionamento e robustas à incerteza em relação aos cenários de geração futuros. Através de estudos realizados na literatura do problema, verificou-se que novos modelos e metodologias de abordagem do PERTEEG se fazem necessários. Ao se modelar o PERTEEG visando construir redes de transmissão que contornem as incertezas em relação aos cenários de geração futuros e concomitantemente minimizar o custo de investimento para a expansão do sistema, o planejador se depara com um problema de otimização multiobjetivo. Existem na literatura da pesquisa operacional diversos algoritmos que visam lidar com problemas multiobjetivos. Nesta tese, foram aplicados dois desses algoritmos: Nondominated Sorting Genetic Algorithms-II (NSGA-II) e SPEA2: Strength Pareto Evolutionary Algorithm (SPEA2). Em primeira análise, se destacou uma das maiores dificuldade de lidar com o PERTEEG, a saber, o esforço computacional elevado. Por isso, vislumbrou-se que uma possível solução para contornar esta dificuldade esteja na computação paralela. Para se confirmar esta suspeita, nesta tese foram implementadas versões paralelas dos algoritmos sequenciais testados. A qualidade das soluções encontradas pelos algoritmos foram bastante superiores às soluções encontradas pelos algoritmos sequenciais. Neste trabalho também será mostrado que as soluções ótimas clássicas considerando somente o objetivo de m´mínimo custo são incapazes de atender às novas necessidades dos sistemas elétricos de potência. Testes computacionais foram realizados e analisados neste trabalho. Considerando as metodologias conhecidas na literatura para medição da qualidade das soluções encontradas por algoritmos multiobjetivo, se pode afirmar de que a proposta de abordagem do problema de PERTEEG pode ser viável tanto do ponto de vista de engenharia como do ponto de vista da computação matemática. / The main objective of this study is to propose a new methodology to deal with the long-term transmission system expansion planning with multiple generation dispatch scenarios problem (TEP-MDG). With the methodology proposed in this thesis we aim to build expansion plans with minimum investment cost and also capable of meeting the new demands of modern electrical systems, such as uncertainty about the future generation scenarios and congestion in the transmission systems. By modeling the TEP-MDG aiming to build transmission networks that circumvent the uncertainties regarding the future generation scenarios and simultaneously minimize the cost of investment for transmission networks expansion, the planner faces a multiobjective optimization problem. One can find various algorithms that aim to deal with multiobjective problems in the literature of operations research. In this thesis, we apply two of these algorithms: Nondominated Sorting Genetic Algorithms-II (NSGA-II) and SPEA2: Strength Pareto Evolutionary Algorithm (SPEA2). In a first analysis, we have found that the most critical issue with the TEP-MOG is the high computational demand. Therefore, in order to circumvent this difficulty we have implemented parallel versions of the sequential algorithms tested. In performed tests, the parallel algorithms have found solutions of superior quality than the solutions found by the sequential algorithms. In this thesis we also show that optimal solutions considering only the classical least cost objective are unable to meet the electric power systems new demands. Tests have been performed and analyzed in this work. By considering the methods known in the literature convinced to measure the quality of solutions found by multiobjective algorithms, we concluded that the proposed approach to TEP-MDG may be feasible from the point of view of both engineering and computational mathematics.