XXXI ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
Inovação Tecnológica e Propriedade Intelectual: Desafios da Engenharia de Produção na Consolidação do Brasil no
Cenário Econômico Mundial
Belo Horizonte, MG, Brasil, 04 a 07 de outubro de 2011.
MINIMIZAÇÃO DE CUSTOS DE
COMBUSTÍVEL EM TRANSPORTE DE
GÁS NATURAL POR GASODUTOS
Camila Pecanha de Paula (UENF)
[email protected]
Jose Ramon Arica Chavez (UENF)
[email protected]
Marcia Cristina Bauman Vieira (UENF)
[email protected]
Diferenças de pressão permitem o transporte de gás natural através de
gasodutos. Diversos fatores geram perda de pressão quando o gás
escoa, a qual deve ser restaurada por estações de compressão, que são
sistemas constituintes dos gasodutoss compostos por conjuntos de
compressores que consomem, como combustível, uma parte do gás
transportado. O custo deste combustível é significativo, donde é
importante determinar configurações dos compressores visando
minimizar esse custo. Aqui se trata desse problema, conhecido como
minimização do custo de combustível de transporte por gasodutos. As
variáveis do problema são as pressões, as vazões de massas de gás
natural nos dutos e a operação ou não de cada compressor nas
estações. Assume-se, diferentemente de trabalhos anteriores, que as
estações de compressão são compostas por compressores não
necessariamente idênticos e se esboça uma técnica GRASP para a qual
é necessário resolver dois subproblemas prévios: 1) como distribuir
vazões massa de gás numa rede sem estações de compressão? 2) como
calcular custos mínimos para uma única estação de compressão? Estes
dois subproblemas são abordados neste trabalho. Experimentos
computacionais apresentam resultados satisfatórios.
Palavras-chaves: gasoduto, custo de combustível, metaheurística,
GRASP
XXXI ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
Inovação Tecnológica e Propriedade Intelectual: Desafios da Engenharia de Produção na Consolidação do Brasil no
Cenário Econômico Mundial
Belo Horizonte, MG, Brasil, 04 a 07 de outubro de 2011.
1. Introdução
A indústria de gás natural envolve os seguintes processos: exploração, perfuração,
desenvolvimento e produção, processamento, transporte, armazenamento e distribuição. Para
ser transportado por gasodutos, o gás se conduz por diferença de pressões. Por diversos
motivos, a pressão deve ser restabelecida, pois se perde quando o gás escoa. As estações de
compressão, compostas por conjuntos de compressores, encarregam-se desse
restabelecimento, consumindo como combustível cerca de 3% a 5% do gás transportado, o
que é significativo devido ao grande volume de gás transportado (Wu et al. 2000). Este
trabalho aborda esse problema, minimização do custo de combustível no transporte de gás por
gasodutos, cujo objetivo é encontrar configurações dos conjuntos de compressores que
minimizem o custo de combustível. Considera-se que os sistemas estão em estado contínuo.
O problema proposto tem merecido a atenção de diversos pesquisadores. Entre os que nos
interessa destacar estão Wu et al. (2000) e Ríos-Mercado et al. (2002), que introduzem um
modelo onde duas das principais hipóteses são a conformação das estações de compressão por
compressores idênticos e o fato de o gás comprimido ser dividido em partes iguais entre os
compressores ativados. Observa-se que a função de custo envolvida é implícita e que as
restrições envolvem funções também não explícitas, não convexas e não diferenciáveis.
Adicionalmente, sabe-se que o problema é NP-Completo (o que significa, grosso modo, que o
número de operações para resolvê-lo aumenta exponencialmente com o tamanho do
problema). Wu et al.(2000) desenvolvem propostas de aproximação suave para a função de
custo e aproximações convexas para as restrições. Sob essas hipóteses, formula-se um
problema de otimização contínua que consiste em determinar quantos compressores devem
operar em cada estação de compressão.
Iamashita (2006) e Iamashita et al. (2008) generalizam o modelo anterior ao relaxar a hipótese
de compressores idênticos. Para tanto, precisam introduzir variáveis binárias para a decisão de
operar ou não cada compressor. Resultando um modelo misto-inteiro quadrático não
diferenciável. Esse modelo foi tratado algoritmicamente, com sucesso, usando técnicas
GRASP. Entretanto, observa-se que os autores consideram compressão apenas em nós de
injeção iniciais (i.e., não consideram compressão em nós intermediários).
Azeredo (2008) generaliza o modelo de Iamashita ao considerar estações de compressão
intermediárias com compressores não necessariamente idênticos. Ela considera aproximações
para a função de custo e para o domínio de viabilidade das estações de compressão baseadas
em Wu et al. (2000). Christo (2008) apresenta um algoritmo para lidar com este modelo
usando técnicas GRASP, inspirado nos resultados apresentados por Iamashita (2006).
Em todos os casos, assume-se que a pressão é conhecida em certo nó (pressão de referência).
Neste trabalho, assume-se que o nó de referência é o primeiro nó de injeção do duto. Esta
hipótese explora melhor as propriedades da função custo.
Recentemente Borraz-Sanchéz e Ríos-Mercado (2009) apresentaram uma outra metaheurística (Busca Tabu) para o modelo de Wu et al. (2000) e Ríos-Mercado et al. (2002), onde
se mantém a hipótese de estações de compressão compostas por compressores idênticos. O
objetivo desta pesquisa é adaptar o algoritmo GRASP desenvolvido em Christo (2008) ao
modelo generalizado por Azeredo (2008). Para tanto, é necessário resolver dois subproblemas
prévios: Subproblema 1 - Dado um gasoduto sem estações de compressão, como atender a
demanda de gás dos nós de entrega (i.e., encontrar ao menos uma distribuição de vazões
massa de gás nos dutos e um conjunto de pressões que permitam essa distribuição,
2
XXXI ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
Inovação Tecnológica e Propriedade Intelectual: Desafios da Engenharia de Produção na Consolidação do Brasil no
Cenário Econômico Mundial
Belo Horizonte, MG, Brasil, 04 a 07 de outubro de 2011.
respeitando as demandas operacionais)? Subproblema 2 - Dadas pressões de entrada (sucção),
de saída (descarga) e uma vazão massa de gás a ser comprimida em uma estação de
compressão composta por compressores não necessariamente idênticos, como minimizar o
custo de operação da estação? Muitas das idéias aqui trabalhadas podem ser encontradas em
Rodrigues (2010).
Este trabalho aborda esses dois subproblemas, sendo organizado da seguinte maneira: na
Seção 2 se descreve o modelo generalizado (estações de compressão compostas por
compressores centrífugos não necessariamente idênticos). Na Seção 3, esboça-se o algoritmo
meta-heurístico GRASP para lidar com o modelo generalizado. Na Seção 4 e Seção 5
apresentam-se diversos experimentos numéricos e termina-se, na Seção 6, com as conclusões.
1. Descrição do modelo generalizado
As unidades de geração de custo são as estações de compressão, formadas por múltiplos
compressores. Diferentemente de Wu et al. (2000) e Ríos-Mercado et al. (2002), neste
trabalho se consideram estações de compressão não necessariamente formadas por
compressores idênticos (estações de compressão generalizadas, ECG), i.e., compostas por K
compressores não necessariamente idênticos.
Como se pode notar na Fig. 1, um gasoduto pode ser associado a um grafo dirigido
G  ( N , L  M ) , onde N é o número de nós (vértices de junção entre os dutos),
L  M  N  N o conjunto de arcos, L o conjunto de dutos e M o conjunto de estações de
compressão. Note que na Fig. 1 tem-se ressaltado, dentro de linhas pontilhadas, as sub-redes
que compõem a rede, onde cada sub-rede se caracteriza por não possuir estações de
compressão intermediárias (as estações de compressão na Fig. 1 estão denominadas por CS1,
CS2, etc.), de forma que as estações de compressão conectam esses sub-grafos. Isto é
conveniente para efeitos de representação, como será visto logo adiante.
Figura1. Exemplo de gasoduto (adaptado de Wu et al, 2000)
Considere a seguinte notação:
3
XXXI ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
Inovação Tecnológica e Propriedade Intelectual: Desafios da Engenharia de Produção na Consolidação do Brasil no
Cenário Econômico Mundial
Belo Horizonte, MG, Brasil, 04 a 07 de outubro de 2011.
-
sa : Vazão massa líquida em a  N . sa  0 , se o nó é de injeção; sa  0 , se o nó é de
entrega; e, s a  0 , se o nó é de é de transbordo.
-
p a : Pressão do gás em a  N . Existe limite inferior e superior para cada pressão, p aL e
p aU , respectivamente. O parâmetro t ab  0 , que se assume conhecido, é a resistência à
passagem do gás pelo duto (a, b)  L .
-
K ab : Número de compressores em (a, b)  M .
-
vabk : Vazão massa no compressor k em (a, b)  M .
-
xabk  {0,1} : Variável de operação do compressor k em (a, b)  M . xabk  1 , se o
compressor k está ativo; xabk  0 , caso contrário.
-
unit
: Domínio de operação do compressor k em (a, b)  M .
Dabk
-
unit
S
D
g abk
(vabk , pab
, pab
) : Função custo de combustível no compressor k
na estação
S
D
unit
S
D
, onde pab
e pab
são as pressões de sucção e
, pab
)  Dabk
(a, b)  M , para (vabk , pab
descarga de (a, b)  M , respectivamente.
-
u ab , v ab : Vazão massa no duto (a, b)  L e na estação (a, b)  M , respectivamente.
Considere que não existem custos associados ao transporte de gás através dos dutos e que a
estação (a, b)  M tem custo medido pela soma dos custos associados a cada compressor que
a compõe. Assim, o custo do gasoduto está dado por:
g
( a ,b )M
ab( v1 ,,vK )
S
D
(vab , p ab
, p ab
)
onde os termos da soma representam o custo de operar os K ab compressores da estação
(a, b)  M , cada com uma vazão massa vabk .
Portanto, o modelo de operação do gasoduto está dado por:
Ka b
minimizar
  g (v ,p ,p )
 u  u  s , a  N
(a,b)M k 1
subjeito a
ab
b:( a ,b )L
Ka b
abk
abk
b:( b ,a )L
S
ab
ba
D
ab
(1)
(1.1)
a
vab   x abk vabk  0, (a, b)  M
k 1
2
b
pa2  p  tabuab uab , (a, b)  L
xabk  0,1, k  1,, K ab , (a, b)  M
pa  [ paL , paU ], a  N
S
D
(vab , pab
, pab
)  Dab , (a, b)  M
(1.2)
(1.3)
(1.4)
(1.5)
(1.6)
4
XXXI ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
Inovação Tecnológica e Propriedade Intelectual: Desafios da Engenharia de Produção na Consolidação do Brasil no
Cenário Econômico Mundial
Belo Horizonte, MG, Brasil, 04 a 07 de outubro de 2011.
onde Dab é o domínio de operação da estação (a, b)  M , definido pela relação (7).
Adicionalmente, além da função objetivo, que representa o custo de operação do gasoduto, as
restrições têm o seguinte significado: (1.1), balanço de massas em cada nó; (1.2), balanço de
massas em cada compressor da estação; (1.3), dinâmica de massas e em cada duto; (1.4),
limites de pressão em cada nó; (1.5), viabilidade do ponto para cada estação.
3. Esboço de uma estratégia GRASP para minimização dos custos de transporte
Para avaliar o desempenho do gasoduto num ponto (v, u, p)  m  l  n (onde m  M , l  L e
n  N ), precisa-se assegurar que este seja um ponto viável de operação do gasoduto. Para
tanto, a estratégia sugerida por Christo (2008) consiste em construir inicialmente uma lista de
vazões massa v candidatas a ser comprimidas nas estações de compressão, para logo
estabelecer para algumas delas, escolhidas aleatoriamente, a possibilidade de associar
pressões p , vazões massa u nos gasodutos, construindo, assim, pontos viáveis de operação
do gasoduto (viabilização de um ponto), calculando custos associados nesse ponto e numa
vizinhança dele. Onde, por ponto viável de operação do gasoduto, entende-se um vetor
(v, u, p)  m  l  n viável para o problema (1). A viabilização do ponto é um item chave da
estratégia meta-heurística e pode ser resumida em dois subproblemas: Subproblema 1 – Dado
um gasoduto sem estações de compressão, como determinar pontos viáveis para o gasoduto
(i.e., determinar pressões p e vazões massa u que permitam atender as demandas do
gasoduto)? Subproblema 2 – Dado um ponto (v, u, p)  m  l  n viável para um gasoduto como
calcular o custo mínimo associado à compressão do vetor v  m pelas respectivas estações
de compressão?
Para melhor apresentar a estratégia de viabilização proposta, é conveniente associar ao grafo
G do gasoduto um grafo reduzido G  , da seguinte forma: considere as sub-redes da rede
original G e comprima-os, de forma a convertê-los em vértices do grafo reduzido G 
(denotadas por SR1, SR2, etc.), conecte logo esses vértices reduzidos por arcos dirigidos
determinados pelas estações de compressão do grafo G .
O objetivo principal da rede reduzida é considerar isoladamente as vazões massa
vSRi  , i  M que escoam pelas estações de compressão da rede original, de forma a usar
esse vetor como parâmetro de um conjunto de subproblemas que consistem em determinar
pressões pSRi e vazões massa uSRi de cada sub-rede SRi, tentando construir pontos viáveis
(v, u, p) para o problema (1). A estratégia está formulada no seguinte pseudo-algoritmo:
Algoritmo 1 (viabilização de um ponto de operação)
Passo 1. Determinar um vetor de vazões massa v  (vSR1 ,, vSRm )  m que resolva o
problema de balanço de massas do grafo reduzido G  . Escolher adequadamente uma sub-rede
SR, definir um dos seus vértices como vértice de referência e fixar o valor da pressão de
referência p REF como o valor do limite superior correspondente à pressão nesse vértice.
Passo 2. Encontrar as vazões massa u SR e pressões p SR para a sub-rede SR (i.e., resolver o
Subproblema 1 para SR!) - note que dessa forma se encontram pressões de sucção ou descarga
para todas as estações incidentes à sub-rede SR.
Passo 3. Para cada uma das estações incidentes à sub-rede SR, determinar, a partir das
pressões de sucção (descarga) encontradas no Passo 2, as respectivas pressões de descarga
(sucção) que minimizem das vazões vi , i  M SR ={estações incidentes à sub-rede SR} e
5
XXXI ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
Inovação Tecnológica e Propriedade Intelectual: Desafios da Engenharia de Produção na Consolidação do Brasil no
Cenário Econômico Mundial
Belo Horizonte, MG, Brasil, 04 a 07 de outubro de 2011.
guardar os custos associados (i.e., resolver o Subproblema 2 para estações incidentes a SR!).
Passo 4. Repetir o Passo 2 e o Passo 3 até esgotar todas as sub-redes.
Passo 5. Caso algum dos passos anteriores não consiga solução (i.e., não consiga determinar
u SR , p SR ou não consiga a operação duma estação de compressão com os respectivos valores
de v ), descartar v como vazão massa viável para os compressores e voltar ao Passo 1. Caso
contrário, definir o vetor vazão massa do gasoduto u , a partir dos vetores u SR , e o vetor
pressão do gasoduto p , a partir dos vetores p SR . O vetor (v, u, p) é um ponto viável para o
gasoduto.
4. Subproblema 1: Determinação de vazões massa e pressões para operação dum
gasoduto sem estações de compressão
Associada ao sub-grafo G se tem a matriz de incidência A  [ Al , Am ] , onde Al é a matriz
(n  l ) de incidência nó-duto e Am é a matriz (n  m) de incidência nó-estação.
Considerando o vetor de vazão de massas decomposto como wT  (uT , vT )  l m , onde u é o
vetor vazão massa através dos dutos L e v o vetor vazão massa através das estações de
compressão M . Assim, as equações de balanço de massas e dinâmica de pressões nos dutos
no modelo (1) podem ser escritas como
Aw= Al u + Amv = s
(2)
AlT p 2 = φ(u) ,
(3)
onde ( p 2 ) T  ( p12 ,, pn2 ) e  (u)T  (t1u1 | u1 |, , tl ul | ul |) . Note que se v for fixado, a
solução (u, p) para o sistema (2)-(3) determina a distribuição do fluxo de massas entre os
dutos e pressões nos nós do gasoduto, se o vetor p estiver dentro do limites requeridos.
Como observado por Ríos-Mercado et al. (2002), é preciso que se fixe a pressão em um dos
nós. Este nó é chamado de nó de referência e seu valor é denotado por pREF . Dadas as
características de função quadrática do sistema (2)-(3), o método de Newton-Raphson
funciona bastante bem para encontrar suas soluções.
A Fig. 1 mostra uma rede com n  48 , l  43 e m  8 , onde as pequenas setas entrando ou
saindo representam a injeção ou entrega de gás, positivas ou negativas, respectivamente. Se as
oito estações de compressão (CS) forem removidas da rede, esta se desconecta, evidenciando
oito sub-redes, que não possuem estações de compressão, a partir do qual se pode construir a
rede reduzida (Fig. 2). Pode-se escolher uma sub-rede adequada (sub-rede de referência) e
num nó dela determinar a pressão de referência dessa sub-rede p REF . Note que todas as subredes da rede original possuem estações de compressão incidentes. Assim, dada uma sub-rede
e uma dada estação incidente nela, esta se diz de sucção ou descarga dependendo de se injeta
ou retira gás da sub-rede.
Observe, por outro lado, que se um vetor v m é candidato a fazer parte da solução do
problema (1), deve satisfazer:
AlRED v  s RED ,
(4)
onde AlRED é a matriz de incidência do grafo reduzido. Sabe-se que a relação (4) tem uma
única solução se e somente se o grafo reduzido for uma árvore.
6
XXXI ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
Inovação Tecnológica e Propriedade Intelectual: Desafios da Engenharia de Produção na Consolidação do Brasil no
Cenário Econômico Mundial
Belo Horizonte, MG, Brasil, 04 a 07 de outubro de 2011.
Seja nSR o numero de sub-redes e v m qualquer solução de (4), o sistema (2)-(3), pode ser
escrito como:
Ali u SRi  s SRi  Ami v, i  1,, nSR ,
(5)
2
( Ali )T p SRi
  (u SRi ), i  1,, nSR ,
(6)
onde Ali , Ami , uSRi e pSRi , para i = 1,,nSR , são partes da matriz de incidência nó-duto, um
rearranjo da matriz de incidência nó-estação e partes dos vetores u e p correspondentes às
sub-redes, respectivamente. O vetor (v, u, p) que satisfaz (4)-(6), é um ponto viável para o
modelo (1), se
p j  [ p Lj , pUj ], j  1, ,n , e (vi , piS , piD )  Di ,i = 1,,m ,
onde Di é o domínio viável da estação de compressão i , definido como:


D  (v, p S , p D ) : v  v1    vK , (vk , p S , p D )  Dkunit or vk  0, k  1,, K ,
(7)
sendo (v1 ,, vK ) uma possível da vazão massa v , que entra na estação, particionada entre os
K compressores que a compõem (ver a definição de Dunit em Azeredo (2008)).
Estas idéias foram utilizadas na elaboração de um código em Matlab que encontra para cada
sub-rede da rede original a distribuição de vazões massa e posteriormente as pressões em cada
nó (i.e., os vetores u e p no sistema (5)-(6)).
Vários experimentos numéricos foram realizados, dos quais se apresentam três a seguir, onde
se consideram as sub-redes SR1, SR2 e SR3 da rede da Fig. 1, considerando os dados
encontrados em Wu et al (2000).
Utilizando como referência para as sub-redes SR1 o nó 1, com pressão de 1300 psia, o nó 3
para SR2, com pressão de 1150 psia, e o nó 9 para SR3, com pressão de 1300 psia,
apresentam-se os resultados nas Tabelas (1) e (2), com a distribuição de fluxos e as pressões
nos nós pertencentes a estas sub-redes
SR1
SR2
SR3
duto
(1,2)
(3,4)
(4,7)
(5,6)
(6,7)
(7,8)
(9,10)
(10,11)
(10,12)
vazão
600
200
400
200
400
1000
200
1000
1100
Tabela 1. Vazão em MMSCFD ( = 106 pés3 por dia)
SR1
nó
1
p
1.300,0
SR2
2
914,9
SR3
3
4
5
6
7
8
9
10
1.150,
1.131,4
1.312,2
1.131,4
1.042,5
920,8
1.300,0
1.354,3
11
12
1.263,0 1.234,8
7
XXXI ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
Inovação Tecnológica e Propriedade Intelectual: Desafios da Engenharia de Produção na Consolidação do Brasil no
Cenário Econômico Mundial
Belo Horizonte, MG, Brasil, 04 a 07 de outubro de 2011.
Tabela 2: Pressões em psia
Com base em (5)-(6), Christo (2008) formula um procedimento de viabilização do vetor v
para a rede original análogo ao Algoritmo 1, considerando a primeira sub-rede a ser tratada
como a determinada pelo nó de referência, o ultimo nó de entrega do grafo original. Neste
trabalho, baseado no fato de que a função de custo de combustível tipicamente decresce com
o aumento da pressão de sucção (Wu et al. 2000), escolhe-se como nó de referência o
primeiro nó de injeção, tentando injetar a vazão de massa (v,u ) com o limite superior de
pressão. Se não for possível, decresce-se pREF , adequadamente, até que se atinja viabilidade
para (v,u ) .
5. Subproblema 2: Cálculo da função de custo de combustível para uma estação de
compressão
Para calcular a função de custo associada a uma estação de compressão é usada a relação (7),
levando em conta que para alguns vetores (v, pS , pD )  D diferentes combinações de
compressores podem ser usadas, donde os custos associados podem ser diferentes
(AZEREDO, 2008). Para este item se desenvolveu um código em Matlab com o objetivo de
encontrar a configuração de custo mínimo de uma estação de compressão generalizada.
O problema abordado consiste do seguinte: Dada uma vazão massa de gás v a ser
comprimida numa estação de compressão generalizada (composta por K A compressores Tipo
A, K B compressores Tipo B, etc.), onde a pressão de sucção é pS e pressão de descarga pD ,
determinar a configuração de ativação de compressores, incluindo, as parcelas de v que cada
um deve comprimir, de forma a obter o menor custo. Para ilustrar o algoritmo desenvolvido, a
seguir, apresenta-se o caso de uma estação de compressão composta por K A compressores
Tipo A e K B compressores Tipo B, sendo K A  2 e K B  3 . Feita a partição da vazão v
entre os compressores A e B ( v A e vB ) em décimos, v é novamente distribuído entre as
combinações pré-definidas, também em décimos. Estas partições se programam
computacionalmente definindo matrizes de alocação entre os tipos de compressores,
chamadas de ListaA e ListaB. Calcula-se, logo, o custo de transporte para cada combinação
viável através de uma sub-rotina (Cálculo do custo). Ao encontrar um custo menor do que o
anterior se atualiza o valor do custo e a respectiva configuração dos compressores ativados.
Ao final dos cálculos tem-se o menor custo de transporte ( CustoTotal ) para os valores de
e
(v, p S , p D )  D ,
ConfiguraçãoFinalB ).
as
configurações
correspondentes
( ConfiguraçãoFinalA
e
Algoritmo 2. (Cálculo do custo mínimo para pontos viáveis)
Passo 1. Ingressar dados (v, p S , p D ) e os dados da ECG. Definir CustoFinal :  . Sejam
Listav , Lista A e Lista B as listas de possíveis partições da vazão massa v  (v A , vB ) , a serem
alocadas entre os compressores Tipo A e Tipo B, e as alocações possíveis dessa partições
entre os compressores Tipo A e Tipo B, respectivamente.
Passo 2. (Cálculo da viabilidade e custo de compressão de possíveis configurações)
Se Listav   , escolher v  Listav . Caso contrário ir ao Passo 6.
8
XXXI ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
Inovação Tecnológica e Propriedade Intelectual: Desafios da Engenharia de Produção na Consolidação do Brasil no
Cenário Econômico Mundial
Belo Horizonte, MG, Brasil, 04 a 07 de outubro de 2011.
Passo 3. Escolher alocações de v A e vB nessas listas. Se estas alocações resultarem viáveis,
calcular os custos associados e o custo total atual: CustoAtual : CustoA  CustoB . Guardar as
alocações de v que originam esses custos: ConfiguraçãoA e ConfiguraçãoB . Retirar as
alocações escolhidas das listas Lista A e Lista B .
fazer
e
CustoAtual  CustoFinal ,
CustoFinal : CustoAtual
ConfiguraçãoFinalA : ConfiguraçãoA e ConfiguraçãoFinalB : ConfiguraçãoB . Repetir o Passo
3, enquanto Lista A   e Lista B   .
Passo
4.
Se
Passo 5. Retirar v  (v A , vB ) da Listav e voltar ao Passo 2.
Passo 6. Gravar CustoFinal , ConfiguraçãoFinalA e ConfiguraçãoFinalB .
O Algoritmo 2 (ver detalhes em Rodrigues (2010)) foi testado em vários exemplos da
literatura. A modo de ilustração apresentam-se resultados para dois exemplos que utilizam
como dados de entrada pontos retirados do domínio encontrado em Wu et al (2000).
Exemplo 1. Para
(v , pS , pD )  (2560, 675, 800) tem-se:
CustoTotal 
6,4083*106;
ConfiguraçãoFinalA  (0, 0, 0); ConfiguraçãoFinalB  (1280, 1280); i.e., o menor custo
encontrado foi de 6408300 MMSCFD (106 pés3 por dia), para os compressores Tipo B
ativados (com uma vazão v de 1280 em cada).
(v, pS , pD )  (2500, 675, 870), tem-se: CustoTotal  9,6978*106;
ConfiguraçãoFinalA  (750, 0, 0); ConfiguraçãoFinalB  (1750, 0); i.e., o menor custo encontrado
foi de 9697800 MMSCFD, para um compressor Tipo A (com uma vazão v de 750) e um
compressor Tipo B (com uma vazão v de 1750) ativados.
Exemplo 2. Para
5. Conclusões
Abordam-se neste trabalho dois subproblemas que se derivam do problema de minimização
de custos de combustível em transporte de gás natural por gasodutos, quando este problema se
aborda heuristicamente: Subproblema 1 – Dado um gasoduto sem compressores, como
distribuir a vazão massa de gás entre os dutos e determinar as pressões nos vértices de forma a
atender as demandas de gás estabelecidas; e Subproblema 2 – Dada certa vazão massa, certa
pressão de sucção e certa pressão de descarga, a ser comprimida por uma estação de
compressão, composta por compressores não necessariamente idênticos, como calcular o
custo mínimo de compressão associado? Sabe-se que problemas de convexidade, não
diferenciabilidade, definição implícita de funções que descrevem as restrições e a função
objetivo, assim como os modelos misto-inteiros quadráticos associados a estes subproblemas
se constituem em problemas NP-completos, pelo que, neste trabalho se abordam por
algoritmos heurísticos.
Desenvolvem-se aqui rotinas computacionais, programadas em ambiente Matlab, rodadas em
um notebook comum, que se comportam muito bem, como mostrado nos experimentos
computacionais aqui indicados.
Pretende-se, no que segue, incluir as rotinas aqui desenvolvidas para compor um algoritmo
GRASP, como sugerido nos trabalhos referenciados.
Referências
9
XXXI ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
Inovação Tecnológica e Propriedade Intelectual: Desafios da Engenharia de Produção na Consolidação do Brasil no
Cenário Econômico Mundial
Belo Horizonte, MG, Brasil, 04 a 07 de outubro de 2011.
AZEREDO, M. M. Aproximações do Domínio e a Função Custo de uma Estação de Compressão no
Transporte de Gás Natural. Campos dos Goytacazes / RJ, Brasil: Dissertação de Mestrado em Engenharia de
Produção, Universidade Estadual do Norte Fluminense Darcy Ribeiro, 2008.
BORRAZ-SÁNCHEZ, C.; RIOS-MERCADO, R. Z. (2009). Improving the operation of pipeline systems on
cyclic structures by tabu search. Computers and Chemical Engineering 33, p. 58–64, 2009.
CHRISTO, A. Z. T. Uma Metaheurística GRASP para o Planejamento de Movimentação de Gás Natural em
Gasodutos. Campos dos Goytacazes / RJ, Brasil: Dissertação de Mestrado em Engenharia de Produção,
Universidade Estadual do Norte Fluminense Darcy Ribeiro, 2008.
IAMASHITA, E. K. Sistema de Planejamento de movimentação de Gás Utilizando metaheurísticas. Macaé /
RJ, Brasil: Tese de Doutorado em Engenharia de Reservatório e de Exploração de Petróleo, Universidade
Estadual do Norte Fluminense Darcy Ribeiro, 2006.
IAMASHITA, E. K.; GALAXE, F.; ARICA, J. A Planning Model for Offshore Natural Gas Transmission.
Pesquisa Operacional, Vol.28, n.1, p.29-44, Janeiro – Abril, 2008.
RÍOS-MERCADO, R. Z.; WU, S.; SCOTT, R. L. BOYD, E. A. A Reduction Technique for Natural Gas
Transmission Network Optimization Problems. Annals of Operations Research, p. 217-234, 2002.
RODRIGUES, P. F. C. Uma Metaheurística GRASP para Minimização do Custo de Combustível no
Transporte de Gás Natural por Gasodutos. Campos dos Goytacazes / RJ, Brasil: Dissertação de Mestrado em
Engenharia de Produção, Universidade Estadual do Norte Fluminense Darcy Ribeiro, 2010.
WU, S.; RÍOS-MERCADO, R. Z.; BOYD E. A.; SCOTT, L. R. Model Relaxations for the Fuel Cost
Minimization of Steady-State Gas Pipeline Networks. Elsevier Science: Mathematical and Computer Modeling,
2000.
10