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.
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.
– 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:
- Definir conjuntos, parâmetros (distâncias, tempos, prêmios, janelas),
- Variáveis de decisão (binárias para visitar e para transição entre poços, contínuas para tempos de chegada),
- 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 e ele ficar em produção após a perfuração, em geral contamos
Queremos maximizar a produção total acumulada durante o horizonte. Se perfurarmos o poço
ou, se simplificarmos e só somarmos o prêmio
como proxy,
Passo 5
Restrições principais
-
Visita única de cada poço:
-
Conectividade / sequência em cada rota (fluxo de roteamento):onde “0” é o depósito/base (início e fim da rota).
-
Janela de tempo e causualidade de chegada:
Para todo, comgrande o suficiente. -
Respeitar janelas:
-
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
.