Ilha SolteiraIlha Solteira UNIVERSIDADE ESTADUAL PAULISTA “JÚLIO DE MESQUITA FILHO” Câmpus de Ilha Solteira - SP VALBER SARDI LOPES METAHEURÍSTICA GRASP PARA O PROBLEMA DE PLANEJAMENTO DA EXPANSÃO DE SISTEMAS DE TRANSMISSÃO DE ENERGIA ELÉTRICA Ilha Solteira - SP 2013 VALBER SARDI LOPES METAHEURÍSTICA GRASP PARA O PROBLEMA DE PLANEJAMENTO DA EXPANSÃO DE SISTEMAS DE TRANSMISSÃO DE ENERGIA ELÉTRICA Dissertação apresentada à Faculdade de Engenharia do Câmpus de Ilha Solteira - UNESP como parte dos requisitos para ob- tenção do título de Mestre em Engenharia Elétrica. Especialidade: Automação. Prof. Dr. Rubén Augusto Romero Lázaro Orientador Ilha Solteira - SP 2013 FICHA CATALOGRÁFICA Elaborada pela Seção Técnica de Aquisição e Tratamento da Informação Serviço Técnico de Biblioteca e Documentação da UNESP - Ilha Solteira. Lopes, Valber Sardi. L864m Metaheurística GRASP para o problema de planejamento da expansão de sistemas de transmissão de energia elétrica / Valber Sardi Lopes. – Ilha Solteira : [s.n.], 2013 83 f. : il. Dissertação (mestrado) - Universidade Estadual Paulista. Faculdade de Engenharia de Ilha Solteira. Área de conhecimento: Automação, 2013 Orientador: Rubén Augusto Romero Lázaro Inclui bibliografia 1. GRASP (Sistema operacional de computador. 2. Otimização. 3. Planejamento. 4. Modelagem matemática. 5. Heurísticas. 6. Metaheurísticas. Aos meus pais Nieta e Vandir, aos meus irmãos Virgiani e Vandir Filho, pela contribuíção na formação do meu caráter. À minha noiva e amiga Andréa Proto, pela confiança e incentivo em todos os momentos. AGRADECIMENTOS Agradeço a todos, que direta ou indiretamente contribuíram para a realização deste trabalho. Em especial, dedico meus agradecimentos: • Aos meus pais Nieta e Vandir e aos meus irmãos Virgiani e Vandir Filho pelos créditos e incentivos a mim dedicados; • À minha noiva Andréa Proto por compreender meus momentos de angústia durante esta trajetória; • Ao Prof. Dr. Rubén, por todo ensinamento, incentivo, confiança e orientação; • Ao meu amigo e professor Arlenes Silvino, pelo suporte e segurança a mim confiados nos momentos conturbados deste processo; “Seja a mudança que quer ver no mundo.” Mahatma Gandhi RESUMO O Problema do Planejamento da Expansão de Sistemas de Transmissão é um problema de oti- mização combinatória, cujo objetivo é buscar o atendimento de requisitos de cargas a custos mínimos de investimentos, percebendo um horizonte de longo prazo. A perspectiva do plane- jamento otimizado deve ser feita observando duas possiblidades: o planejamento estático e o planejamento multiestágio. No planejamento estático, o planjedor procura responder as ques- tões onde e que tipos de elementos de transmissão precisam ser adicionados ou construídos para integrar a solução do sistema futuro. No entanto, quando a estratégia de expansão ótima abrange todo um período, o planejador deseja saber quando o circuito deve ser instalado, trata-se de um planejamento multiestágio. Em ambas alternativas, a resolução do problema do planejamento deve abranger duas etapas consecutivas: a modelagem matemática e a técnica de solução para resolver essa modelagem. Neste trabalho é apresentada uma proposta de planejamento estático utilizando a Metaheurística GRASP como técnica de solução para o problema do planejamento. Palavras-chave: GRASP. Otimização. Planejamento. Modelagem Matemática. Heurísticas. Metaheuísticas. ABSTRACT The Problem of Expansion Planning of Transmission Systems is a combinatorial optimization problem whose goal is to seek the assistance of cargo requirements at minimal cost investment, realizing a long-term horizon.The prospect of planning should be optimized observing two pos- sibilities: planning static and multistage planning. In planning static, designer seeks to answer the questions where and what types of transmission elements need to be added or built to inte- grate the solution of the future system. However, when the optimal expansion strategy covers the whole period, the planner wants to know when the circuit must be installed, it is a multistage planning. In both alternatives, solving the problem of planning should cover two consecutive steps: mathematical modeling and solution technique to solve this modeling.This work presents a planning proposal using the static technique as GRASP metaheuristic solution to the problem of planning. Keywords: GRASP. Optimization. Planning. Mathematical Modeling. Heuristic. Metaheuris- tic. LISTA DE FIGURAS Figura 1 Sistema inical de 3 barras. . . . . . . . . . . . . . . . . . . . . . . . . . 21 Figura 2 Sistema de 3 barras com 2 circuitos na configuração base. . . . . . . . . . . 27 Figura 3 Métodos de solução. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 Figura 4 Configuração base do sistema de 3 barras. . . . . . . . . . . . . . . . . . 42 Figura 5 Solução ótima contínua. . . . . . . . . . . . . . . . . . . . . . . . . . . 43 Figura 6 Sistema de 3 barras após uma adição. . . . . . . . . . . . . . . . . . . . . 44 Figura 7 Sistema de 3 barras após duas adições. . . . . . . . . . . . . . . . . . . . 45 Figura 8 Configuração final do sistema de 3 barras. . . . . . . . . . . . . . . . . . 46 Figura 9 Topologia base. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 Figura 10 Sistema IEEE de 24 de barras. . . . . . . . . . . . . . . . . . . . . . . . 68 Figura 11 Sistema Sul Brasileiro - Rede inicial. . . . . . . . . . . . . . . . . . . . . 69 LISTA DE ABREVIAÇÕES E SIGLAS DC Corrente Contínua GRASP Procedimento de Busca Gulosa Aleatória Adaptativa PPET Problema de planejamento da Expansão de Sistemas de Transmissão AC Corrente Alternada PNLIM Programação Não Linear Inteira Mista PLIM Programação Linear Inteira Mista PL Programação Linear AHC Algorítmo Heurístico Construtivo VGS Villasana-Garver-salon MHL Modelo Híbrido Linear SA Recozimento Simulado AG Algorítmos Genéticos TS Busca Tabu RCL Lista Restrita de Candidatos VNS Pesquisa de Vizinhança Variável VND Descida de Vizinhança Variável SUMÁRIO 1 INTRODUÇÃO 13 1.1 Motivação do Trabalho 14 1.2 Objetivos do Trabalho 15 1.3 Estrutura do Trabalho 15 2 O Problema de Planejamento da Expansão de Sistemas de Transmissão 16 2.1 Modelagem Matemática 18 2.1.1 Modelo DC 19 2.1.2 Modelo de Transportes 22 2.1.3 Modelo Híbrido Linear 25 2.2 Uma Revisão Sobre o Planejamento da Expansão de Sistemas de Transmissão 28 3 Técnicas Usadas na Resolução do Problema do Planejamento 36 3.1 Métodos Exatos 37 3.1.1 Decomposição de Benders 37 3.1.2 Branch and Bound 37 3.2 Métodos Aproximados 39 3.2.1 O AHC de Garver 40 3.2.2 O AHC de Villasana-Garver-Salon 46 3.2.3 Metaheurísticas 49 4 A Metaheurística GRASP para o Problema da Expansão de Sistemas de Transmissão 52 4.1 GRASP para o Modelo de Transportes 54 4.1.1 Fase Construtiva 55 4.1.2 Fase de Pós-processamento de Busca Local 56 4.1.2.1 Retirada de Linhas de um Mesmo Grupo e Reotimização com AHC de Garver 56 4.1.2.2 Uso de Estratégias de Vizinhança Tradicional 57 4.2 GRASP para o Modelo DC 58 4.2.1 Fase Construtiva 58 4.2.2 Fase de Busca Local do Modelo DC 59 5 Testes e Resultados 60 5.1 Sistema de Garver 6 Barras 60 5.1.1 Modelo de Transportes 62 5.1.2 Modelo DC 62 5.2 Sistema IEEE de 24 Barras 63 5.2.1 Modelo de Transportes 63 5.2.2 Modelo DC 63 5.3 Sistema Sul Brasileiro de 46 Barras 64 5.3.1 Modelo de Transportes 64 5.3.2 Modelo DC 65 5.4 Análise Crítica dos Resultados Encontrados 66 6 Conclusões 70 REFERÊNCIAS 72 APÊNDICE A - Dados dos Sistemas Testados 76 APÊNDICE A.1 - Sistema de 6 Barras de Garver 76 APÊNDICE A.2 - Sistema IEEE de 24 Barras 77 APÊNDICE A.3 - Sistema Sul Brasileiro de 46 Barras 79 13 1 INTRODUÇÃO A energia elétrica é um requerimento humano primário no cotidiano. A utilização deste tipo de fonte de energia proporciona o uso de praticamente todos os tipos de equipamentos conhecidos, tornando óbvia a importância de gerar, transmitir e distribuir energia elétrica com qualidade e no menor custo possível. É importante ressaltar que atualmente existem várias técnicas de geração de energia elétrica com o propósito de suprir uma demanda específica. No entanto, segundo literaturas especiali- zadas, este procedimento nem sempre é trivial e investir em novas linhas de transmissão e/ou transformadores, com intuito de escoamento perfeito deste tipo de geração é fato igualmente importante, levando em conta que predominantemente os geradores com aproveitamento de recursos hidráulicos estão afastados dos centros consumidores. Do ponto de vista comercial, a capacidade de transmissão e distribuição de energia elétrica planejada é um aspecto significante no processo decisivo de concorrência de mercado. Segundo Escobar (2008), o setor de energia elétrica possui segmentos que caracterizam monopólio natu- ral e industrial, que requerem operação centralizada de serviços e outras especificidades como operações com níveis mais elevados de potência. Estes segmentos permitem a exploração de economias de escala e escopo, originando a necessidade de planejamento da expansão da rede de transmissão de energia elétrica. O problema do planejamento de expansão de sistemas de transmissão busca otimizar siste- mas de energia elétrica, ou seja, procura-se atender novos requisitos de carga a custos mínimos de investimentos numa demanda futura. Motivações indicativas para que o planejamento seja de demanda futura se deve a fatores como a dificuldade de construção de novas unidades de geração em locais próximos aos centros consumidores, atenuando-se ao alto custo econômico e demora em sua construção. Fatores como estes são requisitos suficientes para que pesqui- sadores estipulassem critérios na busca de solução do problema do planejamento visando um horizonte de longo prazo. Sistematicamente, o problema de planejamento de sistemas de transmissão é um problema de otimização que segue parâmetros de etapas de modelagem matemática e de escolha de téc- nica para sua resolução. As elaborações de modelos matemáticos no problema do planejamento resultam em operações de caráter combinatório, o que torna estritamente complexa a sua solu- ção, devido a um número elevado de possibilidades. A eficiência da técnica de resolução do problema do planejamento está diretamente re- 1.1 Motivação do Trabalho 14 lacionada à exatidão da modelagem matemática, porém, nem sempre a resolução do modelo matemático encontra uma solução do problema da vida real e, além disso, a técnica deve seguir as restrições de esforço computacional aceitáveis. Categoricamente, verifica-se a segmenta- ção da técnica de solução em métodos exatos (analíticos ou de otimização clássica) e métodos aproximados (heurísticas e metaheurísticas), sendo que ambos devem seguir procedimentos de cálculos objetivando um plano de expansão otimizado para resolver o problema. As técnicas de resolução para problema de planejamento da expansão de sistemas de trans- missão visa determinar onde e que tipo de novos equipamentos devem ser instalados na con- figuração base (conhecida) do sistema de transmissão para suprir uma determinada demanda, observando um horizonte a longo prazo, levando em consideração os modelos matemáticos do problema. As restrições do estudo com percepção de ambiente a longo prazo para o problema do planejamento é parte essencial no processo de solução, já que compreende fases de inovações tecnológicas valoradas. A solução deve ser ótima do ponto de vista técnico e econômico. O problema da expansão da transmissão pode ser formulado considerando na função objetivo, a minimização dos custos de investimento, a obtenção de certos níveis de confiabilidade, a minimização das perdas e a mi- nimização da potência não fornecida aos consumidores (racionamento), entre outros aspectos. Também, o problema é chamado planejamento estático quando o plano de expansão encontrado considera um único horizonte, e planejamento multiestágio quando se tem em conta vários pe- ríodos de tempo dentro dos quais se devem fazer os reforços. Neste trabalho faz-se referência ao planejamento estático como ambiente alvo dos estudos. 1.1 Motivação do Trabalho O contexto de mudanças no “cenário" do setor de energia, em toda a sua complexidade para geração, transmissão e distribuição, está vinculada em aspectos como restrição de investi- mentos, concorrência de mercado, crescimento de demanda, e etc., preconiza a necessidade de exploração de soluções otimizadas. Diversas soluções já foram apresentadas em pesquisas e literaturas especializadas que de- monstraram bons resultados em vastos “cenários". Entende-se que devido a complexidade em mensurar todas as possibilidades de exploração desses “cenários", o problema de planejamento da expansão de sistemas de transmissão é um problema de natureza combinatória e assim, opor- tuniza a exploração de novas técnicas de soluções. Além disso, a evolução computacional traz contribuições significativas para o auxílio de simulações de modelos que representam o problema do planejamento, proporcionando um au- xílio no processo de operações, no surgimento de novas técnicas e contribuindo para a evolução das existentes. 1.2 Objetivos do Trabalho 15 1.2 Objetivos do Trabalho Este trabalho tem por objetivo analisar resultados obtidos a partir de testes computacio- nais de simulação para o problema de planejamento da expansão de sistemas de transmissão, utilizando a Metaheurística GRASP como técnica de solução. Para tanto, faz-se necessário apresentar o seguintes descrições como objetivos específicos: • Caracterizar a modelagem matemática; • Apresentar uma revisão bibliográfica sobre o problema; • Descrever diversas técnicas de resolução, enfatizando a Metaheurística GRASP; • Determinar a estratégia de uso da Metaheurística GRASP para o problema do planeja- mento em simulação computacional com o auxílio do compilador de código FORTRAN; • Testar e apresentar os resultados obtidos. 1.3 Estrutura do Trabalho Este trabalho está organizado da forma descrita a seguir: No capítulo 2 é feito uma apresentação descritiva da modelagem matemática e uma revisão sobre o problema do planejamento da expansão de sistemas de transmissão. No capítulo 3 apresentam-se diversos métodos usados na resolução do problema do plane- jamento. No capítulo 4 apresenta-se o GRASP para o Modelo de Transportes e o Modelo DC para o problema do planejamento. No capítulo 5 descrevem-se testes e resultados obtidos pela simulação computacional. Finalmente, no capitulo 6, são apresentadas algumas considerações finais e perspectivas de trabalhos futuros. 16 2 O PROBLEMA DE PLANEJAMENTO DA EXPANSÃO DE SISTEMAS DE TRANSMISSÃO A dificuldade em construir usinas hidrelétricas perto de centros consumidores de energia elétrica e o custo econômico para provê-lo, são fortes requisitos para que pesquisadores de planejamento se aprofundem em estudos de técnicas para o empreendimento de soluções alter- nativas percebendo restrições ambientais e socioeconômicas para o atendimento de demandas do mercado. As soluções devem ser consideradas observando espaço de tempo que segundo li- teraturas especializadas, o de longo prazo é mais interessante para o problema de planejamento. Assim sendo, neste trabalho é especificado o problema de planejamento da expansão de siste- mas de transmissão em longo prazo (PPET), no espaço de tempo típico estimado de 10 anos futuros. Considera-se que no sistema elétrico atual, já se tenha conhecimento da sua topologia cor- rente e que no PPET procura-se um planejamento otimizado tentando responder as questões onde e que tipos de elementos de transmissão precisam ser adicionados ou construídos para integrar a solução do sistema futuro. Nestas condições, quando o PPET tenta responder apenas essas duas questões, significa que é um planejamento estático, caso este em que o planejador não se interessa em saber quando o circuito deve ser instalado, mas sim encontrar uma topologia final otimizada para uma situação futura definida. Por outro lado, quando a estratégia de expan- são ótima abrange todo um período de planejamento, dividido em vários estágios, então trata-se de um planejamento multiestágio em que segundo Taglialenha (2008), 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. Neste trabalho é considerado o estudo sobre o planejamento estático e posteriormente pode ser estendido para o planejamento multiestágio. Na prática, a resolução do PPET envolve duas etapas consecutivas: a modelagem matemá- tica e a técnica de solução para resolver essa modelagem. Neste contexto, é possível especificar três modelos matemáticos ainda usados para a representação do PPET: O modelo DC, o modelo de transportes e o modelo híbrido. Literaturas especializadas afirmam que o modelo ideal de representação matemática para o PPET deve atender integralmente as duas leis de Kirchhoff (somente o modelo DC contempla as duas leis), sendo que a primeira lei especifica que a soma dos fluxos de potência que entram numa barra deve ser igual à soma do fluxo de potência que saem dessa barra. Por outro lado, a segunda lei especifica que a queda de tensão de cada laço deve ser nula. O modelo de transporte e o modelo híbrido são modelos aproximados do modelo DC. Contudo, a resolução para o 2 O problema do planejamento 17 modelo DC é de grande complexidade, pois se trata de um problema de programação não-linear inteira mista (PNLIM) apresentando características de explosão combinatória, que pertence ao grupo de problemas NP-completo, para os quais não são conhecidos algoritmos que contornem os problemas de esforço computacional e de convexidade (HASHIMOTO, 2005). No processo de técnica de resolução dos modelos matemáticos, é possível encontrar várias técnicas de otimização as quais podem ser divididas em dois grupos: métodos exatos (analíticos ou de otimização clássica) e os métodos aproximados (heurísticas e metaheurísticas). Os métodos exatos apresentam características de solucionar o problema do planejamento para sistemas de transmissão de pequeno e de médio porte, utilizando técnicas de decomposição matemática e técnicas de otimização com programação linear, programação dinâmica, progra- mação não-linear e programação inteira mista, contudo apresenta problemas de convergência e grande esforço computacional. Os métodos aproximados se subdividem em dois grupos: os algoritmos heurísticos cons- trutivos e as metaheurísticas. Os algoritmos heurísticos construtivos buscam adicionar em cada passo um ou vários circuitos na configuração base, tornando esta, a configuração corrente mais atrativa identificada por um critério de sensibilidade, ou seja, a cada vez que houver uma itera- ção na configuração corrente, um indicador de sensibilidade irá adicionar um ou vários circuitos tornando a nova configuração como a nova configuração corrente até que este indicador informe que um critério de parada foi atingido. Este indicador de sensibilidade está de alguma maneira relacionada com a variação da função objetivo a alguma variação dos parâmetros do sistema, considerando como sistema a configuração corrente. O indicador de sensibilidade tem as se- guintes características (ROMERO, 2000): • Identifica os caminhos mais atrativos para realizar adição de circuitos; • É um indicador de caráter local, isto é, identifica a melhor estratégia para a configuração corrente em contraposição de um indicador de caráter global que identificaria a melhor estratégia para identificar a melhor configuração; • Como os indicadores locais nem sempre coincidem com os indicadores globais então os algoritmos heurísticos construtivos, frequentemente, não tem capacidade de encontrar as configurações ótimas globais de sistemas reais. Em geral os algoritmos heurísticos construtivos fornecem uma solução de boa qualidade com pouco esforço computacional, porém não há garantia de solução ótima para sistemas reais de grande porte e não são capazes de oferecerem informações sobre a qualidade da solução obtida. A vantagem deste tipo de estratégia de solução é a simplicidade da implementação que em alguns casos existe a possibilidade do planejador transformar seu conhecimento em um programa (sistema especialista) fazendo associação de matemática e lógica para a verificação 2.1 Modelagem Matemática 18 da validade dos resultados. Segundo Romero (2000), os algoritmos heurísticos construtivos são importantes pelos seguintes motivos: • Na primeira fase de pesquisas (décadas de 60 e 70) era a única maneira que existia para resolver problemas de planejamento de sistemas elétricos de grande porte; • A maioria destes algoritmos são robustos e simples de entender, programar e usar; • Os esforços computacionais destes algoritmos são muito pequenos; • Muitas características e propriedades destes algoritmos podem ser usadas no desenvol- vimento de algoritmos mais complexos como as metaheurísticas (simulated annealing, algoritmo genético, busca tabu, GRASP, etc.); • Ainda hoje, esses algoritmos são os mais usados pelas empresas do setor elétrico. O algoritmo heurístico de Garver é um dos mais importantes usados em planejamento de sistemas de transmissão que além de ter sido um dos primeiros a ser apresentado, contribuiu como base para pesquisas posteriores. Na seção 3.2.1 faz-se um detalhamento desse algoritmo, apresentando suas características e restrições. Nas metaheurísticas, há a descrição de como deve ser explorado o espaço de busca sem se prender em soluções ótimas locais para um problema específico. Estes algoritmos coorde- nam 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 (TAGLIALENHA, 2008). Estas técnicas têm se mostrado mais efetivas em soluções de problemas complexos e de grande porte, porém apresentando a característica do fenômeno combinatório e elevado es- forço computacional. Dentre as metaheurísticas destacam-se Simulated Annealing, Algoritmos Genéticos, Busca Tabu (“Tabu Search"), GRASP, entre outras. Neste trabalho é dada ênfase ao GRASP, com estudos detalhados nos capítulos 4 e 5. 2.1 Modelagem Matemática A formulação de modelos matemáticos em sistemas de transmissão de energia elétrica deve assumir uma representatividade adequada de conjuntos de variáveis relacionadas ao problema da vida real. Essa modelagem deve assumir a possibilidade de apresentar uma solução técnica com esforço computacional aceitável, observando aspectos de comprometimento para obter soluções de problemas da vida real. Especificamente no problema do planejamento, deseja-se encontrar um modelo matemático para representar a topologia corrente do sistema, cuja perspectiva é encontrar um plano de 2.1 Modelagem Matemática 19 expansão otimizado, tentando identificar onde e que tipos de circuitos devem ser construídos para adequar a capacidade do sistema ao crescimento de uma demanda futura. De maneira geral, o PPET consiste em fazer escolhas de circuitos candidatos dentro de um conjunto predefinido, incorporando-os ao sistema de modo que minimize custos de investimentos e operabilidade no plano de geração de energia elétrica em uma perspectiva de vários anos futuros. O modelo matemático mais indicado para a representação do problema seria por meio de relações matemáticas de fluxo de carga AC (Alternating Current), tipicamente utilizadas em análise da operação do sistema elétrico. Contudo esta modelagem mostra-se inviável, pois sua aplicação ainda está restrita a fases iniciais de pesquisa em desenvolvimento. Contudo, testes experimentais exaustivos mostraram que os resultados obtidos com o modelo DC (Direct Cur- rent) apresentam soluções muito próximas ao modelo AC no que diz respeito à distribuição de fluxos de potência ativa e existem várias técnicas de solução que resolvem de maneira ade- quada os problemas do modelo DC (ROMERO, 2000). O modelo DC leva em conta as duas leis de Kirchhoff apenas para o balanço de fluxo de potência ativa, caso este que resulta em um problema de programação não-linear inteira mista (PNLIM), de elevado nível de complexidade para sistemas de grande porte. Além do modelo DC, outros modelos ainda são usados em problemas de planejamento como, por exemplo, o modelo de transportes e o modelo híbrido, que são versões relaxadas do modelo DC, este considerado o modelo ideal. O modelo DC, modelo de Transportes e o modelo Híbrido são discutidos nas próximos subseções. 2.1.1 Modelo DC No modelo DC, considerado como o modelo mais indicado para o PPET, o sistema elétrico deve satisfazer as duas leis de Kirchhoff, isto é, todas as barras do sistema devem satisfazer a primeira lei de Kirchhoff e todos os laços existentes devem satisfazer a segunda lei de Kirchhoff. A primeira lei de Kirchhoff especifica que o somatório dos fluxos de potência que entram em uma barra do sistema deve ser igual ao somatório do fluxo que saem dessa barra. A segunda lei de Kirchhoff especifica que a queda de tensão de cada laço deve ser nula. Assim sendo, o modelo DC é o seguinte: min v = ∑ (i, j) ∈ Ω ci jni j (1) s.a. S f +g= d (2) fi j− γi j(noi j+ni j)(θi−θ j) = 0 (3) | fi j| ≤ (noi j+ni j) f i j (4) 2.1 Modelagem Matemática 20 0≤ g≤ g (5) 0≤ ni j ≤ ni j (6) ni j inteiro, fi j irrestrito, θ j irrestrito (7) ∀(i, j) ∈ Ω (8) O modelo DC assume a forma apresentada em (1)-(8), sendo: v: Investimento devido às adições de circuitos. ci j: Custo de um circuito que pode ser adicionado no caminho i j. ni j: Número de circuitos adicionadas no processo de otimização i j. n0i j: Número de circuitos existentes na topologia base. ni j: Número máximo de circuitos adicionados no caminho i j. γi j: Susceptância de um circuito no caminho i j. f : Vetor de fluxos com elementos fi j (o fluxo de potência total através dos circuitos no caminho i j). f i j: Capacidade de transmissão de um circuito no caminho i j. g: Vetor de geração com elementos gk (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: Ângulos de tensão na barra i. Ω: Representa o conjunto de caminhos em que é possível adicionar circuitos. O conjunto de restrições (2) representa as equações correspondentes à primeira lei de Kir- chhoff, uma equação para cada barra do sistema, e as restrições (3) representam as equações correspondentes à segunda lei de Kirchhoff. As restrições (4) representam as restrições de capacidade de transmissão dos circuitos (linhas e/ou transformadores) e o valor absoluto é ne- cessário, pois os fluxos de potência podem fluir nos dois sentidos. As restrições (5) e (6) são triviais e representam apenas restrições de limite de geração e de circuitos adicionados em cada caminho candidato i j. Finalmente, as variáveis fi j e θi são irrestritas em valores e as variáveis ni j devem ser inteiras, representando a maior fonte de complexidade do 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. Segue abaixo um exemplo de sistema de 3 barras com modelo DC: 2.1 Modelagem Matemática 21 Figura�1�-�Sistema�inical�de�3�barras. � � �� 1 g1 = 80 3 2 20MW 60 PB = 100MW f 12 = 35MW c12 = 3 γ12 = 1 3 f 13 = 40 c13 = 2 γ13 = 1 2 f 23 = 40 c23 = 2 γ23 = 1 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . � � � � � � � � � � � � � � � � � � ...... . . . . . . . . . . . . . . . . . . . . . ...... f12f13 f23 � �� � �� � Fonte:�Romero�(2000) Observando a Figura 1, têm-se os seguintes dados: Custo dos circuitos: c12 = 3, c13 = 2 e c23 = 2 US$ Susceptâncias: γ12 = 1 3 , γ13 = 1 2 e γ23 = 1 2 (p.u. para uma base de 100 MW). Geração máxima e carga: g= 80MW , d2 = 60MW e d3 = 20 MW. Fluxo máximo por linha: f 12 = 35MW , f 13 = 40MW e f 23 = 40 MW. Número máximo de adições permitida por caminho: n12 = n13 = n23 = 2. Inicialmente deve-se escolher um sentido para os fluxos fi j. Embora esta escolha seja arbitrária, em todos os exemplos apresentados neste trabalho os sentidos dos fluxos, em cada caminho, é escolhido no sentido da barra de numeração menor para a barra de numeração maior como é mostrado na Figura 1. As equações correspondentes a primeira lei de Kirchhoff aplicadas para cada barra, consi- derando positivo o fluxo que entra na barra, produz as seguintes equações: 1. Equações da primeira lei de Kirchhoff: Barra 1: − f12− f13+g1 = 0 Barra 2: f12− f23 = 0,60 Barra 3: f13+ f23 = 0,20 2. Equações da segunda lei de Kirchhoff: Circuito 1-2: f12 = 1 3(1+n12)(θ1−θ2) 2.1 Modelagem Matemática 22 Circuito 1-3: f13 = 1 2(1+n13)(θ1−θ3) Circuito 2-3: f23 = 1 2(1+n23)(θ2−θ3) 3. Restrições correspondentes aos limites de fluxos: Circuito 1-2: | f12| ≤ 0,35(1+n12) Circuito 1-3: | f13| ≤ 0,40(1+n13) Circuito 2-3: | f23| ≤ 0,40(1+n23) As outras restrições são triviais e assim, para o exemplo de Figura 1, a modelagem mate- mática do modelo DC assume a seguinte forma: min v = 3n12+2n13+2n23 s.a. − f12− f13 +g1 = 0 f12 − f23 = 0,60 f13 + f23 = 0,20 f12 = 1 3 (1+n12)(θ1−θ2) f13 = 1 2 (1+n13)(θ1−θ3) f23 = 1 2 (1+n23)(θ2−θ3) | f12| ≤ 0,35(1+n12) | f13| ≤ 0,40(1+n13) | f23| ≤ 0,40(1+n23) 0≤ g1 ≤ 0,80 n12, n13 e n23 ∈ {0,1,2} f12, f13, e f23 irrestritos θ1, θ2, e θ3 irrestritos As incógnitas no problema são: v, n12, n13, n23, f12, f13, f23, θ1, θ2, θ3 e g1. 2.1.2 Modelo de Transportes No modelo de Transportes leva-se em consideração apenas a primeira lei de Kirchhoff, que especifica que a soma dos fluxos da potência que entram numa barra deve ser igual ao fluxo que saem dessa barra. Neste caso, considera-se este modelo como um modelo simplificado em 2.1 Modelagem Matemática 23 relação ao Modelo DC (que atende as duas leis de Kirchhoff), resultando num problema de programação linear inteiro misto (PLIM). Este modelo matemático proposto por Garver foi o primeiro a ser utilizado em planejamento de sistemas de transmissão que apesar de ser linear, suas soluções podem apresentar resultados aproximados ou menos adequados para o problema real. Observando as restrições anteriores, formula-se o modelo de transportes para o PPET da seguinte maneira: minv = ∑ (i, j) ∈ Ω ci jni j (9) s.a. S f +g= d (10) | fi j| ≤ (noi j+ni j) f i j (11) 0≤ g≤ g (12) 0≤ ni j ≤ ni j (13) fi j irrestrito (14) ni j inteiro (15) (i, j) ∈ Ω (16) O modelo de transportes assume a forma apresentada em (9)-(16), sendo: v: Investimento devido às adições de circuitos. ci j: Custo de um circuito que pode ser adicionado no caminho i j. ni j: Número de circuitos adicionadas no processo de otimização. n0i j: Número de circuitos existentes na topologia base. ni j: Número máximo de circuitos adicionados no caminho i j. f : Vetor de fluxos com elementos fi j (o fluxo de potência total através dos circuitos no caminho i j). f i j: Capacidade de transmissão de um circuito no caminho i j. g: Vetor de geração com elementos gk (geração na barra k). g: Vetor de geração máxima. S: Matriz de incidência nó-ramo transposta do sistema elétrico. Ω: Representa o conjunto de caminhos em que é possível adicionar circuitos. O conjunto de restrições (10) representam primeira lei de Kirchhoff. O que se observa é que 2.1 Modelagem Matemática 24 os parâmetros e incógnitas são os mesmos do modelo de DC, porém eliminando as restrições da segunda lei de Kirchhoff. Pesquisas sobre o problema (9)-(16) demonstram ser um problema de programação linear inteiro misto (PLIM), e que a solução ótima desse problema não é trivial principalmente para sistemas elétricos de grande porte. Porém, caso fossem permitidas adicionar frações de circuitos (linhas de transmissão e/ou transformadores), isto é, se fosse permitido que os ni j assumissem valores reais, a solução do sistema se tornaria facilitada pois se transformaria em um problema de programação linear (PL), mesmo para sistemas de grande porte. Romero (2000) afirma que a 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 da linearidade 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. O exemplo a seguir mostra uma representação deste sistema para o modelo de transportes levando em consideração os dados da Figura 1 apresentando o sistema de 3 barras. 1. Equações da primeira lei de Kirchhoff: Barra 1: − f12− f13+g1 = 0 Barra 2: f12− f23 = 0,60 Barra 3: f13+ f23 = 0,20 2. Restrições correspondentes aos limites de fluxos: Circuito 1-2: | f12| ≤ 0,35(1+n12) Circuito 1-3: | f13| ≤ 0,40(1+n13) Circuito 2-3: | f23| ≤ 0,40(1+n23) 3. O parâmetro sobre capacidade de geração produz a seguinte restrição: Barra de geração 1: 0≤ g1 ≤ 0,80 4. Os parâmetros sobre o número máximo de adições permitidas em cada caminho candidato produzem as seguintes restrições: Caminho 1-2: 0≤ n12 ≤ 2 Caminho 1-3: 0≤ n13 ≤ 2 Caminho 2-3: 0≤ n23 ≤ 2 A função objetivo assume a seguinte forma: min v = 3n12+ 2n13+ 2n23. Assim, para o exemplo da Figura 1, o modelo matemático pode ser escrito como: 2.1 Modelagem Matemática 25 min v = 3n12+2n13+2n23 s.a. − f12− f13 +g1 = 0 f12 − f23 = 0,60 f13+ f23 = 0,20 | f12| ≤ 0,35(1+n12) | f13| ≤ 0,40(1+n13) | f23| ≤ 0,40(1+n23) 0≤ g1 ≤ 0,80 n12, n13 e n23 ∈ {0,1,2} f12, f13, e f23 irrestritos As incógnitas no problema são: v, n12, n13, n23, f12, f13, f23, e g1. 2.1.3 Modelo Híbrido Linear Outro modelo considerado no problema do planejamento é o modelo Híbrido, que combina características dos modelos DC e transportes. Esta modelagem introduzida por Villasana,Garver e Salon (1985), especifica que ao considerar um sistema da configuração base, todos os circuitos neste tipo devem satisfazer as duas leis de Kirchhoff e que ao adicionar novos circuitos, estes devem satisfazer exclusivamente a primeira lei de Kirchhoff. A ideia de utilizar o modelo híbrido no problema de planejamento de sistemas de trans- missã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 mo- delo DC. Por outro lado, o modelo DC pode apresentar sérios problemas devido a 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 proble- mas 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 pro- cesso de resolução do modelo DC em algoritmos de planejamento de sistemas de transmissão (ROMERO; MONTICELLI, 1994a; VILLASANA; GARVER; SALON, 1985). Observando as devidas restrições, o modelo híbrido pode ser formulado da seguinte maneira: 2.1 Modelagem Matemática 26 min v = ∑ (i, j) ∈ Ω ci jni j (17) s.a. S f +S0 f 0+g= d (18) f 0i j− γi j(noi j)(θi−θ j) = 0,∀(i, j) ∈Ω0 (19) | f 0i j| ≤ noi j f i j,∀(i, j) ∈Ω0 (20) | fi j| ≤ ni j f i j,∀(i, j) ∈Ω (21) 0≤ g≤ g (22) 0≤ ni j ≤ ni j (23) f 0i j irrestritos ∀(i, j) ∈Ω0 (24) fi j e θ j irrestritos ∀(i, j) ∈Ω (25) O modelo híbrido linear assume a forma apresentada em (17)-(25) como um problema de programação linear inteiro misto em que os fluxos estão separados em dois grupos (fluxos em circuitos existentes na topologia base f 0i j, e os fluxos nos circuitos que não estão presentes na topologia base, fi j). O mesmo acontece com os circuitos adicionados: n0i j, ni j, que representa respectivamente, o número de circuitos presentes no caminho i j 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. S0 é a matriz de incidência nó-ramo dos circuitos existentes na topologia base. As demais variáveis são como em (1)-(8) no modelo DC. As restrições (18) representam a primeira lei de Kirchhoff e o conjunto de restrições (19) representam as equações correspondentes à segunda lei de Kirchhoff, com uma equação para cada caminho que apresenta pelo menos um circuito na configuração base. Este último con- junto 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 f 0i j− γi j(noi j + ni j)(θi− θ j), simplesmente não aparece. Já no modelo híbrido aparece somente uma parcela dessas equa- ções 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. Segue abaixo um exemplo do sistema de 3 barras com modelo híbrido linear considerando dois circuitos na configuração base, conforme mostra a Figura 2: 1. Equações da primeira lei de Kirchhoff: Barra 1: − f 013− f12− f13+g1 = 0 2.1 Modelagem Matemática 27 Figura�2�-�Sistema�de�3�barras�com�2�circuitos�na�configuração�base. θ1 θ2 � � �� 1 g1 3 2 20MW 60 f12 f13 f23� �� � �� � . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . � � � � � � � � � � � � � � � � � � ...... . . . . . . . . . . . . . . . . . . . . . ...... θ3 ������� � ����� ����� Barra 2: − f 023+ f12− f23 = 0,60 Barra 3: − f 013+ f 023+ f13+ f23 = 0,20 2. Equações da segunda lei Kirchhoff: Circuito 1-3: f 013 = 1 2(θ1−θ3) Circuito 2-3: f 023 = 1 2(θ2−θ3) 3. Desigualdades correspondentes aos limites de fluxos para circuitos da configuração base: Circuito 1-2: | f 013| ≤ 0,40 Circuito 2-3: | f 023| ≤ 0,40 4. Desigualdades correspondentes aos limites de fluxos para circuitos fora da configuração base: Circuito 1-2: | f12| ≤ 0,35 n12 Circuito 1-3: | f13| ≤ 0,40 n13 Circuito 2-3: | f23| ≤ 0,40 n23 As outras restrições são triviais e assim, para o exemplo da Figura 2, e utilizando a formu- lação (17)-(25), a modelagem matemática do modelo híbrido assume a seguinte forma: 2.2 Uma Revisão Sobre o Planejamento da Expansão de Sistemas de Transmissão 28 min v = 3n12+2n13+2n23 s.a. − f 013 − f12− f13 +g1 = 0 − f 023+ f12 − f23 = 0,60 f 013+ f 023 + f13+ f23 = 0,20 f 013 = 1 2 (θ1−θ3) f 023 = 1 2 (θ2−θ3) | f 013| ≤ 0,40 | f 023| ≤ 0,40 | f12| ≤ 0,35 n12 | f13| ≤ 0,40 n13 | f23| ≤ 0,40 n23 0≤ g1 ≤ 0,80 n12, n13 e n23 ∈ {0,1,2} f 013, f 023, f12, f13 irrestritos θ1, θ2, e θ3 irrestritos As incógnitas no problema sao: v, n12, n13, n23, f12, f13, f23, θ1, θ2, θ3 e g1. 2.2 Uma Revisão Sobre o Planejamento da Expansão de Sistemas de Transmissão Ao se fazer uma análise sobre o problema do planejamento da expansão de sistemas de transmissão verifica-se a existência de vários modelos matemáticos tradicionais e técnicas para a resolução do problema, observando a restrição da minimização de custos de investimento. A procedência nos trabalhos iniciais em problema do planejamento tinha como respaldo apenas usar ferramentas de análise como os utilizados em cálculo de fluxo de potência, estudos de estabilidade, curto-circuito, etc. Segundo Latorre (2003), o planejador do sistema de ener- gia 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 modelos mencionados anteriormente, e que devido ao crescimento dimensional das redes de transmissão, este tipo de procedimento se tornou inoportuno. Pesquisas na área de planejamento de sistemas de transmissão experimentaram uma expan- são e apareceram novos desenvolvimentos de modelos e técnicas de solução. Muitos artigos e 2.2 Uma Revisão Sobre o Planejamento da Expansão de Sistemas de Transmissão 29 relatos sobre novos modelos foram publicados na literatura especializada devido principalmente a melhoria das ferramentas tecnológicas disponíveis, novos algoritmos de otimização, e o maior nível de incerteza introduzido pela expansividade do setor de energia. O trabalho pioneiro 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 foi o de Garver (1970) que 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. Kaltenbatch, Peshon e Gehrig, também no ano de 1970, propuseram 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 período de planejamento. Este trabalho é pioneiro para pro- blemas de planejamento de expansão de redes de transmissão considerando múltiplos estágios. Um algoritmo puro de programação dinâmica proposto por Dusonchet e El-Abiad (1973) parecia contornar as dificuldades em obter a solução ótima dos 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, Gonzaga (1973), propôs um algoritmo de busca em grafos. Este algoritmo, uma versão de algoritmo dual, procura encon- trar 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 com sistemas Brasileiros. O conceito de rede adjunta combinada com o modelo de fluxo linearizado foi a proposta apresentada por Fischl e Puntel (1973). Este trabalho procurava pela variação contínua das susceptâncias dos circuitos que minimiza o custo de reforços na rede de transmissão. Posterior- mente, um procedimento heurístico chamado método do vizinho mais próximo seria utilizado para obter os valores discretos das susceptâncias dos circuitos. A primeira proposta de algoritmos do tipo Branch and Bound para este problema apareceu no trabalho de Lee, Hocks e Hnylicza (1974). Contudo, assim como nos métodos de progra- mação dinâmica, a utilização de algoritmos combinatórios tipo Branch and Bound fica restrita 2.2 Uma Revisão Sobre o Planejamento da Expansão de Sistemas de Transmissão 30 a aplicações a sistemas de pequeno porte face aos recursos computacionais exigidos. O uso de análise de sensibilidade no problema de planejamento de sistemas de transmis- sã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 pro- gramaçã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 opera- cionais na rede elétrica. O uso de análise de sensibilidade também foi proposto por Pereira et al. (1987). Monticelli et al. (1985) 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. Bennon e Juves (1982) utilizaram análise de sensibilidade com relação às susceptâncias dos circuitos em conjunto com o modelo linearizado de fluxo de potência, com o objetivo de determinar o caminho mais efetivo para a minimização de um índice de desempenho do sistema. Villassana(1984) e Villasana, Garver e Salon (1985), apresentam duas diferentes metodo- logias 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, as- sim 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 plane- jamento 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 corrente 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 in- teiro misto (PNLIM) de complexidade muito parecida com a d 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. 2.2 Uma Revisão Sobre o Planejamento da Expansão de Sistemas de Transmissão 31 O uso de esquemas de decomposição para este problema teve início com o trabalho de Pereira (1985). Neste trabalho, um esquema de decomposição de Benders foi aplicado para decompor o problema global de planejamento de redes em dois subproblemas: um de inves- timento, 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 in- vestimentos 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 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 difi- culdades para métodos de cortes como o algoritmo de decomposição de Benders. A aplicação de métodos de planos cortantes a um problema não-linear e não-convexo pode não ser bem sucedida pois os cortes produzidos podem excluir partes da região de viabilidade do problema, inclusive a região que contém a solução ótima. 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 no trabalho de 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 (mais apurado) 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. Outro método de decomposição proposto para o problema de planejamento, foi o apresen- tado por Levi e Calovic (1991) que dividiram o problema de planejamento em dois problemas menores, um tratando somente com questões de investimento e outro considerando somente problemas relacionados à operação. O problema de investimento foi especificado como um problema de fluxo de custo mínimo em rede. Este problema era decomposto novamente em dois subproblemas, o primeiro para computar o fluxo inicial que utiliza um algoritmo de pro- 2.2 Uma Revisão Sobre o Planejamento da Expansão de Sistemas de Transmissão 32 gramação linear para calcular o mínimo corte de carga. O segundo subproblema utilizava o modelo de rede marginal para obter a solução do modelo de fluxo de carga “sobrecarregado”. Latorre-Bayona e Péres (1994) propuseram uma metodologia heurística que utiliza a van- tagem da decomposição natural do problema em subproblemas de operação e investimento. O subproblema de investimento era 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 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 pro- blema 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 con- siste 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. Uti- lizando 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 hie- rárquica, mas composto por duas fases ao invés de três fases como no trabalho de Romero. 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 tra- balhos não vem da decomposição hierárquica utilizada e sim da maneira como o subproblema de investimento era solucionado. Enquanto que o trabalho anterior resolvia o subproblema de investimento até obter a solução ótima utilizando um algoritmo de enumeração implícita es- pecializado, 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 se obter considerável redução do esforço computacional. Na tese de doutorado de Binato (2000), foi proposta uma aplicação computacional uti- lizando 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 rela- 2.2 Uma Revisão Sobre o Planejamento da Expansão de Sistemas de Transmissão 33 cionado com a utilização do modelo linear (0-1) disjuntivo que pode 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 ex- pansão impede a aplicação com sucesso de técnicas de decomposição. Portanto, é necessário o desenvolvimento de técnicas heurísticas que sejam capazes de prover ’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 exem- plo, 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 por Ro- mero, Gallego e Monticelli (1996), Gallego et al. (1997), Gallego, Monticelli e Romero (1998a, 1998b, 2000), Silva, Gil e Areiza (2000) e, Silva et al. (2001). Recozimento Simulado (Simulated Annealing) foi aplicado por Romero, Gallego e Mon- ticelli (1996) e posteriormente foi paralelizado por Gallego et al. (1997). A qualidade dos resultados publicados nestes dois artigos mostraram que tais métodos têm um excelente poten- cial 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 tem- pos 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 me- taheurísticas aplicadas ao problema de planejamento de sistemas de transmissão. Praticamente todas as propostas de metaheurísticas apresentadas na literatura especializadas foram aplicadas ao planejamento estático. Escobar, Gallego e Romero (2004) apresentaram a 2.2 Uma Revisão Sobre o Planejamento da Expansão de Sistemas de Transmissão 34 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 por 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. Esta metodolo- gia será considerada neste trabalho como estratégia de otimização, sendo suas especificidades apresentadas na seção 4. Algoritmos de Busca Tabu (Tabu Search) foram utilizados nos trabalhos de Gallego, Mon- ticelli e Romero (1998a) e Ortiz (1997). Dois Algoritmos Genéticos foram propostos para resolver problemas de planejamento em (Extended Genetic Algorithms) (GALLEGO; MONTI- CELLI; ROMERO, 1998b) e (Hybrid Genetic Algorithms) (BINATO; ROMERO, 1998). 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 por Faria et al. (2002). Path Relinking é um método que surgiu como uma estratégia de intensifi- caçã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 mul- tiestágio. Assim, por exemplo, Haffner (2000) apresenta uma discussão interessante de mode- lagem deste problema e Romero et al. (2003) apresentam um algoritmo heurístico construtivo para o planejamento multiestágio utilizando o modelo de transportes. 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 inte- ressante e as soluções encontradas por esses algoritmos podem ser utilizadas como base para 2.2 Uma Revisão Sobre o Planejamento da Expansão de Sistemas de Transmissão 35 encontrar soluções melhores utilizando algoritmos mais demorados como as metaheurísticas. 36 3 TÉCNICAS USADAS NA RESOLUÇÃO DO PROBLEMA DO PLANEJAMENTO Na seção 2 foi apresentada uma revisão bibliográfica detalhada do problema do planeja- mento e a abordagem de algumas técnicas para resolução do problema. Destacou-se sobre a importância da formulação de modelos matemáticos para o PPET e suas restrições como, por exemplo, a complexidades que a linearidade e a não linearidade podem oferecer ao problema do planejamento. Foi relatado que o Modelo DC é o modelo mais indicado para representar o PPET, porém este modelo apresenta restrições de não linearidade o que torna complexa a sua solução. Já os modelos de Transportes e Híbrido são versões relaxadas do Modelo DC que podem apresentar soluções aproximadas ao problema real. Mostrou-se que os métodos de soluções estão subdivididos em dois grupos: os métodos exatos e métodos aproximados conforme mostra a Figura 3. Figura�3�-�Métodos�de�solução. PPET MetaheuísticasAnalíticos Clássicos Heurísticas Métodos Aproximados Métodos Exatos Fonte:�Taglialenha�(2008) As técnicas utilizadas, para resolver este problema, podem ser classificadas em duas ca- tegorias (Figura 3): métodos exatos (analíticos e de otimização clássica) como Decomposição de Benders e Branch and Bound; e os métodos aproximados (heurísticas e metaheurísticas). Neste capítulo serão abordadas algumas destas técnicas, sendo que serão analisadas com maio- res detalhes apenas o AHC de Garver e o AHC de Villasana-Garver-Salon devido ao uso desses algoritmos dentro da estrutura GRASP presente neste trabalho. 3.1 Métodos Exatos 37 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 resumidamente os métodos de decomposição de Benders e Branch and Bound. 3.1.1 Decomposição de Benders Na década de 80, iniciou-se uma nova fase na tentativa de resolver a formulação do Modelo DC de maneira ótima, mas, como citado anteriormente, em sistemas de grande porte, já apre- sentavam problemas de esforço computacional e de convergência para resolver a formulação ideal, o que significaria resolver um problema de PNLIM (MANSANO, 2008). Nesta perspectiva, a metodologia mais usada foi a técnica de decomposição de Benders a qual explora a decomposição natural do PPET em duas partes, ou seja: • Um subproblema de investimento em que se escolhe um plano de expansão candidato e, calculam-se os custos de investimento associados ao mesmo; • Um subproblema de operação onde é testado o plano de expansão candidato em termos do adequado atendimento da carga. A otimização global é atingida através de uma resolução iterativa dos subproblemas de operação e investimento. Como as metodologias de decomposição foram incapazes de resolver sistemas de grande porte como o sistema Norte-Nordeste brasileiro, foram iniciadas novas pesquisas relacionadas com os métodos de otimização combinatórias, cujas características fundamentais são as de re- solver sistemas de grande porte, chegar a soluções próximas ao ótimo global e obter soluções em tempos de computação razoáveis. 3.1.2 Branch and Bound O algoritmo Branch and Bound é um algoritmo enumerativo, cuja estrutura de resolução baseia-se na construção de uma árvore onde os nós representam os problemas candidatos e os caminhos representam as novas restrições que devem ser consideradas. Por intermédio dessa ár- vore, todas as soluções inteiras da região viável do problema são enumeradas de modo implícito ou explícito o que garante que todas as soluções ótimas sejam encontradas. A estrutura geral 3.1 Métodos Exatos 38 do algoritmo Branch and Bound apresenta três elementos fundamentais, que serão detalhados a seguir: separação, relaxação e sondagem (TAGLIALENHA, 2008). Na etapa de separação, o problema original (P) é separado em q subproblemas (P1),(P2), ..., (Pq) sujeitos às seguintes condições: (S1) Toda solução viável de (P) é uma solução de somente um dos subproblemas (Pi), i= 1,2, ...,q. (S2) Uma solução viável de qualquer um dos subproblemas (Pi), i = 1,2, ...,q, é também, uma solução viável de (P). Estas condições asseguram que o conjunto das soluções viáveis de cada um dos subproble- mas, (Pi), i= 1,2, ...,q, é uma partição do conjunto das soluções viáveis de (P). Os subproble- mas (Pi), i = 1,2, ...,q, são denominados descendentes de (P) e podem, sucessivamente, gerar seus próprios descendentes. O interesse na separação (branching) é utilizar a estratégia de “dividir para conquistar” para resolver o problema (P). Pode-se descrever, sucintamente, esta estratégia do seguinte modo: enquanto a solução de (P) não é possível, separa-se (P) em dois ou mais subproblemas descendentes, gerando uma lista de problemas candidatos (PC). Então, seleciona-se um dos candidatos dessa lista e tenta-se resolvê-lo. Se a solução não é possível, o problema é novamente separado e seus descendentes são adicionados à lista dos candidatos; caso contrário, o problema é resolvido e uma nova solução é obtida. O valor da função objetivo dessa nova solução é, então, comparado com o valor da solução incumbente, que é a melhor solução viável conhecida até o momento. Caso a nova solução seja melhor do que a solução incumbente, ela se torna a nova incumbente. A seguir, retorna-se à lista e seleciona-se o próximo candidato. Isto é repetido até que a lista esteja vazia, quando pode-se afirmar que a solução do problema é dada pela solução incumbente final. A forma usual de separação (branching) de um problema de programação inteira é através de restrições contraditórias em uma única variável inteira (variável de separação ou de rami- ficação). Assim, a partir do problema original, denominado nó zero, originam-se dois novos subproblemas (cada um dos subproblemas descendentes é mais fácil de resolver que o subpro- blema candidato de origem uma vez que foi acrescentada uma restrição na variável de separa- ção), representados pelos nós 1 e 2 que são sucessivamente divididos formando uma árvore. A cada nó se associa um subproblema candidato e cada ramo indica o acréscimo de uma restrição relacionada à variável empregada na separação. Portanto, à medida que se desce na árvore a região viável dos descendentes gerados vai ficando cada vez mais restrita. A relaxação consiste em, temporariamente, ignorar algumas restrições do problema (P) 3.2 Métodos Aproximados 39 visando torná-lo mais fácil de resolver. A condição que deve ser satisfeita é que o conjunto de soluções viáveis do problema original (P) esteja contido no conjunto de soluções viáveis do problema relaxado (PR). Isto implica que: (R1) Se (PR) não tem solução viável, então o mesmo é verdadeiro para (P). (R2) O valor mínimo de (P) não é menor que o valor mínimo de (PR). (R2) Se uma solução ótima de (PR) é viável em (P), então ela é uma solução ótima de (P). Dentre as formas possíveis de relaxação, destaca-se a eliminação das restrições de integra- lidade das variáveis, o que transforma o problema misto em um problema linear (PL) padrão. Na análise dos problemas candidatos existe a necessidade de determinar quais são promis- sores e, portanto, devem ser examinados, e quais podem ser descartados. Isto é realizado na etapa de sondagem onde o problema candidato (PC) é eliminado (descartado para análises fu- turas), juntamente com todos os seus descendentes, se satisfizer a pelo menos um dos seguintes critérios: (S1) O problema candidato relaxado (PCR) não tem solução viável. Devido a (R1), isto significa que o problema candidato (PC) também não tem solução viável. (S2) A solução ótima do problema candidato relaxado (PCR) é pior (bounding) do que a melhor solução atualmente conhecida para (P) (solução incumbente). Observar que a solu- ção ótima do problema candidato relaxado é sempre melhor ou igual à solução do problema candidato e de seus descendentes. (S3) Uma solução ótima do problema relaxado (PCR) é viável, também, em (PC). Neste caso, devido a (R3), ela é ótima em (PC) e, devido a (S2) ela é também factível em (P). Caso seja melhor que a incumbente, a solução deste problema candidato passa a ser a nova solução incumbente. O algoritmo básico, embora seja conceitualmente simples, apresenta complexidade na im- plementação computacional. Este algoritmo apresenta excelente desempenho para sistemas pequenos, mas em sistemas reais apresenta várias limitações relacionadas com o esforço com- putacional. 3.2 Métodos Aproximados Na literatura especializada são apresentados diversos métodos aproximados que determi- nam planos da expansão de redes de transmissão a longo prazo. Um dos primeiros métodos 3.2 Métodos Aproximados 40 aproximados desenvolvidos foi o de Garver (1970); em que se propõe um algoritmo heurístico construtivo para encontrar uma boa configuração e não necessariamente a configuração ótima. Estes métodos geralmente são de fácil implementação e requerem pouco esforço computacio- nal; com relação a qualidade da resposta, e para sistemas de médio e grande porte, seu valor fica geralmente afastado da resposta ótima. Além do método de Garver, menciona-se o método de Villasana (VILLASANA; GARVER; SALON, 1985), que é uma extensão deste método e trabalha usando o modelo híbrido. 3.2.1 O AHC de Garver O algoritmo heurístico de Garver é um AHC que resolve o modelo de transportes (neste mo- delo, 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 trans- missão, (GARVER, 1970). Nesta proposta, Garver formulou o problema como um problema de fluxo de potência em redes e utilizou algoritmos de programação linear para identificar as rotas mais diretas entre os geradores e as cargas. No PPET este modelo permite que o número de linhas entre barras pode ter uma parte inteira e uma parte fracionária, assim na solução do PL pode-se obter o circuito mais atrativo que deve ser adicionado ao sistema. Observando o modelo de transportes (9)-(16) anteriormente apresentado, Garver sugere que o circuito mais adequado para adicionar ao sistema elétrico deve ser obtido com a informação da solução do seguinte problema de programação linear (PL): min v = ∑ (i, j) ∈ Ω ci jni j (26) s.a. S f +g= d (27) | fi j| ≤ (noi j+n1i j+ni j) f i j (28) 0≤ g≤ g (29) 0≤ ni j ≤ (ni j−ni j) (30) fi j irrestrito (31) ∀(i, j) ∈ Ω (32) A proposta de Garver consiste em resolver o problema (26)-(32), que é uma versão rela- xada do modelo de transportes já que foi relaxada a integralidade das variáveis de invetimento ni j, e encontrar a solução ótima não inteira para a configuração corrente (noi j + n1i j). Assim, conhecidas as incógnitas ni j, encontradas usando um algoritmo de PL, pode-se encontrar os fluxos de potência em todos os circuitos antigos (noi j), os já adicionados no processo iterativo 3.2 Métodos Aproximados 41 n1i j, e os novos (ni j). Portanto, aquele caminho novo i j, identificado pelo ni j que leva o maior fluxo de potência, representa o caminho mais atrativo de acordo com a proposta de Garver. A proposta de Garver então consiste em adicionar um circuito na configuração corrente naquele caminho mais atrativo e atualizar a configuração corrente de acordo com a adição escolhida. Um processo repetido dessa 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 apre- senta uma solução com todos os ni j = 0, o que significa que não é necessário realizar mais adições e o conjunto de adições realizadas representa a proposta de solução do algoritmo de Garver (ROMERO, 2000). O algoritmo de Garver pode ser resumido nos seguintes passos: 1. Assumir a configuração base noi j como configuração corrente e com n1i j = 0. 2. Resolver o PL correspondente do problema (26)-(32) para a configuração corrente. Se todos os ni j = 0 então pare pois foi encontrada uma boa configuração factível. Em caso contrário ir ao passo 3. 3. Calcular os fluxos em todos os novos circuitos adicionados pelo PL, (ni j �= 0), usando a relação f vi j = ni j f i j. Identificar o caminho novo i j com o maior valor de f vi j e atualizar a configuração corrente adicionando um circuito naquele caminho i j (portanto, atualizando um elemento em n1i j). Voltar ao passo 2. O maior esforço computacional do algoritmo corresponde ao passo 2 que consiste em re- solver um problema de PL. Entretanto, o algoritmo apresentado pode ainda ser modificado para obter versões alternativas ligeiramente diferentes do algoritmo de Garver. Assim, podem ser realizadas as seguintes modificações: 1. Após a resolução do primeiro PL, pode-se incorporar na configuração base, simultanea- mente, a parte inteira de todos os circuitos que apresentam valores de ni j ≥ 1. 2. Em cada passo, pode-se escolher para adição de um circuito, aquele caminho com maior valor de ni j em lugar de escolher o caminho com maior valor de f vi j. 3. Em cada passo, pode-se manter o critério de adição daquele caminho com maior valor de f vi j, mas em lugar de adicionar um circuito simples naquele caminho, pode-se adicionar um número de circuitos igual à parte inteira de ni j. 4. Incorporar um processo de Fase II para retirar circuitos irrelevantes adicionados na fase inicial. 3.2 Métodos Aproximados 42 Segundo Romero (2000) 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 configuração ótima global, o que significa que o algoritmo encontra com facilidade as configurações ótimas de sistemas pequenos, mas em sistemas de grande porte essas configurações podem ficar bastante afastadas da configuração ótima. O exemplo da Figura 4 mostra o uso de um algoritmo Garver para um sistemas de 3 barras com apenas um circuito na configuração base. Figura�4�-�Configuração�base�do�sistema�de�3�barras. � � �� 1 g1 = 80 3 2 20MW 60 f 12 = 35MW c12 = 3 γ12 = 1 3 f 13 = 40 c13 = 2 γ13 = 1 2 f 23 = 40 c23 = 2 γ23 = 1 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . � � � � � � � � � ...... . . . . . . . . . . . . . . . . . . . . . ...... Fonte:�Romero�(2000) Assumindo que não há limites para as adições de circuitos em cada caminho, a modelagem matemática assume a seguinte forma (ROMERO, 2000): min v = 3n12+2n13+2n23 s.a. − f12− f13 +g1 = 0 f12 − f23 = 0,60 f13+ f23 = 0,20 | f12| ≤ 0,35 n12 | f13| ≤ 0,40(1+n13) | f23| ≤ 0,40 n23 0≤ g1 ≤ 0,80 n12,n13,n23, inteiros f12, f13,e f23 irrestritos 3.2 Métodos Aproximados 43 O algoritmo de Garver resolve o sistema através das seguintes iterações: Primeira iteração: Passo 1: A configuração base com n013 = 1, n012 = n023 = 0 e n112 = n113 = n123 = 0 permite a montagem do sistema e representa a configuração corrente. Passo 2: Após usar um algoritmo de PL é obtida a solução mostrada na Figura 5. A função objetivo corrente é: v= 4,43 que é a solução ótima do PL correspondente. Passo 3: Da Figura 5, pode-se verificar que existe maior fluxo de potencia através do novo caminho 1-2 com f v12 = 40 MW pois o maior fluxo é obtido comparando somente os fluxos dos novos caminhos da configuração corrente. Assim, adiciona-se um circuito no caminho 1-2 para obter a nova configuração corrente: no12 = no23 = 0; no13 = 1 n112 = 1; n113 = n123 = 0 Figura�5�-�Solução�ótima�contínua. � � �� 1 g1 = 80 3 2 20MW 60 n12 = 1,143 40MW � 40 20 n23 = 0,5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . � � � � � � � � � ...... . . . . . . . . . . . . . . . . . . . . . ...... � �� � �� Fonte:�Romero�(2000) Segunda iteração: Passo 2: 3.2 Métodos Aproximados 44 Com a adição de um circuito em 1-2 a modelagem matemática sofre apenas uma restrição | f12| ≤ 0,35 n12 para | f12| ≤ 0,35(1+n12) . Após usar um algoritmo de PL é obtida a solução mostrada na Figura 6. A função objetivo corrente é: v = 3+ 1,43 = 4,43. Onde o valor 3 apresenta o custo do circuito 1-2, adicionado na iteração anterior, e o valor 1,43 é o valor da função objetivo do PL correspondente. Passo 3: Da Figura 6, pode-se verificar que existe maior fluxo de potência através do novo caminho 2-3 com f v23 = 20 MW pois o maior fluxo é obtido comparando somente os fluxos dos novos caminhos da configuração corrente. Assim, adiciona-se um circuito no caminho 2-3 para obter a nova configuração corrente: no n112 = n123 = 1; n113 = 012�= no23�= 0;� no13�= 1� Figura�6�-�Sistema�de�3�barras�após�uma�adição. � � �� 1 g1 = 80 3 2 20MW 60 n12 = 1,143 5 � � 35 40 20 n23 = 0,5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . � � � � � � � � � ...... . . . . . . . . . . . . . . . . . . . . . ...... � �� � �� Fonte:�Romero�(2000) Terceira iteração: Passo 2: Com a adição de um circuito 2-3 a modelagem matemática é muito parecida à obtida na iteração anterior mudando apenas a restrição | f23| ≤ 0,40 n23 para | f23| ≤ 0,40(1+n23). Após usar um algoritmo de PL é obtida a solução mostrada na Figura 7. A função objetivo corrente é: v= 5+0,25= 5,25 onde o valor 0,25 é o valor da função objetivo do PL correspondente. Passo 3: Da Figura 7, pode-se verificar que existe apenas um novo caminho atrativo de 1-3 com 3.2 Métodos Aproximados 45 f v13 = 5 MW. Assim, adiciona-se um circuito no caminho 1-3 para obter a nova configuração corrente: no12 = no23 = 0; no13 = 1 n112 = n113 = n123 = 1 Figura�7�-�Sistema�de�3�barras�após�duas�adições. � � �� 1 g1 = 80 3 2 20MW 60 35 � 40 5 n13 = 0,125 25 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . � � � � � � � � � � � � � � � � � � � ��� �� � �� Fonte:�Romero�(2000) Quarta iteração: Passo 2: Com a adição de um circuito em 1-3 a modelagem matemática é muito parecida à obtida na iteração anterior mudando apenas a restrição | f13| ≤ 0,40(1+n13) para | f13| ≤ 0,40(2+n13). Após usar um algoritmo de PL é obtida a solução mostrada na Figura 8. Não existe adição de novos caminhos pois os ni j = 0. Portanto, as adições realizadas são suficientes para que o sistema opere adequadamente para o modelo de transportes. A configuração final obtida é a seguinte: no12 = no23 = 0; no13 = 1 n112 = n113 = n123 = 1 Com investimento igual a v= 7. Neste caso, o algoritmo de Garver não encontra a solução ótima global para o modelo de transportes. Pois já foi verificada por outras técnicas que a solução ótima deste problema é a seguinte: n13 = 1 e n23 = 2 com investimento de v= 6. 3.2 Métodos Aproximados 46 Figura�8�-�Configuração�final�do�sistema�de�3�barras. � � �� 1 g1 = 80 3 2 20MW 60 35 � 45 25 � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� � �� Fonte:�Romero�(2000) 3.2.2 O AHC de Villasana-Garver-Salon O algoritmo proposto por 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 otimi- zaçã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 ni j . Assim, em cada passo, o algoritmo VGS resolve o PL (33)-(43). minv = ∑ (i, j) ∈ Ω ci jni j (33) s.a. S f +S0 f 0+S1 f 1+g= d (34) f oi j− γi jn0i j(θi−θ j) = 0,∀(i, j) ∈Ω0 (35) f 1i j− γi jn1i j(θi−θ j) = 0,∀(i, j) ∈Ω1 (36) | f oi j| ≤ n0i j f i j,∀(i, j) ∈Ω0 (37) | f 1i j| ≤ n1i j f i j,∀(i, j) ∈Ω1 (38) | fi j| ≤ ni j f i j,∀(i, j) ∈Ω (39) 0≤ g≤ g (40) 0≤ ni j ≤ (ni j−n1i j) (41) 3.2 Métodos Aproximados 47 f 0i j, f 1 i j e fi j irrestritos (42) θ j irrestrito (43) Em que: S: Matriz de incidência nó-ramo transposta para os circuitos candidatos à adição. S0: Matriz de incidência nó-ramo transposta para os circuitos da topologia base. S1: Matriz de incidência nó-ramo transposta para os circuitos adicionados e dos nós conec- tados 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 fi j. f 0: Vetor de fluxos totais através dos circuitos da topologia base, com elementos f 0i j. f 1: Vetor de fluxos totais através dos caminhos adicionados no processo iterativo e com elementos f 1i j (fluxo nos circuitos já adicionados no caminho i j ). Ω: 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 (33)-(43) os fluxos em cada caminho estão sepa- rados em três grupos (fluxos em circuitos existentes na topologia base: f 0i j, fluxos nos circuitos já adicionados no processo iterativo do algoritmo VGS: f 1i j e os fluxos nos circuitos adicionados na resolução do PL, fi j). O mesmo acontece com os circuitos n0i j, n 1 i j e ni j representando, res- pectivamente, o número de circuitos presentes no caminho i j 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 (33)-(43) tivermos v = 0 e, portanto, ni j = 0 , ∀(i, j) ∈ Ω 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. 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 proposto por Villasan, Garver e Salon (1985) utiliza um indicador de 3.2 Métodos Aproximados 48 sensibilidade definido a partir da solução ótima do modelo híbrido linear (MHL) correspon- dente à topologia corrente (circuitos da topologia base e os adicionados no processo iterativo) e relaxando a integralidade das variáveis ni j, isto é, a resolução do modelo (33)-(43). Considerando que relaxando a integralidade das variáveis ni j, o problema (33)-(43) se torna um problema de programação linear (PL), o índice de sensibilidade é definido como sendo o fluxo de potência pelos circuitos com ni j �= 0 na solução do PL. Em cada passo do AHC, o circuito selecionado para adição é aquele identificado pelo seguinte índice de sensibilidade: IS= max{ISi j = ni j f i j : ni j �= 0} (44) em que ni j é 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 adi- cionado 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 (33)-(43). 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 (33)-(43) 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. Em caso contrário ir ao passo 3. Passo 3: Utilizar o índice de sensibilidade (44) para identificar o circuito mais atrativo que deve ser adicionado ao sistema. Atualizar a topologia com o circuito adicionado, acrescentando i j em Ω1 e ir ao passo 2. Um significado importante no algoritmo VGS sobre o índice de sensibilidade é que a so- lução ótima do PL apresenta um conjunto de ni j �= 0 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 3.2 Métodos Aproximados 49 transportes. Para outros índices, ver Romero et al. (2003). 3.2.3 Metaheurísticas As metaheurísticas são um conjunto de técnicas de otimização desenvolvidas para resolver problemas complexos que apresentam o chamado fenômeno da explosão combinatória. Uma metaheurística pode ser vista como uma estrutura algorítmica geral que possa ser aplicada aos diferentes problemas de otimização com relativamente poucas modificações para se adaptar a um problema específico. Algoritmos tais como: “Simulated Annealing", Algoritmos Genéticos, Busca Tabu e GRASP, são algoritmos gerais de alta qualidade. Estes algoritmos são chamados de metaheurísticas, e estão sendo empregados na solução de sistemas de pequeno, médio e de grande porte; nes- tes, reportam-se resultados bastante satisfatórios na maioria das aplicações apresentadas. Neste trabalho será utilizado o GRASP como fonte de estudos em seções posteriores. Simulated Annealing (SA) tenta simular o processo equivalente ao Annealing para encon- trar a solução ótima de um problema complexo. Annealing é uma das técnicas usadas pelos físicos na construção de cristais perfeitos. Nessa técnica o material é aquecido até uma tem- peratura elevada e depois esfriado lentamente, mantendo durante o processo o chamado quase equilíbrio termodinâmico. O processo pára quando o material atinge seu estado de energia mínima na qual se transforma num cristal perfeito (ROMERO, 2000). Sua técnica deriva do chamado algoritmo de Metrópolis, que tem base no método de Monte-Carlo, que estuda as propriedades de equilíbrio da análise de comportamento microscópico dos corpos. O algoritmo de Metrópolis gera uma sequência de estados de um sólido, ou seja: dado um sólido em um estado i e com energia Ei, gera-se o estado seguinte j mediante a aplicação de um mecanismo que transforma para o estado seguinte através de um pequeno distúrbio. A energia do próximo estado é Ej; se a diferença de energia Ei−Ej é menor ou igual a zero, o estado j é aceito. Se a diferença de energia é maior que zero, o estado j é aceito com certa probabilidade, a qual é dada por (HASHIMOTO, 2005): e (Ei−E j) (KbT ) , em que T denota a temperatura, e Kb é uma constante física conhecida como constante de Boltzmann. A regra de aceitação descrita é chamada critério de Metrópolis e o algoritmo como algoritmo deMetrópolis. Se a diminuição da temperatura for feita de maneira paulatina, o sólido pode alcançar o estado de equilíbrio em cada nível. No algoritmo de Metrópolis, essa condição 3.2 Métodos Aproximados 50 é encontrada após gerar um grande número de transições em dado nível de temperatura. Para cada valor de temperatura T , o sólido deve atingir um equilíbrio térmico, caracterizado pela propriedade de estar no estado i com energia Ei determinado pela distribuição de Boltzmann: PT = [X = i] = 1 Z(T ) e ( −Ei KbT ) em que X é uma variável estocástica do estado atual do sólido, Z(T ) = ∑ i e ( −Ei KbT ) , um fator de normalização, conhecido como função partição; Kb, a constante de Boltzmann e e ( −Ei KbT ) o fator de Boltzman. Algoritmos Genéticos (AG) tem base no princípio da seleção natural que fornece maiores possibilidades de sobrevivência aos indivíduos mais adaptados ao ambiente. Este algoritmo possui alta probabilidade de encontrar muitas soluções ótimas locais e a solução ótima global para problemas grandes e complexos. A evolução é baseada em leis de seleção natural (sobrevivência do mais preparado) e recom- binação de informação genética dentro da população. O desenvolvimento da população testa o espaço de busca e acumula conhecimentos sobre áreas de boa ou má qualidade, recombinando este conhecimento para formar soluções com ótimo desempenho para problemas específicos. No princípio, uma população de M soluções é gerada aleatoriamente, codificada em cadeias de símbolos (preferencialmente cadeias binárias) representando cromossomos naturais. Cada membro da população é então codificado para uma solução do problema real e um valor de “aptidão” (“fitness”) é atribuído para o mesmo por uma função qualidade que dá a medida da qualidade da solução. Quando a evolução é completada, indivíduos da população são selecionados em pares para reproduzir e formar indivíduos “descendentes” (ou seja, novas soluções do problema). A sele- ção é desenvolvida probabilisticamente de modo que uma probabilidade de seleção do indivíduo é proporcional à aptidão do mesmo. Isto assegura que soluções de alta qualidade serão seleci- onadas muitas vezes e tornam-se pais de muitas novas soluções enquanto soluções de baixa qualidade contribuirão menos para a nova população com a probabilidade de não serem esco- lhidas para reprodução. Quando dois pais são selecionados suas cadeias de símbolos são combinadas para pro- duzirem uma solução “de descendência” usando a genética como operadores. Os principais operadores utilizados são: Seleção, recombinação e mutação (ROMERO, 2000). Busca Tabu (Tabu Search - TS) realiza um conjunto de transições através do espaço de soluções do problema e, nesse processo de transições, deve-se passar pela solução ótima ou so- 3.2 Métodos Aproximados 51 luções quase ótimas de problemas complexos, também é um algoritmo adequado para resolver problemas combinatórios (ROMERO, 2000). Um dos principais componentes da Busca Tabu é seu uso de memória adaptativa, o qual cria um comportamento de busca mais flexível, ou seja, permite a implementação de procedimentos que são capazes de fazer uma busca em uma grande parte do espaço de solução com pouca solicitação de memória. Visto que escolhas locais são guiadas pela informação coletada durante a busca, a Busca Tabu contrasta com procedimentos sem memória que dependem grandemente de processos semi-randômicos, bem como, com procedimentos de memória rígida típicos de estratégias “branch and bound”. Por outro lado, a conjetura de exploração sensível na Busca Tabu é que uma escolha es- tratégica ruim pode fornecer mais informação do que uma escolha aleatória boa. Com o uso da memória, uma escolha estratégica ruim para um ponto particular na busca pode tornar-se uma decisão boa para um ponto posterior no processo. Embora isto possa ser visto como uma forma primitiva de aprendizagem, a exploração sensível integra os princípios básicos da busca inteligente (exploração de características de solução boa enquanto explora novas regiões pro- missoras). 52 4 A METAHEURÍSTICA GRASP PARA O PROBLEMA DA EXPANSÃO DE SISTEMAS DE TRANSMISSÃO No Capítulo 3 foram apresentadas as principais técnicas usadas na resolução do problema do planejamento enfatizando o AHC de Garver e o AHC de Villasana-Garver-Salon, cuja im- portância desses algoritmos se justifica por se tratar de fontes de objetos de estudos para este trabalho. Neste Capítulo, é apresentada a fundamentação teórica da Metaheurística GRASP e sua técnica para a solução do PPET. Segundo Romero (2000), a ideia básica do algoritmo GRASP é encontrar soluções de ex- celente qualidade de problemas complexos usando uma estrutura de otimização formada por uma generalização de um algoritmo heurístico construtivo (fase construtiva) e um algoritmo de busca através de vizinhança tradicional (fase de melhoria local), isto é, uma versão melhorada do steepest descent heuristic. Assim, o GRASP é uma evolução dos algoritmos heurísticos cons- trutivos, especialmente do algoritmo guloso e de uma heurística tradicional de busca através de vizinhança. Um algoritmo heurístico construtivo guloso encontra uma boa solução factível de um problema complexo adicionando em cada passo uma componente da solução. Em cada passo do algoritmo é escolhido o melhor componente identificado por um indica- dor de sensibilidade. Para o caso do problema de planejamento de sistemas de transmissão, em cada passo é adicionado um circuito ao sistema, aquele circuito que apresenta o melhor critério de desempenho ou indicador de sensibilidade. Um dos principais problemas dos indicadores de sensibilidade de um algoritmo heurístico é que, além de serem indicadores aproximados, o conceito de melhor circuito a ser adicionado é dependente da configuração corrente que está sendo analisada, isto é, existe a melhor pro- posta para a topologia corrente o que não significa que seja a melhor proposta para encontrar a topologia ótima. Entretanto, em cada passo do processo heurístico, é muito provável que o melhor circuito que deve ser adicionado ao sistema, em termos de topologia ótima, se encontre entre os melhores classificados pelo indicador de sensibilidade, mas nem sempre deve ser o melhor classificado. Portanto, GRASP sugere escolher um circuito de uma lista dos k circuitos melhores classificados pelo indicador de sensibilidade porque é altamente provável que nessa lista de k circuitos existam circuitos que fazem parte da topologia ótima. A escolha do circuito de uma lista reduzida, na formulação básica, é realizada de forma aleatória, mas existem várias formas de realizar essa escolha, por exemplo, usando funções de probabilidade que, funda- mentalmente, fornecem maior probabilidade na escolha dos circuitos melhores classificados. A escolha aleatória de um circuito, de uma lista de k circuitos, permite encontrar muitas topologias de qualidade através de processos repetitivos usando sementes diferentes para gerar a sequên- 4 A Metaheurística GRASP para o Problema da Expansão de Sistemas de Transmissão 53 cia de números aleatórios. O conceito adaptativo aparece quando é usada uma lista, chamada lista reduzida RCL, de tamanho variável e que depende da qualidade das soluções candidatas e do processo de solução. Portanto, esse tipo de algoritmo usa uma lista reduzida de tamanho k variável (os elementos de RCL), mas o tamanho de RCL também pode ser mudado usando um parâmetro α variável, representando uma variante do algoritmo GRASP chamado de algo- ritmo GRASP reativo. Obviamente, cada nova topologia encontrada deve ser submetida a um processo de busca local tentando encontrar um ótimo local a partir da topologia encontrada. O algoritmo GRASP, para um problema genérico, assume a seguinte forma: 1. Implementar a fase de pré-processamento. 2. Realizar a fase de busca construtiva. 3. Realizar a fase de pós-processamento de busca local. Atualizar a incumbente caso seja possível. 4. Se o critério de parada não for satisfeito, voltar ao passo 2. Caso contrário, pare. A resposta do algoritmo é a incumbente armazenada. O pré-processamento tenta identificar determinadas subestruturas, isto é, atributos ou con- junto de atributos, que permitem iniciar o processo de busca construtiva ou diminuir o espaço de soluções do problema. Por exemplo, no problema da árvore de expansão mínima, pode-se formar uma lista com as arestas de menor peso. Cada elemento dessa lista pode ser usado para iniciar um processo de busca na fase construtiva. No problema de planejamento da expansão de sistemas de transmissão não usamos a fase de pré-processamento. A fase de busca construtiva consiste em encontrar uma solução de qualidade para o pro- blema usando um algoritmo heurístico construtivo escolhendo, em cada passo, um elemento de uma lista de tamanho k. A fase construtiva do algoritmo GRASP apresenta os seguintes passos: 1. Escolha a solução inicial que pode ser vazia, isto é, sem adição de variáveis ou compo- nentes, que se transforma na solução corrente. 2. Para a solução corrente e usando um índice de desempenho ou indicador de sensibilidade, elaborar uma lista com as k variáveis mais atrativas. 3. Escolha uma variável da lista de k elementos e atualizar a solução corrente com a adição da variável escolhida. 4. Se a solução corrente é factível ou foi satisfeito o critério de parada (sem encontrar uma solução factível) terminar com a fase construtiva. Caso contrário voltar ao passo 2. 4.1 GRASP para o Modelo de Transportes 54 Analisamos, brevemente, uma forma adequada para encontrar os elementos da lista RCL. Seja z(x) a função objetivo de um problema com variáveis de decisão x. Tipicamente, uma função de mérito ou indicador de sensibilidade apresenta a seguinte forma genérica: h(xi)α ∂ z ∂xi A função h(xi) permite encontrar a lista de variáveis atrativas que fazem parte do conjunto RCL. Considerando que o problema é de minimização da função objetivo z(x), então a variável mais atrativa, xi, identificado por um algoritmo guloso, é aquele que apresenta um menor valor de h(xi). Portanto, fazem parte do conjunto RCL todas as variáveis cujos índices satisfazem a seguinte relação: RCL= {i ∈ X \ .hmin ≤ h(xi)≤ hmin+α(hmax−hmin)} em que X é o conjunto de índices das variáveis que ainda podem ser adicionadas e α é um parâmetro fornecido pelo usuário com valores 0 ≤ α ≤ 1, hmax e hmin assumem a seguinte forma: hmax = maxi∈X{h(xi)} hmin = mini∈X{h(xi)} Logicamente, um algoritmo heurístico construtivo (guloso) escolheria a variável xi com h(xi) = hmin. O parâmetro α representa um compromisso entre escolha aleatória e gulosa, pode-se verificar que α = 1 representa um processo totalmente aleatório e α = 0 um processo guloso. A escolha da variável da lista RCL pode ser realizada de duas formas: (1) aleatoria- mente e, (2) usando uma função de distribuição de probabilidade como, por exemplo, a função de distribuição de probabilidade linear bi = 1/ri em que ri representa a posição que ocupa a variável i na lista de variáveis atrativas RCL. Portanto, a probabilidade de escolha da variável i é encontrada usando a relação: pi = bi ∑ j∈RCL b j 4.1 GRASP para o Modelo de Transportes A fase construtiva do algoritmo GRASP para o modelo de transportes usa apenas uma g