XXIX ENCONTRO NACIONAL DE ENGENHARIA DE PRODUÇÃO
A Engenharia de Produção e o Desenvolvimento Sustentável: Integrando Tecnologia e Gestão.
Salvador, BA, Brasil, 06 a 09 de outubro de 2009
UMA HEURÍSTICA PARA O PROBLEMA
DA ALOCAÇÃO DE SONDAS DE
PRODUÇÃO EM POÇOS DE PETRÓLEO
Alexandre Venturin Faccin Pacheco (UFES)
[email protected]
Arnaldo Cezar Teixeira Dias Filho (UFES)
[email protected]
Glaydston Mattos Ribeiro (UFES)
[email protected]
Uma atividade de extrema importância no processo de extração de
petróleo é a intervenção dos poços por meio de sondas, processo
chamado de workover. As sondas são um recurso escasso e por esse
motivo muitos métodos para a utilização racionaal das mesmas vem
sendo desenvolvidos. O Problema da Alocação de Sondas de Produção
em Poços de Petróleo (PASPPP) consiste em buscar a melhor
programação das sondas disponíveis de modo a minimizar a perda de
vazão dos poços que estão à espera de manutenção. O presente estudo
propõe uma solução para esse problema utilizando uma heurística de
melhoria chamada de Bubble Swap. Foram estudados também novos
lower bounds, usando a técnica de relaxação, para instâncias
propostas na literatura. Testes computacionais efetuados com essas
instâncias mostram que a heurística Bubble Swap apresenta bons
resultados em um tempo computacional baixo.
Palavras-chaves: heurística de busca local, problema de alocação,
sondas de produção, petróleo
XXIX ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
A Engenharia de Produção e o Desenvolvimento Sustentável: Integrando Tecnologia e Gestão
Salvador, BA, Brasil, 06 a 09 de outubro de 2009
1 Introdução
Desde a sua descoberta no século XX, o petróleo tem sido uma das mais importantes matérias
primas de toda e qualquer indústria, motivo pelo qual ele exerce grande influência no
desenvolvimento e na economia das nações (OLIVEIRA et al, 2007). Sendo assim, muito tem
sido investido no desenvolvimento de novas tecnologias para tornar a extração o mais eficaz,
segura e rentável possível. Uma das maneiras de se obter um melhor rendimento na
exploração de jazidas de petróleo é fazer uso racional dos recursos utilizados, principalmente
dos mais escassos.
Neste contexto estão as sondas de produção de petróleo que são equipamentos utilizados para
iniciar, corrigir ou terminar os trabalhos em um reservatório. Após terminar a perfuração em
um poço, para deixá-lo em condições de operar de forma segura e econômica, efetua-se um
processo denominado completação. Um processo de completação feito de forma adequada
ajuda a minimizar o número de intervenções futuras para manutenção, processo chamado de
workover. Após a completação do poço, segundo Medeiros (2008), ainda podem ser efetuadas
intervenções de avaliação, recompletação, restauração, limpeza, mudança de método de
elevação, estimulação e abandono.
Por apresentarem um custo elevado, as sondas constituem um recurso restrito que causam
perdas consideráveis com a não produção de poços que estão aguardando a realização da
intervenção solicitada (OLIVEIRA et al, 2007). Por isso, o Problema da Alocação de Sondas
de Produção em Poços de Petróleo (PASPPP) tem sido muito estudado, uma vez que propõe a
otimização do uso das sondas visando reduzir a perda de vazão dos poços.
Considerando o contexto acima, o presente trabalho propõe uma heurística de melhoria para o
PASPPP definido conforme Costa & Ferreira Filho (2004; 2005), ou seja:
 inclui janelas de tempo de intervenção (cada poço tem uma data mínima para início dos
trabalhos bem como uma data limite para o término da intervenção);
 exige que todos os poços devem ser atendidos pelas sondas somente uma vez no horizonte
de planejamento estabelecido;
 considera o grupo de sondas homogêneo e que qualquer sonda pode realizar qualquer tipo
de trabalho;
 trata como desprezível o tempo de deslocamento da sonda entre os poços.
Cada poço tem associado um valor de perda de captação que indica o quanto aquele poço
deixa de produzir em unidades de volume por unidade de tempo se ele não for atendido.
Dessa maneira, deve-se alocar às sondas aos poços o mais breve possível para minimizar a
perda de vazão total.
Além da heurística de melhoria denominada Bubble Swap, este trabalho apresenta as soluções
ótimas para uma classe de problemas até então não conhecidas, obtidas por um solver
comercial. Os resultados encontrados pela heurística de melhoria foram, em alguns casos,
melhores que os da literatura.
O restante do trabalho está assim organizado: na Seção 2 é feita uma breve revisão da
literatura e é apresentada a formulação matemática proposta por Costa & Ferreira Filho
(2004); na Seção 3 é explicado o funcionamento da heurística proposta e suas estruturas
2
XXIX ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
A Engenharia de Produção e o Desenvolvimento Sustentável: Integrando Tecnologia e Gestão
Salvador, BA, Brasil, 06 a 09 de outubro de 2009
principais; na Seção 4 são mostrados os resultados computacionais e na Seção 5 são
apresentadas as conclusões e as possibilidades de trabalhos futuros.
2 Revisão da literatura e formulação matemática
O PASPPP possui uma complexidade interessante e por isso a literatura apresenta um
conjunto variado de heurísticas e metaheurísticas para o problema. Costa & Ferreira Filho
(2004; 2005), além de apresentarem um conjunto de instâncias para o PASPPP baseado em
dados reais, apresentaram duas heurísticas construtivas, denominadas HMPT (Heurística de
Máxima Prioridade Tricritério) e HMD (Heurística de Montagem Dinâmica), que geram boas
soluções para o PASPPP. Os resultados obtidos por Costa & Ferreira Filho (2004; 2005) vem
sendo utilizados para comparação desde então.
No campo das metaheurísticas, Alves & Ferreira Filho (2006) apresentaram um Algoritmo
Genético para o PASPPP. Nesse algoritmo, um cromossomo (solução viável para o PASPPP)
é representado por um vetor de números inteiros que indicam poços que necessitam de
intervenção. A função de aptidão de um cromossomo é definida como a perda de vazão
gerada pela solução factível correspondente. Esse algoritmo apresentou, em alguns casos,
resultados melhores que os encontrados por Costa & Ferreira Filho (2004; 2005).
Oliveira et al (2007) apresentaram um Scatter Search para as instâncias propostas por Costa
& Ferreira Filho (2004; 2005). O Scatter Search é um método evolucionário que opera com
uma população de soluções e aplica procedimentos de combinação para gerar novas soluções.
Os autores desenvolveram sete versões do método para o PASPPP.
Costa (2005) implementou um GRASP que não obteve um bom desempenho quando
comparado aos resultados encontrados pelas duas heurísticas apresentadas em Costa &
Ferreira Filho (2004; 2005). O autor atribui este baixo desempenho ao método de busca local
empregado.
Existem outros trabalhos que também utilizam metaheurísticas, mas consideram variações do
PASPPP, ou seja, consideram, por exemplo, a distância entre os poços, o aumento da frota de
sondas se necessário e até mesmo situações de atraso, veja Gouvêa et al (2002), Noronha et al
(2001), Aloise et al (2006), Trindade (2005), Neves (2007) e Neves & Ochi (2007) para mais
detalhes.
No campo dos modelos matemáticos, Costa & Ferreira Filho (2005) apresentaram um modelo
de programação linear inteira com variáveis binárias de decisão. Para estes modelos, cada
poço que necessita de intervenção tem os seguintes atributos associados:
 perda de vazão, que mostra o quando aquele poço esta deixando de produzir, em unidades
de volume por unidade de tempo;
 tempo de intervenção, que depende apenas do tipo de trabalho a ser realizado;
 janela de tempo que determina o período para a intervenção.
Conforme apresentado na Seção 1, as sondas são idênticas e qualquer uma delas pode atender
a qualquer tipo de solicitação.
3
XXIX ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
A Engenharia de Produção e o Desenvolvimento Sustentável: Integrando Tecnologia e Gestão
Salvador, BA, Brasil, 06 a 09 de outubro de 2009
Sendo assim, seja N  {1,2,..., n} o conjunto dos n poços que estão sujeitos à intervenção,
M  {1,2,..., m} o conjunto das m sondas disponíveis, e seja T  {1,2,..., hp} o conjunto dos
instantes de tempo t no horizonte de planejamento hp.
Os valores de tempos e datas são expressos em intervalos inteiros em uma unidade comum
que melhor se adequar ao conjunto de dados. Os parâmetros de entrada a seguir são
considerados conhecidos e determinísticos:


Pi : a perda de vazão dada em m³/unidade de tempo do poço i;
d i : a data de liberação para inicio dos serviços no poço i;
Di : a data para término dos serviços no poço i;

ti : o tempo de serviço no poço i.

A variável de decisão é xikt , binária, sendo xikt  1 quando o poço i é atendido pela sonda k no
instante t; caso contrário, xikt  0 . Logo, o modelo trabalha com m  n  hp variáveis binárias
de decisão.
O modelo matemático de otimização tem como objetivo minimizar a perda de vazão
calculando o produto da vazão perdida Pi pelo tempo de espera até o início da intervenção, ou
seja, (t  ti  d i ) , sendo t o instante da intervenção no poço i. Com isso, o modelo
matemático proposto por Costa & Ferreira Filho (2004) é apresentado a seguir:
hp
n
m
v( PASPPP )  MIN  t  ti  d i Pi xikt
t 1 i 1 k 1
(1)
(PASPPP) Sujeito a:
hp
m
 x
1
i  N
(2)
i  N ; k  M ; t T / Di  ti  t  d i
(3)
k  M ; t T
(4)
xikt  x jkt '  1
i  N ; k  M ; t  T ;
t ' T / t  t '  t  ti ; j  N / j  i
(5)
xikt  0,1
i  N ; k  M ; t T
(6)
ikt
t 1 k 1
xikt  0
n
x
i 1
ikt
1
A restrição (2) indica que cada poço i deve ser atendido exatamente uma única vez e por uma
única sonda. A restrição (3) refere-se a janela de tempo e garante que todo poço i não pode ser
atendido por uma sonda k após o instante Di  ti  nem antes de d i . A restrição (4) garante
que no instante t, uma sonda k inicia o serviço em no máximo um poço i. A restrição (5)
garante que quando uma sonda k inicia os trabalhos no poço i no instante t, ela fica
indisponível para iniciar outros trabalhos nos instantes t’ compreendidos na janela de tempo
t, t  ti  em todos os outros poços j diferentes de i. Conforme indicada por Costa & Ferreira
Filho (2004), a restrição (5) faz uma análise pareada ponto a ponto no espaço das variáveis
4
XXIX ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
A Engenharia de Produção e o Desenvolvimento Sustentável: Integrando Tecnologia e Gestão
Salvador, BA, Brasil, 06 a 09 de outubro de 2009
xikt , analisa sub-planos limitados nos eixos de i e t nos quais só se é permitido a presença de
um único valor 1 nas variáveis contidas nele. Por último, as variáveis xikt são definidas como
binárias em (6).
Costa & Ferreira Filho (2004; 2005) apresentaram instâncias testes com 25, 50, 75, 100 e 125
poços baseadas em dados reais e variaram o número de sondas disponíveis para as
intervenções. O resultado foi à criação de um conjunto de testes que, quando submetidos a um
solver comercial, impõe muitas dificuldades ao processo de solução.
Para avaliar as soluções encontradas com as heurísticas de construção, Costa & Ferreira Filho
(2004; 2005) utilizaram as soluções ótimas das instâncias com 25 poços obtidas com o
CPLEX 9.0. Para as demais, o CPLEX não foi capaz de resolvê-las. Sendo assim, os autores
utilizaram lower bounds (LBs) simples, conforme definido por Barnes (1977). Esses LBs
foram então obtidos utilizando-se o maior valor entre B(n) e a seguinte equação (BARNES,
1977):
 1 
LB   m  1B(n)  2 B(1)
 2m 
(7)
onde B(1) e B(n) representam, respectivamente, a perda total ótima com 1 e n sondas. Para o
calcular B(1), Smith (1956) mostra em seu trabalho que o sequenciamento ótimo para 1 sonda
é obtido quando os poços são ordenados segundo valores decrescentes de Pi/Δti. A esta
seqüência deu-se o nome de “Ordem Natural”.
3 Heurística proposta – Bubble Swap
A heurística proposta neste trabalho é constituída de duas etapas principais: na primeira
busca-se uma solução factível que é então melhorada na etapa seguinte.
Para a primeira etapa, optou-se por gerar uma solução factível através da Heurística de
Máxima Prioridade Tricritério (HMPT), desenvolvida por Costa & Ferreira Filho (2004),
utilizando um dos 3 critérios de ordenação definidos na próxima subseção.
Já a segunda etapa consiste em uma heurística de melhoria, denominada Bubble Swap (BS),
que efetua trocas de poços através de duas estruturas básicas: Bubble Swap Horizontal (BSH)
e Bubble Swap Vertical-Diagonal (BSV-D). Mais abaixo é explicado o mecanismo de
funcionamento dessas estruturas.
O pseudocódigo mostrado na Figura 1 representa, em linhas gerais, a heurística proposta neste
trabalho.
PSEUDOCÓDIGO - HEURÍSTICA PROPOSTA
//Definições e Dados de Entrada:
// Z: No máximo de iterações para o Bubble Swap
// S: No máximo de iterações para a Bubble Swap Horizontal
// R: No máximo de iterações para a Bubble Swap Vertical-Diagonal
// FO: Função objetivo como descrita na Equação (1)
// FO*: Melhor função objetivo encontrada até o momento
// programação*: Melhor programação encontrada até o momento
//Fase I - Heurística de Máxima Prioridade Tricritério
1.
Selecionar um critério;
2.
[programação*, FO*]  Aplicar (HMPT com o critério selecionado);
//Fase II - Bubble Swap
3.
Para z de 1 até Z Faça
4.
Para s de 1 até S Faça
5.
[programação, FO]  Aplicar (BSH);
6.
Se FO < FO*
7.
FO*  FO;
5
XXIX ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
A Engenharia de Produção e o Desenvolvimento Sustentável: Integrando Tecnologia e Gestão
Salvador, BA, Brasil, 06 a 09 de outubro de 2009
8.
programação*  programação;
9.
Para r de 1 até R Faça
10.
[programação, FO]  Aplicar (BSV-D);
11.
Se FO < FO*
12.
FO*  FO;
13.
programação*  programação;
14. Retorne FO* e programação*
Figura 1 - Pseudocódigo da heurística proposta
Uma peculiaridade das instâncias geradas por Costa & Ferreira Filho (2004; 2005) é que,
mesmo os autores modelando matematicamente o problema para resolver instâncias com
janelas de tempo, as instâncias apresentadas possuem janelas de tempo que compreendem
todo o horizonte de planejamento, não sendo então restritivas. Sendo assim, como será visto
mais adiante no detalhamento das duas etapas da heurística de melhoria proposta, não se leva
em consideração a restrição de janelas de tempo. Fato este que não impede a comparação com
outros trabalhos uma vez que todos usaram os mesmos conjuntos de testes, veja Costa &
Ferreira Filho (2004; 2005), Alves & Ferreira Filho (2006) e Oliveira et al (2007).
3.1 Etapa I - programação inicial
A programação inicial tem por objetivo gerar uma solução de boa qualidade para que a etapa
seguinte possa desenvolver a busca local em uma região promissora do espaço de busca.
Tendo em vista a função objetivo, a solução mais intuitiva seria ordenar e programar as
sondas para atenderem primeiro os poços com maior vazão e menor tempo de atendimento.
A partir dessa idéia tem-se o primeiro critério de ordenação: ordenar os poços por ordem
decrescente de vazão e montar uma programação onde os primeiros poços dessa lista sejam os
primeiros a serem atendidos. Esse critério também foi utilizado por Costa & Ferreira Filho
(2004; 2005) junto com dois outros critérios baseados na idéia de “Ordem Natural” de Smith
(1956). Esses dois outros critérios são as ordenações decrescentes por Pi / ti e P
i t i , que
completam os critérios que são abordados para a programação inicial.
Depois de ordenados de acordo com algum dos critérios citados, os poços são alocados à
primeira sonda disponível. A Figura 2 apresenta o pseudocódigo de como proceder com essa
organização. Cabe ressaltar que, no presente trabalho, uma solução para o PASPPP é uma
matriz em que cada linha representa uma sonda e nas colunas têm-se, sequencialmente, os
poços alocados.
PSEUDOCÓDIGO - HEURÍSTICA DE MÁXIMA PRIORIDADE TRICRITÉRIO
1.
2.
3.
3.
4.
5.
5.
6.
Selecione um critério;
Ordene os poços de maneira decrescente de acordo com o critério escolhido;
Programação  []
Enquanto existirem poços não alocados Faça;
Aloque o próximo poço na primeira sonda disponível;
Atualize Programação
FO  Calcular_FO (Programação);
Retorne Programação e FO
Figura 2 - Pseudocódigo da HMPT proposta por Costa & Ferreira Filho (2004)
3.2 Etapa II - método de melhoria da solução inicial
Após a solução inicial ter sido encontrada, inicia-se o processo de melhoria. Para isso foi
desenvolvida a seguinte estratégia: trocar dois poços de posição na programação das sondas e
analisar o efeito dessa troca na função objetivo (FO). Se com a troca a nova solução
apresentar uma FO melhor do que a da solução anterior, a troca é mantida; caso contrário
6
XXIX ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
A Engenharia de Produção e o Desenvolvimento Sustentável: Integrando Tecnologia e Gestão
Salvador, BA, Brasil, 06 a 09 de outubro de 2009
desfaz-se a troca e procede-se com uma nova troca. Esse processo é repetido durante um
número finito de vezes e tem-se ao final a melhor solução encontrada.
O processo de troca é executado como uma Bubble Sort, ou seja, como o método de
ordenação da bolha muito usada para tarefas de ordenamento. Entretanto, as trocas são
executadas horizontalmente na mesma sonda (Bubble Swap Horizontal) e verticalmente entre
sondas distintas (Bubble Swap Vertical-Diagonal).
A Bubble Swap Horizontal (BSH) troca poços entre a mesma sonda. Para aumentar a
possibilidade de uma mudança melhorar a FO, considere um parâmetro denominado Grau de
Troca Horizontal (GTH). A Bubble Sort ordena um vetor ordenando vizinhos diretos dois a
dois, ou seja, entre as posições j e j+1 do vetor. Com o Grau de Troca Horizontal a BSH
pode-se efetuar, não somente testes de trocas entre vizinhos diretos, mas também entre
vizinhos do tipo j e j+1, j e j+2,...,j e j+GTH. Logo, cada um dos poços da programação de
uma sonda poderá ser testado em até GTH posições, já que varia linearmente. A Figura 3
apresenta um exemplo da BSH com GTH = 2.
Bubble Sort
Iteração 1
Iteração 2
Iteração 3
Iteração 4
j
Bubble Swap com GTH=2
j
j+1
j
j
j+1
j
j+1
j
j
j+1
GTH=1
j+GTH
j
j+GTH
GTH=2
j+GTH
GTH=1
j+GTH
GTH=2
Figura 3 – Comparação entre o funcionamento da Bubble Sort com a Bubble Swap Horizontal
Porém, seguindo o conceito da Bubble Sort e considerando que uma solução para o PASPPP é
representada por meio de uma matriz, não seria possível, com a Bubble Swap Horizontal da
Figura 3, trocar um poço alocado na sonda k com um poço de uma outra sonda qualquer. Para
tornar possível esse tipo de troca e ampliar a busca no espaço de soluções viáveis, define-se a
Bubble Swap Vertical (BSV) como a troca entre poços programados em diferentes sondas que
trabalha com um parâmetro definido como Grau de Troca Vertical (GTV). A BSV com o
GTV permite a troca entre o poço j alocada à sonda k (k,j) com o poço j alocado à sonda k+1
(k+1, j), k+2 (k+2, j),..., k+GTV (k+GTV, j). No entanto, a troca é testada e somente é
mantida se ela contribuir para a redução da função objetivo. Para conseguir que um poço
Bubble Swap Vertical
GTV=2
Iteração 1
Bubble Swap Vertical-Diagonal
GTV=2 e GTD=2
(k,j)
(k,j)
(k+GTV,j)
(k+GTV,j)
(k,j)
(k, j)
(k+GTV,j+GTD)
Iteração 2
(k+GTV,j)
7
XXIX ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
A Engenharia de Produção e o Desenvolvimento Sustentável: Integrando Tecnologia e Gestão
Salvador, BA, Brasil, 06 a 09 de outubro de 2009
tenha mais chances de mudar de sonda, esses testes devem ser feitos entre a posição (k,j) e
várias posições da sonda k+GTV, não só com a posição (k+GTV,j). Com isso, Bubble Swap
Vertical ganha mais um parâmetro, o Grau de Trocas Diagonais (GTD), gerando a Bubble
Swap Vertical-Diagonal (BSV-D). Utilizando a BSV-D consegue-se uma grande chance de
trocas bem sucedidas, tendo em vista que um poço poderá efetuar trocas com outros em várias
posições da outra sonda. Na notação adotada, a BSV-D faz trocas entre posições (k,j) e (s,p)
para s=k+1, k+2,.., k+GTV e p=j+0, j+1, j+2,..., j+GTD. A Figura 4 apresenta a idéia das
trocas executadas pelas estruturas Bubble Swap Vertical e Bubble Swap Vertical-Diagonal.
Figura 4 – Comparação entre o funcionamento da Bubble Swap Vertical
com a Bubble Swap Vertical-Diagonal
A utilização conjunta dessas duas estratégias, BSH e BSV-D, garante que trocas poderão ser
efetuadas dentro de uma mesma sonda ou entre sondas diferentes. Antes das trocas serem
efetuadas existe um teste para saber se a troca é plausível ou se em algum momento os valores
j+GTH, k+GTV e j+GTD extrapolam os limites da matriz. Além desses métodos de troca,
existem estruturas na heurística que provocam a repetição de cada um desses métodos um
determinado número de vezes e também a repetição da heurística como um todo. A partir
dessas repetições objetiva-se efetuar o maior número possível de trocas. A Figura 5 apresenta
o pseudocódigo da heurística de melhoria Bubble Swap.
PSEUDOCÓDIGO - HEURÍSTICA DE MELHORIA BUBBLE SWAP
//Definições e Dados de Entrada:
// Z: No máximo de iterações para o Bubble Swap
// S: No máximo de iterações para a Bubble Swap Horizontal
// R: No máximo de iterações para a Bubble Swap Vertical-Diagonal
// GTH: Grau máximo de trocas horizontais
// GTV: Grau máximo de trocas verticais
// GTD: Grau máximo de trocas diagonais
// MAX_POÇOS: Número de poços
// MAX_SONDAS: Número de sondas
// FO: Função objetivo como descrita na Equação (1)
// FO*: Melhor função objetivo encontrada até o momento
// programação*: Melhor programação encontrada até o momento
//Bubble Swap
1. Para z de 1 até Z Faça
2.
Para d de (-GTD) até GTD Faça
3.
Para v de 1 até GTV Faça
4.
Para r de 1 até R Faça
5.
Para j de 1 até MAX_POÇOS Faça
6.
Para i de 1 até MAX_SONDAS Faça
7.
Troque [i][j] com [i+GTV][j+GTD];
8.
Se FO < FO*
9.
FO*  FO;
10.
programação*  programação;
11.
Senão
12.
Desfaça a troca;
13.
Para h de 1 até GTH Faça
14.
Para s de 1 até S Faça
15.
Para j de 1 até MAX_POÇOS Faça
16.
Para i de 1 até MAX_SONDAS Faça
17.
Troque [i][j] com [i][j+GTH];
18.
Se FO < FO*
19.
FO*  FO;
20.
programação*  programação;
21.
Senão
22.
Desfaça a troca;
23. Retorne FO* e programação*
Figura 5 – Pseudocódigo da Bubble Swap
4 Resultados Computacionais
8
XXIX ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
A Engenharia de Produção e o Desenvolvimento Sustentável: Integrando Tecnologia e Gestão
Salvador, BA, Brasil, 06 a 09 de outubro de 2009
Para fins de comparação foram utilizadas as instâncias geradas por Costa & Ferreira Filho
(2004; 2005). Os testes foram executados em um computador equipado com um processador
Pentium Core 2 Duo com 1,8GHz e 1 GB de memória RAM.
Para tentar melhorar os LBs propostos por Costa & Ferreira Filho (2004; 2005) novos testes
computacionais foram realizadas como CPLEX 10 (Ilog, 2006). Entretanto, os experimentos
mostraram que essa versão foi capaz apenas de encontrar as soluções ótimas das instâncias
com até 50 poços e 10 sondas.
Para os demais problemas apresentados por Costa & Ferreira Filho (2004; 2005), ou seja,
problemas com 75, 100 e 125 poços, o CPLEX 10 não conseguiu ler os dados, parando por
falta de memória. Sendo assim, optou-se por uma relaxação de programação linear.
Novamente por falta de memória, o CPLEX 10 não foi capaz de gerar LBs para problemas
com 75, 100 e 125 poços. Diante de todas as condições adversas, um estudo foi realizado para
avaliar o impacto das restrições no processo de otimização e na qualidade da solução gerada.
Com isso, verificou-se que o conjunto de restrições definido em (5) cresce consideravelmente
para as instâncias maiores. Em alguns casos têm-se 50 milhões de restrições. Então, optou-se
por uma relaxação simples do modelo (1)-(6) que se constitui na remoção da restrição (5) do
modelo matemático, denominada PASPPPREL.
Não há garantias de que a solução relaxada obtida para uma instância qualquer seja uma
solução factível, entretanto, considerando a teoria de relaxação, com a remoção da restrição
(4), tem-se um LB.
A Tabela 1 apresenta os principais resultados encontrados para as instâncias com 25 e 50
poços. Cabe destacar que o nome da instância indica também o número de sondas e poços
utilizado. Por exemplo, a instância “P25A-10” indica 25 poços e 10 sondas. Para essas
instâncias o CPLEX encontrou as soluções ótimas. Nos testes computacionais com a
heurística Bubble Swap foram adotados os seguintes valores para os parâmetros de entrada:
Z=20, GTD=6, GTV=MAX_SONDAS, R=1, GTH=4 e S=5. Os parâmetros MAX_SONDAS e
MAX_POÇOS variam de acordo com a instância: para a instância PXA-Y, MAX_SONDAS=Y
e MAX_POÇOS=X.
Analisando primeiramente os valores obtidos para a relaxação PASPPPREL percebe-se
claramente que, na medida em que o número de sondas aumenta, v(PASPPPREL) se aproxima
de v(PASPPP).
CPLEX 10
Instância
BUBBLE SWAP
PASPPPREL
PASPPP
Alves &
Ferreira
Filho (2006)
Costa &
Ferreira Filho
(2004; 2005)
Oliveira et
al (2007)
v(PASPPP)
T(s)
v(PASPPPREL)
T(s)
Solução
T(s)
Solução
Solução
Solução
P25A-1
28911*
1,47
15479
0,11
28911*
0,045
28917
28911*
-
P25A-2
16329*
2,12
10608
0,50
16332
0,045
16329*
16421
16338
P25A-4
10312*
2,09
8232
0,03
10338
0,045
10314
10348
10358
P25A-6
8497*
3,47
7571
0,05
8525
0,045
8497
8555
8561
P25A-8
7733*
4,84
7217
0,05
7735
0,045
7733
7735
7772
P25A-10
7322*
6,56
7054
0,06
7325
0,045
7323
7329
7352
P50A-1
125458*
16,24
Não Obtido
-
125458*
0,186
125471
125458*
-
P50A-2
66904*
32,11
2913
0,17
66926
0,189
66947
66920
67834
9
XXIX ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
A Engenharia de Produção e o Desenvolvimento Sustentável: Integrando Tecnologia e Gestão
Salvador, BA, Brasil, 06 a 09 de outubro de 2009
P50A-4
37891*
95,29
21608
0,19
37908
0,292
37891*
37936
38232
P50A-6
28369*
92,42
19196
0,13
28420
0,294
28369*
28485
28674
P50A-8
23788*
44,18
17996
0,23
23810
0,138
23793
23839
24083
P50A-10
21348*
84,38
17342
0,30
21390
0,138
21352
21409
21488
*Soluções ótimas
Tabela 1 – Resultados obtidos para as instâncias de 25 e 50 poços
Considerando a Tabela 1 e comparando-se os resultados da heurística Bubble Swap (BS) com
os resultados encontrados por Alves & Ferreira Filho (2006), Costa & Ferreira Filho (2004;
2005) e Oliveira et al (2007), percebe-se que a BS apresentou resultados semelhantes aos
melhores conhecidos, veja valores em negrito. Repare, entretanto, que a heurística Bubble
Swap utilizou um tempo computacional muito baixo. No pior caso, a heurística precisou de
0,30s.
A Tabela 2 apresenta os resultados obtidos para as demais instâncias. Percebe-se que, na
maioria dos casos, o limitante obtido com a relaxação PASPPPREL é melhor que o limitante de
Barnes (1977), ou seja, é maior. Essa informação é interessante, pois permite melhor avaliar
os resultados das heurísticas uma vez que as soluções ótimas dessas instâncias não são
conhecidas.
CPLEX 10
Instância
PASPPP
BUBBLE
SWAP
PASPPPREL
LB Barnes
v(PASPPPREL)
(1977)
Alves & Ferreira Costa & Ferreira Oliveira
Filho (2006)
Filho (2004; 2005) et al (2007)
T(s)
Solução
T(s)
Solução
Solução
Solução
P75A-1
356265
118911
0,5
356265
0,093
356318
356265
-
P75A-2
102405
75123
0,48
187339
0,234
187339
187358
192536
P75A-4
38930
53279
0,53
103301
0,327
103302
103364
106534
P75A-6
34905
46069
0,66
75602
0,375
75583
75871
77714
P75A-8
34905
46576
0,73
62048
0,513
61893
62179
63600
P75A-10
34905
40475
0,92
53956
0,561
53888
54099
55171
P100A-1
578724
158755
1,39
578724
0,327
579650
578724
-
P100A-2
159010,75
96416
1,34
299105
0,375
299243
299093
319162
P100A-4
54200,375
65433
1,51
160007
0,561
160176
160016
169671
P100A-6
37857
55115
1,88
114372
0,654
114479
114456
120377
P100A-8
37857
50142
2,67
91875
0,702
91844
91954
96736
P100A-10
37857
47189
3,00
78478
0,795
78462
78541
83552
P125A-1
741641
211130
2,89
741641
0,513
744459
741641
-
P125A-2
199627,5
122173
2,92
380674
0,654
382001
380631
413843
P125A-4
64070
77919
3,36
200471
0,888
200969
200408
218513
P125A-6
38961,3
63182
4,84
140634
1,077
141000
140648
152420
P125A-8
37248
55915
6,31
110980
1,311
111059
111015
119365
P125A-10
37248
51561
7,84
93159
1,404
93308
93280
103265
Tabela 2 – Resultados obtidos para as instâncias de 75, 100 e 125 poços
10
XXIX ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
A Engenharia de Produção e o Desenvolvimento Sustentável: Integrando Tecnologia e Gestão
Salvador, BA, Brasil, 06 a 09 de outubro de 2009
Os resultados apresentados na Tabela 2 mostram que a Bubble Swap apresenta resultados tão
bons quanto as demais heurísticas. Cabe ressaltar que para algumas instâncias os resultados
encontrados pela Bubble Swap foram melhores que os reportados na literatura. Entretanto,
mesmo com resultados e LBs melhores, não foi possível definir novas soluções ótimas. Veja
por exemplo a instância P125A-10 em que v(PASPPPREL) = 51561 e Bubble Swap = 93159, o
(93159  51561)
que produz o seguinte gap: gap 
100  44,65% . Isso mostra que novas
93159
pesquisas devem ser realizadas para tentar fechar os gaps residuais.
Considerando as Tabelas 1 e 2, os resultados mostram que para instâncias de pequeno porte, o
AG proposto por Alves & Ferreira Filho (2006) obtém melhores resultados, com exceção das
instâncias com um único poço. Somente a partir das instâncias de 75 poços que a Bubble
Swap começa a obter melhores resultados. Em especial, para 125 poços a heurística proposta
neste trabalho apresenta a maioria dos melhores resultados.
Pode-se perceber também que a Bubble Swap obteve um desempenho superior ao Scatter
Search (OLIVEIRA et al, 2007) em todos os testes e superou as heurísticas HMPT e HMD,
propostas por Costa & Ferreira Filho (2004; 2005), na maioria dos casos.
5 Conclusões e Futuros trabalhos
Neste trabalho foi proposta uma heurística de melhoria denominada Bubble Swap (BS) para
solucionar o Problema da Alocação de Sondas de Produção em Poços de Petróleo (PASPPP).
As soluções obtidas pela BS se mostraram interessantes para problemas com 25 e 50 poços
quando comparadas com as soluções ótimas do CPLEX.
Para instâncias com 75, 100 e 125 poços, percebe-se que os resultados da BS foram, em
muitos casos, melhores do que aqueles apresentados na literatura. Cabe ressaltar ainda que a
BS é muito rápida. No pior caso, a BS utilizou menos de 2,0s para encontrar uma solução.
Além da BS, este trabalho também apresentou novos lower bounds (LBs) para algumas
instâncias. Esses limitantes podem ser utilizados para se avaliar novas soluções para o
PASPPP.
Em trabalhos futuros, serão estudadas novas estruturas para serem adicionadas ao BS que
proporcionem alguma aleatoriedade no mecanismo da heurística, tal que novos e melhores
resultados sejam obtidos.
Referências
ALOISE, D.; NORONHA T.F.; MAIA R.S.; BITTENCOURT, V.G. & ALOISE D.J. Heurística de colônia
de formigas com path-relinking para o problema de otimização da alocação de sondas de produção terrestre.
Em Anais do XXXIV Simpósio Brasileiro de Pesquisa Operacional, 2002.
ALVES, V.R.F.M. & FERREIRA FILHO, V.J.M. Proposta de algoritmo genético para a solução do
problema de roteamento e sequenciamento de sondas de manutenção. Em Anais do XXXVIII Simpósio
Brasileiro de Pesquisa Operacional, p. 1837-1845, 2006.
BARNES, J.W.; BRENNAN, J.J. & KNAP, R.M. Scheduling a Backlog of Oil well Workovers, Journal of
Petroleum Technology, v., n., p. 1651-1653, 1977.
COSTA, L.R. Soluções para o problema de otimização de itinerário de sondas. Dissertação de Mestrado,
Universidade Federal do Rio de Janeiro, 2005.
11
XXIX ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
A Engenharia de Produção e o Desenvolvimento Sustentável: Integrando Tecnologia e Gestão
Salvador, BA, Brasil, 06 a 09 de outubro de 2009
COSTA, L.R. & FERREIRA FILHO, V.J.M. Uma heurística de montagem dinâmica para o problema de
otimização de itinerários de sondas. Em anais do XXXVII Simpósio Brasileiro de Pesquisa Operacional, p. 112, 2005.
FERREIRA FILHO, V.J.M. & COSTA, L.R. Uma Heurística para o Problema do Planejamento de
Itinerários de Sondas em Intervenções de Poços de Petróleo. Em anais do XXXVI Simpósio Brasileiro de
Pesquisa Operacional, v.1. p. 1844-1853, 2004.
GOUVÊA, E. F.; GOLDBARG, M.C. & COSTA, W.E. Algoritmos evolucionários na solução do problema
de otimização do emprego de sondas de produção em poços de petróleo. Em anais do XXXIV Simpósio
Brasileiro de Pesquisa Operacional, 2002.
ILOG. Ilog Cplex 10.0: Reference manual. France: [s.n.], 2006. 610 p.
MEDEIROS,
A.C.R.
Completação
de
poços
Notas
de
Aula,
disponível
em
<http://www.lenep.uenf.br/~bueno/DisciplinaIntroducaoEngenhariaPetroleo/Aulas/Aula-03-Completacao-01TiposEtapas/Aula-03-Completacao-01-TiposEtapas-AnaCatarina.ppt>, Acesso em 28/04/2009 às 23:26h.
NEVES, T.A. Heurísticas com memória adaptativa aplicadas ao problema de roteamento e scheduling de
sondas de manutenção, Dissertação de Mestrado, Universidade Federal Fluminense, 2007.
NEVES, T.A & OCHI, L.S. GRASP com Memória Adaptativa aplicado ao Problema de escalonamento de
sondas de manutenção. Em anais do XXVII Congresso da Sociedade Brasileira de Computação – Encontro
Nacional de Inteligências Artificial, v. 1. p. 1242-1251, 2007
NORONHA, T.F.; LIMA, F.C.J & ALOISE, D.J. Um algoritmo heurístico guloso aplicado ao problema do
gerenciamento das intervenções em poços petrolíferos por sondas de produção terrestre. Em anais do XXXIII
Simpósio Brasileiro da Pesquisa Operacional, p. 135-135, Campos do Jordão, SP, 06 a 09 de novembro de 2001.
OLIVEIRA, E.F.; PAGOTO, F.B.; SILVA, F.T. & LORENZONI, L.L. Scatter Search aplicado ao
problema de otimização de sondas de produção terrestre. Em anais do XXVII Encontro Nacional de Engenharia
de Produção, p. 1-10, 2007.
SMITH, W. E. Varios Optimazers for Single Stage Production, NRLQ., v. 2, pp. 59-66, 1956
TRINDADE, V.A. Desenvolvimento e análise experimental da metaheurística GRASP para um problema de
planejamento de sondas de manutenção, Dissertação de Mestrado, Universidade Federal Fluminense, 2005.
12