XLVI
SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL
Pesquisa Operacional na Gestão da Segurança Pública
16 a 19
Setembro de 2014
Salvador/BA
APLICAÇÃO DE UMA HEURÍSTICA RELAX-AND-FIX À ROTEIRIZAÇÃO E
PROGRAMAÇÃO DE NAVIOS PETROLEIROS
Vinícius Picanço Rodrigues
Universidade Federal de São Carlos – UFSCar
Departamento de Engenharia de Produção
Rodovia Washington Luís, km 235 - SP-310
São Carlos - São Paulo - Brasil - CEP 13565-905
[email protected]
Reinaldo Morabito
Universidade Federal de São Carlos – UFSCar
Departamento de Engenharia de Produção
Rodovia Washington Luís, km 235 - SP-310
São Carlos - São Paulo - Brasil - CEP 13565-905
[email protected]
Este trabalho estuda o problema de roteirização e programação de navios que realizam o escoamento
de petróleo das plataformas marítimas para os terminais terrestres, motivado por uma situação real de
uma empresa brasileira da indústria petrolífera. O Brasil é um dos maiores produtores mundiais de
petróleo, e cerca de 80% de seu petróleo é explorado no mar. Dentro deste contexto, os custos de
transporte desempenham um papel importante na busca pela excelência operacional e as tendências
de crescimento da exploração de petróleo no Brasil têm tornado as operações mais complexas e
sistemas ágeis de apoio à decisão que contemplem o dinamismo do setor petrolífero são necessários.
O objetivo deste trabalho consiste em apresentar uma abordagem de otimização composta por um
modelo de programação linear inteira mista, em conjunto com métodos de solução baseados em
programação matemática (MIP-Heuristics) para resolver o modelo, conhecidos como relax-and-fix.
O modelo proposto é inspirado em uma formulação de problemas de coleta e entrega com janelas de
tempo (pickup and delivery with time windows – PDPTW) e frota heterogênea, no qual busca-se
minimizar os custos decorrentes do consumo de combustível dos navios e contratos de afretamento.
O modelo é do tipo origem-destino, no qual os pares coleta/entrega são pré-determinados e a decisão
do modelo refere-se à alocação de navios para os diferentes pares, compondo uma rota. Além disso,
são propostas restrições adicionais que contemplam limitações de acesso a terminais e de atracação
em plataformas de acordo com os tipos de navio, além da incompatibilidade de mistura de produtos,
entre outros. O modelo foi implementado utilizando uma linguagem de modelagem em conjunto com
um software de otimização. Experimentos computacionais com o modelo e as heurísticas são
apresentados para diferentes conjuntos de dados fornecidos pela empresa e comprovam o potencial
das abordagens para encontrar boas soluções para o problema, mas também suas dificuldades para
encontrar soluções para exemplares de tamanho realista, por tratar-se de um problema NP-difícil do
ponto de vista de teoria de complexidade.
Palavras-chave: roteirização e programação de navios; relax-and-fix; petróleo.
3136