-
256
1 Introdução
2~ SIMPÓSIO BRASILEIRO DE AUTOMAÇÃO INTELIGENTE
No Estado de São Paulo, a produção e distribuição dos derivados
de petróleo é feita através de um conjunto de refinarias e
terminais da Petrobrás. As refinarias processam o petróleo cru nos
seus diversos derivados ~ os quais são distribuídos aos mercados
consumidores através dos terminais. Estes mercados estabelecem o
planejamento tanto da produção dos derivados nas refinarias quanto
da demanda nas bases (refinarias ou terminais). Embora a
distribuição seja feita nas refinarias e terminais , a produção é
concentrada apenas nas refinarias por questões economicas. Isto
implica na necessidade de transporte entre bases , o qual é feito ,
em sua grande maioria , por meio de uma rede de dutos que as
interligam. Entretanto , na eminência de desabastecimento, podem
ser usados caminhões. Nesse problema, o objetivo principal da
Petrobrás está em encontrar uma solução que atenda as demandas e
reduza os custos de transporte . Além disso, deve satisfazer as
restrições tecnológicas e temporais.
Este artigo propõe uma sucinta definição do problema, a qual
procura agregar as suas reais características. A partir dessa
definição , é desenvolvido um modelo , em programação matemática
[WiI78] , caracterizado por sua estrutura de fluxo em rede com
multi-períodos [LN93 , JB80]. As equações presentes no modelo são
todas lineares e isto permite , pelo menos no âmbito teórico , a
aplicação de Métodos de Otimização Linear. Além do modelo , são
apresentados alguns resultados obtidos na sua solução para uma
instância do problema.
2 Definição do Problema
A definição de um problema envolve pelo menos dois aspectos: os
dados e a solução. Em particular . o presente problema se
classifica como de Otimização Combinatória [NW88] e, portanto , é
caracterizado por uma função objetivo, a qual quantifica a solução
encontrada.
A rede de transporte é o primeiro dado do problema,
exemplificada pela figura 1, e possui as informações das
características das bases e dos dutos. As bases apresentam
capacidades de armazenamento e os dutos possuem capacidades e
vazões que dependem dos produtos e do sentido do transporte. Os
mercados consu-midores estabelecem as campanhas de produção e
demanda diárias de cada produto em cada base. Além desses dados, a
situação da rede também faz parte dos dados de entrada. Essa
situação é representada por quais produtos, e suas respectivas
quantidades , estão armazenados nos dutos e bases da rede. A rede
está sujeita a falhas e os mercados não são estáveis, o que implica
na característica dinâmica do problema. Para resolver essa questão,
assumir-se-á uma situação estática a cada evento dinâmico.
A solução do problema está em encontrar o fluxo de produtos nos
dutos, o qual garanta o abastecimento dos mercados e também atenda
as restrições tecnológicas e temporais. Como restrição tecnológica,
cita-se a seqüência em que os produtos são transportados, tendo em
vista que, para cada produto existe apenas um subconjunto de
produtos que podem entrar em contato com o mesmo. As restrições
temporais , por sua vez, estão relacionadas com a disponibilidade
de produto e a capacidade de armazenamento no momento da execução
de uma operação de transporte.
É interesse da Petrobrás reduzir os custos de transporte e de
operação do sistema. Entretanto, o objetivo principal tem se
limitado ao atendimento das demandas, dado que o sistema é
programado exclusivamente através da interação humana. Isso
justifica a busca de um método automático capaz de encontrar uma
solução que reduza esses custos.
3 Modelo em Programação Matemática
A apresentação do modelo será feita através de um pequeno
exemplo cuja rede é formada por duas bases , A e B, interligadas
por um duto. Dado que o duto possui capacidade CAPDUTO, ele será
representado por um conjunto de vértices , cada qual representando
um segmento do duto , tal que cada vértice possua a capacidade
equivalente à vazão durante um período de tempo. A rede resultante
da representação de dutos por vértices é replicada quantos forem os
períodos utilizados. Na figura 2 está ilustrada a rede do exemplo
com um período e o duto com dois vértices. Nessa rede , os arcos
representam os possíveis transportes (6 , 7, 9, 10 , 12 e 13) , o
estado inicial (1 , 2, 3 e 4) e as campanhas de produção e demanda
das bases (15 , 16 , 21 e 22) . O vértice que representa o segmento
do duto mais próximo à base A, no início do período 1, possui
quatro arcos: 2, 7, ...
-
.~
~~ ~ -~
/
2! SIMPÓSIO BRASILEIRO DE AUTOMAÇÃO INTELIGENTE
IUICAP - CA7fJAVA
257
Figura 1: representação gráfica da rede de transporte da
Petrobrás no Estado de São Paulo. Os rótulos dos vértices do grafo
identificam as refinarias e terminais . REPLAN , por exemplo,
identifica a Refinaria de Paulínea.
8 e 9, representando as quantidades , respectivamente.
inicialmente armazenada, transferida para A, restante no seg~ento e
transferida para o outro segmento do duto durante o período 1. O
modelo exemplo considera que apenas dois produtos (G e Q) podem ser
transportados na rede. As variáveis xnp indicam a quantidade de
produto p E {G , Q} que foi transportada através do arco n E {1, 2,
... , 22}. As variáveis Ynp são variáveis binárias que indicam qual
produto está armazenado, no início de um período, em um dado
segmento. Por exemplo, YnG = 1 indica que o segmento para o qual o
arco n é incidente possui o produto G no início do período
correspondente. A partir das definições acima, seguem abaixo as
restrições do modelo , classificadas por suas respectivas funções
.
1. Restrições que estabelecem o estado inicial do sistema.
(a) Restrições de produtos armazenados nos dutos, onde CAPDUTO é
a capacidade do duto. Assume-se que somente o produto G está
inicialmente armazenado no duto .
X2G CAPDUTO/2 x2Q O
Y2G 1
Y2Q O
x3G CAPDUTO/2 x3Q O
Y3G 1
Y3Q O
-
258
2.
BASE A"""""",
INICIO DO PERIODO 1
INICIO DO PERIODO 2
17 18 19
2! SIMPÓSIO BRASILEIRO DE AUTOMAÇÃO INTELIGENTE
....
20
........ BASE B .'
Figura 2: Rede correspondente ao exemplo com duas bases, um
período e dois vértices por duto.
(b) Restrições de estoque nas bases, onde ESTpb indica o estoque
inicial do produto p E {G, Q} arma-zenado na base b E {A, B}. .
1 X1G ESTGA X1Q ESTQA X4G ESTGB X4Q = ESTQB
Conservação de fluxo no início dos períodos 1 e 2.
xlG = x5G + x6G x6G + x7G + x16G x16G + x17G xlQ = x5Q + x6Q x6Q
+ x7Q + x15Q = x16Q + x17Q x2G = x7G + xaG + x9G x6G + xaG + xl0G
xlaG x2Q = x7Q + xaQ + x9Q x6Q + xaQ + xl0Q = xlaQ x3G = xl0G +
xllG + x12G x9G + xllG + x13G x19G x3Q xl0Q + xllQ + x12Q x9Q +
xllQ + x13Q = x19Q x4G = x13G + x14G x12G + x14G + x21G x20G + x22G
x4Q = x13Q + x14Q x12Q + x14Q + x21Q x20Q + x22Q
3. Produção e demanda nas bases durante o período 1, onde
PRODpbt (DEMpbt) é a produção (demanda) do produto p na base b
durante período t.
x16G PRODGAl x15Q PRODQAl x16G = DEMGAl x16Q = DEMQAl X21G =
PRODGBl x21Q PRODQBl x22G = DEMGBl x22Q = DEMQBl
4. Capacidade de armazenamento nas bases no início do período 2,
onde CAPpb é a capacidade de arma-zenamento do produto p na base
b.
1 X5G + X7G + X15G X5Q + X7Q + X15Q X12G + X14G + X21G X12Q +
X14Q + X21Q
< CAPGA < CAPQA < CAPGB < CAPQB
.. ~
-
22 SIMPÓSIO BRASILEIRO DE AUTOMAÇÃO INTELIGENTE 259
5. Restrições que garantem armazenamento de um único produto, no
início de cada período, em cada segmento do duto.
XSG + XSG + xl0G xSQ + xSQ + xl0Q Y8G + YSQ x9G + xllG + x13G
x9Q + xllQ + x13Q YllG + YllQ
= (YsG)·(CAPDUTO/2) (Y8Q)·(CAPDUTO/2)
1 (YllG)'( CAPDUTO/2) (YllQ)·(CAPDUTO/2)
1
6. Restrições que garantem fluxo comum em todos os segmentos do
duto.
Xl0G + xl0Q x13G + x13Q
x9G + x9Q x12G + x12Q
7. Restrição de capacidade no duto.
{XSG + xSQ + x7G + x7Q ~ CAPDUTO/2
8. Restrições de precedência dos produtos nos dutos, onde
assume-se que o produto G pode entrar em contato com o produto Q e
vice-versa.
{ Y8G
Y8Q
< YllG + Yl1Q < Yl1G + YllQ
o modelo em programação matemática se completa ao acrescentar-se
a função objetivo ao conjunto de restrições acima. Abaixo segue a
função objetivo, a qual procura minimizar os custos de
transporte.
Minimize
Se o modelo exemplo apresentasse três produtos, G, Q e p, tais
que apenas Q e D não pudessem entrar em contato, as equações que
garantem a precedência dos produtos nos dutos seriam dadas pelas
equações abaixo.
{
YSG Y8Q Y8D
< Yl1G + Yl1Q + YllD < Yl1G+Yl1Q < YllG + YllD
Para uma rede com t períodos, n bases, m dutos, p produtos e q
vértices correspondentes a segmentos de dutos, o número de
variáveis e restrições é da ordem de O(mpt + npt + qpt) [CLR90].
Dado que normalmente q > Max{m, n}, o número de variáveis e
restrições pode ser aproximado para O(qpt).
4 Resultados
Na intenção de averiguar a aplicabilidade prática do modelo,
implementou-se um código para gerar o modelo correspondente ao
problema da Petrobrás. O modelo foi então otimizado através do
otimizador CPLEX 3.0 [CPL94], que é capaz de resolver problemas de
programação linear, com variáveis contínuas e inteiras, usando os
algoritmos Simplex [BJ77] e Branch-and-Bound [NW88].
Os dados de entrada para o modelamento são os dados descritos na
definição do problema. Em particular, existem dois parâmetros que
afetam profundamente o tamanho da rede e, conseqüentemente, o
número de variáveis e restrições. O primeiro parâmetro é o
intervalo de tempo entre cada período. Por razões operacionais, as
operações de transporte entre as bases da Petrobrás não são
inferiores a uma hora de duração, o que indica que o intervalo de
tempo adequado para cada período deve ser de, aproximadamente, uma
hora. O outro parâmetro é o tempo total que a rede deve abranger a
partir do instante corrente. A
-
260 2' SIMPÓSIO BRASILEIRO DE AUTOMAÇÃO INTELIGENTE
partir da experiência adquirida pelo grupo responsável pela
programação do sistema da Petrobrás, a rede deve abranger não menos
do que sete dias . Esta exigência é proveniente da grande
capacidade e distância de alguns dutos. Tais dutos podem armazenar
cerca de 42 .000m3 e o bombeamento de produto de uma extremidade
para outra pode levar mais do que quatro dias. A rede resultante
para o problema apresenta intervalo de uma hora para cada período,
n = 14 bases, m = 28 dutos, p = 7 produtos derivados de petróleo ,
t = 168 períodos e um total de q = 280 vértices correspondentes a
segmentos de dutos . Para uma rede com intervalo de quatro horas
para cada período, q = 82 vértices , t = 12 períodos (dois dias) e
p = 7 produtos, a relaxação linear consumiu cerca de quatro horas
de cpu em uma máquina Sun modelo SparcServerlOOO.
5 Conclusões
Apesar dos avanços obtidos durante as últimas duas décadas na
área de Transporte [DDSS93] , ainda existem muitos problemas de
cunho prático e teórico a serem resolvidos como, por exemplo, o da
Petrobrás tratado neste artigo. A partir de uma dificuldade
concreta, a qual envolve questões estratégicas de uma grande
empresa, um problema foi definido e modelado matematicamente.
Embora o modelo esteja bastante próximo da realidade, os métodos
exatos utilizados não se mostraram eficientes para solução do
problema. Para um modelo com dimensões inferiores às reais
necessidades, o tempo de cpu foi exageradamente elevado, mesmo
utilizando um otimizador de reconhecida eficiência (CPLEX 3.0) , em
uma máquina rápida como a SparcServerlOOO. Esses resultados indicam
que as abordagens exatas provavelmente não são adequadas ou faz-se
necessário o desenvolvimento de técnicas exatas específicas para o
problema em questão. Uma alternativa para solução do problema é o
desenvolvimento de algoritmos heurísticos [MM81] que possam
encontrar soluções aproximadas ou sobre o modelo matemático ou
sobre os requisitos do problema. Uma abordagem heurística de
decomposição do problema já foi proposta pelos autores [CdS95] . A
extensão dessa abordagem decompõe o problema em três etapas. A
primeira é constituída pela etapa de geração de jobs (operações de
transporte) que devem ser executados a fim de suprir as demandas. A
segunda etapa é formada pela busca de rotas que conectam a base
produtora à base consumidora de cada job. Por fim, a última etapa
corresponde ao escalonamento dos jobs através de um Job Shop
Scheduling [Bak74] modificado, onde os dutos são as máquinas e as
rotas são as listas de tarefas dos jobs.
Referências
[Bak74] K. R. Baker. Introduction to Sequencing and Scheduling.
John Wiley, 1974.
[BJ77] M. Bazaraa and J. Jarvis. Linear Programming and Network
Flows. John Wiley & Sons, 1977.
[CdS95] E. Camponogara and P. S. de Souza. A solução de um
problema de transporte através de sua decomposição. In XXII
Seminário Integrado de Software e Hardware, 1995.
[CLR90] T. H. Cormen, C . E. Leiserson, and R. L Rivest.
Introduction to Algorithms. MIT Press, 1990.
[CPL94] CPLEX Optimization, Inc. Using the CPLEX Callable
Library, 1994.
[DDSS93] J. Desrosiers, Y. Dumas, M. M. Solomon, and F. Soumis.
Time Constrained Routing and Sche-duling. September 1993.
Forthcoming in Handbooks in Operations Research and Management
Science.
[JB80]
[LN93]
P. A. Jensen and J. W . Barnes. Network Flow Programming. John
Wiley, 1980.
A. R. Lari and B. N. Nag. A model management solution system for
multicommodity network flows. European Journal of Operational
Research, 71:398-418, 1993.
[MM81] H. Muller-Merbach. Heuristics and their design: a survey.
European Journal of Operational Research, 8, 1981.
[NW88] G. Nemhauser and L. Wolsey. Integer and Combinatorial
Optimization. John Wiley & Sons, 1988.
[WiI78] H. P. Williams. Afodel Building in Mathematical
Programming. John Wiley & Sons, 1978.
