PROGRAMA DE PÓS-GRADUAÇÃO EM ENGENHARIA ELÉTRICA “Busca em Vizinhança Variável Aplicado na Solução do Problema de Planejamento da Expansão do Sistema de Transmissão de Energia Elétrica” WALNEY ANDRADE MARTINS Orientador: Prof. Dr. Rubén Augusto Romero Lázaro Dissertação apresentada à Faculdade de Engenharia - UNESP – Campus de Ilha Solteira, para obtenção do titulo de Mestre em Engenharia Elétrica. Área de Conhecimento: Automação. Ilha Solteira – SP Novembro/2009 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. Palavras-chave: Metaheurísticas. VNS. Planejamento de Sistemas de Transmissão 5 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. KeyWords: Metaheuristics. VNS. Planning of Transmission Systems. 6 Dedicatória Dedico esta dissertação a toda a minha família, em especial à minha mãe, que sempre nos momentos mais difíceis esteve ao meu lado. 7 AGRADECIMENTOS A Deus por guiar meus caminhos; Ao Professor Doutor Rubén Augusto Romero Lázaro, pela competência, atenção, apoio, dedicação e em especial ao auxílio e paciência dedicados até a conclusão deste trabalho; A minha esposa Lidiane, que me apoiou, incentivou e não mediu esforços para a realização deste trabalho; Aos meus familiares, em especial a minha irmã Waléria que foi a minha inspiração para escolher este caminho; Aos professores do DEE, que de forma direta e indireta fizeram parte deste trabalho; A todos os amigos e colegas de departamento pela amizade construída ao longo deste trabalho. 8 LISTA DE FIGURAS Pseudo Código 1 Algoritmo VND 44 Pseudo Código 2 VNS reduzida – RVNS 47 Pseudo Código 3 Algoritmo BVNS 49 Pseudo Código 4 Algoritmo GVNS 50 Figura 4.1 Algoritmo VND para o PPEST 53 Figura 4.2 Sistema de 6 barras com seis circuitos na configuração base e seis circuitos adicionados 54 Figura 4.3 Codificação de uma proposta de solução para o PPEST 54 Figura 4.4 Vizinhos em )(1 xN 58 Figura 4.5 Vizinhos em )(2 xN 58 Figura 4.6 Vizinhos em )(3 xN 59 Figura 5.1 Solução VGS para o sistema de 6 barras de Garver 63 Figura 5.2 Codificação da solução inicial do sistema de 6 barras de Garver 63 Figura 5.3 Vizinhos candidatos em )(2 nN 64 Figura 5.4 Solução ótima (VND/DC) do sistema de 6 barras de Garver 65 Figura 5.5 Solução inicial utilizando AHC – VGS 66 Figura 5.6 Solução sistema IEEE 24 barras utilizando VND 66 Figura 5.7 Sistema IEEE 24 barras 67 9 LISTA DE TABELAS Tabela 1.1 Dados de linhas do sistema de Garver de 6 barras 79 Tabela 1.2 Dados de Barras do sistema de Garver de 6 barras 79 Tabela 2.1 Sistema IEEE 24 barras: Dados das Linhas 80 Tabela 2.2 Sistema IEEE 24 barras – Geração e Demanda 81 Tabela 3.1 Sistema Sul Brasileiro: Dados de Linhas 82 Tabela 3.2 Sistema Sul Brasileiro: Dados de Barras 85 10 SUMÁRIO 1 INTRODUÇÃO 12 2 O PROBLEMA DE PLANEJAMENTO DA EXPANSÃO DE SISTEMAS DE TRANSMISSÃO 15 2.1 MODELAGEM MATEMÁTICA 17 2.1.1 Modelo DC 18 2.1.2 Modelo de Transportes 20 2.1.3 Modelo Híbrido 22 2.2 UMA REVISÃO SOBRE PLANEJAMENTO DA EXPANSÃO DE SISTEMAS DE TRANSMISSÃO 25 3 TÉCNICAS DE SOLUÇÃO 33 3.1 MÉTODOS EXATOS 33 3.1.1 Decomposição de Benders 33 3.2 ALGORITMOS APROXIMADOS 34 3.2.1 Algoritmo Heurístico Construtivo de Garver 35 3.2.2 AHC de Villasana-Garver-Salon 37 3.2.3 Algoritmos Metaheurísticos 40 4 METAHEURISTICA DE BUSCA EM VIZINHANÇA VARIÁVEL 41 4.1 ESQUEMAS FUNDAMENTAIS DA BUSCA EM VIZINHANÇA VARIÁVEL 41 4.1.1 VNS de Descida: Algoritmo VND 43 11 4.1.2 VNS Reduzida: Algoritmo RVNS 46 4.1.3 VNS Básica: Algoritmo BVNS 48 4.1.4 VNS Geral: Algoritmo GVNS 50 4.1.5 Extensões da VNS 52 4.2 ALGORITMO VNS APLICADO AO PROBLEMA DE PLANEJAMENTO DE SISTEMAS DE TRANSMISSÃO 53 4.2.1 Passo 1: Codificação do PPEST 53 4.2.2 Passo 2: Solução Inicial 55 4.2.2.1 Solução Inicial com o Modelo DC 55 4.2.3 Passo 3: Definição das estruturas de vizinhanças 57 4.2.4 Passo 4: Busca Local 59 4.2.4.1 Modelo DC 60 4.2.5 Critério de Parada 61 5 TESTES E RESULTADOS 62 5.1 SISTEMAS CONSIDERADOS PARA TESTE 62 5.2 VND COM MODELO DC NO SISTEMA DE 6 BARRAS DE GARVER 62 5.3 SISTEMA IEEE 24 BARRAS 65 5.4 SISTEMA SUL BRASILEIRO DE 46 BARRAS 69 6 CONCLUSÕES 70 REFERÊNCIAS 72 APÊNDICE 79 12 1 INTRODUÇÃO O mercado de energia elétrica cada vez mais vem se tornando competitivo e exigente sob os aspectos técnico-econômicos, obrigando que as empresas concessionárias de energia elétrica desenvolvam esforços no sentido de atender a demanda a consumidores cada vez mais exigentes. Nesse sentido o problema de planejamento de sistemas de transmissão torna-se uma ferramenta de grande importância para o setor, que busca conciliar interesses econômicos com um bom atendimento aos seus consumidores. O problema de planejamento de sistemas de transmissão considerado neste trabalho é o problema de longo prazo, cuja modelagem matemática corresponde a um problema de programação não-linear inteira mista. Um dos problemas encontrados em sua resolução está relacionado com a natureza combinatória do processo de planejamento, que na maioria das vezes leva a um número explosivo de candidatos. Outro problema está relacionado com a sua estrutura multimodal que apresenta um número muito elevado de ótimos locais, o que leva a maioria dos métodos aproximados a parar numa solução ótima local, muitas vezes de qualidade inferior. No problema estático de planejamento da expansão dos sistemas de transmissão de energia elétrica, procura-se determinar o plano de expansão com um custo mínimo, ou seja, deve- se determinar onde e que tipos de equipamentos devem ser instalados para que o sistema opere adequadamente, atendendo às necessidades do mercado de energia elétrica. Por ser um problema de otimização matemática deve se especificar claramente dois aspectos importantes: a modelagem matemática e a técnica de solução escolhida para resolver o modelo matemático. Pode-se considerar pelo menos três modelos matemáticos para representar o problema de planejamento de sistemas de transmissão: modelo DC, modelo de transportes e modelo híbrido. O modelo DC é considerado como sendo o modelo mais indicado para representar o problema de planejamento, sendo os modelos de transporte e híbrido, versões relaxadas ou simplificadas do modelo DC. Na solução destes modelos várias técnicas de otimização são encontradas na literatura especializada. Essas técnicas podem ser divididas em duas categorias: métodos exatos (analíticos ou de otimização clássica) e os métodos aproximados (heurísticas e metaheurísticas). 13 Na formulação destes modelos, o problema de Planejamento da Expansão de Sistemas de Transmissão (PPEST) é descrito como um problema de otimização com uma função objetivo, sujeita a um conjunto de restrições. Estas restrições procuram modelar grande parte dos critérios técnicos, econômicos, e de confiabilidade necessários para a expansão do sistema. Os métodos analíticos apresentam a característica de determinarem a solução do problema de planejamento. São muito eficientes em sistemas de pequeno e médio porte, mas para sistemas de grande porte ainda apresentam problemas de convergência e de elevado esforço computacional. As técnicas heurísticas são as alternativas atuais para os modelos de otimização matemática. O termo heurística (um método de resolver problemas através de técnicas práticas aprendidas com a experiência) é utilizado para descrever todas essas técnicas que é um método que gera, passo a passo, uma solução avaliando e selecionando opções de expansão. Para isto, nos modelos heurísticos realizam-se buscas locais com a orientação lógica ou empírica de índices de sensibilidade (regras heurísticas). Em geral, estes métodos apresentam a vantagem de fornecerem soluções de boa qualidade com esforços computacionais pequenos, mas não garantem que se encontre a solução ótima de sistemas reais e não fornecem informações sobre a qualidade da solução obtida. Surgiram também os algoritmos metaheurísticos, que descrevem como se explorar o espaço de busca sem se prender a um problema específico. Estes algoritmos coordenam heurísticas mais simples com uma busca local, com o propósito de encontrar soluções de melhor qualidade do que as obtidas utilizando as heurísticas isoladamente. O propósito deste trabalho é apresentar a metaheurística Busca em Vizinhança Variável (Variable Neighborhood Search) aplicada ao PPEST. A metaheurística VNS é baseada num principio simples: explorar o espaço de soluções através de trocas sistemáticas de estruturas de vizinhança durante o processo de busca. O trabalho está organizado da seguinte forma: No Capítulo 2 apresenta-se o problema de planejamento da expansão do sistema de transmissão e descrevem-se os modelos matemáticos e o estado da arte do PPEST. No Capítulo 3 são apresentadas as principais técnicas de solução já aplicadas no PPEST. Nessa abordagem é dada especial prioridade para os tópicos relacionados com a dissertação. No capítulo 4 são apresentados os fundamentos da metaheurística Busca em Vizinhança Variável, também são apresentadas as principais formas ou estratégias para implementar o algoritmo VNS. Também é realizada uma breve discussão sobre algumas aplicações e as 14 possibilidades de extensão do algoritmo VNS. Finalmente é apresentado o algoritmo VNS juntamente com um exemplo ilustrativo. No Capítulo 5 são apresentados os testes e resultados. Neste caso usamos 3 sistemas muito conhecidos na literatura especializada, isto é, o sistema de Garver de 6 barras, o sistema IEEE de 24 barras e o sistema sul brasileiro de 46 barras. No Capítulo 6 são apresentadas as conclusões sobre o trabalho e ainda algumas considerações finais. 15 2 O PROBLEMA DE PLANEJAMENTO DA EXPANSÃO DE SISTEMAS DE TRANSMISSÃO Com o passar dos anos, o aumento da demanda de energia elétrica se torna cada vez maior e com consumidores cada vez mais exigentes. Nesse sentido, o Problema de Planejamento da Expansão de Sistemas de Transmissão é um problema de grande importância para o setor elétrico, que através de sua solução busca-se garantir o atendimento aos consumidores de forma confiável e econômica. Nos últimos anos o sistema elétrico está passando por um processo de desregulamentação, mudando de uma estrutura centralizada para uma descentralizada, que tem como objetivo obter uma maior eficiência dos agentes participantes do setor, (geração, transmissão, distribuição, entre outros) que decidirão onde e quando investir seus recursos para expandir o sistema, este processo deverá sofrer a intermediação de um agente central que deve funcionar como um plano de referência de forma a garantir uma expansão ótima global do sistema, otimizando a utilização dos recursos disponíveis e os custos para os consumidores. Novos parques geradores e novas rotas de transmissão devem ser construídos para atender esta nova carga do sistema. No Brasil a maior parte da energia elétrica produzida no país é de origem hidrelétrica, e como os centros geradores estão distantes dos grandes centros consumidores, torna-se necessária a construção de novos circuitos de transmissão com a finalidade de transmitir a potência elétrica produzida nestas usinas, para aumentar a confiabilidade do sistema, otimizar recursos hídricos, etc. As decisões do processo de planejamento estão relacionadas à seleção das melhores unidades geradoras, das melhores rotas de transmissão e das melhores malhas para garantir um suprimento de energia de forma econômica e confiável. No processo de planejamento a tomada de decisões dá origem a um problema de otimização complexo. É necessário o desenvolvimento de estratégias e técnicas de solução que assegurem que as decisões tomadas durante o processo de planejamento sejam as melhores decisões possíveis. Este problema não pode ser resolvido sem que sejam feitas simplificações. Normalmente, o problema de planejamento é separado com 16 relação aos seus principais agentes. O problema de planejamento da geração, que não leva em conta os custos da expansão da transmissão, o problema de planejamento da transmissão, que supõe conhecidas as estimativas de crescimento da demanda e programas alternativos de expansão da geração, até o ano horizonte de planejamento e o planejamento da distribuição. No planejamento de sistemas de transmissão ainda é possível separar o problema em dois tipos: (1) planejamento estático; (2) planejamento multiestágio. No planejamento estático existe apenas um estágio de planejamento, onde o planejador procura conhecer o circuito ótimo para ser adicionado em um único ano no horizonte de planejamento, ou seja, o planejador não está interessado em saber quando o circuito deverá ser construído, mas encontrar a topologia final ótima para uma futura situação definida. Por outro lado, se múltiplos anos são considerados e a estratégia de expansão ótima abrange todo o horizonte, o planejamento é classificado como multiestágio. Neste caso, o modelo matemático deve conter restrições de tempo para considerar a expansão ao longo dos anos de tal forma que o valor presente dos custos ao longo do planejamento seja minimizado enquanto que as restrições impostas sejam atendidas. O planejamento multiestágio é muito complexo, pois deve levar em consideração não só as especificações técnicas e a alocação dos circuitos planejados, mas também considerações sobre o tempo. Poucos trabalhos sobre planejamento dinâmico para problemas reais de planejamento podem ser encontrados na literatura. Em Latorre et al. (2003) são apontados alguns destes trabalhos. Neste trabalho, interessa-se pelo planejamento da expansão de sistemas de transmissão nos horizontes de médio e longo prazo (10 anos ou mais) que consiste em determinar onde novos equipamentos de transmissão (linhas de transmissão, transformadores, etc.) devem ser instalados de forma a atender a demanda de forma econômica e confiável. Devido tanto às incertezas como também às dimensões inerentes a este tipo de problema, métodos rápidos e aproximados de análise são requeridos. 17 2.1 MODELAGEM MATEMÁTICA O problema de planejamento da expansão de sistemas de transmissão de energia elétrica consiste em se escolher, entre um conjunto pré-definido de circuitos candidatos, aqueles que devem ser incorporados ao sistema de forma a minimizar os custos de investimento e operação e atender a demanda de energia futura ao longo de um horizonte de planejamento com confiabilidade, assumindo como conhecido o plano de geração. Esse problema tem uma natureza dinâmica, isto é, requer a consideração de múltiplos períodos de tempo, determinando-se uma sequência (estágios) de planos de expansão do sistema. Quando o horizonte de planejamento reduz-se a apenas um estágio, o problema multiestágio se transforma em um problema estático, em que o objetivo é determinar onde e que tipo de novos equipamentos de transmissão devem ser instalados de forma a minimizar os custos de investimento sujeito a uma conjunto de restrições técnicas e operativas. Os dados para este problema são a previsão de carga futura, bem como o despacho dos geradores para atender ao mercado. Além disso, são necessários dados para a rede existente, também chamada de rede básica, e dados para os novos circuitos que podem ser adicionados à rede básica. Note que a rede básica não tem capacidade suficiente para o atendimento da demanda no mercado futuro. O modelo matemático mais indicado para representar a operação adequada do sistema seria a representação do problema por meio de relações matemáticas de fluxo de carga AC (Alternating Current), tipicamente usada na análise da operação do sistema elétrico. Entretanto o uso desta modelagem é muito recente e, portanto, sua aplicação ainda se encontra restrita e em fase de desenvolvimento. Para alguns detalhes sobre a aplicação do modelo AC no planejamento da expansão de sistemas de transmissão ver Rider, Garcia e Romero (2007). Assim, considera-se que a modelagem matemática mais indicada em trabalhos de planejamento de sistemas de transmissão a longo prazo, é o chamado modelo DC (Direct Current) que leva em conta as duas leis de Kirchhoff apenas para o balanço e o fluxo de potência ativa. Nesse caso, o problema resultante é do tipo de programação não-linear inteiro misto de elevada complexidade para sistemas de grande porte. 18 2.1.1 Modelo DC Como foi mencionado anteriormente, o modelo DC é atualmente considerado o modelo matemático mais indicado para representar o problema de planejamento da expansão de sistemas de transmissão ao longo prazo. Os principais motivos para essa opção são os seguintes: (1) É a modelagem mais aceita por pesquisadores e especialistas em planejamento das empresas de energia elétrica; (2) Existem várias técnicas de solução (algoritmos) que resolvem de maneira adequada os problemas de planejamento que usam o modelo DC; (3) Neste modelo, o tempo de processamento não é elevado. Neste modelo, o sistema completo deve satisfazer as duas leis de Kirchhoff, ou seja, todas as barras do sistema devem satisfazer a primeira lei de Kirchhoff (a primeira lei de Kirchhoff simplesmente especifica que o somatório dos fluxos de potência que entram numa barra do sistema deve ser igual ao somatório do fluxo de potência que saem dessa barra do sistema), e todos os laços existentes devem satisfazer à segunda lei de Kirchhoff (a segunda lei de Kirchhoff especifica que a queda de tensão em cada laço deve ser igual à zero). 19 O modelo DC assume a forma apresentada em (2.1)-(2.8), sendo: v : Investimento devido as adições de circuitos. ij c : Custo de um circuito que pode ser adicionado no caminho ij. ijn : Número de circuitos adicionados no processo de otimização. 0 ijn : Número de circuitos existentes na topologia base. ijn : Número máximo de circuitos que podem ser adicionados no caminho ij. ijγ : Suceptância de um circuito no caminho ij. f : Vetor de fluxos com elementos ijf (o fluxo de potência total através dos circuitos no caminho ij). ijf : Capacidade de transmissão de um circuito no caminho ij. g : Vetor geração com elementos kg (geração na barra k). g : Vetor de geração máxima. S: Matriz de incidência nó-ramo transposta do sistema elétrico. iθ : Ângulo de tensão na barra i. Ω : Representa o conjunto de caminhos em que é possível adicionar circuitos. 20 O conjunto de restrições (2.2) representa as equações correspondentes à primeira lei de Kirchhoff, uma equação para cada barra do sistema, e as restrições (2.3) representa às equações correspondentes à segunda lei de Kirchhoff. As restrições (2.4) representam as restrições de capacidade de transmissão dos circuitos (linhas e/ou transformadores) e o valor absoluto é necessário, pois os fluxos de potência podem fluir nos dois sentidos. As restrições (2.5) e (2.6) são triviais e representam apenas restrições de limite de geração e de circuitos adicionados em cada caminho candidato ij. Finalmente, as variáveis ijf e iθ são irrestritas em valor e as variáveis ijn devem ser inteiras, representando a maior fonte de complexidade no problema. A presença de todas as equações correspondentes à segunda lei de Kirchhoff no modelo DC transforma este modelo num problema não linear inteiro misto e produzem um alto nível de complexidade no processo de solução. 2.1.2 Modelo de Transportes O modelo de transportes é uma modelagem mais simplificada, que considera apenas a primeira lei de Kirchhoff. Nesse caso, o problema resultante é do tipo linear inteiro misto. Mesmo sendo linear, ainda não é possível encontrar a solução ótima para o modelo de transportes para sistemas de grande porte. O modelo de transportes foi a primeira proposta sistemática de modelagem matemática usado com muito sucesso no problema de planejamento de sistemas de transmissão. O modelo foi proposto em Garver (1970) e representou o início de uma sistemática de pesquisa nos problemas de planejamento de sistemas de transmissão, sugerindo o uso de modelos diferentes para os problemas de operação e de planejamento. Garver sugere que, devido aos grandes problemas de usar o modelo de fluxo de carga AC utilizado para operação, deve-se usar modelos mais relaxados que permitam encontrar topologias ou configurações atrativas do crescimento do sistema elétrico mesmo que estas propostas sejam aproximadas. Assim, sugere a utilização de um modelo matemático que deve satisfazer somente a primeira lei de Kirchhoff (LKC), isto é, a modelagem matemática proposta não leva em conta a segunda lei de Kirchhoff (LKT). Este modelo matemático é conhecido como modelo de 21 transportes. Obviamente, esta modelagem matemática é uma representação menos adequada do problema real que, por exemplo, o modelo DC e, portanto, a solução encontrada pelo modelo de transportes pode ser menos adequada para o problema real. No modelo de transportes se deseja encontrar uma configuração que produza o menor investimento no plano de expansão do sistema elétrico e condições adequadas de operação desse sistema elétrico. Condições adequadas de operação significam que o sistema deve satisfazer a primeira lei de Kirchhoff e que os circuitos e as usinas de geração operem dentro de seus limites especificados. Levando em conta as observações anteriores, o modelo de transportes para o problema de planejamento de sistemas de transmissão pode ser formulado por (2.10)-(2.17): em que os parâmetros e as incógnitas são os mesmos do modelo DC. Na verdade, o modelo de transportes pode ser obtido a partir do modelo DC após relaxar (eliminar) as restrições da segunda lei de Kirchhoff (2.3). Do ponto de vista de pesquisa operacional o problema (2.10)-(2.17) é um problema de programação linear inteiro misto (PLIM). Encontrar a solução ótima desse problema não é simples, especialmente para sistemas elétricos de grande porte. Entretanto, se fossem permitidas adições fracionárias de circuitos (linhas de transmissão e/ou transformadores), isto é, se fossem permitido que os ijn assumissem valores contínuos, então o sistema (2.10)-(2.17) se transformaria 22 num simples problema de programação linear (PL), fácil de resolver mesmo para o caso de sistemas de grande porte. É evidente que a restrição ijn inteiro produz a maior complexidade no problema (2.10)- (2.17). Estas características são aproveitadas para desenvolver vários tipos de algoritmos para resolver o problema de planejamento de sistemas de transmissão quando é usado o modelo de transportes. A grande vantagem do modelo de transportes é que praticamente não existe diferença entre resolver problemas de sistemas conexos e altamente ilhados e a característica linear facilita o processo de resolução. A desvantagem principal é que a solução apresentada pelo modelo de transportes pode estar distante da solução correspondente ao modelo DC, considerado como modelo mais indicado. 2.1.3 Modelo Híbrido Outro modelo considerado no PPEST é o modelo híbrido, que combina características do modelo DC e do modelo de transportes. Esta modelagem, numa formulação mais simples preserva as propriedades lineares do modelo de transportes, considerando a primeira lei de Kirchhoff em todos os nós da rede, e a segunda lei de Kirchhoff somente nos circuitos existentes na rede base (e não necessariamente nos circuitos que serão adicionados). O modelo híbrido foi proposto originalmente em Villasana, Garver e Salon (1985), sendo que essa modelagem matemática especifica o seguinte: a parcela do sistema elétrico correspondente aos circuitos existentes na configuração base devem satisfazer as duas leis de Kirchhoff e a outra parcela correspondente aos circuitos novos devem satisfazer unicamente a primeira lei de Kirchhoff. Portanto, o modelo híbrido é uma mistura entre o modelo de transportes e o modelo DC. É claro que uma vez definida a modelagem matemática desta maneira, a solução ótima encontrada também deve satisfazer as duas leis de Kirchhoff na parte do sistema correspondente aos circuitos da configuração base e somente a primeira lei de Kirchhoff para os novos circuitos 23 adicionados. Em outras palavras, no modelo híbrido linear, deve-se satisfazer a primeira lei de Kirchhoff em todas as barras do sistema e a segunda lei de Kirchhoff somente naqueles laços formados por circuitos existentes na configuração base. Assim, por exemplo, se no processo de planejamento for adicionado um circuito, então os laços que eventualmente podem aparecer como conseqüência da adição deste circuito não estão obrigados a satisfazer a segunda lei de Kirchhoff. Esta modelagem, chamada de modelo híbrido linear, pode ser usada como estratégia de otimização para encontrar soluções factíveis para o modelo DC. Esta proposta foi apresentada por Villasana, Garver e Salon (1985), onde a modelagem é apenas utilizada como uma forma de auxílio para o indicador de sensibilidade do algoritmo heurístico proposto. Existe ainda um modelo híbrido não-linear, o qual não será considerado neste trabalho. A ideia de utilizar o modelo híbrido no problema de planejamento de sistemas de transmissão é para contornar alguns problemas que apresentavam os modelos de transportes e DC. O modelo de transportes é preferido por sua natureza linear, pois para esse tipo de problema existem algoritmos relativamente eficientes, inclusive com provas de otimalidade. Mas, em contrapartida, as soluções encontradas podem ficar muito afastadas da solução ótima do modelo DC. Por outro lado, o modelo DC pode apresentar sérios problemas devido sua natureza não- linear. Assim, o modelo híbrido permite encontrar soluções mais próximas da solução ótima do modelo DC e com a vantagem de trabalhar com técnicas de otimização para problemas lineares. A versão do modelo híbrido linear, que está sendo apresentada e as diferentes variantes que aparecem na literatura especializada, são utilizadas apenas para auxiliar no processo de resolução do modelo DC em algoritmos de planejamento de sistemas de transmissão (ROMERO; MONTICELLI, 1994a; VILLASANA; GARVER; SALON, 1985). Levando em conta estas observações o modelo híbrido linear pode ser formulado por (2.19)-(2.27): 24 Pode-se verificar que o modelo aqui apresentado é um problema de programação linear inteiro misto. Deve-se observar também, que no modelo mostrado em (2.19)-(2.27) os fluxos nos circuitos estão separados em dois grupos (fluxos em circuitos existentes na topologia base, 0 ijf e os fluxos nos circuitos que não estão presentes na topologia base, ijf ). O mesmo acontece com os circuitos adicionados: 0 ijn , ijn que representam, respectivamente, o número de circuitos presentes no caminho ij na configuração base e os circuitos que podem ser adicionados no processo de otimização. Também, 0Ω representa o conjunto dos circuitos presentes na configuração base e Ω representa o conjunto dos circuitos que podem ser adicionados. 0 S é a matriz de incidência nó- ramo dos circuitos existentes na topologia base. As demais variáveis são como em (2.1)-(2.8). As restrições (2.20) representam a primeira lei de Kirchhoff e o conjunto de restrições (2.21) representam as equações correspondentes a segunda lei de Kirchhoff, com uma equação para cada caminho que apresenta pelo menos um circuito na configuração base. Este último conjunto de equações representa a diferença entre os três modelos matemáticos que estão sendo apresentados. No modelo de transportes, o conjunto de equações ( )( ) 000 =−+− jiijijijij nnf θθγ , simplesmente não aparece, já no modelo híbrido aparece somente uma parcela dessas equações 25 constituídas pelos circuitos existentes na configuração base e, finalmente, no modelo DC aparecem todas as equações desse tipo, uma para cada caminho existente e/ou novos caminhos candidatos à adição de circuitos. 2.2 UMA REVISÃO SOBRE O PLANEJAMENTO DA EXPANSÃO DE SISTEMAS DE TRANSMISSÃO Nesta seção considerou-se como base para realizar a revisão os trabalhos de Latorre et al. (2003), Faria (2005), Taglialenha (2008) e alguns trabalhos recentes. Nas fases iniciais dos trabalhos em planejamento da expansão, as únicas ferramentas disponíveis para a síntese de redes de transmissão eram os softwares de análise como os utilizados no cálculo de fluxo de carga, estudos de estabilidade, curto-circuito, etc. O planejador do sistema de energia elétrica era o responsável por determinar onde instalar novos equipamentos para suprir as novas cargas do sistema, resultando em uma configuração que deveria ser analisada através dos métodos mencionados anteriormente. Com o crescimento das dimensões das redes de transmissão, este procedimento se torna inviável. Mas as pesquisas na área de planejamento de sistemas de transmissão experimentaram uma expansão e novos desenvolvimentos de modelos e técnicas de solução. Muitos artigos e relatos sobre novos modelos foram publicados na literatura especializada devido principalmente à melhoria das ferramentas tecnológicas disponíveis, novos algoritmos de otimização, e o maior nível de incerteza introduzida pela desverticalização do setor de energia. O trabalho pioneiro de Knight (1960) teve o mérito de propor a distinção entre os métodos de análise e métodos matemáticos de projeto (síntese) de sistemas de transmissão de energia elétrica. Um dos primeiros trabalhos propostos para a solução deste problema é Garver (1970). O autor formulou o problema considerando apenas a Primeira Lei de Kirchhoff e resolveu este modelo matemático usando um Algoritmo Heurístico Construtivo (AHC) que em cada passo era escolhido o circuito mais interessante para ser incorporado ao sistema identificado após resolver um problema de programação linear. Na seção 3.2.1 este método será detalhado. 26 Em Kaltenbatch, Peschon e Gehrig (1970), também no ano de 1970, foi proposto combinar programação linear com programação dinâmica. Programação linear era usada para encontrar o mínimo incremento da capacidade da rede para atender às variações de demanda e geração nas barras do sistema. Após essa etapa, era utilizada programação dinâmica para achar a melhor sequência de investimentos (contínuos) para o horizonte de planejamento. Este trabalho é pioneiro para problemas de planejamento de expansão de redes de transmissão considerando múltiplos estágios. Um algoritmo ‘puro’ de programação dinâmica foi proposto em Dusonchet e El-Abiad (1973). Esta proposta parecia contornar as dificuldades em obter a solução ótima encontrada por trabalhos anteriores. Contudo, devido aos altos recursos computacionais requeridos, resultado do formalismo da programação dinâmica, simplificações ou relaxações de importantes restrições eram necessárias em aplicações práticas. Tendo em vista as desvantagens da programação dinâmica, foi proposto, por Gonzaga (1973), um algoritmo de busca em grafos. Este algoritmo, uma versão de algoritmo dual, procura encontrar um caminho de custo mínimo em grafos de expansão utilizando heurísticas para reduzir o número de alternativas a serem analisadas. Com base em tal algoritmo, foi implementado um programa computacional chamado Tania, que foi muito utilizado na solução de problemas de planejamento da expansão de redes de sistemas Brasileiros. A primeira proposta de algoritmos do tipo Branch and Bound para este problema apareceu em Lee, Hocks e Hnylicza (1974). Contudo, assim como nos métodos de programação dinâmica, a utilização de algoritmos combinatórios tipo Branch and Bound fica restrita à aplicações em sistemas de pequeno porte face aos recursos computacionais exigidos. Em Monticelli et al. (1982) propuseram o uso de ferramentas interativas para o planejamento da transmissão. Para ordenar as possibilidades de adições era utilizado o índice de ’Mínimo Esforço’, que consiste de uma análise de sensibilidade em relação às susceptâncias dos circuitos em um problema de otimização correlato cujo resultado é idêntico ao modelo de fluxo de carga linearizado. A proposta era basicamente um algoritmo heurístico construtivo usando o modelo DC. O uso de análise de sensibilidade no problema de planejamento de sistemas de transmissão foi inicialmente proposto no trabalho de Champs, Vankelecom e Amoulle (1979). Eles utilizaram análise de sensibilidade em relação às susceptâncias a partir de um problema de 27 programação linear cujas restrições são as equações do modelo de fluxo de carga linearizado em conjunto com limites de transporte nos circuitos e de capacidade nos geradores. O objetivo do problema era obter o mínimo corte de carga necessário para eliminar todas as violações operacionais na rede elétrica. O uso de análise de sensibilidade também foi proposto em Pereira et al. (1987). Em Villasana (1984) e depois em Villasana, Garver e Salon (1985), são apresentadas duas diferentes metodologias para serem aplicadas ao planejamento da expansão de sistemas de transmissão. Estas propostas consistiam de um aperfeiçoamento do trabalho feito por Garver (1970), que propôs o modelo de transportes, representando uma técnica fundamental na pesquisa em planejamento da expansão de sistemas de transmissão, pois naquela época era a única forma disponível de otimizar este problema. Esse modelo relaxado, diferente dos usados em análise de operação, foi chamado de modelo de síntese de sistemas de transmissão. O modelo de transportes, assim como todo modelo de síntese, faz apenas o planejamento considerando o fluxo de potência ativa. Portanto, resolve apenas o problema de capacidade de transmissão. O problema de planejamento de reativos era resolvido na fase seguinte. Na tentativa de aperfeiçoar estas propostas e diminuir a complexidade do problema, Villasana determinou soluções viáveis para o modelo DC resolvendo modelos híbridos lineares, em que apenas os circuitos existentes na configuração base devem obrigatoriamente, satisfazer as duas leis de Kirchhoff. Em contraste, o modelo híbrido não-linear é um problema de programação¸ não-linear inteiro misto (PNLIM) de complexidade muito parecida como o modelo DC. Esse modelo foi pouco usado por pesquisadores em planejamento de sistemas de transmissão porque devem ser utilizadas as mesmas técnicas utilizadas para o modelo DC e, portanto, pode ser preferível trabalhar diretamente com o modelo DC, considerado ideal. Mesmo assim, o modelo híbrido não- linear deve ser mais fácil de resolver que o modelo DC. O uso de esquemas de decomposição para este problema teve início com o trabalho de Pereira (1985). Naquele trabalho, um esquema de decomposição de Benders foi aplicado para decompor o problema global de planejamento de redes em dois subproblemas: um de investimento, que tem por objetivo propor um plano de expansão; e outro de operação, que deve analisar o plano proposto e expressar as restrições operacionais em termos das variáveis de investimento através de restrições lineares chamadas de cortes de Benders. Esta nova restrição deve ser adicionada ao subproblema de investimento e novas iterações de Benders são repetidas 28 até a obtenção da convergência. O modelo adotado para formular o problema de planejamento da expansão de redes de transmissão é não-linear e não-convexo, o que pode trazer sérias dificuldades para métodos de cortes como o algoritmo de decomposição de Benders. Com o objetivo de contornar esta deficiência do método de decomposição de Benders, em relação ao modelo não-linear e não-convexo, foi proposto na tese de doutorado de Romero (1993), aparecendo também em Romero e Monticelli (1994a), uma metodologia de decomposição¸ hierárquica composta por três fases distintas. Na primeira fase o problema de planejamento deve ser resolvido por decomposição de Benders considerando somente o modelo de transporte para o subproblema de operação. Além disso, a integralidade das variáveis de investimento deveriam ser relaxadas. Na segunda fase o modelo do subproblema de operação deve ser trocado por um modelo Híbrido que consiste do modelo de fluxo de potência linearizado para os circuitos existentes e um modelo de transporte para computar o fluxo nos circuitos planejados. Finalmente, na terceira fase deste trabalho, o modelo de fluxo de carga linearizado era utilizado para o cálculo do fluxo de carga em todos os circuitos da rede de transmissão. O subproblema de investimento considera as variáveis de investimento discretas e utiliza um algoritmo especializado de enumeração implícita (ROMERO, 1993; ROMERO; MONTICELLI, 1994b). Pinto e Nunes (1990) usaram o esquema de decomposição de Benders combinado com um algoritmo de enumeração implícita. Com o objetivo de reduzir o esforço computacional, que pode ser muito grande, eles utilizaram duas técnicas para redução do espaço de busca do problema: redução por inviabilidade e por custo. Latorre-Bayona e Péres (1994) propuseram uma metodologia heurística que utiliza a vantagem da decomposição natural do problema em subproblemas de operação e investimento. O subproblema de investimento é resolvido utilizando-se um procedimento heurístico de busca em árvore iniciada a partir de uma solução viável obtida por outros modelos. As variáveis de investimento (ramos da árvore de busca) poderiam ser classificadas de três maneiras: as variáveis questionáveis (circuitos incluídos na solução viável inicial, mas que o usuário pensa não pertencer ao plano ótimo), as variáveis atrativas (circuitos que o usuário pensa pertencer ao planejamento ótimo) e as variáveis congeladas (circuitos que não serão testados no processo de busca). Esta classificação das variáveis já consiste de um critério de truncamento utilizado por este trabalho com o objetivo de redução do tempo computacional. Os outros critérios utilizados 29 eram limites na profundidade e na largura do processo de busca na árvore, limite no número de resoluções do subproblema de operação e limite no número de ’passos errados’ do processo de busca na árvore. Binato e Oliveira (1995) propuseram um método de busca, backward/forward para o problema de planejamento de expansão de redes de transmissão multiestágio. Neste método são definidos passos para uma análise de planejamento a dois estágios: o passo backward, que consiste de um planejamento retornando no tempo buscando antecipações de circuitos já definidos para os anos seguintes e o passo forward, que faz uma análise no sentido correto do tempo. Utilizando de uma maneira organizada estes dois passos, o método explora a região de viabilidade do problema em busca de economias de escala quando são considerados vários estágios durante o horizonte de planejamento. Também Oliveira, Costa e Binato (1995) utilizaram um esquema de decomposição hierárquica, mas composto por duas fases ao invés de três fases como no trabalho de Romero (1993). A primeira fase, da mesma forma que no trabalho de Romero, considera somente o modelo de transporte, porém não relaxa a integralidade das variáveis de investimento, enquanto que a segunda fase é igual à terceira do trabalho de Romero. A maior diferença entre estes dois trabalhos não vem da decomposição hierárquica utilizada e sim da maneira como o subproblema de investimento é resolvido. Enquanto que o trabalho anterior resolvia o subproblema de investimento até obter a solução ótima utilizando um algoritmo de enumeração implícita especializado, neste trabalho, utiliza-se um algoritmo de branch and bound com o objetivo de achar somente a primeira solução viável. Com isso, é possível obter considerável redução do esforço computacional. No trabalho de Binato (2001), foi proposta uma aplicação computacional utilizando decomposição de Benders que assegura que a solução ótima, obtida pelo método de decomposição, é o plano ótimo de expansão da rede de transmissão. Isso está diretamente relacionado com a utilização do modelo linear (0-1) disjuntivo que pôde ser aplicado a problemas testes com sistemas reais devido à obtenção de valores mínimos para a constante disjuntiva. Uma nova heurística para determinar a convergência do problema mestre da decomposição de Benders resultou também em grandes economias em termos de tempo computacional gasto. Entretanto, muitas vezes, o número elevado de candidatos de um caso de planejamento da expansão impede a 30 aplicação com sucesso de técnicas de decomposição. Portanto, é necessário o desenvolvimento de técnicas heurísticas que sejam capazes de fornecer ’boas’ soluções para o problema. Na década de 90 apareceram novos algoritmos heurísticos e metaheurísticos, diferentes dos algoritmos tradicionais, geralmente mais eficientes e com uma grande variedade de tempo de processamento que pode ser calibrado para cada tipo de aplicação. Pertence a esse tipo de algoritmos técnicas de otimização como algoritmos genéticos e evolutivos em geral, tabu search, GRASP, particle swarm, ant colony, etc. As metaheurísticas apresentam a grande vantagem de que a forma de resolver um problema varia muito pouco quando se muda a modelagem matemática do problema. Assim, por exemplo, em planejamento de sistemas de transmissão, a forma usada para resolver os modelos de transporte, híbridos e o modelo DC é praticamente a mesma. Em cada caso, deve-se resolver apenas um PL sob diferentes formas. Por esse motivo, todas as aplicações de metaheurísticas em planejamento de sistemas de transmissão foram aplicadas diretamente no modelo DC. As principais aplicações de metaheurísticas no problema de planejamento são apresentadas em Romero, Gallego e Monticelli (1996); Gallego et al. (1997); Gallego, Monticelli e Romero (1998a); Gallego, Monticelli e Romero (1998b), Gallego, Monticelli e Romero (2000), Silva, Gil e Areiza Ortiz (2000); e, Silva et al. (2001). Recozimento Simulado (Simulated Annealing) foi aplicado em Romero, Gallego e Monticelli (1996) e posteriormente foi paralelizado em Gallego et al. (1997). A qualidade dos resultados publicados nestes dois artigos mostraram que tais métodos têm um excelente potencial para a solução deste problema. As pesquisas apresentadas, utilizando metaheurísticas, indicam que, no momento, esses tipos de algoritmos são os mais competitivos para encontrar soluções de excelente qualidade de sistemas complexos. As metaheurísticas apresentam a vantagem de que são relativamente fáceis de implementar e, geralmente, apresentam excelente desempenho para todos os tipos de sistemas elétricos. Apresentam a grande desvantagem de que geralmente requerem tempos de processamento elevados para encontrar soluções de excelente qualidade. No entanto, deve-se observar que o tempo de processamento não é um problema crucial em planejamento de sistemas de transmissão. Nos próximos anos deve continuar muito ativa a pesquisa em metaheurísticas aplicadas ao problema de planejamento de sistemas de transmissão. 31 Praticamente todas as propostas de metaheurísticas apresentadas na literatura especializadas foram aplicadas ao planejamento estático. Em Escobar, Gallego e Romero (2004) foi apresentada a primeira metaheurística aplicada ao planejamento multiestágio de sistemas de transmissão. Mais tarde, outras metaheurísticas também foram propostas. GRASP (Greedy Randomized Adaptive Search Procedure) foi utilizado em Binato, Pereira e Granville (2001). As melhores soluções já conhecidas para dois sistemas testes brasileiros reais utilizados no estudo foram obtidas pela metaheurística, assim como melhoramentos na solução do caso do planejamento da expansão do sistema sudeste brasileiro, mostrando o potencial do método. Algoritmos de Busca Tabu (Tabu Search) foram utilizados nos trabalhos de Gallego, Monticelli e Romero (1998a) e, Areiza Ortiz (1997). Dois Algoritmos Genéticos foram propostos para resolver problemas de planejamento em (Extended Genetic Algorithms) Gallego, Monticelli e Romero, (1998b) e (Improved Genetic Algorithms) em Silva et al. (2000). Silva et al. (2001) utilizaram Busca Tabu para resolver o problema de planejamento estático de redes de transmissão. Foram utilizados vários conceitos da Busca Tabu como memória de curto-prazo, lista tabu e critério de aspiração. Uma fase de intensificação, que explora regiões do espaço de busca onde boas soluções devem existir, foi implementada juntamente com uma fase de diversificação, que direciona a busca para regiões não exploradas, utilizando conceitos de memória de médio e longo prazo. Uma metodologia híbrida combinando GRASP com Path Relinking foi desenvolvida em Faria et al. (2005). Path Relinking é um método que surgiu como uma estratégia de intensificação para melhorar a qualidade da solução de outras metaheurísticas. Nos poucos trabalhos em que foi utilizado, obteve grande sucesso. Neste estudo foi aprimorada a qualidade da busca por novas soluções, ajudando a obter a solução ótima dos problemas propostos com um número menor de iterações. Praticamente todas as pesquisas apresentadas em planejamento da expansão de sistemas de transmissão foram realizadas apenas utilizando o modelo de planejamento estático. Existe pouca bibliografia de modelagem e otimização de modelos matemáticos de planejamento multiestágio. Assim, por exemplo em Haffner (2000) é apresentada uma discussão interessante de modelagem deste problema e em Romero et al. (2003) é apresentado um algoritmo heurístico construtivo para o planejamento multiestágio utilizando o modelo de transportes. 32 Todos os algoritmos heurísticos encontram apenas soluções de boa qualidade para sistemas de médio e grande porte, e a qualidade dessas soluções pode ficar muito distante das soluções ótimas ou sub ótimas como acontece, por exemplo, com o sistema norte-nordeste brasileiro. A vantagem dos algoritmos heurísticos é que são simples de entender, robustos e muito rápidos. No momento, os algoritmos heurísticos ainda representam um campo de pesquisa muito interessante e as soluções encontradas por esses algoritmos podem ser utilizadas como base para encontrar soluções melhores utilizando algoritmos mais demorados como as metaheurísticas. Existe ainda uma extensa bibliografia tratando de outros aspectos do problema de planejamento da expansão de sistemas de transmissão tais como o planejamento da expansão considerando contingências, o planejamento da expansão considerando incertezas na demanda, o planejamento da expansão considerando um ambiente de mercado competitivo, entre outros. Para ver detalhes de trabalhos desse tipo ver as referências de Fang e Hill (2003); Garces et al (2009); e, Silva et al. (2005). 33 3 TÉCNICAS DE SOLUÇÃO O PPEST pode ser representado por, pelo menos, três modelos matemáticos como detalhado no capítulo anterior. Quando utiliza-se o modelo de transportes ou o modelo híbrido linear, obtém-se um problema de programação linear inteiro misto, e quando utiliza-se os modelos híbridos não-lineares ou DC, obtém-se um problema de programação não-linear inteiro misto, que já foi mencionado serem problemas de difícil solução, em especial quando se trata de sistemas de grande porte. As técnicas utilizadas, para resolver este problema, podem ser classificadas em duas categorias: métodos exatos (analíticos e de otimização clássica) como Branch and Bound e Decomposição de Benders; e os métodos aproximados (heurísticas e metaheurísticas). Neste capítulo serão abordadas algumas destas técnicas. 3.1 MÉTODOS EXATOS Os métodos de otimização clássica, geralmente usando técnicas de decomposição matemática, apresentam a característica de encontrar a solução ótima do problema de planejamento e são muito eficientes em sistemas de pequeno e médio porte, mas, para sistemas de grande porte ainda apresentam um esforço computacional elevado e problemas de convergência. A seguir descreve-se de forma resumida apenas a Decomposição de Benders. 3.1.1 Decomposição de Benders A Decomposição de Benders é uma técnica que permite decompor o problema de planejamento em dois subproblemas: um subproblema de operação ou escravo e um subproblema de investimento ou mestre. As variáveis de operação como os fluxos e os ângulos das tensões de barras fazem parte do subproblema de operação, o qual é um problema de programação linear 34 que pode ser facilmente resolvido utilizando algoritmos eficientes de PL. Por outro lado, as variáveis de investimento fazem parte do subproblema de investimento, o qual é um problema de programação linear inteira mista com uma única variável contínua que aparece como parte da decomposição. Assim, a decomposição de Benders resolve o PPEST através de uma solução iterativa dos subproblemas de operação e investimento. A otimização global é atingida através de uma resolução iterativa das soluções separadas dos subproblemas de operação e investimento. Esta técnica não foi capaz de resolver sistemas de grande porte, como o sistema Norte-Nordeste Brasileiro. 3.2 ALGORITMOS APROXIMADOS Numa tentativa de contornar as diversas dificuldades enfrentadas para resolver o problema de planejamento utilizando ferramentas de otimização matemática, devido principalmente a sua natureza não-linear e não-convexa, surgiram os algoritmos aproximados. Sendo uma classe bastante ampla, são exemplos de algoritmos aproximados: algoritmos heurísticos construtivos e algoritmos metaheurísticos. Um algoritmo heurístico construtivo (AHC) é um procedimento iterativo de escolhas ou decisões tomadas passo a passo que, de maneira sistemática, determina uma boa proposta de solução para um problema complexo. No caso do planejamento da expansão dos sistemas de transmissão de energia elétrica, a partir de uma configuração base, em cada passo é adicionado ao sistema um ou vários circuitos até que o conjunto de adições realizadas permita uma operação adequada do sistema elétrico. Portanto, em cada passo, a configuração do sistema é modificada pela adição de um ou vários circuitos, e esta configuração obtida passa a ser denominada configuração corrente. O circuito escolhido em cada passo para ser adicionado à chamada configuração corrente é um circuito que corresponde ao caminho mais atrativo identificado por um critério de sensibilidade, indicador de sensibilidade ou índice de desempenho. Assim a diferença fundamental entre os algoritmos heurísticos construtivos está no indicador de sensibilidade escolhido e, obviamente, no modelo matemático escolhido (transporte, híbrido ou DC). 35 3.2.1 Algoritmo Heurístico Construtivo de Garver O algoritmo heurístico de Garver é um AHC que utiliza o modelo de transportes (neste modelo, apenas as restrições da primeira lei de Kirchhoff devem ser obrigatoriamente satisfeitas), e foi o primeiro algoritmo de grande difusão utilizado no planejamento de sistemas de transmissão (GARVER, 1970). Nesta proposta, Garver formulou o problema como um problema de fluxo de potência e utilizou algoritmos de programação linear para identificar as rotas mais diretas entre os geradores e as cargas. Utilizando o modelo (2.10)-(2.17), e relaxando a integralidade das variáveis inteiras ijn , Garver encontrou a solução ótima contínua, ou seja, variáveis assumindo valores fracionários, para a configuração, corrente 0 ijn , resolvendo apenas um problema de PL. Tendo conhecidas as incógnitas ijn , pode encontrar os fluxos de potência em todos os circuitos antigos ( 0 ijn ) e novos ( ijn ). Portanto, aquele caminho novo ij identificado pelo ijn que leva o maior fluxo de potência representa o caminho mais atrativo de acordo com esta proposta. Um processo repetitivo desta estratégia, adicionando em cada passo um circuito no caminho mais atrativo, constitui o algoritmo de Garver. O processo termina quando a solução do PL correspondente à configuração, corrente apresenta uma solução, com todos os 0=ijn , o que significa que não é mais necessário realizar adições de circuitos ao sistema. O conjunto de adições realizadas representa a proposta de solução do algoritmo de Garver. Em cada passo o algoritmo de Garver resolve o PL abaixo, em que o vetor 1 ijn armazena os circuitos adicionados em cada passo do processo de otimização. 36 O algoritmo de Garver pode ser resumido nos seguintes passos: Passo 1: Assumir a configuração base 0 ijn e 01 =ijn como configuração corrente. Passo 2: Resolver o PL correspondente ao sistema (3.1)-(3.7) para a configuração corrente. Se todos os 0=ijn então pare, pois foi encontrada uma boa configuração factível. Caso contrário, ir ao passo 3. Passo 3: Calcular os fluxos através de todos os novos circuitos adicionados pelo PL, (n 0≠ij ), usando a relação, ijij v ij fnf = . Identificar o novo caminho ij com o maior valor de v ijf e atualizar a configuração, corrente 1 ijn adicionando um circuito naquele caminho ij. Voltar ao passo 2. A grande vantagem do modelo de transportes é que praticamente não existe diferença entre resolver problemas de sistemas conexos e altamente ilhados. A desvantagem está no fato de que a solução, ótima encontrada por este modelo algumas vezes pode ficar longe da solução ótima do modelo DC, pois a solução, do modelo de transportes não satisfaz necessariamente, a segunda lei de Kirchhoff. Do ponto de vista de otimização matemática, o algoritmo de Garver é um algoritmo heurístico construtivo que, na prática, encontra configurações de boa qualidade, mas do ponto de vista teórico, não existe garantia de encontrar a solução ótima global. 37 3.2.2 AHC de Villasana-Garver-Salon O algoritmo proposto em Villasana, Garver e Salon (1985) é um AHC que utiliza o modelo híbrido linear com a estratégia de resolver apenas um PL em cada passo do processo de otimização. A estratégia consiste em resolver um PL de tal forma que seja possível verificar se os circuitos já adicionados permitem que o sistema opere adequadamente para o modelo DC ou, caso contrário, identificar o circuito mais promissor que deve ser adicionado ao sistema. Esses objetivos são atingidos resolvendo um PL que é um caso especial do modelo híbrido linear após relaxar a integralidade das variáveis de investimento ijn . Assim, em cada passo, o algoritmo VGS resolve o PL (3.8)-(3.17). 38 Em que: S: Matriz de incidência nó-ramo transposta para os circuitos candidatos à adição. 0 S : Matriz de incidência nó-ramo transposta para os circuitos da topologia base. 1 S : Matriz de incidência nó-ramo transposta para os circuitos adicionados e dos nós conectados a esses caminhos no processo iterativo do algoritmo VGS. f: Vetor de fluxos totais nos circuitos novos que devem ser adicionados na resolução, do PL com elementos ijf . 0f : Vetor de fluxos totais através dos circuitos da topologia base, com elementos 0 ijf . 1f : Vetor de fluxos totais através dos caminhos adicionados no processo iterativo e com elementos 1 ijf (fluxo nos circuitos já adicionados no caminho ij). Ω : Conjunto de índices dos circuitos candidatos. 0Ω : Conjunto de índices dos circuitos presentes na topologia base. 1Ω : Conjunto de índices dos circuitos adicionados no processo de otimização pelo VGS. Deve-se observar que no PL mostrado em (3.8)-(3.17) os fluxos em cada caminho estão separados em três grupos (fluxos em circuitos existentes na topologia base: 0 ijf , fluxos nos circuitos já adicionados no processo iterativo do algoritmo VGS: 1 ijf e os fluxos nos circuitos adicionados na resolução do PL, ijf . O mesmo acontece com os circuitos ijijij nenn 10 , representando, respectivamente, o número de circuitos presentes no caminho ij na configuração base, circuitos já adicionados no processo iterativo pelo algoritmo VGS e os circuitos adicionados na resolução do PL. E ainda, 0Ω representa o conjunto dos circuitos presentes na configuração base e 1Ω representa o conjunto dos circuitos já adicionados pelo VGS. Se na solução do PL (3.8)-(3.17) tivermos v = 0 e, portanto, 0=ijn , Ω∈∀ ),( ji então, o sistema opera adequadamente apenas com os circuitos da topologia base e os já adicionados no processo iterativo. Como esses circuitos obedecem as duas leis de Kirchhoff, então a proposta de solução, isto é, os circuitos que foram adicionados, é uma proposta factível para o modelo DC. 39 Caso contrário, a solução encontrada nos permite identificar o circuito mais atrativo que deve ser adicionado ao sistema elétrico no próximo passo. O AHC proposto em Villasana, Garver e Salon (1985) utiliza um indicador de sensibilidade definido a partir da solução ótima do modelo híbrido linear (MHL) correspondente à topologia corrente (circuitos da topologia base e os adicionados no processo iterativo) e relaxando a integralidade das variáveis ijn , isto é, a resolução do modelo (3.8)-(3.17). Considerando que relaxando a integralidade das variáveis ijn , como mostra o problema (3.8)-(3.17) então devemos resolver um problema de programação linear (PL), e o índice de sensibilidade é definido como sendo o fluxo de potência pelos circuitos com 0≠ijn na solução do PL. Em cada passo do AHC, o circuito selecionado para adição é aquele identificado pelo seguinte índice de sensibilidade: { },0:max ≠== ijijijij nfnISIS (3.18) em que ijn é a solução do PL depois de relaxar a condição de integralidade no AHC. Em cada passo a solução corrente é, então, atualizada, e assim a topologia corrente é formada pela topologia base juntamente com os circuitos adicionados durante o processo iterativo. A característica mais interessante apresentada no algoritmo VGS é que cada circuito adicionado durante o processo deve satisfazer as duas leis de Kirchhoff, simultaneamente, o que significa que a solução determinada pelo VGS é uma solução factível para o modelo DC. O algoritmo VGS pode ser resumido nos passos a seguir. Passo 1: Assumir a topologia base como solução corrente e usar o modelo híbrido linear modificado relaxado mostrado (3.8)-(3.17). Todos os circuitos presentes na solução corrente devem satisfazer as leis de Kirchhoff da corrente e da tensão. Passo 2: Resolver o PL (3.8)-(3.17) para a topologia corrente. Se a solução indicar que o sistema está operando adequadamente com a nova adição e, portanto, v = 0, pare. Uma nova solução para o modelo DC foi encontrada. 40 Passo 3: Utilizar o índice de sensibilidade (3.18) para identificar o circuito mais atrativo que deve ser adicionado ao sistema. Atualizar a topologia com o circuito adicionado, acrescentando ij em 1Ω e ir ao passo 2. A vantagem de se utilizar esta estratégia é que em cada passo se resolve apenas um PL, mas no final do processo encontra-se uma solução para o modelo DC. Outra possibilidade é resolver o próprio modelo DC após relaxar a integralidade das variáveis ijn mas, nesse caso, deve-se resolver um problema de programação não-linear em cada passo do AHC. Do ponto de vista de otimização matemática o VGS é um algoritmo heurístico construtivo que, na prática, encontra configurações de boa qualidade, mas do ponto de vista teórico, não existe garantia de encontrar a solução ótima global. Um significado importante no algoritmo VGS sobre o índice de sensibilidade é que a solução ótima do PL apresenta um conjunto de 0≠ijn que identificam o melhor investimento proposto satisfazendo somente a primeira lei de Kirchhoff. Quando o circuito é incorporado no sistema, ele passa a cumprir ambas as leis de Kirchhoff. Assim, o índice de sensibilidade utilizado pode não apresentar o desempenho desejado como o índice utilizado no modelo de transportes. Para outros índices, ver (ROMERO et al., 2003). O algoritmo VGS é usado nesta dissertação para encontrar uma solução inicial de boa qualidade. 3.2.3 Algoritmos Metaheurísticos As metaheurísticas (O termo metaheurísticas foi criado por Fred Glover em 1986 e foi amplamente aplicado na literatura) são métodos de busca que combinam métodos heurísticos. Estes métodos têm-se mostrado muito efetivos na solução de problemas difíceis de grande porte, inclusive no problema de planejamento da expansão de sistemas de transmissão. Exemplos de Metaheurística são os métodos de Recozimento Simulado, Algoritmos Genéticos, Grasp, Busca Tabu, VNS entre outros. Neste trabalho analisamos em detalhe apenas o algoritmo VNS que é uma metaheurística usada neste trabalho de pesquisa. 41 4 METAHEURÍSTICA DE BUSCA EM VIZINHANÇA VARIÁVEL Neste capítulo apresenta-se a metaheurística Busca em Vizinhança Variável. Assim, na seção 4.1, tem-se o desenvolvimento desta metaheurística que foi proposta em meados da década de 90, (MLADENOVI�, 1995; MLADENOVI�; HANSEN, 1997), é uma metaheurística que explora basicamente a idéia de trocas sistemáticas de estruturas de vizinhança no espaço de soluções durante o processo de busca. Na sequência, algumas extensões são consideradas, incluindo versões híbridas. As aplicações práticas mais importantes desta metaheurística estão descritas na seção 4.2. 4.1 ESQUEMAS FUNDAMENTAIS DA BUSCA EM VIZINHANÇA VARIÁVEL Metaheurística é uma estratégia de busca através do espaço de soluções de um problema complexo, onde a busca é realizada através de transições no espaço de busca a partir de um ponto inicial ou de um conjunto de pontos iniciais. Nesse contexto, a diferença principal entre as diferentes metaheurísticas é a estratégia usada para realizar as transições no espaço de busca. Discussões e aplicações das melhores metaheurísticas conhecidas podem ser encontradas em Reeves (1993) e, em Glover e Kochenberger (2003). Busca em Vizinhança Variável – VNS (Variable Neighborhood Search) é uma metaheurística que foi proposta por Mladenovi� (1995; MLADENOVI�; HANSEN, 1997), sendo um método de busca local que explora basicamente a idéia de mudanças sistemáticas de estruturas de vizinhança no espaço de soluções durante o processo de busca para encontrar soluções ótimas locais e para sair desses ótimos locais. Nesse aspecto fundamental, VNS é significativamente diferente de outras metaheurísticas. A maioria das metaheurísticas aceita a degradação da solução corrente (ou do conjunto de soluções correntes) como uma estratégia para sair de uma solução ótima local. O algoritmo VNS não aceita essa possibilidade. 42 O algoritmo VNS muda a vizinhança como uma forma de sair de soluções ótimas locais. Nesse processo a solução corrente também é a incumbente o que não acontece nas outras metaheurísticas. Assim, podemos afirmar que o algoritmo VNS realiza um conjunto de transições no espaço de busca de um problema e em cada passo a transição é realizada para a nova incumbente. Se o processo encontra um ótimo local então o algoritmo VNS muda de vizinhança para sair desse ótimo local e passar para a nova incumbente. Como uma consequência dessa estratégia, se o algoritmo VNS encontra o ótimo global então a busca fica parada nesse ponto de ótimo global sem possibilidade de sair desse ponto. Esse tipo de comportamento não acontece com as outras metaheurísticas. A metaheurística VNS explora sistematicamente as seguintes observações: Fato 1: Um mínimo local com relação a uma estrutura de vizinhança não é necessariamente um mínimo local com relação a uma outra; Fato 2: Um mínimo global é um mínimo local em relação a todas as estruturas possíveis de vizinhança; Fato 3: Para muitos problemas, um mínimo local com respeito a uma estrutura de vizinhança compartilha características comuns com o mínimo local que corresponde a outra estrutura de vizinhança. Em geral os mínimos locais para várias estruturas de vizinhança também compartilham características comuns, sendo possível passar de um mínimo local de uma estrutura de vizinhança para o mínimo local de outra estrutura de vizinhança. Os fatos 1 a 3 sugerem, então, o uso de várias estruturas de vizinhança nas buscas locais para abordar um problema de otimização, ou seja, a idéia é definir um conjunto de estruturas de vizinhanças que podem ser utilizadas de forma determinística, de forma aleatória ou determinística e aleatória. Essas formas de utilizar as estruturas de vizinhanças produzem algoritmos VNS de desempenhos diferentes. O fato 3, o qual é de caráter empírico, implica que uma solução ótima local fornece informações importantes em relação ao ótimo global especialmente se a solução ótima local for de excelente qualidade. Existe também a observação empírica de que as soluções ótimas locais 43 geralmente estão concentradas em regiões específicas do espaço de busca. Se as soluções ótimas locais estivessem uniformemente distribuídas no espaço de busca todas as heurísticas baseadas em vizinhança se tornariam ineficientes. Portanto, se for encontrado um ótimo local da região em que se encontra o ótimo global então uma metaheurística tipo VNS tem grandes chances de encontrar esse ótimo global. Por outro lado, se o ótimo global se encontra em outra região então a única possibilidade de encontrar o ótimo global é implementar um processo de diversificação. Por esse motivo um equilíbrio entre intensificação e diversificação no processo de busca pode ser importante em uma metaheurística. Na próxima seção pode-se ver a evolução da VNS. Existem várias formas de implementar o algoritmo VNS e, portanto, podem ser implementada uma família de algoritmos VNS. Diversas propostas de algoritmos VNS podem ser utilizadas de forma independente ou integradas à estruturas VNS mais complexas. Neste trabalho apresentamos alguns desses algoritmos. 4.1.1 VNS de Descida: Algoritmo VND É um método de busca local que consiste em explorar o espaço de soluções através de trocas sistemáticas de estruturas de vizinhanças, aceitando somente soluções de melhora da solução corrente e retornando a primeira estrutura quando uma solução melhor é encontrada. O algoritmo VND apresentado em Hansen e Mladenovic� (2001) assume a forma mostrada no pseudo código 1. A solução final proporcionada por este algoritmo é um mínimo local em relação a todas as maxk estruturas de vizinhança, e portanto, a probabilidade de se alcançar um mínimo global é maior de que quando se usa somente uma estrutura. 44 ——————————————————————————————————— Inicialização: Selecione o conjunto de estruturas de vizinhanças kN , para max,...,1 kk = , que será utilizado durante o processo; encontre uma solução inicial x (ou aplique a regra a um x conhecido). Repetir a seqüência até que nenhuma melhora da solução seja obtida: (1) Faça 1←k ; (2) Repetir até que maxkk = : (a)Exploração: Encontre x’ de x ( )(' xNx k∈ ); (b)Mover ou não: Se a solução assim obtida é melhor que x, faça 'xx ← e 1←k ; Caso contrário, 1+← kk . ——————————————————————————————————— Pseudo Código 1: Algoritmo VND. Ao se implementar o algoritmo VND do pseudo código 1, alguns cuidados devem ser tomados, em particular, considerando as seguintes questões: (i) Que complexidade tem os diferentes movimentos? (ii) Qual a melhor ordem para considerá-los? (iii) Os movimentos são considerados suficientes para garantir uma exploração completa da região que contém x? (iv) Qual a precisão desejada para a solução encontrada? A primeira pergunta refere-se à seleção e classificação dos movimentos: se eles envolvem muitas mudanças elementares, a heurística resultante pode ser muito lenta e frequentemente pode levar mais tempo que um algoritmo exato em problemas de tamanho pequenos ou médios. A questão (ii) também influi no esforço computacional empregado para se alcançar soluções de qualidade. Uma implementação frequente consiste em realizar movimentos por ordem crescente de complexidade (movimentos realizados em vizinhanças de dimensões, )(xNk , crescentes), e voltar a realizar a busca considerando o primeiro tipo de movimento (na 45 primeira vizinhança) cada vez que uma direção de descida é encontrada e um passo é realizado naquela direção. Alternativamente, todos os movimentos podem ser aplicados em sequência contanto que seja feita uma descida em alguma das vizinhanças consideradas. A terceira questão é crucial: para alguns problemas movimentos elementares não são suficientes para sair de um ótimo local, e heurísticas que só os utilizam podem oferecer resultados muito pobres. Finalmente, a precisão desejada, como questionado em (iv) dependerá se a VND é usada isoladamente, ou dentro de alguma estrutura maior, como a própria VNS. No primeiro caso, pode-se realizar um esforço para obter a melhor solução possível dentro do tempo de processamento considerado; no outro caso, prefere-se determinar uma solução boa mais rapidamente através da VND e melhorá-la depois através da VNS básica, a qual será descrita na seção 4.1.3. Ainda em relação à qualidade de um ótimo local, existe um outro aspecto importante que deve fazer parte da lógica de implementação de um algoritmo VNS. Um ótimo local de função objetivo de melhor qualidade não necessariamente pode ser mais adequado para tentar encontrar um ótimo global. Supor que existem duas soluções ótimas locais ba xex em que )()( ba xfxf < para o problema de minimização. Na análise tradicional pode-se concluir que ax é um ótimo local de melhor qualidade que bx . Entretanto, se essas soluções forem utilizadas para iniciar (ou reiniciar) o processo de busca então pode-se afirmar que aquela solução com características internas mais próximas da solução ótima global é a mais adequada para iniciar (ou reiniciar) a busca e, portanto, não necessariamente a solução ax deve ser escolhida. Assim, por exemplo, para o PPEST a solução ótima local que tiver o maior número de elementos ijn iguais aos da solução ótima é a mais adequada para iniciar (ou reiniciar) a busca. Logicamente, em muitos casos considerados não se conhece a solução ótima. Entretanto, existem problemas onde a solução ótima é conhecida e existem vários algoritmos heurísticos para encontrar soluções ótimas locais para esse problema. Nesse contexto, pode-se usar a observação anterior para identificar o algoritmo heurístico que produz soluções ótimas locais de melhor qualidade para iniciar a busca usando o algoritmo VNS. Esse tipo de comportamento acontece no PPEST em que existem instâncias (sistemas elétricos) cujas soluções ótimas são conhecidas e existem muitos algoritmos heurísticos construtivos para encontrar excelentes soluções ótimas 46 locais. Assim, pode-se identificar o melhor algoritmo heurístico construtivo para ser incorporado na estrutura de solução de um algoritmo VNS. Aplicações da VND podem ser encontradas em Brinberg et al. (2000); Hansen e Mladenovi� (2001c) e, Hansen, Mladenovi� e Pérez (2003). 4.1.2 VNS Reduzida: Algoritmo RVNS Assumimos que se tenha encontrado um mínimo local x e que se pretenda então encontrar outro de melhor qualidade. Nas versões básicas da VNS, assume-se que não há nenhum conhecimento prévio do espaço de busca. Então, as questões a seguir devem ser respondidas: (i) Em qual direção realizar a busca? (ii) Qual a distância a ser percorrida? (iii) Como modificar movimentos se eles não oferecem êxito? A pergunta (i) relaciona a possibilidade de alcançar qualquer ponto factível Xx ∈ ou qualquer vale; a resposta mais simples é escolher uma direção ao acaso. Para problemas em variáveis 0-1 isto equivalerá a complementar algumas variáveis; para problemas Euclidianos contínuos, considerar um coeficiente angular ao acaso leva em conta todos os pontos de X. A pergunta (ii) é crucial. De fato, ao se explorar ao limite o Fato 2 da seção 4.1, i.e., que em muitos problemas de otimização combinatória global, os ótimos locais tendem a ser próximos um do outro e estarem situados em uma região pequena (ou às vezes várias regiões) de X. Assim, uma vez encontrado um ótimo local, sempre se encontra informações implícitas sobre outros ótimos, e talvez até de ótimos globais. É, então, natural explorar primeiro sua vizinhança. Mas, se o vale que cerca um ótimo local for grande, isto pode não ser suficiente, e o que fazer é questionado em (iii). Novamente uma resposta natural é ir mais adiante. Estes objetivos são almejados no esquema da RVNS (Reduced Variable Neighborhood Search) apresentado no pseudo código 2. Um conjunto de vizinhanças )(),...,(),( max21 xNxNxN k será considerado ao redor da solução atual x, (o qual pode ser 47 ou não um ótimo local). Normalmente, estas vizinhanças são encaixantes, i.e., cada uma contém a anterior. Então, um ponto x’ é escolhido aleatoriamente na primeira vizinhança. Se seu valor é melhor que o da incumbente, (i.e., )()'( xfxf < , a busca é reiniciada nesta vizinhança )'( xx ← ). Caso contrário, passa-se à próxima vizinhança. Após todas as vizinhanças terem sido consideradas, retoma-se a busca na primeira vizinhança, até que a condição de parada seja satisfeita (normalmente utiliza-se o tempo máximo de processamento desde a última melhoria, ou número máximo de iterações). ——————————————————————————————————— Inicialização: Selecione o conjunto de estruturas de vizinhanças max,...,1, kkparaN k = , que será utilizado durante o processo; encontre uma solução inicial x; escolha uma condição de parada; Repetir a sequência seguinte até que a condição de parada esteja satisfeita: (1) Faça 1←k ; (2) Repetir os passos seguintes até que maxkk = : (a) Exploração: Identifique uma solução aleatória x’ de x ))('( xNx k∈ ; (b) Mover ou não: Se a solução assim obtida é melhor que x, faça 'xx ← e continue a busca em )1(1 ←kN N1; Caso contrário, 1+← kk . Pseudo Código 2: Algoritmo VNS reduzida - RVNS. Devido as vizinhanças serem encaixantes, o tamanho das vizinhanças vão aumentando sucessivamente. Então, deve-se explorar mais completamente as vizinhanças mais próximas de x do que as mais distantes, e só explorar as mais distantes quando não mais for possível se obter melhorias dentro da primeira vizinhança. Deve-se observar que o algoritmo RVNS produz uma escolha de vizinhos mais dinâmica escolhendo vizinhos de todas as estruturas de vizinhança (diversificação) e priorizando a primeira estrutura de vizinhança (intensificação) nas fases iniciais da busca. Entretanto, um componente importante da estrutura RVNS é a capacidade de encontrar novas regiões promissoras a partir de um ótimo local. O algoritmo RVNS também pode ser usado de forma independente ou pode ser integrado em uma estrutura mais complexa de algoritmo VNS. 48 A RVNS é útil em problemas em que uma busca local é muito demorada. Observa-se que o melhor valor para maxk é freqüentemente 2. E para a condição de parada, geralmente, é utilizado o número máximo de iterações entre duas melhorias. 4.1.3 VNS Básica: Algoritmo BVNS Algoritmos VNS mais eficientes podem ser formulados integrando as características do algoritmo VND, que permite encontrar ótimos locais de qualidade, e do algoritmo RVNS que permite encontrar novas regiões promissoras a partir de um ótimo local. Assim, juntando-se estas características podem ser formulados dois tipos de algoritmos VNS que geralmente apresentam excelente desempenho. Esses algoritmos são chamados de Basic Variable Neighborhood Search (BVNS) e General Variable Neighborhood Search (GVNS). O algoritmo BVNS combina a busca local com mudanças sistemáticas de estruturas de vizinhança em torno do ótimo local encontrado (HANSEN; MLADENOVI�, 2001d). A estrutura do algoritmo BVNS é mostrada na pseudo código 3. A lógica de trabalho do algoritmo BVNS é muito interessante. Inicialmente deve-se escolher as k estruturas de vizinhanças. O processo de otimização é iniciado com uma solução Xx ∈ na primeira vizinhança )(1 xN . Na seqüência escolhe-se de forma aleatória um vizinho 'x de x em )(1 xN . A partir de x’ é iniciado um processo de busca local para encontrar um ótimo local x’’. Nesse contexto podem acontecer 3 casos: (1) se x’’ = x significa que x já era o ótimo local da vizinhança e, portanto, deve-se mudar para outro nível de vizinhança ( )(2 xN neste caso); (2) se x” é de pior qualidade que x então foi encontrado um ótimo local de pior qualidade que a incumbente x e também deve-se mudar de vizinhança; (3) se x” é de melhor qualidade que x, significa que foi encontrada uma solução melhor que a incumbente e, portanto, deve-se atualizar a incumbente e reiniciar a busca permanecendo 49 na vizinhança )(1 xN . Em qualquer iteração do processo, sempre que a busca local encontra uma nova incumbente volta-se para a vizinhança )(1 xN e sempre que a busca local encontra uma solução de igual ou pior qualidade que a incumbente então passa-se para uma vizinhança maior. ——————————————————————————————————— Inicialização: Selecione o conjunto de estruturas de vizinhanças max,...,1 kkparaN k = , que será utilizado durante o processo; encontre uma solução inicial x; escolha uma condição de parada; Repetir a sequência seguinte até que a condição de parada esteja satisfeita: (1) Faça 1←k ; (2) Repetir os passos seguintes até que maxkk = : (a)Agitação: Gerar aleatoriamente uma solução x’ na k-ésima vizinhança de ))('( xNxx k∈ ; (b)Busca local: Aplicar algum método de busca local com x’ como solução inicial; denote por x” o mínimo obtido por esta busca; (c)Mover ou não: Se a solução x” assim obtida é melhor que x, faça "xx ← e continue a busca em )1(1 ←kN ; Caso contrário, 1+← kk . ——————————————————————————————————— Pseudo Código 3: Algoritmo BVNS. Essa estratégia e a escolha aleatória do vizinho x evita ciclagem e permite encontrar ótimos locais distantes da incumbente corrente. Se a última vizinhança for alcançada sem que seja encontrada uma solução melhor que a incumbente, a busca é iniciada novamente na primeira vizinhança )(1 xN até que uma condição de parada seja cumprida, como por exemplo, o tempo máximo de processamento, ou número máximo de iterações, ou número máximo de iterações desde a última melhoria. 50 4.1.4 VNS GERAL: Algoritmo GVNS A busca local no algoritmo BVNS pode ser qualquer estratégia heurística. Entretanto, também pode-se usar uma estratégia do algoritmo VNS. Assim, o algoritmo BVNS pode ser transformado em um algoritmo mais geral chamado General Variable Neighborhood Search (GVNS). O algoritmo GVNS é obtido generalizando o algoritmo BVNS simplesmente considerando um algoritmo VND como busca local e utilizando o algoritmo RVNS do pseudo código 2 para melhorar a solução corrente. O algoritmo GVNS é mostrado no pseudo código 4. A GVNS tem sido uma das aplicações que mais obteve êxito recentemente (ANDREATTA; RIBEIRO, 2002; BRINBERG et al., 2000; CAPOROSSI; HANSEN, 2000; HANSEN; MLADENOVI�, 2001c; RIBEIRO; SOUZA, 2002). Inicialização: Selecione um conjunto de estruturas de vizinhanças kN , para max,...,1 kk = , que será usado durante a agitação; selecione um conjunto de estruturas de vizinhanças max,...,1,' jjparaN j = , que será usado durante a descida; encontre uma solução inicial x; escolha uma condição de parada; Repetir a sequência seguinte até que a condição de parada esteja satisfeita: (1) Faça 1←k ; (2) Repetir os passos seguintes até que maxkk = : (a)Agitação: Determinar, aleatoriamente, uma solução vizinha x’, na k- ésima vizinhança de x ))('( xNx k∈ ; (b)Busca local: Aplicar a busca VND com as estruturas jN ' , para max,...,1 jj = ; denote por x” o mínimo assim obtido; (c)Mover ou não: Se a solução x” assim obtida é melhor que x, faça "xx ← e continue a busca em )1(1 ←kN ; Caso contrário, 1+← kk . ——————————————————————————————————— Pseudo Código 4: Algoritmo GVNS. 51 Várias questões sobre a seleção das estruturas de vizinhança devem ser consideradas: (i) Que propriedades devem ter as vizinhanças para que o esquema resultante possa achar um ótimo global ou uma solução quase ótima? (ii) Que propriedades das vizinhanças serão úteis para determinar uma solução quase ótima? (iii) As vizinhanças devem ser encaixantes? Caso contrário, como deveriam ser ordenadas? (iv) Quais as propriedades desejáveis para dimensão do espaço de busca das vizinhanças? As duas primeiras perguntas relacionam a habilidade da metaheurística VNS de determinar as melhores regiões, e fazê-lo rapidamente. Para evitar ser bloqueado em uma região, enquanto existir outra melhor, a união das vizinhanças de qualquer solução factível x deve conter todo o conjunto de soluções factíveis: XxNxNxNxNX k ∈∀∪∪∪∪⊆ ,...)()()( max321 . (4.2) Estes conjuntos podem cobrir X sem necessariamente particionar, o que é mais fácil implementar por exemplo, quando utilizam-se estruturas de vizinhanças encaixantes (aninhadas), i.e., XxNXNxNxNxN kk ∈∀⊂⊂⊂⊂⊂ ,,...)()()( maxmax321 . (4.3) Se estas propriedades não forem asseguradas, não se pode garantir que o espaço de soluções X seja completamente percorrido. Vizinhanças aninhadas podem ser facilmente obtidas em muitos problemas de otimização combinatória, por exemplo, definindo uma primeira vizinhança )(1 xN por um tipo de movimento (por exemplo 2-opt no problema de caixeiro viajante) e então iterando k para obter as vizinhanças )(xN k , para max,...,2 kk = . Assim definidas, as vizinhanças, elas têm a propriedade de que os 52 seus tamanhos estão aumentando conforme k aumenta. Assim, ao se percorrer várias vezes a sucessão inteira de vizinhanças, a primeira delas será explorada mais completamente que as demais. Isto é desejável devido ao Fato 3 mencionado na seção 4.1, i.e., ótimos locais tendem a estarem próximos uns dos outros. 4.1.5 EXTENSÕES DA VNS Hansen e Mladenovi� (2001a), propuseram várias extensões da VNS para resolver problemas de grandes instâncias. Em Hansen e Mladenovi� (2003a) é descrito um tutorial sobre VNS, incluindo extensões, exemplos ilustrativos e questões em relação à implementação. Na literatura aparecem diversas formas de estender a VNS, às quais geralmente são acrescentadas algumas características adicionais. As primeiras extensões derivaram-se diretamente da VNS básica. A BVNS é um método do tipo descendente obtido através da primeira melhoria com aleatorização. Sem muito esforço adicional pode ser transformado em um método ascendente-descendente: basta fazer no passo (2c) "xx ← com alguma probabilidade, ainda que a solução encontrada seja pior que a solução incumbente. Também pode ser transformado em uma busca do melhor movimento: aplicando um movimento na melhor vizinhança * k entre todas as maxk vizinhanças. Outras extensões da VNS consistem em encontrar a solução x’ no passo (2a) como sendo a melhor entre b (um parâmetro) soluções geradas aleatoriamente na k-ésima vizinhança, ou introduzir passokekmin , dois parâmetros que controlam o processo de troca de vizinhança: no algoritmo anterior, em vez de min,1 kkfazerk ←← , e em vez de fazer 1+← kk , fazer passokkk +← . Assim. Existem várias extensões da metaheurística VNS. Entretanto, esses tópicos especializados estão fora do escopo deste trabalho. Para maiores detalhes ver os trabalhos apresentados por Hansen e Mladenovi� (2003a). 53 4.2 ALGORITMO VNS APLICADO AO PROBLEMA DE PLANEJAMENTO DE SISTEMAS DE TRANSMISSÃO Nesta seção descrevem-se os detalhes de implementação da Busca em Vizinhança Variável aplicada ao Problema de Planejamento da Expansão de Sistemas de Transmissão. Nesta implementação, utiliza-se a VNS de descida, VND, com o modelo DC e, nesse caso, a solução inicial é obtida utilizando-se o algoritmo Villasana-Garver-Salon. Nos casos considerados, seguiu-se os passos do algoritmo descrito na Figura 4.1, os quais serão explicados em detalhes nas seções seguintes. ——————————————————————————————————— Passo 1. Codificação do problema: como representar as propostas de soluções; Passo 2. Solução inicial: Utilizar um algoritmo heurístico para determinar uma solução inicial; Passo 3. Definição das vizinhanças: Caracterizar cada vizinhança e determinar seus elementos; Passo 4. Busca local: Indicar um mecanismo que possa determinar a melhor configuração em cada vizinhança da solução corrente. ——————————————————————————————————— Figura 4.1: Algoritmo VND para o PPEST. 4.2.1 Passo 1: Codificação do PPEST Considere o sistema da Figura 4.2, em que existem seis circuitos na topologia básica (representados pelos traços contínuos na Figura 4.2): 10 35 0 24 0 23 0 15 0 14 0 12 ====== nnnnnn e seis circuitos adicionados (representados pelos traços pontilhados na Figura 4.2): 21 46 1 35 1 26 1 23 1 12 ===== nennnn . Pode-se adicionar circuitos em todos os caminhos. 54 Figura 4.2: Sistema de 6 barras com seis circuitos na configuração base e seis circuitos adicionados. Esta configuração pode ser representada através de um vetor ,...),( 1312 nnn = de dimensão nl, em que nl indica o número de caminhos (ramos) em que é possível adicionar circuitos, com elementos ijn que indicam a quantidade de circuitos adicionados no caminho ij, como pode ser observado na Figura 4.3. Figura 4.3: Codificação de uma proposta de solução para o PPEST. Assim, a configuração n da Figura 4.3 mostra que existe um circuito adicionado no caminho 1 (entre as barras 1 e 2), um circuito adicionado no caminho 6 (entre as barras 2 e 3), 55 outro no caminho 9 (entre as barras 2 e 6), outro no caminho 11 (entre as barras 3 e 5) e outros dois no caminho 14 (entre as barras 4 e 6). Nos demais caminhos não existe nenhum circuito adicionado. 4.2.2 Passo 2: Solução Inicial Para gerar uma solução inicial de boa qualidade, usamos um AHC que apresenta excelente desempenho para determinar a solução inicial do problema de planejamento da expansão do sistema de transmissão, em cada passo é escolhido um circuito a ser adicionado ao sistema, onde a escolha é dada por um indicador de sensibilidade especificado pelo AHC. O processo iterativo é finalizado quando uma solução factível e geralmente de boa qualidade foi encontrada. Embora os AHC sejam robustos e convirjam rapidamente, em problemas grandes e complexos apenas convergem em uma solução de boa qualidade (mínimo local). 4.2.2.1 Solução Inicial com o Modelo DC Para determinar uma solução inicial factível para o modelo DC utiliza-se o AHC proposto por Villasana, Garver e Salon (1985), o qual já foi descrito na seção 3.2.2, e considerando-se o modelo híbrido (4.12)-(4.22) com a estratégia de resolver apenas um PL em cada passo do processo de otimização após relaxar a integralidade das variáveis de investimento ijn . 56 Assim, em cada passo, no algoritmo VGS resolve-se o PL (4.12)-(4.22) e verifica se os circuitos já adicionados permitem uma operação adequada do sistema ou, caso contrário, identifica o circuito mais promissor que deve ser adicionado ao sistema, que é determinado através do índice de sensibilidade definido como sendo o fluxo de potência pelos circuitos com 0≠ijn na solução do PL: Do ponto de vista de otimização matemática, o algoritmo de Garver e o algoritmo Villasana-Garver-Salon são algoritmos heurísticos construtivos que na prática encontram configurações de boa qualidade, mas do ponto de vista teórico, não existe garantia de encontrarem a solução ótima global. 57 4.2.3 Passo 3: Definição das estruturas de vizinhanças Na solução do Problema de Planejamento da Expansão de Sistemas de Transmissão utilizando esquemas VNS, as estruturas de vizinhanças podem ser divididas em duas formas: - Básicas: entram um circuito no caminho k e sai um circuito no caminho p; - Especializada: entram circuitos em k caminhos e saem circuitos em p caminhos. Assim, dada uma solução n, utilizando a definição (4.1), pode-se definir a seguinte estrutura de vizinhanças no espaço de soluções S: em que knnd =)',( é a quantidade de posições com atributos distintos em 'nen . Assim, considerando 6max =k , os elementos de cada vizinhança são obtidos, respectivamente, realizando os seguintes movimentos: N1(n): Retirada de circuitos em um caminho; N2(n): Troca de circuitos em dois caminhos (entram circuitos em um caminho e saem circuitos de outro caminho); N3(n): Troca de circuitos em três caminhos (entram circuitos em um caminho e saem circuitos de dois outros caminhos, ou entram circuitos em dois caminhos e saem circuitos de outro caminho); N4(n): Troca de circuitos em quatro caminhos (entram circuitos em dois caminhos e saem circuitos de dois caminhos), ou entram circuitos em três caminhos e saem circuitos em um caminho, ou entram circuitos em um caminho e saem circuitos em três caminhos); N5(n): Troca de circuitos em cinco caminhos (entram circuitos em dois caminhos e saem circuitos em três caminhos, ou entram circuitos em três caminhos e saem circuitos em dois caminhos, ou entram circuitos em um caminho e saem circuitos em quatro caminhos, ou entram circuitos em quatro caminhos e saem circuitos em um caminho); 58 N6(n): Troca de até seis caminhos (entram circuitos em três caminhos e saem circuitos em três caminhos, ou entram circuitos em um caminho e saem circuitos em cinco caminhos, ou entram circuitos em cinco caminhos e saem circuitos em um caminho, ou entram circuitos em dois caminhos e saem circuitos em quatro caminhos, ou entram circuitos em quatro caminhos e saem circuitos em dois caminhos). Note que pode-se retirar ou acrescentar mais que um circuito no mesmo caminho considerado. Para exemplificar, considere-se a configuração n da Figura 4.3. As configurações 2 1 1 1 nen da Figura 4.4 são vizinhos de n em 1N . O vizinho )(1 1 1 nNn ∈ foi obtido a partir de n com a retirada de um circuito no caminho 9, e o vizinho )(1 2 1 nNn ∈ , foi obtido a partir de n com a retirada de um circuito no caminho 14. Figura 4.4: Vizinhos em )(1 nN . As configurações 2 2 1 2 nen na Figura 4.5 são vizinhos de n em )(2 nN . O vizinho )(2 1 2 nNn ∈ foi obtido a partir de n com a entrada de dois circuitos no caminho 8 e a retirada de um circuito no caminho 11. O vizinho )(2 2 2 nNn ∈ foi obtido de n com a retirada de um circuito no caminho 6 e com a entrada de dois circuitos no caminho 12. Figura 4.5: Vizinhos em )(2 nN . 59 As configurações 2 3 1 3 nen na Figura 4.6 são vizinhos de n em )(3 nN . O vizinho )(3 1 3 nNn ∈ foi obtido a partir de n com a adição de um circuito no caminho 3 e a adição de 2 circuitos no caminho 12 e com a retirada de 2 circuitos no caminho 14. O vizinho )(3 2 3 nNn ∈ foi obtido de n com a retirada de um circuito no caminho 6, com a adição de dois circuitos no caminho 9 e com a retirada de um circuito no caminho 14. Figura 4.6: Vizinhos em )(3 nN . Da mesma forma pode-se obter os demais vizinhos através do critério de vizinhança definido. 4.2.4 Passo 4: Busca Local A partir de uma solução factível inicial, pretende-se determinar outras soluções factíveis de melhor qualidade que se encontrem na vizinhança desta solução. E isso deve ser feito em todas as estruturas de vizinhanças predefinidas, sendo que existe a necessidade de verificar se essas propostas de soluções são factíveis ou infactíveis. A factibilidade de uma proposta de solução (neste caso, as soluções vizinhas da topologia corrente) é verificada resolvendo um PL que verifica apenas se o sistema opera adequadamente. Assim, deve-se apenas verificar se com a proposta de solução candidata o sistema opera com corte ou sem corte de carga. 60 4.2.4.1 Modelo DC Quando se utiliza o modelo DC, a busca local nas vizinhanças consideradas é realizada utilizando-se o modelo (4.33)-( 4.41). Na vizinhança )(1 nN tenta-se retirar aqueles circuitos que, uma vez simulada sua saída, não produzem corte de carga no sistema, ou seja, se 0=ω em (4.33), significa que a topologia avaliada representa uma solução factível para o modelo DC. Caso contrário, a proposta representa uma solução infactível, e é então descartada, e passa-se à avaliação da próxima proposta de solução candidata. Nas demais vizinhanças, a busca local é feita através da troca de caminhos. Neste caso, deve-se simular a retirada de circuitos em um caminho (um ou mais circuitos no mesmo caminho considerado) que tem adição na configuração corrente e a adição de circuitos em cada um dos caminhos candidatos. Para isso, calculam-se as variações de custos devido às trocas (diferença do custo das linhas que são adicionadas no sistema e das linhas que saem do sistema) e só se verifica a operação do sistema para as trocas de linhas que apresentam variação negativa, ou seja, só 61 resolvem-se PL’s para as propostas de solução que acarretam uma redução no valor da função objetivo. Se a simulação indicar, ao resolver o PL (4.33)-(4.41), que se trata de uma configuração factível, essa configuração é, então, armazenada para, no fim da busca local, se escolher a melhor configuração candidata para realizar o melhor movimento. Ou seja, durante a busca local, para decidir se a configuração candidata é uma proposta factível para o modelo DC, é verificado se na solução do PL (4.33)-(4.41) tem-se 0=ω . Caso contrário, a proposta representa uma solução infactível e é então descartada, ou seja, a simulação de trocas de circuitos é cancelada e passa-se para a próxima tentativa. 4.2.5 Critério de Parada O critério de parada utilizado foi parar o processo de busca ao se determinar a solução ótima ou parar ao se alcançar maxkN o nível máximo de vizinhança ou após resolver um número máximo de problemas de PLs previamente especificado. 62 5 TESTES E RESULTADOS 5.1 SISTEMAS CONSIDERADOS PARA TESTES A literatura especializada apresenta alguns sistemas utilizados com grande frequência por pesquisadores em planejamento da expansão de sistemas de transmissão. Esses sistemas apresentam dimensão e complexidade variada. Neste trabalho trataremos dos seguintes sistemas: (1) sistema de Garver de 6 barras e 15 circuitos, (2) sistema IEEE 24 barras e 41 circuitos, (3) sistema sul brasileiro de 46 barras e 79 circuitos. O algoritmo proposto foi implementado utilizando-se a linguagem de programação FORTRAN e o MINOS 5.0, (MURTAGH; SAUNDERS, 1995), como uma sub-rotina de resolução de PL. 5.2 VND COM MODELO DC NO SISTEMA DE 6 BARRAS DE GARVER Para o sistema de 6 barras de Garver sem reprogramação da geração o algoritmo VGS encontra a solução ótima global e, portanto, não existe necessidade de usar o algoritmo VNS. Assim, apresentamos de forma detalhada o teste para o caso em que não existe reprogramação da geração. Utilizando uma estrutura de vizinhança básica e considerando-se o sistema de 6 barras de Garver com a rede básica representada pelos circuitos de traços contínuos e respectivos custos, ijc , descritos na Figura 5.1, para se determinar uma solução inicial factível para o mo