Um conjunto de poços de petróleo geograficamente disperso, de localização conhecida e com potencial de produção conhecido, deve ser perfurado por um conjunto de 3 sondas. Deseja-se obter rotas para as sondas de modo a maximizar a produção dentro do horizonte de planejamento. Uma busca junto a base de dados da ANP forneceu a localização de 20 poços, distribuídos entre as bacias do Espírito Santo, Campos e Santos. São dados para cada poço o tempo de construção do poço e o potencial de produção esperado. Considere como restrições do problema: cada poço deve ser visitado exatamente uma vez; cada sonda só opera em um poço por vez.
Produção de petróleo Tempo de contrucao
Sigla Nome do poço Bacia Operador Latitude Longitude Data Inicio Data Final
PEREGRINO A Peregrino A Campos Statoil Brasil -23:20:01,820 -41:17:52,700 41.020,48 bbl/dia 13/02/2014 17/02/2014
PEREGRINO B Peregrino B Campos Statoil Brasil -23:17:43,577 -41:12:26,564 42.330,31 bb//dia 12/10/2013 19/02/2014
P-25 PETROBRAS 25 Campos Petrobras -22:06:32,256 -39:54:59,556 33.106,67 bb//dia 18/12/2013 19/01/2014
P - 26 PETROBRAS 26 Campos Petrobras -22:28:01,064 -40:01:48,443 22.185,02 bb//dia 01/07/2014 19/01/2014
p. 31 PETROBRAS 31 Campos Petrobras -22:07:46,640 -39:57:58,507 23.286,06 bbl/dia 25/06/2014 08/08/2014
p. 33 PETROBRAS 33 Campos Petrobras -22:22:13,910 -40:01:36,199 9.577,19 bb//dia 09/07/2014 16/09/2014
P-35 PETROBRAS 35 Campos Petrobras -22:26:07,109 -40:04:10,210 27.068,95 bbl/dia 29/06/2014 26/08/2014
PCP-1 PLATAFORMA DE CARAPEBA-I Campos Petrobras -22:14:36,095 -40:26:39,667 6.623,94 bb//dia 24/10/2014 11/10/2014
PCP-| PLATAFORMA DE CARAPEBA-II Campos Petrobras -22:13:54,771 -40:24:59,499 3.475,18 bb//dia 14/11/2014 23/11/2014
CVIX FPSO CIDADE DE VITÓRIA Espirito Santo Petrobras -20:02:32,988 -39:31:31,015 15.205,26 bbl/dia 22/08/2013 17/02/2014
CDSM FPSO CIDADE SÃO MATEUS Espirito Santo Petrobras -19:55:14,481 -39:38:00,852 2.249,52 bbl/dia 03/08/2014 17/04/2014
PPER PEROA Espirito Santo Petrobras -19:33:50,192 -39:15:12,839 507,23 bul/dia 07/06/2014 22/09/2014
FPCAR FPSO CIDADE DE ANGRA DOS REI Santos Petrobras -25:32:34,760 -42:50:29,010 87.887,43 bb//dia 11/10/1986 19/12/1986
FPCI FPSO CIDADE DE ITAJAÍ Santos Petrobras -26:27:58,090 -46:31:41,610 66.641,81 bb//dia 20/10/2013 11/09/2013
FPCP FPSO CIDADE DE PARATY Santos Petrobras -25:22:00,502 -42:45:35,159 103.957,62 bb//dia 13/03/2014 19/03/2014
FPCST FPSO CIDADE DE SANTOS Santos Petrobras -24:18:05,444 -42:42:50,865 8.049,83 bb//dia 17/11/2013 01/01/2014
FPCSP FPSO CIDADE DE SÃO PAULO Santos Petrobras -25:47:57,603 -43:15:46,221 108.735,61 bbl/dia 24/10/2014 24/11/2014
SS-83 ALPHA STAR Santos Petrobras -25:21:13,116 -42:37:53,470 787,59 bul/dia 14/12/2013 20/12/2013
FPCMB FPSO CIDADE DE MANGARATIBA Santos Petrobras -25:12:12,853 -42:52:41,291 5.188,99 bb//dia 27/08/2013 28/11/2013
NS-39 Ocean-Rig Mykonos Santos Petrobras -25:11:55,260 -42:54:59,890 446,87 bul/dia 25/02/2014 18/03/2014

Passo 1

Beleza, vamos recapitular o que o enunciado pede. Temos 20 poços, cada um com
  • coordenadas (latitude/longitude),
  • tempo de perfuração ,
  • potencial de produção diária ,
  • janela de tempo disponível (data início e data fim).
E temos 3 sondas que saem de uma base (ou se movimentam de poço em poço), cada sonda só pode perfurar um poço por vez, e cada poço deve ser perfurado exatamente uma vez.
O objetivo é montar até 3 rotas (uma para cada sonda) de forma a maximizar a produção total dentro de um horizonte de planejamento.
Conteúdo da matéria:
– Modelagem de roteamento de veículos com prêmios (Team Orienteering Problem with Time Windows).
– Variáveis de decisão binárias, programação inteira, restrições de tempo e de visita única.
O que vamos precisar:
  1. Definir conjuntos, parâmetros (distâncias, tempos, prêmios, janelas),
  2. Variáveis de decisão (binárias para visitar e para transição entre poços, contínuas para tempos de chegada),
  3. Função-objetivo e restrições típicas de roteamento com time windows.

Passo 2

Definindo formalmente:
Conjuntos e parâmetros
  • : índices dos poços.
  • : índice das sondas.
  • : tempo de deslocamento (em horas ou dias) entre o poço e o poço , calculado via fórmula de Haversine nas latitudes/longitudes.
  • : tempo de perfuração do poço .
  • : produção diária esperada do poço .
  • : janela de tempo em que o poço pode ser perfurado (data início e data fim convertidas para um mesmo sistema de unidades, ex. dias desde um dia-zero).
  • : horizonte de planejamento (data final – data inicial).

Passo 3

Variáveis de decisão
  • : vale 1 se a sonda vai diretamente de para .
  • : vale 1 se o poço é perfurado pela sonda .
  • : instante de início de perfuração do poço pela sonda .

Passo 4

Função-objetivo
Queremos maximizar a produção total acumulada durante o horizonte. Se perfurarmos o poço max ; sumkin Ksumiin I pi ;yi^k times (;H - (Ti^k + ti);),, e ele ficar em produção após a perfuração, em geral contamos
max ; sumkin Ksumiin I pi ;yi^k
ou, se simplificarmos e só somarmos o prêmio como proxy,

Passo 5

Restrições principais
  1. Visita única de cada poço:
    sumkin K yi^k = 1 forall iin I
  2. Conectividade / sequência em cada rota (fluxo de roteamento):
    sumjin Icup0 xij^k = yi^k e sumjin Icup0 xji^k = yi^k forall iin I,;kin K,
    onde “0” é o depósito/base (início e fim da rota).
  3. Janela de tempo e causualidade de chegada:
    Para todo Ti^k + ti + dij ;<=; Tj^k + M,(1 - xij^k) forall i,jin Icup0,;kin K, ,
    ai ;yi^k ;<=; Ti^k ;<=; bi ;yi^k forall iin I,;kin K
    com T0^k = 0, Tj^k + tj + dj0 ;<=; H forall jin I,;kin K grande o suficiente.
  4. Respeitar janelas:
  5. Horizonte de cada rota:

Passo 6

Explicando a teoria aplicada
  • Isso é um Problema de Roteamento de Veículos com Prêmios e Time Windows (team orienteering with time windows), que é NP-difícil.
  • A formulação MIP acima usa variáveis binárias e para definir as rotas e variáveis contínuas para controlar o tempo de serviço.
  • A função-objetivo capta o lucro (produção) de cada poço visitado.
  • As restrições garantem que todo poço seja perfurado uma vez, que a sequência faça sentido (fluxo), e que as janelas/horário sejam respeitados.

Resposta

Modelando o problema exatamente como acima numa ferramenta de MIP (por exemplo, CPLEX, Gurobi ou COIN-OR) e rodando a otimização, obtemos as três rotas que maximizam a produção dentro do horizonte .

Exercícios relacionados