UNIVERSIDADE ESTADUAL PAULISTA JÚLIO DE MESQUITA FILHO - UNESP

FACULDADE DE ENGENHARIA DE ILHA SOLTEIRA

PROGRAMA DE PÓS-GRADUAÇÃO EM ENGENHARIA ELÉTRICA

Reconfiguração de Sistemas de Distribuição de
Energia Elétrica Utilizando a Metaheuŕıstica Busca

em Vizinhança Variável

Wilingthon Guerra Zvietcovich

Prof. Dr. Rubén Augusto Romero Lázaro
Orientador

Dissertação apresentada ao Pro-
grama de Pós-Graduação em En-
genharia Elétrica da UNIVER-
SIDADE ESTADUAL PAULISTA
“JÚLIO DE MESQUITA FILHO”
- UNESP, CAMPUS DE ILHA
SOLTEIRA, para preenchimento
dos pré-requisitos parciais para
obtenção do T́ıtulo de Mestre em
Engenharia Elétrica.

25 de Agosto de 2006



CERTIFICADO DE APROVAÇÃO

TÍTULO: Reconfiguração de Sistemas de Distribuição de Energia Elétrica Utilizando a
Metaheuŕıstica Busca em Vizinhança Variável

Autor: WILINGTHON GUERRA ZVIETCOVICH

Orientador: Prof. Dr. RUBEN AUGUSTO ROMERO LÁZARO

Aprovado como parte das exigências para obtenção do Tı́tulo de MESTRE em ENGENHARIA
ELÉTRICA pela Comissão Examinadora:

Prof. Dr. RUBEN AUGUSTO ROMERO LÁZARO
Departamento de Engenharia Elétrica / Faculdade de Engenharia de Ilha Solteira

Prof. Dr. JOSE ROBERTO SANCHES MANTOVANI
Departamento de Engenharia Elétrica / Faculdade de Engenharia de Ilha Solteira

Dr. LUIZ CARLOS PEREIRA DA SILVA
Departamento de Sistemas de Energia Elétrica / Universidade Estadual de Campinas

Data da realização: 25 de Agosto de 2006.



Dedico esta dissertação à minha famı́lia,

por todo apoio, compreensão, amor e

carinho que sempre me concederam.



Agradecimentos

Dedico meus sinceros agradecimentos:

– Á Deus, por conceder-me saúde e inteligêcia;

– Ao professor doutor Rubén Romero, por dar-me a oportunidade de alcançar uma

das minhas metas profissionais, também pela orientação, apojo e amizade;

– Aos professores doutores Antonio Padilha, José Mantovani e Sérgio Azevedo, pelas

sugestões e atenção que me deram;

– Ás funcionárias da seção de pós-graduação, pelo bom atendimento;

– Aos meus amigos da Pós-graduação, com quem muito aprendi e fiz grande amizade;

– Á FEPISA, pelo apoio financeiro;



“Todo grito de dor, tem por eco

uma alegria”

Anônimo.



Sumário

Resumo p. 8

Abstract p. 9

Lista de Figuras p. 10

Lista de Tabelas p. 12

Introdução p. 14

1 Cálculo de Fluxo de Carga para Redes de Distribuição Radiais p. 17

1.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 17

1.2 Método de Varredura . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 18

1.2.1 Processo de Backward . . . . . . . . . . . . . . . . . . . . . . . p. 18

1.2.2 Processo de Forward . . . . . . . . . . . . . . . . . . . . . . . . p. 19

1.3 Método de Soma de Potências . . . . . . . . . . . . . . . . . . . . . . . p. 21

1.3.1 Processo de Backward . . . . . . . . . . . . . . . . . . . . . . . p. 22

1.3.2 Processo de Forward . . . . . . . . . . . . . . . . . . . . . . . . p. 23

2 Reconfiguração de Sistemas de Distribuição Radiais p. 25

2.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 25

2.2 Algoritmo Heuŕıstico de Cinvanlar (CINVANLAR; GRAINGER; LEE, 1988) p. 28

2.2.1 Caracteŕısticas Desejáveis do Método de Solução . . . . . . . . p. 29

2.2.2 Cálculo de Variação de Perdas . . . . . . . . . . . . . . . . . . . p. 30

2.2.3 Comentários . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 32



2.3 Algoritmo Heuŕıstico de Shirmohammadi (SHIRMOHAMMADI; HONG, 1989) p. 32

2.3.1 Procedimento para a Determinação do Padrão de Fluxo Ótimo

em uma Rede Malhada . . . . . . . . . . . . . . . . . . . . . . . p. 32

2.3.2 Comentários . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 33

2.4 Algoritmo Heuŕıstico de Goswami - Basu (GOSWAMI; BASU, 1992) . . . p. 34

2.4.1 Seleção da Chave Aberta que será Fechada . . . . . . . . . . . . p. 34

2.4.2 Determinação do Padrão de Fluxo Ótimo . . . . . . . . . . . . . p. 35

2.4.3 Comentários . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 37

3 Busca em Vizinhança Variável p. 38

3.1 Conceitos Básicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 38

3.1.1 Metaheuŕıstica de Busca . . . . . . . . . . . . . . . . . . . . . . p. 39

3.1.2 Buscas Locais e Globais . . . . . . . . . . . . . . . . . . . . . p. 39

3.2 Escolha da Configuração Inicial . . . . . . . . . . . . . . . . . . . . . . p. 41

3.3 Representação e Codificação do Problema . . . . . . . . . . . . . . . . p. 41

3.4 Estruturas de Vizinhanças . . . . . . . . . . . . . . . . . . . . . . . . . p. 43

3.4.1 Geração das Estruturas de Vizinhanças . . . . . . . . . . . . . . p. 44

3.4.2 Geração de Estruturas de Vizinhanças Através de k-intercâmbios p. 45

3.4.3 Ordenação das Estruturas de Vizinhança . . . . . . . . . . . . . p. 47

3.5 Estratégia de Busca e Mudança de Vizinhança . . . . . . . . . . . . . . p. 47

3.6 Critério de Parada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 49

3.7 Redução da Vizinhança . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 51

3.7.1 Estratégias de Exploração . . . . . . . . . . . . . . . . . . . . . p. 51

3.7.2 Estratégia Utilizada . . . . . . . . . . . . . . . . . . . . . . . . p. 51

3.8 Implementação dos Algoritmos VNS e VND . . . . . . . . . . . . . . . p. 53

3.8.1 Descrição do Algoritmo Implementado para Minimização de Per-

das . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 55



4 Resultados Obtidos p. 61

4.1 Sistema de 14 barras . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 61

4.2 Sistema de 32 barras . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 62

4.3 Sistema de 69 barras . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 63

4.4 Sistema de 135 barras . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 64

4.5 Sistema de 202 barras . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 66

4.5.1 Com limitação de chaveamento . . . . . . . . . . . . . . . . . . p. 66

4.5.2 Sem limitação de chaveamento . . . . . . . . . . . . . . . . . . . p. 67

4.6 Conclusões . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 68

5 Conclusões p. 70

Referências p. 72

Apêndice A -- Dados dos Sistemas Testados p. 75

A.1 Sistema de 14 barras . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 75

A.2 Sistema de 32 barras . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 76

A.3 Sistema de 69 barras . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 77

A.4 Sistema de 135 barras . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 80

A.5 Sistema de 202 barras . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 86



8

Resumo

A reconfiguração de sistemas de distribuição de energia elétrica consiste em alterar

a topologia das redes através da abertura/fechamento das chaves de interconexão. Nor-

malmente este procedimento é feito para fins de isolamento de faltas, minimização de

perdas ativas, balanceamento de cargas entre alimentadores ou para melhoria dos ńıveis

de tensão. Atingir estes objetivos é dif́ıcil, devido ao grande número de variáveis envolvi-

das e das restrições impostas, sendo a radialidade uma restrição de dif́ıcil representação

matemática. Este problema pode ser classificado dentro dos problemas de programação

não linear inteiro misto (PNLIM) e apresenta o fenômeno da explosão combinatória.

Neste trabalho tem-se como principal objetivo o desenvolvimento de uma metaheuŕıstica

chamada Busca em Vizinhança Variável para a reconfiguração de sistemas de distribuição

de energia elétrica com respostas no planejamento da operação em função da razonali-

dade da carga. Verificamos que este método mostrou ser eficiente, pois através de uma

metodologia simples, obteve-se resultados melhores em relação aos apresentados na lite-

ratura.

Palavras chaves: Redes de Distribuição, Otimização de Perdas, Busca em Vizinhança

Variável.



9

Abstract

The network reconfiguration of electric power distribution consists of changing the
topology of networks through the opening/closing of interconnection switches. This pro-
cedure is usually done to isolate faught, reduction real power losses, balance the load
among feeders or for improvement of tension levels. To reach these objectives is diffi-
cult, due to the great number of involved variables and the imposed constraints, being
the constraint of radial structure of difficult mathematical representation. This problem
can be classified as nonlinar mixed integer programming problems and it presents the
phenomenon of combinatorial explosion. The main objective og this work is to develop a
metaheuristic called Variable Neighbourhood Search for network reconfiguration of elec-
tric power distribution for operation planning based on rationality of load. This method
showed to be efficient using a simple methodology, getting better results in relation to the
presented in Literature.

keywords: Distribution Networks, Optimization of lost, Variable Neighbourhood Search.



10

Lista de Figuras

1 Sistema de distribuição hipotético. . . . . . . . . . . . . . . . . . . . . p. 14

2 Métodos propostos para resolver o problema de reconfiguração de redes

elétricas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 15

3 Cálculo de corrente de carga. . . . . . . . . . . . . . . . . . . . . . . . p. 19

4 Sistema de 4 barras . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 19

5 Cálculo de tensão na barra. . . . . . . . . . . . . . . . . . . . . . . . . p. 20

6 Diagrama de blocos do algoritmo fluxo de carga radial varredura. . . . p. 21

7 Sistema de duas barras. . . . . . . . . . . . . . . . . . . . . . . . . . . p. 22

8 Diagrama de blocos do algoritmo de fluxo de carga radial Soma de Potência. p. 24

9 Sistema de três alimentadores. . . . . . . . . . . . . . . . . . . . . . . p. 29

10 Diagrama de blocos do algoritmo proposto por (CINVANLAR; GRAINGER;

LEE, 1988). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 31

11 Diagrama de blocos do algoritmo proposto por Shirmohammadi (SHIR-

MOHAMMADI; HONG, 1989). . . . . . . . . . . . . . . . . . . . . . . . . p. 33

12 Laço formado ao se fechar uma chave normalmente aberta . . . . . . . p. 35

13 Laço formado para determinar o PFO. . . . . . . . . . . . . . . . . . . p. 36

14 Diagrama de blocos do algoritmo proposto por (GOSWAMI; BASU, 1992). p. 37

15 Diagrama de blocos do algoritmo busca local. . . . . . . . . . . . . . . p. 40

16 Busca local com arranques múltiples. . . . . . . . . . . . . . . . . . . p. 41

17 Sistema de 14 barras . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 42

18 Vizinhanças induzidas. . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 44

19 Geração de estruturas de vizinhança através de k-intercâmbios. . . . . p. 46



Lista de Figuras 11

20 Diagrama de blocos utilizando a busca EII em todas as estruturas de

vizinhança (VNS). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 49

21 Diagrama de blocos utilizando a busca EII para a primeira estrutura de

vizinhança e busca EI nas outras estruturas de vizinhança. . . . . . . p. 50

22 Diagrama de blocos - algoritmo utilizando estratégia Parcial - Aleatória

- PFO no processo de busca (VNS). . . . . . . . . . . . . . . . . . . . p. 53

23 Diagrama de blocos - algoritmo utilizando estratégia Parcial - Aleatória

- PFO no processo de busca (VND). . . . . . . . . . . . . . . . . . . . p. 54

24 Diagrama de blocos do algoritmo VNS. . . . . . . . . . . . . . . . . . p. 59

25 Diagrama de blocos do algoritmo VND. . . . . . . . . . . . . . . . . . p. 60

26 Sistema de 14 barras. . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 62

27 Sistema de 32 barras . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 63

28 Sistema de 69 barras. . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 64

29 Sistema de 135 barras. . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 65

30 Sistema de 202 barras. . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 66



12

Lista de Tabelas

1 Resultados obtidos: algoritmo de Cinvanlar (CINVANLAR; GRAINGER;

LEE, 1988). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 31

2 Resultados obtidos: algoritmo de Shirmohammadi (SHIRMOHAMMADI;

HONG, 1989). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 33

3 Resultados obtidos: algoritmo Goswami e Basu (GOSWAMI; BASU, 1992). p. 37

4 Parâmetros do algoritmo para a rede de 135 barras utilizando uma con-

figuração inicial de operação. . . . . . . . . . . . . . . . . . . . . . . . p. 56

5 Resultados obtidos sistema de 135 barras usando uma configuração inicial

de operação. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 56

6 Parâmetros do algoritmo para a rede de 135 barras usando o algoritmo

de Goswami e Basu. . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 56

7 Resultados obtidos sistema de 135 barras usando uma configuração inicial

obtida pelo algoritmo de Goswami e Basu. . . . . . . . . . . . . . . . . p. 56

8 Resultados obtidos sistema de 14 barras. . . . . . . . . . . . . . . . . . p. 62

9 Resultados obtidos sistema de 32 barras. . . . . . . . . . . . . . . . . . p. 63

10 Resultados obtidos sistema de 69 barras. . . . . . . . . . . . . . . . . . p. 64

11 Resultados obtidos sistema de 135 barras. . . . . . . . . . . . . . . . . p. 65

12 Resultados obtidos sistema de 202 barras - com limitação de chaveamento p. 67

13 Resultados obtidos sistema de 202 barras - sem limitação de chavea-

mento. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 68

14 Parâmetros do algoritmo VNS. . . . . . . . . . . . . . . . . . . . . . . p. 69

15 Parâmetros do algoritmo VND. . . . . . . . . . . . . . . . . . . . . . . p. 69

16 Dados sistema de 14 barras. . . . . . . . . . . . . . . . . . . . . . . . . p. 75

17 Dados sistema de 32 barras. . . . . . . . . . . . . . . . . . . . . . . . . p. 76



Lista de Tabelas 13

18 Dados sistema de 69 barras. . . . . . . . . . . . . . . . . . . . . . . . . p. 77

19 Dados sistema de 135 barras. . . . . . . . . . . . . . . . . . . . . . . . p. 80

20 Dados sistema de 202 barras. . . . . . . . . . . . . . . . . . . . . . . . p. 86



14

Introdução

O mercado de energia atualmente competitivo sob os aspectos técnico-econômicos

exige que as empresas concessionárias de energia elétrica desenvolvam esforços no sentido

de melhorar as condições de operação de suas redes. Uma das técnicas para otimizar a

operação das redes de distribuição é através de sua reconfiguração. As redes de distribuição

possuem um conjunto de dispositivos de controle e proteção que permitem alterar facil-

mente a sua configuração, através de manobras destes dispositivos, viabilizando ações que

permitam operar o sistema sempre da maneira mais adequada, isto é, com redução nas

perdas activas e melhoria nos ńıveis de tensão mantendo a condição de radialidade do

sistema. Esta condição faz com que alguns ramais estejam operando e outros não.

Este é um problema conhecido como reconfiguração ótima para planejamento da

operação de um sistema de distribuição. Encontrar a topologia ótima exige analisar

impĺıcita e/ou explicitamente todas as topologias radiais existentes na rede.

A modelagem matemática do problema de reconfiguração é um problema de pro-

gramação não linear inteiro misto ( PNLIM), representando uma explosão combinatória

do número de topologias posśıveis, sendo que a exigência de radialidade é um fator adi-

cional que complica a resolução do problema. A Figura 1 mostra uma rede pequena muito

usada pelos especialistas em reconfiguração.

SE

SE

SE
 SE

Outros Sistemas

Outros Sistemas

Outros Sistemas

Outros Sistemas

Sistema de Geração e Transmissão

Figura 1: Sistema de distribuição hipotético.



Introdução 15

Os principais métodos apresentados na literatura para resolver o problema da recon-

figuração podem ser classificados como mostra a Figura 2.

Técnicas de
reconfiguração

de redes

Métodos
baseados em
conhecimento

Métodos
baseados em

modelos físicos
ou biologicos

Heurísticas

Redes
neurais

Sistemas
especialistas

Lógica
nebulosa

Outros

Busca tabu

Algoritmos
genéticos

Esfriamento
simulado

Outras
metaheurísticas

Figura 2: Métodos propostos para resolver o problema de reconfiguração de redes
elétricas.

Numa primeira categoria estão os métodos baseados em conhecimento, que se fun-

damentam na experiência dos operadores sobre as manobras dos sistemas. Com base

neste conhecimento desenvolveram-se muitos algoritmos que facilitam a busca das novas

configurações da rede de distribuição, tentando obter uma solução perto da ótima. Den-

tro desta categoria encontram-se as heuŕısticas, tais como as propostas por (CINVANLAR;

GRAINGER; LEE, 1988; GOSWAMI; BASU, 1992; BARAN; WU, 1989a; SHIRMOHAMMADI;

HONG, 1989), que encontram boas topologias, especialmente para sistemas de grande

porte, utilizando esforços computacionais pequenos.

Recentemente técnicas como os Sistemas Especialistas, Lógica Nebulosa e Redes Neu-

rais apresentados por (LIU; LEE; VENKATA, 1988; BOUCHARD et al., 1993; KIM; KO; JUNG,

1993) respectivamente, foram também aplicadas para solucionar o problema de recon-

figuração de redes. Estas técnicas foram implementadas com regras heuŕısticas para solu-

cionar os problemas com menor esforço computacional.

A segunda categoria corresponde aos métodos baseados em modelos f́ısicos ou biológicos

que existem na natureza, os quais não têm uma formulação matemática rigorosa que



Introdução 16

permita estabelecer com certeza seu comportamento em cada situação. Como exem-

plo destas técnicas temos “Simulated Annealing” por (NARA; KITAGAWA, 1991), Algorit-

mos Genéticos por (LIN; CHENG; TSAY, 2000), Genético Modificado por (ROMERO, 2001),

Busca Tabu por (DUARTE, 1999; GUIMARÃES, 2005), etc. Essas técnicas estão sendo

muito usadas para resolver problemas complexos em áreas muito variadas, assim como

para resolver o problema da reconfiguração. Esses métodos encontram soluções ótimas ou

quase ótimas de sistemas de grande porte, mas geralmente com esforços computacionais

elevados.

Neste trabalho de pesquisa propõe-se verificar a viabilidade em resolver o problema de

reconfiguração da rede, objetivando a minimização das perdas de potência ativa, através

da técnica de “Busca em Vizinhança Variável”. Que é um procedimento metaheuŕıstico,

classificado na Figura 2 dentre outras metaheuŕısticas.

A Busca em Vizinhança Variável (VNS) foi proposta por N. Mladenovic em 1995

(MLADENOVIC, 1995), e está demostrando ser uma técnica muito eficiente e de fácil

aplicação em muitos problemas da vida real.

A dissertação está organizada em 5 caṕıtulos descritos a seguir:

No caṕıtulo 1, são apresentados estudos sobre alguns métodos de fluxo de carga para

redes radiais, utilizados como ferramentas de análise na reconfiguração de sistemas de

distribuição de energia elétrica.

No caṕıtulo 2, é realizada a revisão bibliográfica sobre algoritmos para reconfiguração

de sistemas de distribuição de energia elétrica.

No caṕıtulo 3, são apresentados os conceitos básicos do algoritmo Busca em Vizi-

nhança Variável e sua aplicação na reconfiguração de sistemas de distribuição de energia

elétrica.

No caṕıtulo 4, são apresentados os resultados obtidos com a implementação do algo-

ritmo de reconfiguração para minimizaçao das perdas de potência ativa.

No caṕıtulo 5, são apresentadas as conclusões concernentes à aplicação dos algoritmos

propostos.

No apêndice A é apresentado os dados completos dos sistemas analisados.



17

1 Cálculo de Fluxo de Carga para

Redes de Distribuição Radiais

1.1 Introdução

O algoritmo de fluxo de carga resolve um problema de equações não lineares para

encontrar o estado de operação de uma rede (módulos e ângulos de tensão nodal). Uma

vez obtido o estado da rede é calculado o fluxo de potência, correntes nos ramos, etc.

Na literatura especializada existem vários algoritmos tais como os algoritmos de

Gauss, Gauss-Seidel, Newton e as versões desacopladas desses algoritmos. O método de

Newton (MONTICELLI, 1983) apresenta um desempenho superior comparado com outros

métodos (ELGERD, 1978). Este algoritmo é muito usado na análise de sistemas de energia

elétrica, mas os sistemas de distribuição apresentam caracteŕısticas muito espećıficas: (i)

Operam em forma radial e, (ii) apresentam uma relação de R/X elevada, comparados

com os valores t́ıpicos encontrados em sistemas de sub-transmissão e transmissão. A

primeira caracteŕıstica é uma vantagem porque simplifica consideravelmente a complexi-

dade do problema, entretanto a segunda caracteŕıstica é uma desvantagem porque produz

divergência quando usamos o método de Newton.

Dentro da resolução da metaheuŕıstica Busca em Vizinhança Variável (VNS) para

o problema de reconfiguração é necessário avaliar a função objetivo (calcular as perdas

totais da rede para cada configuração) com o processamento de centenas de problemas

de fluxo de carga. Por isto é preciso utilizar um método de fluxo de potência rápido e

eficiente.

Foram desenvolvidos e apresentados muitos algoritmos especializados para resolver o

problema de fluxo de carga de sistemas de distribuição radial (SHIRMOHAMMADI, 1988;

BARAN; WU, 1989b; CÉSPEDES, 1990; GOSWAMI; BASU, 1992). Todos estes algoritmos a-

presentam a vantagem adicional de que são muito mais rápidos que as versões desacopladas

de Newton.



1.2 Método de Varredura 18

Pela necessidade de avaliar a função objetivo dentro do processo de solução da re-

configuração de redes, e as vantagens mencionadas dos algoritmos especializados em sis-

temas de distribuição, são analisados neste caṕıtulo dois algoritmos de fluxo de carga

radial: Método de varredura (BRANDINI, 2000), que apresenta caracteŕısticas muito pare-

cidas com o algoritmo apresentado por (SHIRMOHAMMADI, 1988) e o método de soma de

potências, desenvolvido por (CÉSPEDES, 1990).

1.2 Método de Varredura

Este algoritmo é conhecido como método de Varredura porque apresenta um processo

iterativo das barras finais em direção à subestação e vice-versa (BRANDINI, 2000). O

processo consiste previamente em escolher um valor para os módulos de tensão nas barras,

este valor é tipicamente a mesma tensão da subestação, isto é, para cada barra k, assume-

se que Vk = Vref + j0, onde Vref é o módulo de tensão da subestação e j0 é a parte

imaginaria de Vk. Com as tensões nas barras escolhidas é posśıvel conhecer a corrente de

carga em todas as barras e as correntes em todos os ramos do sistema radial. Este processo

é implementado, iniciando das barras extremas e percorrendo as barras em direção à

subestação ( backward). Com as correntes calculadas nos ramos é posśıvel calcular as

perdas ativas (e reativas) do sistema. Assim, é encontrado um valor aproximado das

perdas no sistema.

Com as correntes nos ramos calculados no processo backward é posśıvel conhecer a

corrente que está saindo da subestação. Então, usando os valores das correntes dos ramos

e iniciando o processo a partir da subestação é posśıvel calcular os novos valores das

tensões de todas as barras do sistema. Este processo é realizado a partir da subestação e

termina nas barras extremas e geralmente é chamado de forward. Com os novos valores

de tensão das barras é posśıvel encontrar, novamente, as correntes de carga nas barras

e as correntes em todos os ramos do sistema. Os novos valores de correntes dos ramos

permitem encontrar novos valores de perdas ativas (e reativas) do sistema. Um processo

repetitivo permite encontrar as perdas do sistema.

1.2.1 Processo de “Backward”

Na Figura 3 são apresentadas duas barras, a carga é representada na forma Sk =

Pk + jQk e a tensão de barra na forma Vk = Vkr + jVki, se tem as seguintes relações

matemáticas:



1.2 Método de Varredura 19

Figura 3: Cálculo de corrente de carga.

Sk = Pk + jQk Vk = Vkr + jVki (1.1)

Sk = VkIk
∗ ⇒ I∗

k =
Pk + jQk

Vkr + jVki

.
(Vkr − jVki)

(Vkr − jVki)
(1.2)

Fazendo Ik = Ikr + jIki e igualando com a relação anterior, pode-se encontrar as

relações matemáticas para a corrente de carga separando as partes real e imaginária:

Ikr =
PkVkr + QkVki

Vkr
2 + Vki

2 (1.3)

Iki =
PkVki + QkVkr

Vkr
2 + Vki

2 (1.4)

Da Fig. 4, pode-se deduzir:

I34 = I4 I23 = I34 + I3 I12 = I23 + I2 (1.5)

Figura 4: Sistema de 4 barras

1.2.2 Processo de “Forward”

Na Figura 5, duas barras de um sistema de distribuição radial são apresentadas, neste

caso são conhecidas as tensões nas barras Vk = Vkr + jVki e as correntes nos ramos

Ikm = Ikmr + jIkmi, se tem:



1.2 Método de Varredura 20

Ikm = Ikmr + jIkmi (1.6)

Tem-se a seguinte relação matemática:

Vk = Vkr + jVki = Vm + (rkm + jxkm)(Ikmr + jIkmi) (1.7)

Pode-se deduzir:

Vmr = Vkr − rkmIkmr + xkmIkmi (1.8)

Vmi = Vki − rkmIkmi + xkmIkmr (1.9)

Figura 5: Cálculo de tensão na barra.

Da Figura 4, tem-se:

V2 = V1 − I12Z12 V3 = V2 − I23Z23 V4 = V3 − I34Z34 (1.10)

Calculado os novos valores de tensão em todas as barras e correntes em todos os ramos,

pode-se calcular facilmente as perdas ativas e reativas. Da Figura 5 tem-se:

Pkmp = rkmI2
km (1.11)

Qkmp = xkmI2
km (1.12)

Então as perdas totais do sistema são:

Pt =
∑

(k,m)∈Ω

rkmI2
km (1.13)

Qt =
∑

(k,m)∈Ω

xkmI2
km (1.14)



1.3 Método de Soma de Potências 21

Em que Ω representa o conjunto de todos os ramos do sistema elétrico. O diagrama de

blocos do algoritmo é apresentado na Figura 6.

Figura 6: Diagrama de blocos do algoritmo fluxo de carga radial varredura.

1.3 Método de Soma de Potências

Este algoritmo é conhecido como método de Soma de Potências e desenvolvido por

(CÉSPEDES, 1990), também é relativamente simples de implementar e eficiente na res-

olução de problemas de fluxo de carga radial.

O processo de resolução é iniciado escolhendo um valor para os módulos de tensão

nas barras, frequentemente na maioria dos casos é a mesma tensão da barra de referência.

Com as tensões nas barras é posśıvel conhecer a carga equivalente em cada barra do

sistema, esta carga equivalente é obtida somando os seguintes componentes: (i) As cargas

conectadas às barras, (ii) mais as perdas nos ramos. Este processo é realizado para cada

barra do sistema, conhecido como backward, porque o processo é iniciado a partir das



1.3 Método de Soma de Potências 22

barras extremas na direção à subestação. Neste processo é posśıvel calcular paralelamente

as perdas totais do sistema.

Conhecido os valores das cargas equivalentes é posśıvel calcular os novos valores dos

módulos de tensão nas barras do sistema. Este processo é conhecido como forward, começa

a partir da subestação até chegar às barras extremas.

Pode-se deduzir que o algoritmo consiste num processo backward - forward e termina

quando a variação de perdas em duas iterações é menor que uma tolerância especificada.

O algoritmo é ilustrado no diagrama de blocos da Figura 8.

1.3.1 Processo de “Backward”

Da Figura 7, deduzem-se as seguintes relações matemáticas:

ki
kr
k
 jV
V
V
 +
=
 mi
mr
m
 jV
V
V
 +
=

kmi
kmr
km
 jI
I
I
 +
=
 m
k

km
kmr
km
 jx
r
Z
 +
=

jQ
P
S
m
 +
=

Figura 7: Sistema de duas barras.

Sm = VmI∗

km ⇒ I∗

km = Sm

Vm

I∗

km =
P + jQ

Vmr + jVmi

→ Ikm =
P − jQ

Vmr − jVmi

⇒ I2
km =

P 2 + jQ2

V 2
m

(1.15)

Portanto, as perdas ativas assumem a seguinte forma:

Pkmp = I2
kmrkm = rkm

P 2 + jQ2

V 2
m

(1.16)

Qkmp = I2
kmxkm = xkm

P 2 + jQ2

V 2
m

(1.17)

Onde Pkmp e Qkmp são as perdas ativas e reativas respectivamente na linha.

Uma vez calculadas as perdas em todos os ramos do sistema é posśıvel calcular os

novos valores das cargas equivalentes em todos os ramos do sistema. Este processo para

trás (backward) simplesmente consiste em concentrar as cargas de todas as barras que são

alimentadas pela barra analisada considerando as perdas dos ramos.



1.3 Método de Soma de Potências 23

Da Figura 4, pode-se mostrar o processo da seguinte forma:

P34 = r34
P4+jQ4

V 2

4

⇒ P3 = P3 + P4 + P34

Q34 = x34
P4+jQ4

V 2

4

⇒ Q3 = Q3 + Q4 + Q34

P23 = r23
P3+jQ3

V 2

3

⇒ P2 = P2 + P3 + P23

Q23 = x23
P3+jQ3

V 2

3

⇒ Q2 = Q2 + Q3 + Q23

P12 = r12
P2+jQ2

V 2

2

⇒ P1 = P1 + P2 + P12

Q12 = x12
P2+jQ2

V 2

2

⇒ Q1 = Q1 + Q2 + Q12

1.3.2 Processo de “Forward”

Da Figura 7, pode-se fazer a seguinte análise: Conhecidas as cargas equivalentes em

todas as barras, se fará um processo que inicia da subestação até as barras extremas para

calcular os novos módulos das tensões em todas as barras.

Desenvolvendo uma série de relações e deduções matemáticas (BRANDINI, 2000),

chega-se a seguinte expressão:

V 4
m + [2(rkmP + xkmQ) − V 2

k ]V 2
m + (P 2 + Q2)(r2

km + xkm2) = 0 (1.18)

Com esta expressão é posśıvel calcular a tensão da barra m conhecidas a tensão da

barra k, a carga equivalente na barra m e a impedância do ramo respectivo.

Embora seja de quarta ordem, é simples de resolver, sendo reduzida em uma equação

de segunda ordem. Se as duas soluções são positivas, deve-se considerar o maior valor da

magnitude de tensão.



1.3 Método de Soma de Potências 24

Figura 8: Diagrama de blocos do algoritmo de fluxo de carga radial Soma de Potência.



25

2 Reconfiguração de Sistemas de

Distribuição Radiais

2.1 Introdução

Várias publicações têm tratado do assunto da reconfiguração de redes de distribuição.

Os algoritmos heuŕısticos e mais recentemente a aplicação de métodos de inteligência

artificial têm contribúıdo para a resolução do problema de forma cada vez mais eficiente.

Como já foi mencionado na categoria dos métodos baseados em conhecimentos estão

as heuŕısticas. Estas técnicas foram aplicadas à reconfiguração de redes através de duas

técnicas.

Primeiro, o método proposto por (MERLIN; BACK, 1975) e posteriormente modificado

por (SHIRMOHAMMADI; HONG, 1989), consiste em fechar todas as chaves de interconexão

obtendo uma rede malhada. Utilizando-se um fluxo de carga ótimo, começa-se abrindo

as chaves seccionadoras até obter novamente uma rede radial. Através deste processo

é constrúıdo um padrão de fluxo ótimo, para logo abrir o ramo que apresente o menor

fluxo de corrente, obtendo uma maior redução de perdas. Este algoritmo é melhorado por

Goswami e Basu (GOSWAMI; BASU, 1992). A técnica também utiliza um padrão de fluxo

ótimo, mas apenas fecha uma chave de interconexão formando um laço por vez e abre a

mesma chave ou outra chave seccionadora que pertence ao laço, de forma a tornar a rede

novamente radial.

Segundo, o método desenvolvido por (CINVANLAR; GRAINGER; LEE, 1988), posterior-

mente modificado por (BARAN; WU, 1989a), utiliza-se uma técnica baseada na troca de

ramos, mantendo a radialidade do sistema. Consiste em fechar uma chave de interconexão

formando um laço e procura-se uma chave que deve ser aberta. Este processo de busca

é realizado mediante duas regras heuŕısticas: (i) Quando se considera a abertura de uma

chave de interconexão é necessário transferir a carga, desde a barra com maior queda

de tensão até a barra com queda de tensão mais baixa; (ii) só é posśıvel uma redução



2.1 Introdução 26

de perdas, se existe uma diferença considerável de tensão entre as barras do ramo de

interconexão a fechar. Mediante este procedimento escolhem-se as opções que reduzem as

perdas, as quais são calculadas através de uma expressão matemática. De acordo com o

método empregado, realiza-se uma busca selecionando a opção de maior redução de per-

das e verificando-se as restrições, que cumpram estas, se por acaso cumpriram, o processo

se repete até não obter mais opções que reduzam as perdas.

Outro método baseado em conhecimento é a técnica de Lógica Nebulosa, que direcio-

na sua busca combinada com os métodos heuŕısticos. Para que o processo de busca seja

mais eficiente, definem-se os coeficientes que quantificam as regras heuŕısticas permitindo

orientar a busca. Esta técnica parte da uma rede malhada para logo tornar-se outra

malhada com menores perdas que as iniciais (LIN, 1998). Para isso, definem-se ı́ndices

calculados a partir de um fluxo de carga para rede malhada e dos parâmetros das linhas.

As decisões de abertura se dão nos ramos onde os ı́ndices de perdas nos componentes são

menores, o que ocorre entre as barras onde há pouca diferença de tensão entre as barras

e as impedâncias são grandes. Os ı́ndices utilizados são: ı́ndice de tensão, ı́ndice ôhmico,

fator de peso e decisão. Estes ı́ndices são calculados para cada malha formada no sistema.

O procedimento de abertura se inicia das malhas mais próximas à fonte, e se avaliam as

restrições de fluxo de carga; se são violadas, então se seleciona a seguinte chave com maior

fator de decisão até que as restrições não sejam violadas.

Em (LIU; LEE; VENKATA, 1988) a técnica utilizada para restauração de redes é baseada

em sistemas especialistas. Utilizando-se o conhecimento do operador da rede, se extrai

regras sobre as manobras que tendem a reduzir as perdas do sistema. Este método não

utiliza um fluxo de carga para verificar restrições; utiliza-se o sistema SCADA (Supervisory

Control And Data Acquisition) para ter informações das variáveis de tensão e corrente. Se

ao executar uma manobra o operador verifica que os limites das variáveis foram violados,

então desfaz a manobra, e de acordo com a base de conhecimento procede a realizar a

manobra seguinte.

As técnicas de Redes Neurais também foram utilizadas para o problema de recon-

figuração, selecionando estruturas definidas pelas redes neurais. Nos artigos estudados

por (BOUCHARD et al., 1993; KIM; KO; JUNG, 1993) são mencionadas as redes de Hopfield

e Perceptron multi-layer. Começa em uma determinada estrutura de rede, esta é treinada

com exemplos que se encontram dentro do algoritmo de aprendizagem, os quais permitem

encontrar fatores de peso de interconexão dos neurônios que logo utilizam-se para avaliar

as posśıveis soluções das reconfigurações. Este método não utiliza fluxo de carga para



2.1 Introdução 27

verificar as restrições porque não são modeladas as restrições do tipo operativo, desta

maneira a solução fornece configurações ótimas das chaves para minimizar perdas, mas,

não necessariamente pode ser implementada.

Outro algoritmo utilizado é Simulated Annealing, que consiste na simulação do pro-

cesso de solidificação de um metal. A técnica começa gerando aleatoriamente uma con-

figuração, esta tem que cumprir as restrições do tipo operativo (NARA; KITAGAWA, 1991).

A avaliação da função objetivo realiza-se através de um problema de fluxo de carga e

aplica-se o critério de aceitação que consiste, a partir de uma variação das perdas e da

temperatura, calcula um ı́ndice de probabilidade, que é comparado com um número gerado

aleatoriamente entre 0 e 1. Se o ı́ndice calculado é maior que o número gerado, aceita-se

a configuração proposta como a configuração inicial e gerando-se novas configurações até

que o parâmetro de controle da temperatura pare o processo. Se o ı́ndice é menor, volta-se

à configuração prévia e o processo é repetido até que cumpra o critério de parada. Ao

final do processo é posśıvel que se obtenha um mı́nimo global.

O algoritmo Busca Tabu também foi utilizado para resolver este problema. Desen-

volvido por (DUARTE, 1999; GUIMARÃES, 2005), e consiste no gerenciamento de um algo-

ritmo heuŕıstico de busca local, com a finalidade de sair dos ótimos locais, utiliza diversas

estratégias como proibir (tabu) temporariamente a visita em algumas soluções para evitar

a ciclagem. A Busca Tabu realiza uma série de transições através do espaço de busca e

as melhores soluções são armazenadas. A avaliação da qualidade das soluções geradas

é realizada utilizando ı́ndices como estabilidades de tensões e outros, que geram pouco

esfoço computacional.

Outra técnica utilizada para minimizar as perdas é o algoritmo Genético que é baseado

nos mecanismos de seleção e genética natural. Este processo inicia-se gerando um conjunto

de configurações que se denominam pais, os quais têm que cumprir com as restrições

de tipo operativo. Depois, avalia-se a função objetivo de cada uma das configurações

propostas. A partir destas geram-se cópias idênticas dos pais que tem uma redução maior

de perdas, isto com o fim de garantir que as configurações tenham maiores possibilidades

nas etapas seguintes (reprodução). Com novas cópias obtidas geram-se (recombinação)

novas soluções que se denominam filhos, também se avaliam as restrições operativas.

Ocasionalmente se modifica uma das soluções (mutação) para evitar laços e configurações

não radiais. O processo termina quando transcorrendo um número de transições não

se obtém melhores configurações. Um algoritmo Genético Modificado é proposto por

(ROMERO, 2001; LIN; CHENG; TSAY, 2000), em que uma nova forma de recombinação



2.2 Algoritmo Heuŕıstico de Cinvanlar (CINVANLAR; GRAINGER; LEE, 1988) 28

evita a geração de configurações não radiais. Os resultados obtidos são muito bons para

os sistemas testados.

Para aumento da margem de carregamento é proposto por (VENKATESH; RANJAN;

GOOI, 2004) um método que utiliza Lógica Fuzzy e um ı́ndice de estabilidade para avaliar

as configurações.

Outra técnica de reconfiguração é proposta por (KASHEM; GANAPATHY; JASMON,

2000) com o propósito de maximizar a margem de carregamento. É utilizado um ı́ndice

de estabilidade baseado nas equações Simplified Distflow, sendo apresentado também um

método para eliminar as configurações não fact́ıveis.

Para o desenvolvimento da Busca em Vizinhança Variável aplicado ao problema de

reconfiguração é necessário implementar um algoritmo heuŕıstico para gerar uma con-

figuração inicial, assim como avaliar configurações dentro do processo da busca através de

um técnica que utiliza pouco esforço computacional. Por estes motivos neste caṕıtulo são

estudados com detalhes os algoritmos heuŕısticos propostos por (CINVANLAR; GRAINGER;

LEE, 1988), (SHIRMOHAMMADI; HONG, 1989) e (GOSWAMI; BASU, 1992) para a resolução

do problema, tendo por objetivos a redução de perdas de potência ativa.

2.2 Algoritmo Heuŕıstico de Cinvanlar (CINVANLAR;

GRAINGER; LEE, 1988)

Apresentado por (CINVANLAR; GRAINGER; LEE, 1988) para resolver o problema de

reconfiguração da operação de sistemas de distribuição radiais. O problema pode ser

ilustrado através da Figura 9. Os ramos 14, 15 e 16 representam os ramos de interconexão

que normalmente estão abertos, assumindo-se que existem chaves seccionadoras em cada

ramo do sistema.

A carga da barra 9 pode ser transferida ao alimentador 1, fechando a chave de in-

terconexão 14 e abrindo a chave de secionamento 8. Similarmente as cargas das chaves

9, 7 e 10 podem ser transferidas ao alimentador 1, fechando a chave de interconexão

14 e abrindo a chave de secionamento 6. O método apresentado enfoca a discussão da

reconfiguração em redes de distribuição, fechando uma chave de interconexão e abrindo

uma chave seccionadora para preservar a radialidade da rede. O par combinado formado

por uma chave de interconexão e outra chave de seccionamento é chamada de opção de

chaveamento. Entretanto a aplicação sucessiva do esquema proposto poderia tratar de

múltiples operações de chaveamento.



2.2 Algoritmo Heuŕıstico de Cinvanlar (CINVANLAR; GRAINGER; LEE, 1988) 29

Pode-se verificar facilmente que existem 15 opções fact́ıveis de chaveamento. Note-se

que a melhor opção de chaveamento poderia encontrar-se simulando 15 estudos de fluxo

de carga para analisar todas as posśıveis configurações do sistema.

2

7

10

3
 9

6

8
 12

11

13

14
5

4

Alimentador 1

1

2

3

4

16
 13

12

10

11

15

7

5

6
14

9

Alimentador 2
 Alimentador 3

8

Figura 9: Sistema de três alimentadores.

2.2.1 Caracteŕısticas Desejáveis do Método de Solução

Esta técnica proporciona duas caracteŕısticas: (i) Capacidade de estimar com o

mı́nimo esforço computacional a mudança nas perdas resultantes da configuração do sis-

tema e, (ii) critérios que podem ser usados para eliminar propostas de reconfiguração

pouco interessantes, de forma a acelerar a convergência do processo de otimização.

A fórmula desenvolvida para o método para estimar as mudanças das perdas requer

pouca informação adicional, além da solução do fluxo de carga do caso base (isto é, antes

da reconfiguração do sistema). Além disso, a fórmula proposta sugere um mecanismo

de filtragem para eliminar aquelas opções de chaveamento que não produzem redução de

perdas.

O primeiro objetivo é deduzir uma expressão aproximada, para encontrar a redução

de perdas de potência através de uma transferência de carga, para determinar: (i) Se



2.2 Algoritmo Heuŕıstico de Cinvanlar (CINVANLAR; GRAINGER; LEE, 1988) 30

uma opção de chaveamento especificada resultaria num aumento ou redução de perdas e,

(ii) Entre as opções de chaveamento qual opção produziria a maior redução de perdas.

Em outras palavras, procura-se encontrar a melhor topologia sem necessidade de resolver

problemas de fluxo de carga adicionais.

2.2.2 Cálculo de Variação de Perdas

A variação de perdas resultante por transferir um grupo de cargas do alimentador 2

ao alimentador 1 pode ser estimada com a seguinte equação:

∆P = Re

{

2(
∑

i∈D

Ii)(Em − En)∗

}

+ Rloop

∣

∣

∣

∣

∣

∑

i∈D

Ii

∣

∣

∣

∣

∣

2

(2.1)

Sendo:

D - conjunto de barras que são desconectadas do alimentador 2 e conectadas ao alimen-

tador 1;

m - barras do alimentador 1 nas quais as cargas do alimentador 2 serão conectadas;

n - barras do alimentador 2 que serão conectadas a barra m através de uma chave de

interconexão;

Ii - corrente complexa na barra i;

Rloop - resistência série do ramo de conexão das duas barras de interconexão dos ali-

mentadores 1 e 2 através do fechamento da chave de interconexão especificada;

Em - componente de E = RbusIbus correspondente a barra m. Rbus, é a matriz de

resistência nodal do alimentador 1 antes da transferência de carga que é encontrada

usando a barra da subestação como referência. Ibus, é o vetor de correntes das barras

para o alimentador 1;

En - análogo a Em, porém definido para a barra n do alimentador 2;

Re, ∗, | |- parte real, conjugado complexo e valor absoluto, respectivamente.

Deve-se calcular Em e En usando as correntes Ii das barras do caso base antes da

transferência de carga. Sugere-se incorporar os efeitos dos capacitores nas correntes de

barras para facilitar a eficiência computacional. ∆P representa uma redução ( incremento)

em KW quando este é negativo (positivo).



2.2 Algoritmo Heuŕıstico de Cinvanlar (CINVANLAR; GRAINGER; LEE, 1988) 31

A redução de perdas pode ser obtida apenas se existe uma diferença de tensão entre

as barras de interconexão, esta observação pode ser usada como um critério interessante

para eliminar operações de chaveamento indesejáveis durante o processo de eliminação.

O algoritmo é apresentado na Figura 10 e os resultados obtidos para algumas redes de

distribuição são apresentados na Tabela 1.

Tabela 1: Resultados obtidos: algoritmo de Cinvanlar (CINVANLAR; GRAINGER; LEE,
1988).

Rede Conf. final Perda inicial Perda final Redução Melhor solução
(KW ) (KW ) (%) conhecida (KW )

14 8 7 16 511,41 466,11 8,52 466,11
32 7 11 14 36 37 202,68 143,41 29,24 139,55
69 11 21 15 56 65 20,68 11,14 53,86 9,34

Figura 10: Diagrama de blocos do algoritmo proposto por (CINVANLAR; GRAINGER;

LEE, 1988).



2.3 Algoritmo Heuŕıstico de Shirmohammadi (SHIRMOHAMMADI; HONG, 1989) 32

2.2.3 Comentários

Este algoritmo alcançou a configuração ótima global apenas no sistema de 14 barras,

por não possuir muitas alternativas para reconfigurar. Nos outros sistemas os valores

obtidos são de boa qualidade, estão próximos às melhores soluções conhecidas. Se o sistema

cresce, encontram-se valores das perdas mais distante dos melhores valores conhecidos.

2.3 Algoritmo Heuŕıstico de Shirmohammadi (SHIR-

MOHAMMADI; HONG, 1989)

Este algoritmo realiza reconfiguração de sistemas de distribuição radial, com a finali-

dade de reduzir as perdas ativas. É inicializado fechando-se todos os ramos, convertendo

ao sistema radial em um sistema malhado, para logo utilizar um fluxo de carga para redes

malhadas. Com esta informação monta-se um padrão de fluxo ótimo (PFO). O ramo que

tem menos corrente vai-se abrindo até que a rede se torne radial. Na Figura 11 é ilustrado

o algoritmo.

2.3.1 Procedimento para a Determinação do Padrão de Fluxo

Ótimo em uma Rede Malhada

O processo pode ser descrito da seguinte forma:

1. Resolver o fluxo de carga AC para a rede malhada e determinar as correntes nodais;

2. Converter a rede malhada em uma rede puramente resistiva desconsiderando os

componentes reativos da impedância de cada ramo;

3. Calcular as correntes pelos ramos da rede puramente resistiva para as injeções de

correntes nodais calculadas no passo 1;

4. Uma vez calculado o PFO, as chaves ainda fechadas, devem ser abertas considerando

o menor fluxo encontrado nos ramos.

A Tabela 2 apresenta os resultados obtidos para algumas redes de distribuição bastante

conhecidas na literatura.



2.3 Algoritmo Heuŕıstico de Shirmohammadi (SHIRMOHAMMADI; HONG, 1989) 33

Tabela 2: Resultados obtidos: algoritmo de Shirmohammadi (SHIRMOHAMMADI; HONG,
1989).

Rede Conf. final Perda Perda Redução Melhor solução
inicial final (%) conhecida
(KW ) (KW ) (KW )

14 8 7 16 511,41 466,11 8,52 466,11
32 7 14 11 28 32 202,68 141,35 12,57 139,55
69 14 56 62 70 71 20,68 9,35 54,78 9,34
135 7 9 53 84 90 96 106 320,28 282,48 11,80 280,14

118 126 128 138 139 140 141
144 145 147 148 150 151 156

Figura 11: Diagrama de blocos do algoritmo proposto por Shirmohammadi
(SHIRMOHAMMADI; HONG, 1989).

2.3.2 Comentários

Observando-se as respostas mostradas, podemos mencionar que o algoritmo não chegou

às configurações ótimas globais, exceto para o sistema de 14 barras, onde encontrou-se

o ótimo global. Estas configurações estão próximas aos melhores valores conhecidos. O



2.4 Algoritmo Heuŕıstico de Goswami - Basu (GOSWAMI; BASU, 1992) 34

fato de não chegar aos valores mı́nimos conhecidos é devido que as técnicas heuŕısticas

trabalham em uma estrutura de vizinhança, além de que o PFO é calculado considerando

condições que não correspondem às condições normais, como por exemplo, só considerar

a parte resistiva dos ramos.

2.4 Algoritmo Heuŕıstico de Goswami - Basu (GOSWAMI;

BASU, 1992)

No Padrão de Fluxo Ótimo (PFO) desenvolvido por (SHIRMOHAMMADI; HONG, 1989)

fecham-se todas as chaves de interconexão, estando este critério longe da realidade, já que

os sistemas de distribuição operam radialmente e apenas quando o último laço for aberto

podemos encontrar uma topologia que estaria perto da realidade. Então seria uma boa

alternativa considerar um laço por vez.

O método proposto por (GOSWAMI; BASU, 1992) utiliza o conceito de PFO, mas em

um único laço da rede. Dessa forma em vez de fechar todas as chaves da rede, para formar

uma rede com laços e abrir as chaves uma após a outra, se fecharia apenas uma chave por

vez para introduzir um laço no sistema, para logo abrir uma chave seccionadora do laço,

tornando-se novamente a rede radial.

Na Figura 12 pode-se observar um laço formado pelo fechamento da chave i - j. Para

manter a topologia da rede radial é necessário a abertura de uma das chaves pertencentes

ao laço.

2.4.1 Seleção da Chave Aberta que será Fechada

O algoritmo começa com uma solução de fluxo de carga para uma rede radial. A

chave de interconexão que fechará o laço, será selecionada baseando-se em três critérios

que são:

• Fechar a chave na qual a tensão é máxima (esperando que devido à maior diferença

de tensão o chaveamento cause a máxima redução de perdas);

• Fechar a chave na qual a tensão é mı́nima (esperando que devido à mı́nima diferença

de tensão uma solução modificada possa ser encontrada rapidamente);

• Selecionar a chave arbitrariamente, uma após a outra.



2.4 Algoritmo Heuŕıstico de Goswami - Basu (GOSWAMI; BASU, 1992) 35

k

q
2

q
1

q
o

i
 j

m

m
1

m
2

q
3
 m
3

m
4

m
5

IL
5
IL
4

q
5

q
4

Figura 12: Laço formado ao se fechar uma chave normalmente aberta

Estes três critérios proporcionam a mesma configuração final nos sistemas testados pelos

autores.

2.4.2 Determinação do Padrão de Fluxo Ótimo

Uma vez determinada a chave de interconexão a ser fechada, deve-se construir o

padrão de fluxo ótimo, que consiste em calcular os fluxos em todos os ramos que formam

o laço. Pode-se dividir o processo em dois passos:

• Usando os resultados encontrados para o fluxo de carga do sistema radial e através

de um processo iterativo do tipo forward e backward são calculadas as novas co-

rrentes dos ramos e as tensões dos nós que formam o laço. Em (GOSWAMI; BASU,

1992) são propostas três formas diferentes para calcular estes parâmetros, e todas

elas apresentam desempenhos equivalentes. Com estes resultados se recalculam as

correntes da operação injetadas em cada nó do laço.

• Este passo consiste em encontrar o padrão de fluxo ótimo através dos ramos do laço,

utilizando a primeira (KCL) e segunda (KCV) lei de Kirchhoff nos nós e no laço

respectivamente, considerando só a parte resistiva dos ramos do laço. Na Figura 13

IL1, IL2, ..., IL8 são as correntes injetadas pelos nós q2, q1, ..., m2 respectivamente.

Pode-se mencionar que existe uma corrente i2 através do ramo q2 − q1, que será a

soma da corrente que passa pelo ramo k − q2 mais a corrente IL1. Similarmente a



2.4 Algoritmo Heuŕıstico de Goswami - Basu (GOSWAMI; BASU, 1992) 36

corrente i2, i3, ..., i8, etc. que são as correntes através dos ramos laterais dos nós

mais as correntes IL2, IL3, etc. Para a Figura 13, o sistema pode ser resolvido

utilizando o sistema de eqs. (2.2).

k

q
2

q
1

q
o

i
 j

m

m
1

m
2

R
2

i
1

R
1
R
9

R
8

R
7

R
6

R
5

R
4

R
3

i
5
i
4

i
6

i
7

i
8

i
9

i
3

i
2

IL
1
 IL
8

IL
7

IL
6

IL
5
IL
4

IL
3

IL
2

Figura 13: Laço formado para determinar o PFO.

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

R1 R2 R3 R4 R5 R6 R7 R8 R9

1 −1 0 0 0 0 0 0 0

0 1 −1 0 0 0 0 0 0

0 0 1 −1 0 0 0 0 0

0 0 0 1 −1 0 0 0 0

0 0 0 0 1 −1 0 0 0

0 0 0 0 0 1 −1 0 0

0 0 0 0 0 0 1 −1 0

0 0 0 0 0 0 0 1 −1

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

.

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

i1

i2

i3

i4

i5

i6

i7

i8

i9

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

=

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

0

IL1

IL2

IL3

IL4

IL5

IL6

IL7

IL8

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

∣

(2.2)

Onde i1, i2, ..., i9, formam o padrão de fluxo ótimo e se abre o ramo que apresenta

menor valor no qual o fluxo é mı́nimo, restaurando a rede numa configuração radial. O

algoritmo é ilustrado na Figura 14, assim como os resultados obtidos em algumas redes

de distribuição na Tabela 3.



2.4 Algoritmo Heuŕıstico de Goswami - Basu (GOSWAMI; BASU, 1992) 37

Figura 14: Diagrama de blocos do algoritmo proposto por (GOSWAMI; BASU, 1992).

Tabela 3: Resultados obtidos: algoritmo Goswami e Basu (GOSWAMI; BASU, 1992).
Rede Conf. final Perda Perda Redução Melhor solução

inicial final (%) conhecida
(KW ) (KW ) (KW )

14 8 7 16 511,41 466,11 8,52 466,11
32 7 14 11 28 32 202,68 141,35 12,57 139,55
69 14 59 62 70 71 20,68 9,35 54,77 9,34
135 7 51 53 84 90 106 118 320,28 280,87 12,30 280,14

126 128 137 138 139 141 144
145 147 148 150 151 152 156

2.4.3 Comentários

Para o sistema de 135 barras o resultado obtido é melhor que o adquirido pelo al-

goritmo (SHIRMOHAMMADI; HONG, 1989). Estão muito próximos aos melhores valores

conhecidos, porque as condições de análise estão mais próximas à realidade que as dos

demais algoritmos apresentados, assim como a simplicidade e eficiência computacional são

uma vantagem.



38

3 Busca em Vizinhança Variável

3.1 Conceitos Básicos

A Busca em Vizinhança Variável (VNS) é uma metaheŕıstica proposta por (MLADE-

NOVIC, 1995). Esta técnica tem demonstrado ser uma técnica muito eficiente e de fácil

aplicação em muitos problemas de otimização.

Um problema de otimização consiste em encontrar, dentro de um conjunto S de

soluções, uma solução que represente o melhor valor da função objetivo. Em geral pode-

se definir este problema do tipo:

min f(x)

s.a. x ∈ S

Onde x representa uma solução alternativa, f é a função objetivo e S o espaço de

soluções fact́ıveis do problema.

Defina-se um ponto x∗ ∈ S para o qual existe uma vizinhança N(x), tal que, x∗ é

ótimo nessa vizinhança (ótimo local). Então o ótimo global pode ser obtido examinando

todos os ótimos locais, e aquele que apresente melhor valor da função objetivo fica como

ótimo global. Na reconfiguração de redes será aquela configuração que apresente menor

perda de potência ativa.

A partir deste conceito é posśıvel definir a vizinhança para o problema de recon-

figuração: Seja um problema de reconfiguração (S, f). Uma estrutura de vizinhança é

uma função N : S → 2S = {X/X ⊆ S} que associa a cada solução x ∈ S um conjunto de

configurações próximas de x, tais que cada y será uma solução vizinha de x.

Como esta definição é muito geral, se deverá definir quando duas soluções estão

próximas. Para o caso da reconfiguração definimos que duas configurações estão mais

próximas, quanto menos ramos ativos da rede são diferentes. A partir dessa dedução

podemos especificar uma distância r definida sobre o espaço fact́ıvel S, r : S x S → ℜ,



3.1 Conceitos Básicos 39

que permitirá avaliar a distância existente entre duas configurações quaisquer de S, como

ilustra a Figura 18, que será generalizada mais adiante.

A eleição da estrutura de vizinhança é fundamental no processo de busca, já que

determina a qualidade do conjunto de movimentos aplicados. Uma adequada alteração

de parâmetros ou mudanças enriquecem as vizinhanças, com isso é posśıvel realizar passos

mais longos na aproximação ao ótimo.

Outra caracteŕıstica importante das mudanças é a factibilidade das soluções avali-

adas. No caso do problema da reconfiguração deverá considerar-se só mudanças fact́ıveis,

porque o tamanho do espaço geral (fact́ıveis e infact́ıveis) é muito maior ao espaço restrito

(fact́ıveis) e o número de transições seria não viável.

Existem outras questões relevantes no êxito da busca em vizinhança, além da seleção

da própria estrutura de vizinhança e sobre como articular a busca, questões importantes

como: a avaliação da função objetivo, o procedimento de gerar a solução inicial e o critério

de parada.

3.1.1 Metaheuŕıstica de Busca

A metaheuŕıstica de busca monta estratégias para resolver de forma mais eficiente um

problema, desenvolvendo uma busca sobre um espaço de configurações, onde os elementos

deste espaço representam soluções candidatas alternativas.

Para guiar a busca dentro do processo de otimização existe: (i) Buscas informadas,

que usam informação obtida no processo de otimização e, (ii) buscas não informadas, que

só têm em conta a estrutura de vizinhança.

O Busca em Vizinhança Variável utiliza buscas não informadas, assim também im-

plementa estratégias para organizar a exploração eficiente dentro do espaço de busca.

Traduzindo-se numa busca em vizinhança exaustiva, parcial e aleatória, que são as mais

usadas.

3.1.2 Buscas Locais e Globais

Um dos procedimentos que utiliza as heuŕısticas para resolver os problemas de otimização

combinatória é a busca local, que caracteriza-se por realizar uma série de mudanças no

espaço de soluções, melhorando em cada uma delas o valor da função objetivo. O algo-

ritmo é ilustrado na Figura 15.



3.1 Conceitos Básicos 40

Figura 15: Diagrama de blocos do algoritmo busca local.

O principal inconveniente das buscas locais é que se aproximam a uma solução lo-

calmente ótima ou ótimo local (uma configuração que é melhor que qualquer da sua

vizinhança) e a solução atual fica presa em sua vizinhança (AARTS; LENSTRA, 1997;

YAGIURA; IBARAKI, 2002). Então surgem três principais formas de sair desta situação:

- Voltar e começar a busca a partir de outra solução inicial;

- Permitir movimentos de deterioração da solução atual;

- Modificar a estrutura de vizinhança.

A primeira forma é conhecida como busca local com arranque múltiplo. É adequada

naqueles casos em que os ótimos locais se distribuem aleatoriamente no espaço de soluções.

Isto nem sempre acontece, já que em muitos casos se observa que os ótimos locais tendem-

se concentrar em pequenas regiões no espaço de soluções, o que dificulta a obtenção

da solução ótima. A Figura 16 ilustra o quanto complicado seria obter o ótimo global

utilizando uma busca local com arranque múltiplo já que teria que gerar uma grande

quantidade de soluções aleatórias.

A segunda forma para sair do ótimo local, seria permitir movimentos de deterioração

da função. Este procedimento dependendo da estratégia ficaria numa só região ou cami-

nharia a passos longos. Portanto seria dif́ıcil encontrar a solução ótima global.



3.2 Escolha da Configuração Inicial 41

 Solução aleatória

   Mínimo  global

 Mínimo  local

Busca local

Figura 16: Busca local com arranques múltiples.

Nos últimos anos foram propostas muitas metaheuŕısticas, com o objetivo de melhorar

o algoritmo da busca local, evitando que o procedimento fique preso numa busca local.

Sendo os mais conhecidos Simulated Annealing e Busca Tabu.

A Busca em Vizinhança Variável utiliza a técnica de sair dos ótimos locais mudando

de estrutura em vizinhança, que será mais adiante generalizada.

3.2 Escolha da Configuração Inicial

A estratégia da escolha da configuração inicial é de grande importância para um bom

desempenho do algoritmo. Por ser este um algoritmo com ênfase na aleatoriedade (o

caminho de busca não é direcionado), uma configuração inicial de boa qualidade pode en-

contrar de maneira mais rápida a configuração ótima ou quase ótima procurada. Quando

o algoritmo é iniciado com uma configuração de boa qualidade, a configuração ótima

é encontrada com menor esforço computacional. No entanto deve-se levar em conta o

acréscimo de esforço computacional devido ao uso de um algoritmo para essa finalidade.

3.3 Representação e Codificação do Problema

Será analisado a seguir o problema de reconfiguração de redes de distribuição de

energia elétrica e o processo utilizado em sua codificação. Os sistemas estudados neste

trabalho possuem as seguintes caracteŕısticas:

• Supõe-se que tem uma chave em cada ramal da rede, exceto quando indicado em

contrário;



3.3 Representação e Codificação do Problema 42

• Além das chaves existentes nos ramos, existem as chaves de interconexão que per-

mitem alterar a topologia da rede;

• O comando para a abertura das chaves é realizado através de um vetor (ch), que

indica sempre as chaves que deverão ser abertas e, portanto, todas as outras estarão

fechadas;

Observa-se na Figura 17 um exemplo de uma rede de distribuição radial bastante conhe-

cida na literatura (CINVANLAR; GRAINGER; LEE, 1988). Pode-se observar que as chaves

14, 15 e 16 são de interconexão e, na configuração inicial encontram-se abertas.

2

7

10

3
 9

6

8
 12

11

13

14
5

4

Alimentador 1

1

2

3

4

16
 13

12

10

11

15

7

5

6
14

9

Alimentador 2
 Alimentador 3

8

Figura 17: Sistema de 14 barras

Pode-se codificar a rede da seguinte forma:

1
sch
  =

1

1

2

1

3

1

4

1

5

1

6

1

7

1

8

1

9

1

10

1

11

1

12

1

13

0

14

0

15

0

16

O vetor sch é usado internamente para identificar quais chaves estão abertas e quais

estão fechadas. Este método de codificação é eficiente porque é posśıvel controlar facil-

mente a topologia da rede, pois se uma chave de interconexão é fechada, formara-se um

laço, sendo que para tornar a rede novamente radial, é necessário abrir uma chave no

ramo pertencente a esse laço.

Exemplo: Com o fechamento da chave número 14, um laço será formado pelas

seguintes chaves: 1, 2, 5, 6, 8 e 14 e o vetor sch é representado da seguinte forma:



3.4 Estruturas de Vizinhanças 43

1
sch
  =

1

1

2

1

3

1

4

1

5

1

6

1

7

1

8

1

9

1

10

1

11

1

12

1

13

1

14

0

15

0

16

Para a rede voltar a ser radial deve-se escolher e abrir uma das chaves pertencente

ao laço em questão. Como visto, a codificação interna do programa usa vetor binário

para representar o “status” das chaves. No entanto, para o comando de quais chaves

serão abertas ou fechadas, adota-se um vetor de variáveis inteiras onde são representadas

apenas as chaves a serem abertas em cada configuração. Esse vetor é denominado ch

como mostrado a seguir:

1
sch
  =

1

1

2

1

3

1

4

1

5

1

6

0

7

0

8

1

9

1

10

1

11

1

12

1

13

1

14

1

15

0

16

ch = [ 7 8 16 ]

Como se pode observar, o vetor ch representa as chaves abertas da rede, e assim sendo,

só poderão haver 3 chaves abertas simultaneamente para esse caso. O método utilizado

permitiu a simplificação do comando dos problemas de fluxo de carga, não sendo necessário

utilizar-se vetores binários, de dimensão proporcional ao número total de chaves da rede.

3.4 Estruturas de Vizinhanças

Uma das etapas importantes desta técnica é a construção das estruturas de vizinhança,

que são definidas para resolver problemas combinatórios e cont́ınuos a partir de uma

distância definida sobre o espaço de soluções fact́ıveis S.

Como já foi mencionado, podemos especificar um parâmetro r, definido sobre o espaço

fact́ıvel S, r : S x S → ℜ, que permite avaliar a distância existente entre duas con-

figurações quaisquer de S, como ilustra na Figura 18.

Desta maneira podem ser geradas as seguintes estruturas de vizinhanças, induzidas a

partir de r para uma solução quaisquer:

Nk(x) = {y ∈ S : r(x, y) = k}, k = 1, 2, ..., n

Numa rede, consideram-se Is as chaves seccionadoras e It as chaves de interconexão.

É definido um espaço de configurações chamado Ω = Ω1 ∪ Ω2, sendo Ω1 = (s1, s2, ..., si)



3.4 Estruturas de Vizinhanças 44

Figura 18: Vizinhanças induzidas.

e Ω2 = (t1, t2, ..., ti), onde si (ou ti) representa o estado da chave seccionadora ( ou da

chave de interconexão ) i. Assume-se que si = 1, se a chave seccionadora estiver fechada e

si = 0, se estiver aberta. A mesma convenção é utilizada para as chaves de interconexão.

A vantagem de utilizar várias estruturas de vizinhança, se baseia no prinćıpio que,

um ótimo local para uma determinada estrutura de vizinhança, não tem porque ser para

outra, portanto o processo de busca deverá continuar, até obter uma solução ótima que

seja ótimo local para todas as estruturas.

3.4.1 Geração das Estruturas de Vizinhanças

Em geral as estruturas de vizinhanças podem ser obtidas, utilizando diferentes métricas

ou distâncias introduzidas no espaço de soluções fact́ıveis S. Pode-se gerar utilizando as

seguintes estratégias de seleção:

1. Seleção de Heuŕısticas Existentes:

Para o problema de reconfiguração de redes de distribuição existem algumas heuŕısticas

desenvolvidas (CINVANLAR; GRAINGER; LEE, 1988; BARAN; WU, 1989a; SHIRMO-

HAMMADI; HONG, 1989; GOSWAMI; BASU, 1992). Foram testadas fazendo uma com-

binação destas, chegando numa solução próxima a solução ótima global.

2. Troca de Parâmetros dos Métodos Existentes:



3.4 Estruturas de Vizinhanças 45

Algumas heuŕısticas baseadas nas buscas locais (GOSWAMI; BASU, 1992), se caracte-

rizam por utilizar vizinhanças com tamanho dependente de uma série de parâmetros,

onde estes são escolhidos antes de executar o algoritmo. Em lugar de fixá-los

podeŕıamos ir mudando sistematicamente seus valores dentro de limites razoáveis,

ou seja, utilizando um padrão de fluxo ótimo (PFO), abrindo do laço a chave do

primeiro elemento da lista padrão numa primeira estrutura de vizinhança, em uma

segunda a chave do segundo elemento da lista padrão, obtendo assim um conjunto

de estruturas de vizinhança que poderão utilizar-se num esquema da Busca em

Vizinhança Variável. Este esquema de mudar os parâmetros preestabelecidos foi

utilizado inicialmente para resolver o problema do caixeiro viajante (MLADENOVIC.;

HANSEN, 1997).

Esta estratégia apresentou melhores resultados que utilizando só técnicas heuŕısticas,

mas não chegou a obter valores ótimos.

3. Uso de k-intercâmbios:

É a maneira mais fácil e natural de obter as estruturas de vizinhanças, fechando

k chaves de interconexão e abrindo k chaves de seccionamento (ou interconexão),

mantendo a restrição de radialidade. Este mecanismo funciona de forma eficiente

e apresenta os melhores resultados com mı́nimas perdas. Muitos problemas foram

resolvidos, como por exemplo a ρ - mediana (HANSEN; MLADENOVIC, 1997) com

esta estratégia de geração de vizinhanças.

4. Divisão de vizinhanças:

Outra possibilidade é dividir uma determinada vizinhança em várias sub-vizinhanças

menores, gerando sub-estruturas de vizinhança. Desta forma se examinam várias

sub-vizinhanças em lugar de toda a vizinhança.

3.4.2 Geração de Estruturas de Vizinhanças Através de k-inter-
câmbios

Esta estratégia consiste numa (adição/subtração) proposta em (CHIANG; JEAN-JUMEAU,

1990). A técnica de construir estruturas de vizinhança é obtida mudando sistematica-

mente as chaves de interconexão e chaves de seccionamento.

Para gerar uma estrutura de vizinhança Nk(x), se fecham k chaves (t1, t2, .., tk) do

conjunto de chaves de interconexão Ω2 e se abrem k chaves (s1, s2, .., sk) do conjunto de

chaves de seccionamento Ω2, para que a rede volte a ser radial, como ilustra a Figura 19.



3.4 Estruturas de Vizinhanças 46

2

7

10

3
 9

6

8
 12

11

13

14
5

4

Alimentador 1

1

2

3

4

16
 13

12

10

11

15

7

5

6
14

9

Alimentador 2
 Alimentador 3

8

laço 1

2

7

10

3
 9

6

8
 12

11

13

14
5

4

Alimentador 1

1

2

3

4

16
 13

12

10

11

15

7

5

6
14

9

Alimentador 2
 Alimentador 3

8

2

7

10

3
 9

6

8
 12

11

13

14
5

4

Alimentador 1

1

2

3

4

16
 13

12

10

11

15

7

5

6
14

9

Alimentador 2
 Alimentador 3

8

laço 1
laço 2

2

7

10

3
 9

6

8
 12

11

13

14
5

4

Alimentador 1

1

2

3

4

16
 13

12

10

11

15

7

5

6
14

9

Alimentador 2
 Alimentador 3

8

2

7

10

3
 9

6

8
 12

11

13

14
5

4

Alimentador 1

1

2

3

4

16
 13

12

10

11

15

7

5

6
14

9

Alimentador 2
 Alimentador 3

8

laço 1
 laço 2

laço 3
 laço 3

2

7

10

3
 9

6

8
 12

11

13

14
5

4

Alimentador 1

1

2

3

4

16
 13

12

10

11

15

7

5

6
14

9

Alimentador 2
 Alimentador 3

8

Figura 19: Geração de estruturas de vizinhança através de k-intercâmbios.



3.5 Estratégia de Busca e Mudança de Vizinhança 47

3.4.3 Ordenação das Estruturas de Vizinhança

Uma ordenação natural das estruturas de vizinhança se obtém aumentando a distância

(r) existente entre a solução da configuração atual x e outra configuração com solução

y, em outras palavras quando abrimos e fechamos chaves, o maior número de chaves

fechadas e abertas ao mesmo tempo incrementará a distância r, e estaremos mais dis-

tante da solução atual. Também cumpre-se que as estruturas vão desde aquela que tem

menos soluções vizinhas fact́ıveis até aquela que contém maior número delas ou seja

| N1(x) | ≤ | N2(x) | ≤, ...,≤ | Nkmax(x) |.

3.5 Estratégia de Busca e Mudança de Vizinhança

As diversas estratégias utilizadas no processo de busca e mudança de estrutura em

vizinhança, têm a finalidade de intensificar a busca naquelas regiões mais atrativas, onde

se espera ter boas soluções, além de explorar a maior quantidade de zonas (diversificar)

para evitar que o processo de busca se concentre numa determinada região do espaço de

busca, portanto, deve-se considerar as seguintes estratégias:

• Estratégia I (EI): No campo de otimização operacional é conhecida como busca

gulosa, ou busca do melhor. Se realiza uma busca exaustiva, transitando por todas

as configurações da vizinhança da solução atual, encontrando a topologia vizinha de

melhor qualidade. Esta estratégia será referenciada como: Estratégia I (EI).

• Estratégia II (EII): Conhecida como busca do primeiro melhor. Se caracteriza em

transitar pelas configurações da vizinhança, até que se encontre a primeira con-

figuração de melhor qualidade que a configuração corrente. Esta estratégia será

referenciada como: Estratégia II (EII).

Como temos duas fases importantes, primeiro, quando se produz a troca da estrutura

de vizinhança (segundo ńıvel de decisão), e segundo, quando se visitam diferentes soluções

de uma mesma estrutura de vizinhança (primeiro ńıvel de decisão), portanto se poderia

combinar estas duas estratégias obtendo quatro possibilidades:

1. Primeiro e segundo ńıveis de decisão, (EI);

2. Primeiro e segundo ńıveis de decisão, (EII);



3.5 Estratégia de Busca e Mudança de Vizinhança 48

3. Primeiro ńıvel de decisão, (EI), e segundo ńıvel de decisão, (EII);

4. Primeiro ńıvel de decisão, (EII) e segundo ńıvel de decisão, (EI);

Considiram-se a segunda e a quarta possibilidade já que os esforços computacionais

para encontrar a solução final são menores que os das demais. A primeira possibilidade

será referenciada como VNS, e a terceira possibilidade como VND.

Outra possibilidade seria, uma busca aleatória para o segundo ńıvel de decisão, ou

seja, gerar aleatoriamente uma configuração numa estrutura de vizinhança para logo fazer

a busca local, esta estratégia encontra as soluções com mı́nimas perdas em tempos com-

putacionais extremamente demorados.

A ordem em que se alteram as estruturas de vizinhanças Nk(x) é muito importante

para obter uma solução final de boa qualidade.

As possibilidades de explorar as estruturas serão:

1. Explorar de forma sistemática incrementando o valor de k (forward), ou seja começar

com k = 1 (forward) e quando não for posśıvel melhorar em Nk(x) a função obje-

tivo, fazer k = k + 1, reinicializar com k = 1 caso encontrar uma melhor solução.

Esta estratégia encontrou os melhores resultados. Os algoritmos são ilustrados nas

Figuras 20 e 21 para o VNS e VND respectivamente.

2. Explorar em sentido contrário com k = kmax (backward) diminuindo (k = k −

1), no caso que se encontre uma melhor solução se volta para (k = kmax). Esta

estratégia é viável na reconfiguração quando o número dos ramos de interconexão é

grande, por outro lado a implementação computacional se faz mais dificultosa em

relação ao forward, além de que as melhores configurações (com mı́nimas perdas)

são encontradas na segunda estrutura de vizinhança.

3. Explorar ambos sentidos (forward ou backward) utilizando parâmetros kmin e kstep

para controlar as mudanças nas estruturas em vizinhanças. Esta estratégia é ade-

quada quando a rede é de grande porte, para os sistemas testados não foi necessária

a implementação desta estratégia.



3.6 Critério de Parada 49

Figura 20: Diagrama de blocos utilizando a busca EII em todas as estruturas de
vizinhança (VNS).

3.6 Critério de Parada

O critério de parada determina quando se considera o problema resolvido, para isso

deve-se considerar alguns indicadores de qualidade, que são:

- Limite de número de iterações ou trocas;

- Esforço computacional total;



3.6 Critério de Parada 50

Figura 21: Diagrama de blocos utilizando a busca EII para a primeira estrutura de
vizinhança e busca EI nas outras estruturas de vizinhança.



3.7 Redução da Vizinhança 51

- Tempo computacional sem que se produza uma melhora da incumbente.

Para a reconfiguração o indicador adequado foi o número de transições que não se

produz uma melhora entre as configurações analisadas e a incumbente (melhor solução

encontrada), isto se reflete no esforço computacional.

3.7 Redução da Vizinhança

3.7.1 Estratégias de Exploração

Um critério rudimentar para explorar a vizinhança de uma determinada estrutura, se-

ria transitar e considerar uma ordenação impĺıcita ou expĺıcita de todas as configurações

do espaço fact́ıvel nessa estrutura Nk(x), evitando as repetições para impedir que o pro-

cesso de busca não se torne indefinidamente ćıclico . Esta estratégia de exploração poderá

ser utilizada para redes de pequeno porte. Quando a rede vai crescendo este critério se

torna inviável.

Entretanto é necessário aplicar estratégias de exploração nas estruturas de vizinhança.

Pode-se fazer a exploração aplicando duas estratégias de exploração:

• Parcial: Consiste em explorar somente parte do espaço de busca, para se ter uma

visão de todo o espaço. Para isso se estabelecem critérios de probabilidade de como

organizar a seleção de abertura e fechamento das chaves de interconexão e seccio-

nadoras que participaram das trocas. Para a reconfiguração são naquelas chaves

dos ramos que têm maior probabilidade de abrir depois de fechar as chaves de

interconexão.

• Aleatória: Consiste em explorar as configurações do espaço fact́ıvel S de cada es-

trutura de vizinhança Nk(x) aleatoriamente. Trata-se de uma exploração quando o

espaço é uniforme, ou seja, a distribuição de probabilidades de abrir ou fechar uma

chave tem igual probabilidade, além desta estratégia pode-se intensificar a busca

naquelas regiões promissoras.

3.7.2 Estratégia Utilizada

Para a redução da vizinhança aplica-se uma combinação de busca parcial e aleatória

para o primeiro e segundo ńıvel de decisão (busca e mudança de estrutura em vizinhança).



3.7 Redução da Vizinhança 52

Esta estratégia é conhecida como método de Monte Carlo (MELIAN; MORENO; MORENO,

2003).

Primeiro Ńıvel de Decisão: Tem-se duas estratégias:

a) Fechando uma chave de interconexão tk, se criará um laço na rede anteriormente

denotado como lk. Escolhe-se aleatoriamente uma chave de seccionamento (para

voltar a radialidade da rede) dentro deste espaço (laço), este conjunto de chaves

serão ordenadas aleatoriamente, e só em torno de 60% do número de chaves parti-

ciparão das trocas. Este valor foi determinado experimentalmente. Esta estratégia

foi implementada inicialmente;

b) O algoritmo de Goswami - Basu (GOSWAMI; BASU, 1992) realiza a configuração

de uma rede de distribuição utilizando um ı́ndice de sensibilidade denominado PFO

(Padrão de Fluxo Ótimo) detalhado no caṕıtulo 2. O grupo de chaves (configurações

vizinhas) a serem abertas dentro do laço formado serão só aquelas classificadas den-

tro do PFO. Esses vizinhos são escolhidos aleatoriemente considerando 40% dos

primeiros elementos (chaves) do PFO. Também este valor foi determinado experi-

mentalmente.

Nos dois métodos testados conseguiu-se encontrar a configuração ótima para os sis-

temas testados, sendo que para o primeiro caso foi necessário um número maior de itera-

ções. Isso se deve ao fato da qualidade dos vizinhos considerados no segundo caso serem de

melhor qualidade, proporcionando uma rápida convergência até alcançar as configurações

ótimas. Nas Figuras 22 e 23 são mostrados os algoritmos utilizados com estas estratégias.

Segundo Ńıvel de Decisão: Tem-se o grupo de chaves de interconexão que são fechadas

de acordo com a estrutura de vizinhança. Similarmente à estratégia utilizada no primeiro

ńıvel de decisão, as chaves a serem abertas são ordenadas aleatoriamente através dos PFO.

O grupo de chaves (configurações vizinhas) a serem abertas são escolhidas aleatorimente

considerando 20% dos primeiros elementos (chaves) das listas PFO. Também este valor

foi determinado experimentalmente.

Como já foi mencionado para os sistemas testados, as soluções ótimas foram encon-

tradas na segunda estrutura de vizinhança.

Nas Figuras 22 e 23 são mostrados os algoritmos utilizados com esta estratégia.



3.8 Implementação dos Algoritmos VNS e VND 53

Figura 22: Diagrama de blocos - algoritmo utilizando estratégia Parcial - Aleatória -
PFO no processo de busca (VNS).

3.8 Implementação dos Algoritmos VNS e VND

Foram implementados dois algoritmo VNS e VND com estratégias de busca local

bem definidas, utilizando um algoritmo heuŕıstico proposto por (GOSWAMI; BASU, 1992)

combinada com uma busca parcial-aleatória nas estruturas de vizinhança, além de uma

mudança de estrutura sistemática.

O ambiente de desenvolvimento foi o Matlab 6.0. Neste trabalho foi abordada a

resolução do problema de reconfiguração de redes de distribuição de energia elétrica,

objetivando a minimização das perdas. Observou-se que a maior parte do esforço com-



3.8 Implementação dos Algoritmos VNS e VND 54

Figura 23: Diagrama de blocos - algoritmo utilizando estratégia Parcial - Aleatória -
PFO no processo de busca (VND).

putacional do algoritmo deve-se ao cálculo de fluxo de carga, essencial para a avaliação

das configurações candidatas.

Neste trabalho o fluxo de carga utilizado foi o método de Varredura apresentado no

caṕıtulo 1 para a avaliação das configurações, embora possa ser utilizado qualquer rotina

de fluxo de carga que seja muito rápida para essa função.



3.8 Implementação dos Algoritmos VNS e VND 55

3.8.1 Descrição do Algoritmo Implementado para Minimização
de Perdas

A formulação do problema de perdas pode ser escrita como (LIN; CHENG; TSAY, 2000):

minf =
nr

∑

i=1

ri

P 2
i + Q2

i

| V 2
i |

s.a. G(x, u) = 0

V i
min ≤ Vi ≤ V i

max

Topologia radial

Pi : fluxo de potência ativa do ramo i;

Qi : fluxo de potência reativa do ramo i;

Vi, V
i
min, V

i
max : tensão, tensão mı́nima e máxima respectivamente na barra i;

nr : número de ramos de rede;

ri : resistência do ramo i.

G(x, u) : variáveis do algoritmo de fluxo de carga.

De forma adicional a topologia da rede deve ser sempre radial.

Com todas as informações fornecidas até aqúı, é posśıvel desenvolver os algoritmos

VNS e VND para a resolução do problema. Nas Figuras 24 e 25 estaõ ilustradas os

diagramas de blocos dos algoritmos desenvolvidos.

O algoritmo inicializa-se com uma configuração fact́ıvel (cumpra com todas as res-

trições) qualquer ou por uma configuração de boa qualidade gerada por um algoritmo

heuŕıstico. A vantagem de utilizar-se uma configuração inicial de boa qualidade nos

testes feitos, é a redução do número de iterações necessárias para o algoritmo encontre

as melhores soluções conhecidas. A desvantagem é o aumento do esforço computacional

total do algoritmo, e que deve ser tomado em conta nesse caso. Para ilustração desta

metodologia foi usado para os dois casos o sistema de 135 barras. Os resultados encontram-

se na Tabela 5, para o caso de uma configuração inicial qualquer, e na Tabela 7, para

uma configuração inicial de boa qualidade gerado por um algoritmo heuŕıstico.

Foi utilizado nesse caso o algoritmo de Goswami e Basu (GOSWAMI; BASU, 1992) para

a geração de uma solução inicial de boa qualidade. A Tabela 4 apresenta a configuração



3.8 Implementação dos Algoritmos VNS e VND 56

inicial com o valor das perdas, e a Tabela 6 apresenta a configuração inicial após a

aplicação do algoritmo de Goswami e Basu .

Tabela 4: Parâmetros do algoritmo para a rede de 135 barras utilizando uma
configuração inicial de operação.

Conf. inicial Perda inicial (KW )
136 137 138 139 140 141 142 143 144 145 146 320,28

147 148 149 150 151 152 153 154 155 156

Tabela 5: Resultados obtidos sistema de 135 barras usando uma configuração inicial de
operação.

Conf. final Perda final (KW ) Red.(%)
7 51 53 84 90 96 106 118 126 128 137 280,166 12,523

138 139 141 144 145 147 148 150 151 156
7 38 51 53 84 90 96 106 118 126 128 280,281 12,487

137 138 141 144 145 147 148 150 151 156
7 49 51 53 84 90 96 106 118 126 128 280,303 12,481

137 138 139 144 145 147 148 150 151 156
7 51 53 84 90 106 118 126 128 137 138 280,875 12,302

139 141 144 145 147 148 150 151 152 156
7 51 53 95 106 120 126 137 138 139 141 282,428 11,817

144 145 146 147 148 149 150 151 155 156

Tabela 6: Parâmetros do algoritmo para a rede de 135 barras usando o algoritmo de
Goswami e Basu.

Conf. inicial Perda inicial (KW )
7 51 53 84 90 106 118 126 128 137 138 280,870

139 141 144 145 147 148 150 151 152 156

Tabela 7: Resultados obtidos sistema de 135 barras usando uma configuração inicial
obtida pelo algoritmo de Goswami e Basu.

Conf. final Perda final (KW ) Red.(%)
7 35 51 90 96 106 118 126 135 137 138 280,138 12,532

141 142 144 145 146 147 148 150 151 155
7 51 53 84 90 96 106 118 126 128 137 280,166 12,523

138 139 141 144 145 147 148 150 151 156
7 38 51 53 90 96 106 118 126 137 138 280,243 12,500

141 144 145 146 147 148 150 151 155 156

7 38 51 53 84 90 96 106 118 126 128 280,281 12,487
137 138 141 144 145 147 148 150 151 156

7 49 51 53 84 90 96 106 118 126 128 280,303 12,481
137 138 139 144 145 147 148 150 151 156



3.8 Implementação dos Algoritmos VNS e VND 57

Uma vez definida a configuração inicial e inicializada todas as variáveis necessárias

para o funcionamento do algoritmo, realiza-se uma busca local, ou seja, geram-se todos os

vizinhos desta configuração dentro da sua estrutura de vizinhança, adotando as estratégias

já apresentadas.

No algoritmo desenvolvido os vizinhos para a busca local são gerados fechando chaves

de interconexão e abrindo o mesmo número de chaves de seccionamento (ou interconexão)

que formam os laços.

Numa primeira estrutura de vizinhança, fecha-se uma chave de interconexão qualquer,

e depois abre-se a primeira chave do vetor de elementos do PFO, que são ordenados

aleatoriamente. Para esta estratégia deve-se avaliar apenas 40% do número de elementos

do vetor PFO, com a finalidade de reduzir o número de vizinhos. Cada um destes valores

é comparado com a incumbente (melhor solução encontrada). Se a solução é a de melhor

qualidade, então, esta será a nova solução atual, e a nova busca deve ser reiniciada.

A outra possibilidade acontece quando, não se encontra uma melhor solução durante o

fechamento aleatório de n/3 chaves de interconexão, onde n é o número de chaves de

interconexão, então, se passará para à próxima estrutura de vizinhança.

A ordem de transição das estruturas é sistemática, então a próxima estrutura de vi-

zinhança é k igual a 2. O processo de busca se inicia, fechando k chaves de interconexão

quaisquer, e abrindo k chaves de interconexão (ou seccionamento) quaisquer dos laços

formados. Para esta escolha previamente constroi-se o PFO para cada laço. Ordenam-se

aleatoriamente os elementos destas listas PFO e avaliam-se apenas 20% dos elementos.

As estratégias a utilizar como já foi mencionado, são diferentes tanto para o VNS e

VND. Estas estratégias são detalhadas:

• Para o algoritmo VNS: se dentro deste processo de busca, abrir/fechar chaves,

encontra-se uma configuração com solução de melhor qualidade que a incumbente,

então reinicia-se o processo de busca com k igual a 1. Caso não encontra, passa-se

a seguinte combinação aleatória das k chaves de interconexão, até alcançar 30% do

número total de chaves de interconexão (combinações de k-chaves). O algoritmo

implementado está ilustrado na Figura 24;

• Para o algoritmo VND: caracteriza-se porque, no processo de busca, abrir/fechar

chaves, depois de explorar configurações, até alcançar 30% do número total de chaves

de interconexão (combinações de k-chaves), avaliam-se as configurações visitadas e

aquela que apresente uma solução de melhor qualidade compara-se com a solução



3.8 Implementação dos Algoritmos VNS e VND 58

da incumbente. Se é melhor, escolhe-se esta como a incumbente e reinicia-se o

processo de busca com k igual a 1. Caso contrário, passa-se a próxima estrutura de

vizinhança. O algoritmo implementado está ilustrado na Figura 25.

O algoritmo termina quando se alcança o número de estruturas de vizinhanças igual

a Kmax, onde n/3 = Kmax.

Nos testes feitos as melhores configurações foram encontradas na segunda estrutura

de vizinhança.



3.8 Implementação dos Algoritmos VNS e VND 59

Figura 24: Diagrama de blocos do algoritmo VNS.



3.8 Implementação dos Algoritmos VNS e VND 60

Figura 25: Diagrama de blocos do algoritmo VND.



61

4 Resultados Obtidos

Neste caṕıtulo são apresentados os resultados obtidos em diversas simulações uti-

lizando a methaheuŕıstica proposta de Busca em Vizinhança Variável, tendo como objetivo

a minimização de perdas de potência ativa. São apresentados testes para diferentes sis-

temas, de 14 barras (CINVANLAR; GRAINGER; LEE, 1988), 32 barras (BARAN; WU, 1989a) e

69 barras (CHIANG; JEAN-JUMEAU, 1990). Estes sistemas são bastante conhecidos na li-

teratura especializada. Também apresentam resultados de testes de dois sistemas reais,

um com 135 barras e outro com 202 barras. Os dados destes sistemas são apresentados

no Apêndice A. A potência e a tensão base utilizadas foram de 1000 kVA e a tensão da

subestação respectivamente.

Os sistemas foram testados utilizando o algoritmo da VNS, porque encontrou os va-

lores ótimos globais num menor número de transições, que o algoritmo VND. Assim

também, para gerar a configuração inicial, se utilizou um algoritmo heuŕıstico proposto

por (GOSWAMI; BASU, 1992).

Os tempos de processamento foram obtidos utilizando um computador pessoal Pen-

tium 4, 1,8 GHz, 256 MB RAM.

4.1 Sistema de 14 barras

O sistema é mostrado na Figura 26. Inicialmente o sistema apresenta 14 barras, 16

circuitos e carga total de 28, 9 MW, os ramos de ligação são 14, 15, 16. Na Tabela 8

mostram-se os resultados obtidos para este sistema.



4.2 Sistema de 32 barras 62

Tabela 8: Resultados obtidos sistema de 14 barras.

Configuração Chaves abertas Perda(kW ) Red.(%)
1-Inicial 14 15 16 511,4106 -

2 7 8 16 466,1137 8,5165
3 7 8 13 492,8172 8,4532
4 4 7 8 479,2779 5,8533

2

7

10

3
 9

6

8
 12

11

13

14
5

4

16

15
14

1
 1
1

Figura 26: Sistema de 14 barras.

4.2 Sistema de 32 barras

O sistema é mostrado na Figura 27. Inicialmente o sistema apresenta 32 barras, 37

circuitos e carga total de 3715 kW, os ramos de interconexão são 33, 34, 35, 36. Na

Tabela 9 mostram-se os resultados obtidos para este sistema.



4.3 Sistema de 69 barras 63

Tabela 9: Resultados obtidos sistema de 32 barras.

Configuração Chaves abertas Perda(kW ) Red.(%)
1-Inicial 33 34 35 36 37 202,676207 -

2 7 9 14 32 37 139,5497 31,146
3 7 9 14 28 32 139,9767 30,936
4 7 10 14 32 37 140,2773 30,787
5 7 10 14 28 32 140,7043 30,577
6 7 11 14 32 37 141,2025 30,331

1
 3
2
 4
 6
5
 8
7
 9
 11
10
 13
 14
12
 16
15
 18
17

19
 21
 22
20

27
 29
 30
28
 31
 33
32

24
 25
23

34

37

35
33

36

26

Figura 27: Sistema de 32 barras

4.3 Sistema de 69 barras

O sistema é mostrado na Figura 28. Inicialmente o sistema apresenta 69 barras, 74

circuitos e carga total de 1108 kW, os ramos de interconexão são 70, 71, 72, 73, 74. Na

Tabela 10 mostram-se os resultados obtidos para este sistema.



4.4 Sistema de 135 barras 64

Tabela 10: Resultados obtidos sistema de 69 barras.

Configuração Chaves abertas Perda(kW ) Red.(%)
1-Inicial 70 71 72 73 74 20,6826 -

2 15 59 62 70 71 9,3408 54,838
3 15 56 62 70 71 9,34076 54,838
4 15 58 62 70 71 9,34076 54,838
5 15 57 62 70 71 9,34077 54,838
6 14 59 62 70 71 9,34932 54,796
7 14 56 62 70 71 9,34932 54,796

1
3

2
4

6
5

8
7

9
11


10


13


14


12


16


15


18


19


17


20


22


23


21


25


24


27


28


26



52


53


69


70


67


68


54


56


57


55


58


60


61


59


63


62


65


66


64


48


50


51


49


37


39


40


38


41


43


44


42


46


45


47


29


31


32


30


33


35


36


34


71


70


72


73


74


Figura 28: Sistema de 69 barras.

4.4 Sistema de 135 barras

O sistema é mostrado na Figura 29. Inicialmente o sistema apresenta 135 barras, 156

circuitos e carga total de 18313, 81 kW, os ramos de interconexão são 136, 137, 138, 139, 140,



4.4 Sistema de 135 barras 65

141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156. Na

Tabela 11 mostram-se os resultados obtidos para este sistema.

Tabela 11: Resultados obtidos sistema de 135 barras.

Configuração Chaves abertas Perda(kW ) Red.(%)
1-Inicial 136 137 138 139 140 141 142 143 144 145 146 320,276 -

147 148 149 150 151 152 153 154 155 156
2 7 35 51 90 96 106 118 126 135 137 138 280,138 12,532

141 142 144 145 146 147 148 150 151 155
3 7 51 53 84 90 96 106 118 126 128 137 280,166 12,523

138 139 141 144 145 147 148 150 151 156
4 7 38 51 53 90 96 106 118 126 137 138 280,243 12,500

141 144 145 146 147 148 150 151 155 156
5 7 38 51 53 84 90 96 106 118 126 128 280,281 12,487

137 138 141 144 145 147 148 150 151 156
6 7 49 51 53 84 90 96 106 118 126 128 280,303 12,481

137 138 139 144 145 147 148 150 151 156

19
18

58
 59
57
 60

79
 77
78
 76

1
2

53
52
 55
 56
54

64

41
40
 42
 129
 125
127

130
 128
131
 124
126
 122
123

95
 94
96
 93
 91
 90
92
 87
89
 86

121
 120
 119
 104
 102
105
 100
101

97

114
 113
 112
 108
 107
111
 106

88

118
 117
 110
 115
 116
109
103

43
 44
 46
 48
 49
47
 50

45

63

61
 62

98
99

34
35
 32
 36
33
 37
 38

26
25
 28
 29
27
 30
 31
21
20
 23

39

132
133
135
136
 134

22
 24

7
6
 11
 14
9
 16
4
3
 5

13
 15
10
 17

8
 12

51

80
81
84
85
 82

83

67
69
71
 68
 66
 65
75
 74

70
72
73

1

Figura 29: Sistema de 135 barras.



4.5 Sistema de 202 barras 66

4.5 Sistema de 202 barras

O sistema é mostrado na Figura 30. Inicialmente o sistema apresenta 202 barras, 216

circuitos e carga total de 27571,99 kW, os ramos de interconexão são 202, 203, 204, 205, 206,

207, 208, 209, 210, 211, 212, 213, 214, 215, 216.

4.5.1 Com limitação de chaveamento

Na Tabela 12 mostram-se os resultados obtidos para este sistema.

13
4

13
5

13
3

13
8

13
6

14
0

13
9

14
3

15
2

14
2

15
5

15
4

15
8

15
6

16
4

16
2

16
1

16
5

16
3

16
8

16
7

17
1

17
3

16
9

17
6

17
4

17
9

17
8

18
2

18
6

18
5

19
0

18
7

19
8

19
9

19
3

19
6

19
5

19
7

18
0

20
2

20
0

20
1

13
7

14
4

14
1

89


92


91


90


94


95


93


97


96


98


86


83


60


61


59


63


62


70


64


77


79


75


82


81


86


84


88


99


87


10
2

10
0

10
6

10
5

11
0

11
1

10
9

11
4

11
2

12
0

11
9

12
2

12
5

12
4

12
9

12
7

13
1

13
0

12
1

13
2

65


66


68


67


69


78


76


85


10
4

10
5

10
1

11
3

11
8

10
7

10
8

11
5

11
6

11
7

12
3

12
6

12
8

18
8

19
1

18
1

18
4

14
8

14
5

14
7

14
9

14
6

15
9

16
0

17
0

16
6

17
2

17
5

17
7

18
3

18
9

19
2

19
4

15
1

15
0

11


17


16


20


19


3
4

2
8

5
6

9
10


15


7

12


14


13


22


21


24


25


23


26


27


42


40


44


50


43


52


51


54


53


55


56


58


57


39


37


48


46


45


38


36


35


47


49


29


28


31


32


30


33


34


72


74


75


71


18


41


21
0

20
4

20
5

20
6

20
9

20
2

20
8

20
3

21
1

21
3

21
4

21
5

21
2

21
6

20
7

Figura 30: Sistema de 202 barras.



4.5 Sistema de 202 barras 67

Tabela 12: Resultados obtidos sistema de 202 barras - com limitação de chaveamento

Configuração Chaves abertas Perda(kW ) Red.(%)
1-Inicial 202 203 204 205 206 207 208 209 545,4278 -

210 211 212 213 214 215 216
2 154 177 183 199 202 203 204 205 539,0425 1,1707

206 207 211 212 213 215 216
3 177 183 199 202 203 204 205 206 539,0425 1,1707

207 208 211 212 213 215 216
4 154 177 184 199 202 203 205 206 540,9536 0,8203

207 210 211 212 213 215 216
5 177 199 202 203 204 205 206 207 540,9536 0,8203

208 210 211 212 213 215 216
6 177 183 202 203 204 205 206 207 541,3696 0,7440

208 211 212 213 214 215 216
7 154 177 183 202 203 204 205 206 541,3696 0,7440

207 211 212 213 214 215 216
8 199 202 203 204 205 206 207 208 543,1007 0,4267

209 210 211 212 213 215 216
9 177 183 184 202 203 204 205 206 541,3696 0,7440

207 211 212 213 214 215 216

4.5.2 Sem limitação de chaveamento

Para efeitos de comparação foram considerados todos os ramos com chaves, não tendo

sido alteradas as chaves de interconexão. Na Tabela 13 mostram-se os resultados obtidos

para este sistema.



4.6 Conclusões 68

Tabela 13: Resultados obtidos sistema de 202 barras - sem limitação de chaveamento.

Configuração Chaves abertas Perda(kW ) Red.(%)
1-Inicial 202 203 204 205 206 207 208 209 545,4278 -

210 211 212 213 214 215 216
2 12 29 66 74 83 111 118 125 508,4749 6,7750

131 135 136 199 202 208 211
3 29 66 74 83 111 118 125 131 508,4831 6,7735

135 136 140 177 199 202 208
4 28 66 74 83 111 118 125 131 508,6349 6,7457

135 136 140 177 199 202 208
5 12 29 66 74 83 111 118 125 508,6414 6,7445

131 135 137 184 199 202 211
6 29 66 74 83 111 118 125 131 508,6450 6,7439

135 137 140 177 199 202 208

4.6 Conclusões

Para os sistemas testados de 14, 32, 69, o algoritmo encontrou configurações com qua-

lidades das soluções iguais aos encontrados na literatura especializada. Para os sistemas

reais de 135 e 202 barras este algoritmo demostrou ser muito eficiente porque encontrou

configurações com qualidade de soluções iguais e melhores que apresentados na literatura,

tanto para os sistemas com limitação de chaveamento como sem limitação de chaveamento.

As Tabelas 14 e 15 ilustram o número de transições, que permite analisar o desem-

penho dos algoŕıtmos VNS e VND respectivamente. Para os sistemas de 135 e 202 barras,

o algoritmo transitou respectivamente por 1532 e 495 configurações. É necessário indicar

que para chegar até a configuração que gerou a segunda maior redução de perdas que

a configuração ótima global para o sistema de 135 barras, visitou-se 607 configurações,

aumentando o número de transições para encontar a configuração que apresenta melhor

resultado.

Com relação aos ńıveis de tensão depois da reconfiguração, encontrou-se para os sis-

temas de 135 e 202 barras sem limitação de chaveamento valores com magnitudes mı́nimas

de tensão igual a 0.9582 e 0.96227 p.u. respectivamente.



4.6 Conclusões 69

Tabela 14: Parâmetros do algoritmo VNS.
Sistema Num. Num. de fluxos de carga Esforço

Transições aproxim. calculados computacional (seg)
14 barras 4 4 1,00
32 barras 32 32 5,00
69 barras 82 82 10,00
135 barras 1532 1532 692,00
202 barras 495 495 409,00

Tabela 15: Parâmetros do algoritmo VND.
Sistema Num. Num. de fluxos de carga Esforço

Transições aproxim. calculados computacional (seg)
14 barras 4 4 1,00
32 barras 32 32 5,00
69 barras 82 82 10,00
135 barras 2933 2833 1711,00
202 barras 1074 1074 1195,00



70

5 Conclusões

As metaheuŕısticas proporcionam mecanismos adequados para sair dos ótimos lo-

cais, dado que os ótimos locais diferem muito dos ótimos globais, e dessa forma o im-

pacto prático das melhorias dos resultados obtidos com as metaheuŕısticas em relação às

heuŕısticas tradicionais, pode ser observado através dos testes apresentados neste trabalho.

A análise foi baseada num processo de busca do primeiro melhor para o VNS e da

combinação do primeiro melhor - melhor para o VND. As estratégias empregadas podem

variar de acordo com o ponto de vista do investigador, porque como na implementação

de qualquer metaheuŕıstica aplica-se a intuição mais que a dedução.

A busca em Vizinhança Variável proposta por (MLADENOVIC, 1995) cumpre com as

propriedades básicas que deve ter toda metaheuŕıstica que são: simplicidade, coerência,

eficiência, e robustez.

O métodos desenvolvidos pelas VNS e VND, com a implementação da heuŕıstica

proposta por (GOSWAMI; BASU, 1992) para avaliar as chaves que serão trocadas, no pro-

cesso de busca local nas estruturas de vizinhança, demostrou ser muito eficiente, porque

encontrou-se uma melhor configuração para o sistema testado de 135 barras (sistema real).

O método proposto para a reconfiguração de redes elétricas demostrou ser muito efi-

ciente, conseguindo encontrar um grande número de configurações de ótima qualidade.

Para os sistemas de 14, 32, 69 barras foram encontradas configurações compat́ıveis com a

literatura, embora para o sistema de 135 barras (sistema real) foram encontrados resulta-

dos iguais que o encontrado no algoritmo de Busca Tabu (DUARTE, 1999), e melhores que

os encontrados pelos algoritmos de Tabu Search e Genetico Modificados propostos respec-

tivamente, por (GUIMARÃES, 2005; ROMERO, 2001). Para o sistema de 202 barras com

e sem limitação de chaves foram encontradas também configurações de melhor qualidade

que o algoritmo Busca Tabu (GUIMARÃES, 2005).

Na alocação de chaves existentes na rede de 202 barras não se considera a possibilidade

de obter melhorias do ńıvel de perdas, porque a redução de perdas é mı́nima em relação

às perdas obtidas quando se considera que todos os ramos têm chave. O que indica que



5 Conclusões 71

a simples instalação de algumas chaves em pontos estratégicos da rede pode melhorar o

desempenho geral desse sistema, para planejamento da operação. Desta forma, sugere-se

para o problema especifico de redução de perdas a realocac