Anais do XX Congresso Brasileiro de Automática
Belo Horizonte, MG, 20 a 24 de Setembro de 2014
UMA METAHEURÍSTICA GRASP APLICADA AO PROBLEMA DE PLANEJAMENTO DA EXPANSÃO DOS SD
Abstract This paper presents a GRASP (Greedy Randomized Adaptive Search Procedure) algorithm applied to resolution of
expansion planning of electric power distribution systems (EPDS). The planning problem on Expansion of Electrical Energy
Systems Distribution presented in this work aims to the construction/ reconductoring of circuits and construction/ reinforcement
of substations in optimised form evaluating the construction costs of circuits and/or substations and of system operation in a preestablished planning horizon. The proposed model is a problem of mixed integer nonlinear programming (MINLP), which is solved
by employing the metaheuristic GRASP combined with a Constructive Heuristic Algorithm (CHA) and a VNS (Variable
Neighborhood Search). Results of two distribution systems are demonstrated in order to analyze the algorithm development.
Keywords Planning of the expansion, Metaheuristic, systems of distribution of electrical energy
Resumo Este trabalho apresenta um algoritmo GRASP (Greedy Randomized Adaptive Pesquisa Processo) aplicada a resolução
de planejamento da expansão dos sistemas de distribuição de energia elétrica (PESD). O problema apresentado neste trabalho tem
como objetivo a construção / recondutoramento de circuitos e construção / reforço de subestações em forma otimizada avaliando
os custos de construção de circuitos e / ou subestações e de operação do sistema em uma pré-estabelecido horizonte de
planejamento. O modelo proposto é um problema de programação não-linear inteira mista (MINLP), que é resolvido através da
utilização metaheurística GRASP combinada com um algoritmo heurístico construtivo (AHC) e um VNS (Variable Neighborhood
Search). Os resultados de dois sistemas de distribuição são demonstradas a fim de analisar o algoritmo desenvolvido
Palavras chave Planejamento da expansão, Metaheuristica, sistemas de distribuição de energia elétrica.
´
1
Limite máximo de potência aparente em
uma subestação construída/repotenciada no
nó i (kVA)
Mínima magnitude da tensão;
Máxima magnitude da tensão;
Demanda de potência ativa no nó i (kW);
Demanda de potência reativa no nó i
(kVAr);
Resistência do condutor de tipo a (Ω/km);
Resistência do ramo ij (Ω);
Reatância do condutor de tipo a (Ω/km);
Reatância do ramo ij (Ω);
Impedância do condutor de tipo a (Ω/km);
Impedância do ramo ij (Ω);
Variáveis:
Quadrado da magnitude do fluxo de
,
corrente do circuito ij associada com o
condutor tipo a;
Quadrado da magnitude do fluxo de
corrente do circuito ij;
Quadrado da magnitude da tensão no nó i;
Quadrado da potência aparente provida
pela subestação do nó i;
Fluxo de potência ativa do circuito ij
,
associado com o condutor do tipo a;
Fluxo de potência reativa do circuito ij
,
associado com o condutor do tipo a;
Direção para frente do fluxo da potência
,
ativa do circuito ij associado com o
condutor do tipo a.
Direção para trás de fluxo da potência
,
ativa do circuito ij associado com o
condutor do tipo a.
Notação
Conjuntos:
Conjunto de tipo de condutores;
Ω
Conjunto de nós;
Ω
Conjunto de ramos;
Ω
Conjunto de subestações;
Ω
Constantes:
Número de horas em um ano (8760 h)
Número de anos do período de planejamento
Taxa de recuperação de capital de
construção circuito
Taxa de recuperação de capital da
subestação construção / reforço;
Fator de perda de circuitos
Fator de perda de subestações
Taxa de juros do custo real das perdas de
energia;
Taxa de juros de custo de operação das
subestações;
Limite inferior para a variável ;
Custo fixo da subestação no nó i (US$/
(kW)2 /h);
Custos de construção de circuitos usando o
,
tipo de condutor a (US$/kWh);
Custo da energia (US$);
Máxima magnitude de fluxo de corrente do
condutor tipo a (A);
Comprimento do circuito ij (km);
Limite máximo de potência aparente em
uma subestação existente no nó i (kVA);
1
3620
Anais do XX Congresso Brasileiro de Automática
Belo Horizonte, MG, 20 a 24 de Setembro de 2014
,
heurísticas. Um algoritmo heurístico construtivo com
uma fase de melhoria local é utilizado em (Lavorato,
Rider, Garcia, & Romero, 2010). Neste trabalho, em
primeiro lugar, todas as variáveis de decisão binarias
são relaxadas, tornando-se um problema de
programação não linear (PNL). O problema de PNL é
resolvido a cada iteração e sua solução é utilizada para
calcular o índice de sensibilidade, para ser utilizado no
AHC. Por último, uma heurística de melhoria local, é
utilizada para melhorar a solução encontrada pelo
AHC. Entre as técnicas de metaheurísticas utilizadas
encontram-se os trabalhos com algoritmos genéticos
(Ramirez-Rosado & Bernal-Augustín, 1998) - (Duan
& Yixin, 2003). Em (Ramirez-Rosado & BernalAugustín, 1998), um algoritmo genético é utilizado no
planejamento de sistemas comparativamente maiores.
Em (Diaz-Dorado, Cidras, & Miguez, 2002), um
planejamento estático de rede urbana é resolvido
mediante um algoritmo genético, onde operadores
baseados em cruzamento e mutação são utilizados
para minimizar a geração de soluções fatíveis e uma
estratégia elitista assegura a sobrevivência das
melhores soluções. Um AG específico do problema
chamado AG do caminho mais curto foi proposto em
(Duan & Yixin, 2003), onde os cromossomos são
gerados de forma aleatória e as buscas globais e locais
realizadas com os operadores genéticos e o algoritmo
de rota mais curta, respectivamente. Em (Gómez, et
al., 2004) é empregado um algoritmo de Busca de
Colônia de formigas. Em (Parada, Ferland, Arias, &
Daniels, 2004) os autores utilizam a técnica de
recozido simulado. Em (Ranjan, Vekatesh, & Das,
2002) emprega-se um sistema especialista baseado em
redes neurais que troca o problema original de
planejamento do sistema de distribuição por um
problema de planejamento de grafo dirigido. Em
(Ganguly, Sahoo, & Das, 2011) propõe-se um
algoritmo de enxame de partículas. Porem existem
poucos antecedentes de uso de metaheurísticas
diferentes às populacionais aplicadas ao PESD.
Neste trabalho um algoritmo híbrido GRASP
(Greedy Randomized Adaptive Search Procedure)
com VNS (Variable Neighborhood Search) é proposto
para resolver o problema de PESD com o objetivo de
observar o rendimento da técnica escolhida.
Fluxo potência ativa do circuito ij
Fluxo potência reativa do circuito ij
Potência ativa provida pelo nó i (kW);
Potência reativa provida pelo nó i (kW);
Variável usada no calculo da magnitude da
queda da tensão no nó i;
Variável binaria associada com a direção
para frente do circuito ij;
Variável binaria associada com a direção
de decida do circuito ij;
Variável binaria para a construção/
repotenciação da subestação no nó i;
Variável binaria para construção/
recondutoramento do circuito ij usando o
condutor do tipo a.
2
Introdução
A resolução do problema de planejamento da
expansão do sistema de distribuição (PESD) tem
como objetivo determinar o melhor plano de expansão
do sistema que minimize os investimentos e os custos
de operação, atendendo as restrições de operação, tais
como, os limites da magnitude da tensão, limites da
magnitude de fluxo de potência nos circuitos, limites
de fornecimento da potência das subestações, e a
operação radial do sistema, para um horizonte de
planejamento no qual a demanda é conhecida (Wills,
2004) - (Temraz & Quintana, 1993).
O modelo matemático do PESD que representa de
maneira mais fiel a característica de um sistema de
distribuição real é um Problema de Programação Não
Linear Inteiro Misto (PNLIM) (Bernal-Agustin,
1998). A função objetivo é não diferençável, não
convexa, altamente não linear e apresenta o fenômeno
da explosão combinatória quando o tamanho do
sistema a ser otimizado aumenta. Porem, numerosas
estratégias de solução têm sido relatadas na literatura
especializada e que podem ser divididos em duas
categorias: métodos de programação matemática e
métodos heurísticos, incluindo sistemas especialistas
e algoritmos evolucionários na última categoria.
Dentro das técnicas heurísticas, (Ponnavaikko,
Rao, & Venkata, 1987) e ( Bhowmik, Goswami, &
Bhattacherjee, 2000) usam modelos quadráticos para
o tratamento do PESD. Em (Ponnavaikko, Rao, &
Venkata, 1987) propõe-se um algoritmo heurístico
construtivo (AHC) que aproxima as perdas de
potência ativa através de uma função quadrática, o
algoritmo relaxa a integralidade das variáveis de
decisão e resolve o problema quadrático resultante
para determinar as variáveis que podem ser
arredondadas. Em ( Bhowmik, Goswami, &
Bhattacherjee, 2000) uma técnica iterativa de duas
fases é proposta, na primeira fase é determinado o
tamanho ótimo das subestações, na segunda fase é
fornecida a configuração da rede, a integralidade das
variáveis é relaxada com o objetivo de resolver o
problema quadrático, com esta solução são impostas
restrições de integralidade empregando técnicas
3
Modelo matemático
No modelo são usadas as equações propostas em
(Cespedes, 1990) e (Baran & Wu, 1989), as quais são
frequentemente utilizadas no método de varredura
para o fluxo de carga de sistemas de distribuição
radiais. Além das contribuições no modelamento para
sistemas radiais feitas no trabalho apresentado em
(Rider, Franco, & Borges , 2014) para outro tipo de
problemas próprios dos sistemas de distribuição.
2
3621
Anais do XX Congresso Brasileiro de Automática
Belo Horizonte, MG, 20 a 24 de Setembro de 2014
min
calculadas usando (6)–(8). Os limites da magnitude da
tensão são estabelecidos por (9). As restrições (10) e
(11) representam os limites da magnitude dos fluxos
de corrente do circuito ij relacionado com cada tipo de
condutor e o seu estado de operação respetivamente.
A restrição (12) permite a seleção de um e somente
um tipo de condutor para o circuito ij se este é
construído. A inequação (13) limita o número de
direções de fluxos de potência ativa a somente um
para o circuito ij. A equação (14) junto com as
restrições (2) e (3) são usadas para garantir a operação
radial do sistema como é mostrado em (Lavorato,
Franco, Rider, & Romero, 2012). A restrição (15)
estabelece que cada nó do sistema tem que estar
conectado e alimentado pelo menos por um circuito.
A equação (16) limita o valor da queda de tensão para
o estado de operação do sistema do circuito ij. A
equação (17) calcula o fluxo de potência ativa do
circuito ij com condutor tipo a somando os fluxos de
potência ativa nas direções para frente e para trás. As
restrições (18)–(22) permitem estabelecer limites para
os fluxos de potência ativa e reativa nos circuitos ij
com base no estado de operação e do tipo de condutor
a. As inequações (23) e (24) são os limites de operação
das subestações. As restrições (25) até (28)
representam a natureza binária das variáveis de
decisão.
( , )
+
∈Ω
+
+
,
,
(1)
∈Ω
∈Ω
( , )
,
Sujeito a
−
,
∈Ω
∈Ω
∈Ω
+
=
∈Ω
∈Ω
∈Ω
+
+
=
(2)
∈Ω
(3)
,
∈Ω
−
,
∀
−
,
+
,
∈Ω
,
=
[2
∀
,
+
,
]+
∈Ω
(4)
,
∈Ω
+
=
+
=
,
∀ ∈Ω
∀ ∈Ω
(5)
∀ ∈Ω
(6)
∀ ∈Ω
(7)
∀ ∈Ω
(8)
∀ ∈Ω
(9)
(10)
(11)
(12)
∈Ω
=
,
∈Ω
=
,
∈Ω
≤
0≤
0≤
≤
,
≤
,
∀ ∈Ω,
∈Ω
,
≤
,
∀ ∈Ω,
∈Ω
=
+
,
∀ ∈Ω
4
O GRASP é uma metaheurística de duas fases
(Feo & Resende, 1995). Na primeira fase, são
construídas soluções utilizando um processo guloso
aleatório e na segunda fase, as soluções obtidas da
primeira fase são melhoradas por algum método
enumerativo ou de busca local. A seguir, apresenta-se
a metodologia proposta, onde na fase de construção é
utilizado uma modificação de um AHC e o VNS é
empregado na segunda fase do GRASP na resolução
do PESD.
∈Ω
+
≤1
+
= |Ω | − |Ω |
(13)
(14)
∈Ω
(
+
∈Ω
) ≥1
(15)
∈Ω
∀ ∈Ω −Ω ,
>0
∀ ∈Ω
∀ ∈Ω, ∈Ω
∀ ∈Ω, ∈Ω
(16)
(17)
(18)
0≤
≤
(19)
0≤
≤
∀ ∈Ω, ∈Ω
(20)
0≤
≤
∀ ∈Ω, ∈Ω
,
(21)
0≤
≤
∀
,
∈
Ω
∈
Ω
,
(22)
≤
∀ ∈Ω, ∈Ω
,
,
(23)
≥
+
∀ ∈Ω
´
(24)
≤
+
∀ ∈Ω
∈ {0,1}
∀ ∈Ω
(25)
∀ ∈Ω, ∈Ω
(26)
, ∈ {0,1}
,
∈ {0,1}
∀ ∈Ω
(27)
A função objetivo (1) leva em conta os custos de
investimento e de operação e se encontra baseada no
trabalho realizado em (Lavorato, Rider, Garcia, &
Romero, 2010). As equações (2) e (3) representam o
balanço de potência no nó i. A equação (4) representa
o cálculo da queda de tensão no circuito ij. A equação
(5) estabelece a relação entre os fluxos de potências
ativa e reativa, o quadrado da magnitude da tensão e o
quadrado da magnitude da corrente. As magnitudes do
fluxo de corrente, potências ativa e reativa são
,
≤
=
1−
−
−
Metodologia de solução: GRASP
Figura 1 Diagrama de blocos do GRASP
3
3622
Anais do XX Congresso Brasileiro de Automática
Belo Horizonte, MG, 20 a 24 de Setembro de 2014
4.1.
Fase de construção.
Inicio
Para fornecer uma solução inicial de boa
qualidade, é utilizado um processo guloso aleatório
baseado no algoritmo apresentado por (Lavorato,
Rider, Garcia, & Romero, 2010) em que a cada
iteração resolve um problema de Programação Cônico
de Segunda Ordem PCSO, resultante do relaxamento
das variáveis inteiras do problema de PNLIM que
passam a ser consideradas como contínuas e restritas,
e da conversão da equação (5) a uma restrição cônica,
este último fato está baseado na equivalência existente
entre o modelo de PNLIM e o modelo de Programação
quadrático inteiro misto PQIM o qual é apresentado
em (Rabih, 2013). Através dos resultados obtidos pela
solução do problema de PCSO, são calculados os
índices de sensibilidade que serão usados para
adicionar os circuitos com o tipo de condutor e/ou as
subestações no sistema.
Os índices de sensibilidade estão baseados na potência
aparente para o caso das subestações (ISS) e de
potência ativa para o caso dos ramos (ISC), com o
objetivo de determinar a lista restrita de candidatos em
cada iteração da fase construtiva:
=
,
∈Ω
≠0
(28)
=
,
∈
Ω
,
∈
Ω
≠
0
(29)
,
,
O problema PCSO usado para encontrar os índices de
sensibilidade é obtido a partir de (1) - (27),
considerando o número de novos circuitos e
subestações como variáveis contínuas (mas limitada
entre 0 e 1), relaxando a restrição (5) e acrescentando
dois novos parâmetros (wmas e zmas) para os
conjuntos de restrição (10), (12), (13), (20), (21), (22)
acompanhando as variáveis de decisão e que
controlam a sua escolha segundo o comportamento
dos índices de sensibilidade a cada iteração.
Os critérios de parada do AHC são:
∑ ∈Ω
=0
(30)
Conjuntamente com:
∑ ∈Ω ∑ ∈Ω
(31)
, = |Ω | − |Ω |
Na figura 2 representa o diagrama de blocos da fase
construtiva, a qual é realizada em dois níveis: o
primeiro determina o comportamento das variáveis
relacionadas com as subestações e o segundo nível
determina o comportamento dos circuitos e
condutores conjuntamente.
4.2.
Redução do espaço de busca dos circuitos.
Gerar semente, Determinar
parâmetro alfa, relaxar
PNLIM para um PCSO
Resolver PCSO
SIM
A soma das variáveis
wi é Igual a zero?
NÃO
Calcular indices de
sensibilidade para as
subestações
Criar lista restrita de
candidatos das subestações
Eleger aleatoriamente um
componente dentro da LRC
A restrição de
radialidade é satisfeita
?
SIM
FIM FASE
CONSTRUÇÃO
NÃO
Calcular indice de
sensibilidade para os
circuitos
Criar lista restrita de
candidatos dos circuitos
Eleger aleatoriamente um
componente dentro da LRC
Resolver PCSO
Figura 2 Funcionamento do Algoritmo guloso- aleatório na fase
construtiva.
4.3.
Fase de busca local.
Na fase de busca local geralmente o GRASP
busca melhorar a solução construída pela primeira
fase. Neste trabalho a busca local é realizada
aplicando a metaheurística VNS em uma de suas
variantes, o VNDS (VNS com Decomposição) quem
se adapta à natureza do PESD o qual pode ser divido
em um problema mestre de seleção ótima das
subestações e nos problemas escravos de
reconfiguração e recondutoramento das linhas
(Franco, 2012).
O VNDS usará um conjunto de estruturas de
vizinhança no nível mais superior para eleger uma
combinação de subestações utilizando um RVNS
como busca local e usando no nível mais inferior outra
versão do algoritmo VNS, um VND, para melhorar a
solução corrente usada para iniciar a busca,
procurando boas combinações de circuitos e
condutores conjuntamente (Fernandes, 2011).
Com o objetivo de reduzir o espaço de busca dos
circuitos a construir e recondutorar é empregada uma
sub-rotina posterior à fase de construção onde são
identificados e fixados os valores dos circuitos que só
tem um caminho de alimentação, tendo como base o
tipo de condutor fornecido pelo índice de
sensibilidade na fase construtiva.
4
3623
Anais do XX Congresso Brasileiro de Automática
Belo Horizonte, MG, 20 a 24 de Setembro de 2014
em (Franco, 2012). Assim a fase de busca pode ser
resumida da seguinte forma:
Vizinhanças para
subestações (Estruturas
de primeiro nivel)
Inicio
Vizinhanças para
circuitos e
conductores
(Estruturas de
segundo nivel)
Estabelecer estruturas de
vizinhança para as
subestações e para os
circuitos
Fazer solução inicial a
fornecida na fase
construtiva
Figura 3 Estrutura da busca para o PESD
O VNDS foi adaptado para que cada estrutura de
vizinhança visitada gerasse uma configuração
infactível de tal forma que a busca local possa explorar
todas as rotas alternativas que trazem de volta a
factibilidade do sistema e cuja função objetivo seja
melhorada. A proposta feita neste trabalho é baseada
no trabalho feito em (Fernandes, 2011) e tem as
seguintes caraterísticas:
 Estrutura de vizinhança para seleção das
subestações: A fase construtiva do GRASP
garante a potência para o funcionamento do
sistema de distribuição, porém, as estruturas de
vizinhança de retirada de subestações construídas
ou repotenciações realizadas mostraram-se mais
interessantes do que o acréscimo destas como
estruturas de vizinhança (Fernandes, 2011). Na
primeira parte, utiliza-se o cenário inicial
produzido pela fase construtiva do GRASP e
através das estruturas de vizinhança para seleção
de circuitos, procura-se melhorar a solução
inicial. Partindo dela, exploram-se as estruturas
de vizinhança para subestações que serão
apresentadas a seguir: a) Retirar uma ou duas
subestações construídas pela fase construtiva e
reconectar as barras desconectadas às outras
subestações. A busca local utilizará as estruturas
de vizinhança dos circuitos para conectar os laços
ou barras que ficarem desconectados b) Retirar
uma ou duas repotenciações realizadas pela fase
construtiva do GRASP. Para reconstruir a
radialidade do sistema, todos os circuitos ligados
à subestação são desconectados e é implementado
um algoritmo de tipo guloso para reconectar as
barras desconectadas às subestações, incluindo
aquela sem repotenciação.
 Estrutura de vizinhança para seleção dos
circuitos: a) Escolher aleatoriamente um ou dois
circuitos que serão retirados do sistema,
tornando-o desconexo. Fazer então uma busca
local, onde diferentes circuitos alternativos são
adicionados ao sistema de forma a tornar este
sistema conexo. b) Escolher aleatoriamente um
ou dois circuitos que serão adicionados ao
sistema, criando-se assim um anel. Fazer então
uma busca local na qual é retirado um circuito do
anel para que o sistema seja novamente radial.
Com o objetivo de reduzir o esforço computacional na
avaliação de soluções infactíveis, são proibidas
propostas de combinação das subestações cuja
potência aparente seja menor a potência aparente
demandada pelos nós de carga tal como se recomenda
Realizar busca local na
topologia da solução
inicial
Fazer Kse==1
SIM
Kse > Kmax,se?
FIM
NÃO
Escolher aleatoriamente
uma solução Xse.
Fazer busca local nas
estruturas de vizinhança
de seleção de circuitos
para gerar solução
corrente
NÃO
Fazer Kse = Kse +1
A solução corrente
melhora a incumbente?
SIM
Atualizar incumbente.
Fazer Kse==Kse
Figura 4 Diagrama de blocos do VNS na fase de Busca local do
GRASP.
Baseados na proposta de (Fernandes, 2011) é usada
uma lista de movimentos proibidos, que leve em conta
as mudanças na topologia da solução corrente. Estes
movimentos são proibidos de forma permanente para
o caso das subestações e para os circuitos o atributo só
é retirado quando existe uma troca na combinação da
solução para as subestações.
A diferença da estratégia usada em (Fernandes, 2011),
onde o primeiro nível do VNS é abandonado sem
importar se a solução corrente encontrada na estrutura
de vizinhança é melhor que a incumbente, no presente
trabalho se a solução corrente encontrada em uma
estrutura de vizinhança de primeiro nível gera uma
solução melhor que a incumbente, reinicia-se a busca
nas estruturas de vizinhança de segundo nível sem
mudar a estrutura de vizinhança de primeiro nível. Isto
faz com que o primeiro nível somente seja
abandonado do VNS quando não é alcançada uma
melhora na incumbente, sendo necessário ir para outra
estrutura de vizinhança de primeiro nível.
5
Testes
A metaheurística proposta foi escrita em AMPL
(uma linguagem de programação matemática)
(Fourer, Gay, & Kernighan, 2003) e a solução dos
5
3624
Anais do XX Congresso Brasileiro de Automática
Belo Horizonte, MG, 20 a 24 de Setembro de 2014
PCSO foi obtida usando o solver CPLEX (CPLEX
Division, ILOG Inc, 2008) utilizando um processador
Intel(R) Core (TM) i3- 2328M [email protected] GHz.
Dois sistemas teste foram utilizados para avaliar o
desempenho da metaheurística desenvolvida para
resolver o PESD, ambos testes formam resolvidos
utilizando um alfa de 0.5 para a criação da lista restrita
de candidatos.
5.1.
Sistema de 23 nós
Comparação dos Resultados obtidos para o sistema de 23 barras
(U$)
Custo
Custo de
Anual de
Custo Total
Soluções
Circuitos
Perdas
Lavorato (Lavorato,
Rider, Garcia, &
151.892
20.227
172.119
Romero, 2010)
Fernandes
(Fernandes, 2011)
151.892
19.946
172.119
GRASP
O sistema de 23 nós pode ser encontrado na
literatura em (Nahman & Peric, 2008) é um sistema de
distribuição de 34.5 kV, com uma subestação que gera
10 MVA e tem 21 nós de carga. Os valores mínimo e
máximo de tensão são de 0,97 pu e 1,03 pu,
respectivamente. Os custos de perda de energia são
0,05 US/ KWh, o fator de perda e igual a 0,35, a taxa
de juros é 0,1 e o período de planejamento é de 20 anos
e existe dois tipos de condutores para a construção dos
circuitos, o primeiro com capacidade de 230 A e o
segundo com capacidade de 340 A.
5.2.
Sistema de 54 nós
153.913
17.055
A melhor solução encontrada pela metaheurística foi
de U$3.328.955 que é melhor que a solução
apresentada em (Fernandes, 2011) (Lavorato, Rider,
Garcia, & Romero, 2010). O plano consiste em
construir as duas subestações, todos os circuitos
usando o tipo de condutor de menor capacidade e não
são construídos os seguintes circuitos 8 -7, 18-17, 229, 8-25, 27-8, 28- 6, 10-31, 43-13, 33-39, 16-40, 4742.
Tabela 2 Resultados antecessores na literatura especializada
para o sistema de 54 nós.
Resultados obtidos para o sistema de 54 barras (U$)
Custo
Custo
Custo de
Custo de
Anual
Soluções
subestaçõ
anual de
Circuitos
de
es
operação
Perdas
Lavorato
(Lavorato,
Rider, Garcia,
39.580
2.772
540.000
2.933.183
& Romero,
2010)
Fernandes
(Fernandes,
39.580
2.672
540.000
2.933.183
2011)
40.544
2.374
440.000
2.846.037
GRASP
O sistema de distribuição de 54 nós tem uma
tensão nominal de 13,5-kV e 50 nós de carga. O
sistema possui duas subestações de 0,167 MVA que
podem ser repotenciadas com 0,167 MVA e 0,133
MVA e existe a possibilidade de construir duas novas
subestações de 0,222 MVA cada. São considerados
dois tipos de condutores para realizar a construção e o
recondutoramento, o primeiro deles tem uma
capacidade de 90 A e o segundo tem uma capacidade
de 110 A. As tensões mínima e máxima são de 0,95pu
e 1,05pu. Os custos de perda de energia são 0,1 US/
KWh, o fator de perda é igual a 0,35, a taxa de juros é
0,1, o período de planejamento é de 20 anos e os
custos de operação da subestação são 0,1US/VA h2.
Comparação dos Resultados obtidos para o sistema de 54 barras
(U$)
Soluções
6
170.969
Resultados
Custo Total
Lavorato (Lavorato, Rider, Garcia, &
Romero, 2010)
Fernandes (Fernandes, 2011)
GRASP
Para observar a qualidade da metaheurística
desenvolvida, 100 testes foram realizados para cada
um dos sistemas testes.
A tabela 1 apresenta uma comparação entre o
resultado encontrado pela metodologia proposta e os
resultados encontrados na literatura, a melhor solução
encontrada pela metodologia proposta para este
sistema foi de U$170.969, esta solução é igual à
apresentada em (Rabih, 2013) e é melhor que a
apresentada em (Lavorato, Rider, Garcia, & Romero,
2010), cujo custo é de U$ 172.119. O plano proposto
consiste em usar para todos os circuitos o primeiro
tipo de condutor, exceto para o circuito 1-10 o qual é
construído com o segundo tipo de condutor, que tem
um menor valor de impedância por km o que produz
uma redução nas perdidas que compensa a sua
inversão e gera a melhor solução encontrada até o
momento na literatura. Não são construídos os
circuitos 3-8, 3-16, 4-6, 4-8, 4-9-, 5-14, 6-16, 11-22,
12-15, 13-15, 15-21, 16-22, 19-20.
7
3.515.535
3.515.435
3.328.955
Conclusões
Neste trabalho foi proposta uma metaheurística
híbrida que combina a metaheurística GRASP e uma
metaheurística VNS para resolver o problema de
PESD.
A utilização do modelo de programação cônica de
segunda ordem garanta a obtenção da solução ótima
para o problema relaxado, contribuindo a brindar
maior precisão na escolha dos elementos a inserir em
um plano de expansão na hora de usar as sub-rotinas
na fase de construção e de busca local.
A metodologia proposta obteve melhores resultados
para os testes realizados em relação aos trabalhos
encontrados na literatura especializada. Os resultados
encontrados mostram a capacidade da metodologia
proposta de encontrar soluções de boa qualidade.
Tabela 1 Resultados antecessores na literatura especializada
para o sistema de 23 nós.
6
3625
Anais do XX Congresso Brasileiro de Automática
Belo Horizonte, MG, 20 a 24 de Setembro de 2014
Ganguly, S., Sahoo, N., & Das, D. (Mar de 2011).
Mono- and multi-objective planning of electrical
distribution networks using particle swarm
optimization. Appl. Soft Comput., 11(2), págs.
2391–2405.
Gómez, J., Khodr, H., Oliveira, P., Ocque, L., Yusta,
J., Villasana, R., & Urdaneta, A. (Mai de 2004). Ant
colony system algorithm for the planning of primary
distribution circuits. IEEE Trans. Power Syst, 19(2),
996–1004.
Lavorato, M., Franco, J. F., Rider, M. J., & Romero,
R. (Fev de 2012). Imposing radiality constraints in
distribution system optimization problem. IEEE
Trans. Power Syst, 27(1), págs. 172-180.
Lavorato, M., Rider, M., Garcia, A. V., & Romero, R.
(Ago de 2010). A construtive heuristic algorithm for
distribution system planning. IEEE Trans. Power
Syst., 25(3), págs. 17734-1742.
Nahman, J. M., & Peric, D. M. (Mai de 2008). Optimal
planning of radial distribution networks by
simulated annealing technique. IEEE Trans. Power
Syst., 23, págs. 790-795.
Parada, V., Ferland, J., Arias, M., & Daniels, K. (Jul
de 2004). Optimization of electrical distribution
feeders using simulated annealing. IEEE Trans.
Power Deliv, 19(3), págs. 1135–1141.
Ponnavaikko, M., Rao, K., & Venkata, S. (Out de
1987). Distribution system planning through a
quadratic mixed integer programming approach.
IEEE Trans. Power Deliv, 2(4), págs. 1157–1163.
Rabih, A. J. (Mai de 2013). Polyhedral Formulations
and Loop Elimination Constraints for Distributions
Network Expansion Planning. IEEE Trans. Power
Syst, 28(2), págs. 1888-1897.
Ramirez-Rosado, I., & Bernal-Augustín, J. (Mai de
1998). Genetic algorithms applied to the design of
large power distribution systems. IEEE Trans.
Power Syst, 13(2), págs. 696–703.
Ranjan, R., Vekatesh, B., & Das, D. (Mai de 2002). A
new algorithm for power distribution system
planning. Electr.Power Energy Syst, 62(1), págs.
55–65.
Rider, M. J., Franco, J., & Borges , M. (Fev de 2014).
Optimal Reconfiguration of Electrical Distribution
Systems Using Mathematical Programming. J
Control Autom Electr Syst, 25(1), págs. 103-111.
Temraz, H., & Quintana, V. (Jan de 1993).
Distribution System Expansion Planning Models:
An Overview. Electr Power Syst Res, 26(1), pág.
61.70.
Wills, H. (2004). Power Distribution Planning
Reference Book (Second Edition Revised and
Expanded ed.). New York: Marcel Dekker.
Os testes usados foram resolvidos usando a
formulação para o PNL, mas não foram obtidos
resultados no tempo computacional estabelecido de
15000 s o qual da conta da utilidade das
metaheurísticas para o PESD.
Agradecimentos
Referências Bibliográficas
S., Goswami, S., & Bhattacherjee, P. (Nov
de 2000). Distribution System Planning Through
Combined Heuristic and Quadratic Programing
Approach. Electric Machines & Power Systems,
28(1), págs. 87-103.
Baran, M. E., & Wu, F. F. (Jan de 1989). Optimal
capacitor placement on radial distribution systems.
IEEE Trans. Power Del, 4(2), págs. 725-734.
Bernal-Agustin, L. (1998). Aplicacion de algoritmos
genéticos al diseço optimo de sistemas de
distribución de energía eléctrica. Tesis doctoral,
Universidad de Zaragoza, Departamento de
Ingeniería Eléctrica, Zaragoza.
Cespedes, R. (Jan de 1990). New method for the
analisis of distribution networks. IEEE Trans.
Power De., 5(1), págs. 391-396.
CPLEX Division, ILOG Inc. (2008). CPLEX
Optimization subroutine library guide and reference,
version 11.0. Incline Village, NV USA: SpringerVerlag.
Diaz-Dorado, E., Cidras, J., & Miguez, E. (Aug de
2002). Application of evolutionary algorithms for
the planning of urban distribution networks of
medium voltage. IEEE Trans. Power Syst, 17(3),
págs. 879–884.
Duan, G., & Yixin, Y. (Set de 2003). Power
distribution system optimization by an algorithm for
capacitated steiner tree problems with complexflows and arbitrary cost functions. Electr. Power
Energy Syst, 25(7), págs. 515–523.
Feo, T., & Resende, M. (Mar de 1995). Greedy
randamized adaptive search procedures for Global
Optimization. Journal of Global Optimization, 6(2),
págs. 109-133.
Fernandes, R. F. (2011). Planejamento da Expansão
de Sistemas de Distribuição Usando a
Metaheurística de Busca em Vizinhança Variável.
Dissertação (Mestrado em Engenharia Elétrica),
Universidade Estadual Paulista, Facultade de
engenharia de Ilha Solteira, Ilha Solteira.
Fourer, R., Gay, D. M., & Kernighan, B. W. (2003).
AMPL: A modeling Language for Mathematical
Programming. Pacific Grove, CA: Brooks/ColeThomson Learning.
Franco, J. (2012). Estratégia de Decomposição
aplicada ao Problema de Planejamento da
Expansão de Sistemas de Distribuição. Tese de
doutorado, Universidade Estadual Paulista"Júlio
Mesquita do Filho", Facultade de engenharia de Ilha
Solteira, Ilha Solteira.
Bhowmik,
7
3626