MODELO MATEMÁTICO PARA O PROBLEMA DE ALOCAÇÃO DE BERÇOS
CONTÍNUO (PABC) COM RESTRIÇÕES ESPACIAIS E TEMPORAIS APLICADO
A UMA BASE DE APOIO A PLATAFORMAS DE PETRÓLEO
Ivan Bridi Gimenes Rodrigues
Rodrigo de Alvarenga Rosa
Programa de Pós-Graduação em Engenharia Civil – Transportes
Universidade Federal do Espírito Santo
RESUMO
O Estado do Espírito Santo é hoje o segundo maior produtor de petróleo do Brasil. As plataformas offshore
possuem todas as demandas de suprimento de uma cidade de médio porte isoladas no meio do mar precisando de
peças, rancho, materiais, e outros. Assim, os portos especializados em atender navios de apoio logístico a essas
plataformas, denominados bases de apoio, são importantes para a exploração do petróleo e, visando dar maior
eficiência à operação deles este artigo apresenta um modelo matemático baseado em Programação Linear Inteira
Mista (PLIM) aplicado ao Problema de Alocação de Berços Contínuos com restrições temporais e espaciais
aplicado à maior base de apoio do Estado do Espírito Santo, a Companhia Portuária de Vila Velha (CPVV) que
recebe em média 180 navios por mês que atendem em média a 32 plataformas. O modelo matemático
apresentado foi executado no software CPLEX 12.5 com dados reais do CPVV e instâncias de até 97 navios com
320 metros de cais foram resolvidas de forma exata e os resultados são apresentados neste artigo.
Palavras chave: Problema de Alocação de Berços Contínuo (PAB-C), Operação Portuária, Programação Linear
Inteira Mista.
ABSTRACT
The Espírito Santo state is now the second largest oil producer in Brazil. The offshore platforms have to supply
all demands of a midsize city isolated in the sea and they need spare parts, food, materials, and others. Thus,
ports specialized in logistic support vessels to attend these platforms, called base of support, are vital for oil and
gas exploration and to ensure greater efficiency to their operation, this paper presents a mathematical model
based on Integer Linear Programming mixed (MILP) applied to the Continuous Berth Allocation Problem
(BAPC) with temporal and spatial constraints applied to the largest base of support at Espírito Santo state, the
Companhia Portuária de Vila Velha (CPVV) that receives an average of 180 ships per month that meet 32
platforms. The mathematical model was implemented using software CPLEX 12.5 with real data from CPVV
and instances of up to 90 ships with 320 meters of quay were solved exactly and the results are presented in this
article.
Key words: Berth Allocation Problem Continuous (BAP-C), Port Operation, Mixed Integer Linear
Programming.
1. INTRODUÇÃO
O início da produção comercial do Espírito Santo de petróleo na camada pré-sal aconteceu em
novembro de 2012 no posicionamento e início de operação da plataforma do tipo Floating
Production Storage and Offloading (FPSO) Cidade de Anchieta, no litoral Sul do Estado. No
Espírito Santo, a exemplo da infraestrutura implantada em outros estados, os problemas de
logística concentram-se no atendimento das unidades offshore de exploração e produção,
segmento com os maiores dispêndios da indústria petrolífera. Cada uma dessas unidades de
exploração e produção possuem todas as demandas de suprimento de uma cidade de
médio/pequeno porte isoladas no meio do mar e, portanto, precisam de comida, geração de
energia, tratamento de esgoto, remédios e outros. Desde diesel, água potável, comida e tudo
de hotelaria, passando por todas as spare parts, tudo precisa ser levado de terra para o mar
num fluxo ininterrupto.
A base de apoio Companhia Portuária de Vila Velha (CPVV) atende em média a 180 navios
por mês que atendem em média a 32 plataformas para suprir as necessidades das plataformas
offshore, sendo o CPVV o maior porto de apoio à exploração de petróleo em plataformas
offshore do Espírito Santo. Esses navios fazem uma rota entre porto-plataformas de forma que
é fundamental o tempo de operação no porto para que não haja escassez de material ou
alimento em nenhuma plataforma.
Assim, pode-se perceber que os portos especializados em atender navios de apoio logístico a
essas unidades de exploração são de vital importância para a exploração do pré-sal e, visando
dar maior eficiência à operação destes portos, denominados bases de apoio, faz-se necessário
estudos que visem a maior eficiência destes portos. Os portos são instalações logísticas
estratégicas para um país, pois eles são o elo vital entre os modais terrestres e o modal
aquaviário. No atendimento às plataformas offshore, os portos assumem uma importância
ainda maior, pois 98% do material passam pelos portos.
Devido à sua relevância para a eficiência de um porto o Problema de Alocação de Berços
Contínuo (PABC) tem recebido nos últimos anos considerável atenção da comunidade
acadêmica, podem-se citar alguns artigos que fazem revisões gerais sobre o PABC
apresentando algumas aplicações práticas: Garey e Johnson (1979), Park e Kim (2002), Guan
e Cheung (2004), Imai et al. (2005), Arabshahi et al. (2010). Podem-se citar também alguns
artigos que fazem revisões gerais sobre o PAB apresentando algumas aplicações práticas:
Meersmans e Dekker (2001), Vis e de Koster (2003), Steenken et al. (2004), Vacca et al.
(2007), Stahlbock e Vob (2008), Bierwirth e Meisel (2010) e Rashid e Tsang (2013). Nas
Seções 2 e 3 uma revisão mais extensa é realizada.
Neste sentido, este artigo apresenta um modelo matemático baseado em Programação Linear
Inteira Mista (PLIM) aplicado ao PABC dinâmico e com restrições temporais e espaciais. O
modelo matemático apresentado foi executado no software CPLEX 12.5 e instâncias de até 97
navios com 320 metros de cais foram resolvidas de forma exata com dados reais do CPVV.
Em função dos navios que atracam no CPVV serem pequenos, rebocadores de apoio, optou-se
por considerar o calado de metro em metro visando obter maior precisão da posição de
atracação. Até o momento não se tem conhecimento da aplicação do PABC a portos de
exploração de petróleo offshore.
O artigo é organizado como segue: na Seção 2 tem-se a definição do Problema de Alocação
de Berço Contínuo (PABC), a Seção 3 apresenta uma revisão da literatura, na Seção 4
apresenta-se o porto analisado e suas características, na Seção 5 é apresentada a metodologia
utilizada, na Seção 6 é apresentado o modelo matemático proposto, na Seção 7 são
apresentados os experimentos computacionais e as análises dos resultados encontrados e na
última seção, têm-se as conclusões.
2. PROBLEMA DE ALOCAÇÃO DE BERÇO (PAB)
O PAB se refere basicamente ao problema de planejar a sequência de atendimento de um
conjunto de navios, dentro de um horizonte de tempo, em um layout de berços de porto. O
objetivo mais usual é minimizar o tempo de permanência dos navios no porto, embora possa
haver outros objetivos (Bierwirth e Meisel, 2010). Pode-se resumir que o PAB visa atribuir
uma posição de atracação, um berço, e um tempo de atracação para cada navio que pretende
operar no porto, tal que uma função objetivo seja otimizada.
Os modelos existentes para PAB na literatura podem ser classificados tanto por restrições
temporais como por restrições espaciais. Dentre os atributos temporais podem ser citados:
data de chegada de navio, data de atracação, tempo de espera na fila de navios dentre outros.
Quanto aos atributos espaciais, relativos ao layout do cais, usualmente adotam-se as restrições
de calado, comprimento e boca dos navios.
As restrições espaciais também restringem as posições viáveis de atracação de navios de
acordo com um pré-particionamento do cais em berços. De acordo com Imai et al. (2008) as
seguintes situações podem ocorrer: 1) PAB discreto, 2) PAB Continuo e 3) PAB Hibrido.
Na Figura 1 são ilustrados os três casos, discreto, contínuo e hibrido No caso PAB Discreto, o
cais é dividido em um número de seções denominadas berços e apenas um navio pode ser
operado em cada berço num certo intervalo de tempo. Para o PAB Contínuo não há divisão
do cais, ou seja, os navios podem atracar em posições arbitrárias dentro dos limites do cais.
Nesse layout o planejamento do cais é mais difícil do que para um layout discreto, pois
podem ocorrer espaços vazios que não permitam que navios de certas dimensões atraquem
deixando espaço sem utilização no cais. Porém, apresenta a vantagem de uma maior
flexibilização do espaço de atracação podendo gerar ganhos por aproveitar todos os espaços.
No caso do PAB Híbrido, similar ao caso discreto, o cais é particionado em berços, no
entanto, grandes navios podem ocupar mais de um cais, esta situação pode ser vista no berço
2 e berço 3 da Figura 1, enquanto os pequenos navios podem compartilhar um berço, esta
situação pode ser vista no berço 4 da Figura 1.
Figura 1: Representação PAB Discreto, PAB Contínuo e PAB Híbrido
Restrições temporais ocorrem principalmente em relação aos horários de atracação e de
desatracação dos navios. De acordo com Imai et al. (2008) a seguinte classificação pode ser
feita: 1) chegada estática e 2) chegada dinâmica.
Na situação de chegada estática, considera-se que todos os navios já estão na área de fundeio
do porto, prontos para atracar, portanto, não é realizada nenhuma consideração sobre a data de
previsão para a chegada dos navios. Na chegada dinâmica, os navios possuem horários
previstos de chegada e, portanto, os navios não podem atracar antes da hora prevista de
chegada. Podem ainda haver datas de limite máximo de atracação e, até mesmo, de
desatracação. Na situação de chegada dinâmica, caso existam restrição de horário de
desatracação, toda a operação de um navio tem de ser executada dentro do intervalo
compreendido entre o tempo limite estabelecido para atracação e para desatracação. Esta é
uma condição que representa a realidade da maioria dos portos.
As datas de chegadas dos navios podem ser consideradas como determinísticas e estocásticas.
Quando essas são determinísticas, as datas estimadas de chegada, conhecidas como Estimated
Time of Arrival (ETA), são fixadas como parâmetros do problema. Quando a chegada é
estocástica, são estabelecidas com base em dados históricos curvas estatísticas de distribuição
de tempos de chegada ocasionadas pela incerteza decorrentes de problemas ocorridos em
outros portos e até mesmo de navegação.
Outro ponto importante nos modelos do PAB, oriundo do tipo de chegada dos navios, são as
abordagens em relação a realizar o escalonamento dos navios nos berços ou não. Existem
basicamente duas abordagens: 1) Todos os navios devem ser alocados sem consideração de
data para o momento atual, 2) Deve ser elaborada uma sequencia de atendimento dos navios
para cada berço. A segunda situação reflete melhor a real necessidade gerencial dos portos e,
assim, espera-se alcançar um resultado como o visto na Figura 2 (a) para berços discretos e na
Figura 2 (b) que representa o sequenciamento no gráfico espaço-tempo para berços com
layout contínuo.
Berços
Comprimento
do Cais (m)
280
Navio 1
Berço 4
Navio 1
220
Navio 5
Navio 36
Navio
Berço 3
Navio 5
Navio 2
160
Navio 7
Navio 2
120
Berço 2
Navio 3
Navio 6
80
Navio 3
40
Berço 1
Navio 7
0
Navio 4
5
10
15
(a) PAB Discreto
20
Tempo (Hrs)
Navio 8
Navio 4
Navio 8
0
5
10
(b) PAB Contínuo
15
20
Horizonte de
planejamento
(Horas)
Figura 2: Sequencia de atendimento a navios
O tempo de operação dos navios, na grande maioria dos modelos publicados sobre o PAB, é
tratado como determinístico e estabelecido como parâmetro do problema. Porém, existem
outras abordagens, tais como: o tempo de operação é conhecido a priori e é considerado fixo,
o tempo de operação depende do berço que o navio irá atracar, o tempo de operação é
considerado estocástico por conta das incertezas devido a interrupções imprevistas, como
quebra ou indisponibilidade de equipamento de carga, dentre outras.
3. REVISÃO DA LITERATURA
Esta revisão do PAB é estruturada com base nas restrições espaciais e, assim, divide-se esta
seção em: PAB Contínuo, foco deste artigo, PAB híbrido, usualmente tratado como berço
contínuo, e PAB discreto.
3.1 PAB Contínuo
De acordo com Garey & Johnson (1979) PABC pode ser representado como um problema de
corte e estoque bidimensional com algumas restrições adicionais. Li et al. (1998), Guan et al.
(2002) e Park, Kim (2003) e Guan e Chung (2004) propõem soluções para o PAB contínuo
com chegada estática, e com objetivo de minimizar o tempo total de permanência dos navios
no porto. Gao et al. (2010) tratam o mesmo problema, porém admitem que as datas de
chegada dos navios tenham um comportamento estocástico. Lim (1998), Lim (1999), Tong et
al. (1999) e Goh e Lim (2000) consideram que os tempos de atracação de navios já estão
definidos pelos tempos de chegada e, então, as posições de atracação devem ser decididas
visando minimizar o comprimento de cais necessário para atracar todos os navios.
Minimização de atrasos como um objetivo em BAP dinâmico contínuo é considerado por
Moon (2000), Park e Kim (2002 e 2003), Kim e Moon (2003) e Briano et al. (2005). Eles
usam heurísticas para resolver o mesmo problema e, dentre elas, citam-se o método do
subgradiente e o simullated annealing.
Continuando com o problema do PAB contínuo com chegada estática, Lim (1998) e Tong et
al. (1999) propõem como função objetivo a minimização do comprimento utilizado do caís
em dado tempo de carregamento. Imai et al. (2005) e Chang et al. (2008) consideram o
tempo de carregamento dependente da posição de atracação do navio no berço contínuo e,
também, as restrições de calado. A proposta deles sugere duas etapas, uma primeira que
resolve o problema de forma geral e a segunda que é obtida fazendo modificações das
posições dos navios. Adicionalmente tais trabalhos tratam do PAB contínuo buscando uma
otimização da utilização do comprimento do cais.
No problema tratado por Wang e Lim (2007) ocorre a minimização dos custos de penalização
para os navios rejeitados e apresentam uma heurística robusta que consegue resolver
instâncias com até 400 navios. Na abordagem de Meisel e Bierwirth (2009 e 2010) além de
considerar o PAB, consideram os problemas de alocação de guindastes para terminais de
contêineres. Brown et al. (1997) e Lee e Chen (2008) propõem um caso raro na prática onde
os navios podem ser movimentados durante a operação de um berço para outro.
Park e Kim (2002), e Kim e Moon (2003) abordaram o BAP contínuo pela técnica de
relaxamento de Lagrange (método do subgradiente). Foram testadas simulações numéricas de
no máximo 20 navios e demonstraram a aplicabilidade do método proposto.
Kim e Park (2004) utilizaram o método do quadro GRASP para resolver problema de PABC
considerando os guindastes do cais. O quadro de GRASP consiste em duas fases em cada
iteração: construção e busca local. Na construção do quadro solução, elementos candidatos
são inseridos na solução parcial iterativamente até que uma solução completa é construída.
Arabshahi et al. (2010) propôs um modelo onde os navios possuem um ponto ótimo de
atracação no cais e aplicou penalizações em relação a distância do ponto ótimo. Com o
objetivo de minimizar o tempo de espera dos navios.
3.2 PAB Híbrido
Moorthy e Teo (2006), e Chen e Hsieh (1999) estudam o PAB Híbrido com data de chegada
dinâmica, considerando o tempo de carregamento como fixo e a data de chegada dos navios
de forma estocástica. Cordeau et al. (2005) e Imai el al. (2007) estudam o mesmo problema
citado, porém consideram que o tempo de operação é dependente da posição de atracação do
navio. Nishimura et al. (2001) e Cheong et al. (2010) acrescentam aos seus modelos as
restrições de calado.
Dai et al. (2008) tratam o PAB híbrido num nível mais operacional, onde as posições precisas
são pesquisadas dentro das áreas de atracação disponíveis usando Simulated Annealing. Chen
e Hsieh (1999) propõem uma formulação PLIM considerando chegadas dinâmicas. Imai et al.
(2007), Cordeau et al. (2005), Nishimura et al. (2001), Cheong et al. (2007) e Hoffarth e
Voss (1994) estudam o PAB híbrido com diversas variações de função objetivo e de
restrições.
3.3 PAB Discreto
Imai et al. (1997), Imai et al. (2001), Theofanis et al. (2007) e Imai et al. (2008) analisam o
PAB discreto com chegada estática com a função objetivo que visa minimizar o tempo total
de serviços dos navios e os desvios entre a sequência de chegada e a sequência de atracação
dos navios. Basicamente, eles tratam o PAB como um problema de atribuição e
sequenciamento de navios para berços tendo como objetivo minimizar o tempo de espera e de
operação dos navios. Hansen e Oguz (2003) propõem um modelo PLIM mais compacto para
o mesmo problema. Imai et al. (2001), Monaco and Sammarra (2007) e Imai et al. (2003)
estudam o PAB discreto com chegada dinâmica. Rosa et al. (2012) propuseram um modelo
PLIM exato para o PAB dinâmico com múltiplas cargas. Zhou and Kang (2008) e Han et al.
(2010) lidam com o PAB discreto com chegada dinâmica que considera a data de chegada e o
tempo de carregamento com um comportamento estocástico.
Ainda para o PAB discreto com chegada dinâmica, Cordeau et al. (2005) utilizam a
metaheurística Tabu Search para resolver o PAB. Mauri et al. (2008, 2010) propõem para o
mesmo problema uma abordagem baseada em geração de colunas que segundo os autores
gera melhores soluções num menor tempo de execução e uma solução baseada no trabalho de
Cordeu et al. (2005) tratando o problema como um Problema de Roteamento de Veículos e
utiliza a heurística Population Training Algorithm/Linear Programming (ATP/PL). Imai et al.
(2008) propõem a minimização do número de navios rejeitados por não ser atendido dentro do
prazo máximo estabelecido. Ele utiliza para a solução um algoritmo genético.
No modelo de Golias et al. (2006 e 2007) os horários de chegada e tempos de movimentação
de navios são considerados como variáveis estocásticas. Hansen et al. (2003 e 2008) propõem
uma heurística Variable Neighborhood Search (VNS) para resolver o PAB que apresenta
resultados superiores aos encontrados por Nishimura et al. (2001). Zhou et al. (2006) e Han et
al. (2006) consideram a chegada dos navios como estocástica e que existe uma restrição de
tempo de espera na fila de navios. Ambos utilizam algoritmos genéticos para resolver o
problema.
Vale ressaltar que após a pesquisa bibliográfica realizada até o momento, não foi encontrado
nenhum artigo publicado que tratasse da aplicação do PAB à bases de apoio a plataformas de
apoio a exploração de petróleo offshore.
4. DEFINIÇÃO DO PROBLEMA PRÁTICO ESTUDADO
A Companhia Portuária de Vila Velha (CPVV) (CPVV, 2013) é o maior porto de apoio a
plataformas offshore do Espirito Santo, que atende, em média, a 180 navios por mês que
atendem a 32 plataformas. Para tais funções a CPVV possui acesso ao canal de Vitória e à
estrada de Capuaba movimentando em média 25 mil toneladas de carga geral, 20 mil m³ de
água potável, 6 mil m³ de diesel marítimo e 4 mil toneladas de cimento por mês. Na Figura 3
tem-se uma vista aérea do cais contínuo de 255m o qual conta com o ancoradouro que dista
40m do cais que, para efeito de cálculos o ancoradouro será considerado como parte do cais o
mesmo se aplicando ao Dolphin à esquerda da foto, totalizando 320 metros de espaço útil.
Figura 3: Vista aérea do CPVV
É importante observar que mesmo se tratando de um porto com berço contínuo, algumas
embarcações em função do seu calado possuem locais específicos no caís que podem ser
atracadas. As restrições de calado do CPVV estão indicadas na Tabela 1. Os navios com
menos de 9 metros de calado podem ocupar qualquer espaço do píer, já os com calado entre 9
e 12 metros só podem atracar nos primeiros 225 metros lineares de cais. É importante
perceber, que embarcações com mais de 12 metros de calado não podem atracar no CPVV.
Tabela 1: Calados por metro linear de cais
Divisão do cais (m)
Calado (m)
0 – 225
12
225 – 320
9
5. METODOLOGIA
O modelo matemático exato proposto foi elaborado como um modelo de Programação Linear
Inteira Mista (PLIM). Foram utilizadas as informações da Seção 4 levantadas no CPVV. Os
dados foram fornecidos pela equipe de controle de atracação do CPVV com base nos sistemas
gerenciais.
Dentre os softwares disponíveis no mercado, optou-se pelo uso do CPLEX 12.5 por ser um
software robusto e disponível para uso no meio acadêmico sem custos. Para resolver o
problema de PLIM no CPLEX, traduziu-se o modelo matemático na linguagem específica do
CPLEX e foram cadastrados todos os parâmetros nos arquivos específicos.
Foram levantados junto a própria CPVV dados de atracação referentes ao mês de abril de
2013 e apesar do usual ser a programação dos navios por semana, decidiu-se testar o modelo
em um horizonte de 15 dias, o que perfaz um total para a quinzena de 85 navios. Também
foram levantadas todas as ETAs dos navios, bem como suas características.
Visando ainda buscar o limite do modelo matemático proposto em termos de navios para
serem atracados, foram criadas 6 instâncias, variando a quantidade dos navios em 70, 75, 80,
90, 95 e 97 navios respectivamente. Essas instâncias foram executadas no CPLEX e os
tempos de execução foram apurados.
6. MODELO MATEMÁTICO PROPOSTO
O modelo matemático proposto é apresentado em cinco partes como segue: conjunto, variáveis,
parâmetros, função objetivo e restrições.
- Conjunto
- Conjunto de navios para chegar ao porto, = 1. . ;
- Variáveis
- Tempo de inicio/atracação do navio ∈ ;
- Posição de atracação do navio ∈ ;
-Tempo de término/desatracação do navio ∈
;
Considerando-se o diagrama espaço-tempo com o tempo como abscissa e o cais como ordenada, têmse as variáveis binárias:
1 Se o retângulo do próximo navio ∈ a atracar estiver totalmente acima do retângulo
referente ao navio ∈ no diagrama espaço-tempo e não houver sobreposição;
0 Caso contrário.
1 Se o retângulo do próximo navio ∈ a atracar estiver totalmente à direita do retângulo
referente ao navio ∈ no diagrama espaço-tempo e não houver sobreposição;
0 Caso contrário.
- Parâmetros
- Comprimento do cais;
- Horizonte de tempo;
- Tempo de operação do navio ∈ em unidade de tempo (1 hora);
- Comprimento do navio (LOA) ∈ em unidade de cais (1 metro) já incluindo a folga entre
navios;
- Tempo de chegada do navio ∈ ao porto (ETA);
- Função Objetivo
min
∑ (ci − ai )
(1)
i∈N
- Restrições
− − −
−1 ≥0
− − −
−1 ≥0
+
+
+
≥1
+ =
≤ ≤( − )
∈ "0,1#,
∈ "0,1# ,
,
,
∈ %&
∀
∀
∀
∀
∀
∀
, ∈
, ∈
, ∈
∈
∈
, ∈
,
,
,
≠
≠
≠
,
≠
(2)
(3)
(4)
(5)
(6)
(7)
A função objetivo, representada na expressão (1), representa a diferença entre o tempo de término da
operação, desatracação do navio, e o tempo de chegada do navio ao porto. Ou seja, visa minimizar o
tempo total do navio no porto a fim de que o cais alcance o maior cenário de ocupação possível. As
restrições (2) e (3) garantem que não haja sobreposições no diagrama espaço-tempo no período e
espaço, respectivamente.
As variáveis
e
são variáveis binárias que consideram as posições relativas do retângulo do
navio no gráfico espaço-tempo. Ou seja, assumem valor unitário se o retângulo do navio j está à direta
e acima do navio i no gráfico espaço-tempo, de forma que não haja sobreposição dos retângulos.
Assim, no caso em que o retângulo do navio j está à direita do retângulo referente ao navio i, vem que
= 1. Com isso, tem-se: ≥ + . Isto significa que o navio j vem depois do navio i. Por outro
lado, caso o retângulo do navio j esteja à esquerda do retângulo referente ao navio i,
= 0, o que
leva a + ≥ + que é sempre verdade, pois o horizonte de tempo é um valor muito maior do
que os outros parâmetros.
A não sobreposição dos retângulos é assegurada pela restrição (4). A equação (5) garante que o tempo
de desatracação da embarcação é a soma da atracação com o tempo de operação. A restrição (6)
garante que o navio seja atracado dentro do horizonte de tempo estipulado, ou seja, depois do ETA do
navio e antes do tempo limite. Este horizonte de tempo, T, é calculado como a diferença entre a
data/hora de desatracação do último navio amostrado e a data/hora de atracação do primeiro navio em
análise, adicionando-se um delay.
Por fim, a restrição (7) garante que
e
sejam variáveis binárias e evita que os navios e
sejam tomados como o mesmo navio pelo modelo, assim como que as outras variáveis estejam dentro
do universo dos números Reais e Positivos.
Tempo (minutos)
7. APRESENTAÇÃO E ANÁLISE DOS RESULTADOS
Primeiramente foram testadas as 6 instâncias para avaliar a capacidade do modelo em termos
de navios a serem atracados, considerando um cais de 320 metros, seccionado em seções de
um metro cada. Neste cenário também foram consideradas as restrições de calado. Os testes
foram realizados em um computador Intel Core 2Duo com 6GB de memória rodando o
CPLEX 12.5. O tempo de execução de cada instância pode ser visto no gráfico da Figura 4.
40
30
20
10
Tempo para solução
0
70
75
80
90
95
97
Número de Navios
Figura 4: Tempo gasto pelo software CPLEX para encontrar a solução ótima para diferentes números de navios
Pode se ver na Figura 4 que o modelo conseguiu resultados exatos para a instância com 70
navios em menos de 1 minuto e até instancias com 90 navios ele levou menos de 2 minutos.
No entanto, o tempo de execução começa a subir rápido para instâncias com 95 navios. Para a
instância com 97 navios o modelo foi executado no CPLEX em 32min27seg para obter a
solução ótima.
Vale ressaltar que foi constatado que o limite do modelo de 97 navios equivale a 17 dias, que
pode ser considerado como uma programação de longo prazo visto que programações de
atracação sofrem muitas mudanças de acordo com as necessidades dos envolvidos e
usualmente a programação não passa de uma semana.
Com o resultado do CPLEX foi construído um gráfico, Figura 5, espaço-tempo com o
sequenciamento das atracações dos navios a fim de apresentar aos usuários o escalonamento
dos navios. Pode-se notar que não há sobreposição dos navios em espaço e em tempo.
Metro linear de cais
Programação de Atacações
400
300
200
100
0
Navio 1
Navio 2
Navio 3
0
50
100
Tempo (horas)
150
200
Navio 4
Navio 5
Figura 5: Gráfico (espaço-tempo): Sequenciamento dos navios a atracar
Comparando o resultado alcançado pelo modelo com o que foi alcançado pelo método manual
atualmente em uso, o modelo apresentou poucas distorções do programado e após
verificações com os usuários, pode-se perceber que os motivos foram mudanças de última
hora na programação das plataformas e/ou chegada de carretas que acabaram não sendo
registradas pelo porto. Assim sendo, pode-se afirmar que os resultados ótimos alcançados
pelo modelo estão completamente aderentes ao que hoje é executado, tornando-se assim uma
ferramenta confiável para utilização pelo CPVV.
8. CONCLUSÕES
Este artigo apresentou um modelo matemático para resolver o Problema de Alocação de
Berço Contínuo (PABC) aplicado ao porto Companhia Portuário de Vila Velha (CPVV), que
é um porto de apoio à exploração de petróleo offshore, o que até então na revisão bibliográfica
não há relatos de nenhuma aplicação do PABC com restrições espaciais e temporais com
soluções ótimas a um porto de apoio a plataformas offshore de exploração de petróleo.
O modelo apresentou bons resultados, podendo programar atracações com um horizonte de
até 17 dias, tomando como média o recebimento mensal hoje apurado no CPVV, e que pode
ser considerada uma programação de logo prazo. Desta forma, o modelo assegura uma
solução ótima onde todos os navios são alocados no cais, sem sobreposição de tempo nem
espaço respeitando as restrições de calado.
AGRADECIMENTOS
À Fundação de Amparo à Pesquisa do Espírito Santo (FAPES) pelo apoio via a bolsa Pesquisador Capixaba no
458/2013 e à Companhia Portuária de Vila Velha (CPVV) pela disponibilização das informações e dos dados.
REFERÊNCIAS
Arabshahi, N.; Seyadalizadeh Ganji, S.R.; Babazadeh, A. (2010). Analysis of the continuous berth allocation
problem in container ports using a genetic algorithm. Sci Technol.
Bierwirth, C., Meisel, F., 2009. A fast heuristic for quay crane scheduling with interference constraints. Journal
of Scheduling, doi: 10.1007/s10951-009-0105-0.
Bierwirth, C. and F. Meisel 2010 A survey of berth allocation and quay crane scheduling problems in container
terminals, European Journal of Operational Research, 202 (3) 615– 627.
Briano, C., Briano, E., Bruzzone, A.G., 2005. Models for support maritime logistics: a case study for improving
terminal planning. In: Merkuryev, Y., Zobel, R., Kerckhoffs, E. (Eds.), Proceedings of the 19th European
Conference on Modeling and Simulation (ECMS). pp. 199–203.
Brown, G.G., Cormican, K.J., Lawphongpanich, S., Widdis, D., 1997. Optimizing submarine berthing with a
persistence incentive. Naval Research Logistics 44(4), 301–318.
Chang, D., Yan, W., Chen, C.-H., Jiang, Z., 2008. A berth allocation strategy using heuristics algorithm and
simulation optimisation. International Journal of Computer Applications in Technology 32 (4), 272–281.
Cheong, C.Y., Lin, C.J., Tan, K.C., Liu, D.K., 2007. A multi-objective evolutionary algorithm for berth
allocation in a container port. In: IEEE Congress on Evolutionary Computation 2007 (CEC 2007). IEEE
Computer Society, Washington DC, pp. 927–934.
Cheong, C., Tan, K., Liu, D., Lin, C., 2010. Multi-objective and prioritized berth allocation in container ports.
Annals of Operations Research 180, 63–103.
Chen, C.-Y., Hsieh, T.-W., 1999. A time-space network model for the berth allocation problem. In: 19th IFIP
TC7 Conference on System Modeling and Optimization, Cambridge.
Cordeau, J.-F., Laporte, G., Legato, P., Moccia, L., 2005. Models and tabu search heuristics for the berthallocation problem. Transportation Science 39 (4), 526– 538.
Dai, J., Lin, W., Moorthy, R., Teo, C.-P., 2008. Berth allocation planning optimization in container terminals. In:
Tang, C.S., Teo, C.-P., Wei, K.-K. (Eds.), Supply chain analysis: a handbook on the interaction of
information, System and Optimization. Springer, New York, pp. 69–105.
Gao, C., Zhang, R., Du, Y., Chen, Q., 2010. A proactive and reactive framework for berth allocation with
uncertainties, paper presented at Advanced Management Science (ICAMS), 2010 IEEE International
Conference on, vol. 3, 144 –149.
Garey, M.R. & Johnson, D.S. (1979). Computers and intractability: a guide to the theory of np-completeness.
Freeman, San Francisco, USA.
Goh, K.S., Lim, A., 2000. Combining various algorithms to solve the ship berthing problem. In: Proceedings of
the 12th IEEE International Conference on Tools with Artificial Intelligence (ICTAI’00). IEEE Computer
Society, Los Alamitos, CA, pp. 370–373.
Golias, M., Boile, M., Theofanis, S., 2006. The berth allocation problem: a formulation reflecting time window
service deadlines. In: Proceedings of the 48thTransportation Research Forum Annual Meeting.
Transportation Research Forum, Boston.
Golias, M., Boile, M., Theofanis, S., 2007. The stochastic berth allocation problem. In: Proceedings of the
International Conference on Transport Science and Technology (TRANSTEC 2007). Czech Technical
University, Prague, pp. 52–66.
Guan, Y., Cheung, R.K., 2004. The berth allocation problem: models and solution methods. OR Spectrum 26
(1), 75–92.
Guan, Y., Xiao, W.-Q., Cheung, R.K., Li, C.-L., 2002. A multiprocessor task scheduling model for berth
allocation: heuristic and worst-case analysis. Operations Research Letters 30 (5), 343–350.
Han, M., Li, P., Sun, J., 2006. The algorithm for berth scheduling problem by the hybrid optimization strategy
GASA. In: Proceedings of the Ninth International Conference on Control, Automation, Robotics and
Vision (ICARCV’06). IEEE Computer Society, Washington DC, pp. 1–4.
Han, X., Lu, Z., Xi, L., 2010. A proactive approach for simultaneous berth and quay crane scheduling problem
with stochastic arrival and handling time. European Journal of Operational Research, 207 (3) 1327 –
1340.
Hansen, P., Oguz, C., 2003. A note on formulations of static and dynamic berth allocation problems. Les Cahiers
du GERAD 30, 1–17.
Hansen, P., Oguz, C., Mladenovic, N., 2008. Variable neighborhood search for minimum cost berth allocation.
European Journal of Operational Research 191 (3), 636–649.
Hoffarth, L., Voß, S., 1994. Berth allocation in a container terminal – development of a decision support system
(in German). In: Dyckhoff, H., Derigs, U., Salomon, M., Tijms, H.C. (Eds.), Operations Research
Proceedings 1993. Springer, Berlin et al., pp. 89–95.
Imai, A., Nishimura, E., Hattori, M., Papadimitriou, S., 2007. Berth allocation at indented berths for megacontainerships. European Journal of Operational Research 179 (2), 579–593.
Imai, A., Nishimura, E., Papadimitriou, S., 2001. The dynamic berth allocation problem for a container port.
Transportation Research Part B 35 (4), 401–417.
Imai, A., Nishimura, E., Papadimitriou, S., 2003. Berth allocation with service priority. Transportation Research
Part B 37 (5), 437–457.
Imai, A., Nishimura, E., Papadimitriou, S., 2008. Berthing ships at a multi-user container terminal with a limited
quay capacity. Transportation Research Part E 44 (1), 136–151.
Imai, A., Sun, X., Nishimura, E., Papadimitriou, S., 2005. Berth allocation in a container port: using a
continuous location space approach. Transportation Research Part B 39 (3), 199–221.
Kim, K.H., Moon, K.C., 2003. Berth scheduling by simulated annealing. Transportation Research Part B 37 (6),
541–560.
Kim, K.H., Park, Y.M., 2004. A crane scheduling method for port container terminals. European Journal of
Operations Research, 156 (3), 752–768.
Lee, Y., Chen, C.-Y., 2008. An optimization heuristic for the berth scheduling problem. European Journal of
Operational Research 196 (2), 500–508.
Li, C.-L., Cai, X., Lee, C.-Y., 1998. Scheduling with multiple-job-on-one-processor pattern. IIE Transactions 30
(5), 433–445.
Lim, A., 1998. The berth planning problem. Operations Research Letters 22 (2), 105– 110.
Lim, A., 1999. An effective ship berthing algorithm. In: Thomas, D. (Ed.), Proceedings of the 16th International
Joint Conference on Artificial Intelligence (IJCAI-99-vol-1). Morgan Kaufmann Publishers, San
Francisco, pp. 594–599.
Mauri, G.R., Oliveira, A.C.M., Lorena, L.A.N., 2008. A hybrid column generation approach for the berth
allocation problem. In: van Hemert, J., Cotta, C. (Eds.), Eighth European Conference on Evolutionary
Computation in Combinatorial Optimisation, vol. 4972 of LNCS. Springer, Berlin et al., pp. 110– 122.
Mauri, G.R., Oliveira, A.C.M., Lorena, L.A.N., 2010. Resolução do Problema de Alocação de Berços Através de
Uma Técnica de Geração de Colunas, Pesquisa Operacional, v. 30, n.3, pp. 547– 562.
Meersmans, P.J.M., Dekker, R., 2001. Operations research supports container handling. Econometric Institute
Report 234, Erasmus University Rotterdam.
Monaco, M.F., Sammarra, M., 2007. The berth allocation problem: a strong formulation solved by a Lagrangean
approach. Transportation Science 41 (2), 265–280.
Moon, K., 2000. A mathematical model and a heuristic algorithm for berth planning. Ph.D. Thesis, Pusan
National University, Pusan.
Moorthy, R., Teo, C.-P., 2006. Berth management in container terminal: the template design problem. OR
Spectrum 28 (4), 495–518.
Nishimura, E., Imai, A., Papadimitriou, S., 2001. Berth allocation planning in the public berth system by genetic
algorithms. European Journal of Operational Research 131 (2), 282–292.
Park, K.T., Kim, K.H., 2002. Berth scheduling for container terminals by using a sub-gradient optimization
technique. Journal of the Operational Research Society 53 (9), 1054–1062.
Park, Y.M., Kim, K.H., 2003. A scheduling method for berth and quay cranes. OR Spectrum 25 (1), 1–23.
Rashidi, H., Tsang, E., 2013. Novel constraints satisfaction models for optimization problems in container
terminals. Applied Mathematical Modelling, 37, 3601–3634.
Rosa, R. de A., Resendo, L.C., Lopes, F. T. 2012. Proposta de um modelo matemático para o problema de
alocação de berços para múltiplas cargas (PAB-MC) com restrições temporaris e espacias. In: XXVII
Congresso nacional de Ensino e Pesquisa em Transporte, Joinville.
Stahlbock, R., Voß, S., 2008. Operations research at container terminals: a literature update. OR Spectrum 30
(1), 1–52.
Steenken, D., Voß, S., Stahlbock, R., 2004. Container terminal operation and operations research – a
classification and literature review. OR Spectrum 26 (1), 3–49.
Theofanis, S., Boile, M., Golias, M., 2007. An optimization based genetic algorithm heuristic for the berth
allocation problem. IEEE Congress on Evolutionary Computation 2007 (CEC 2007). IEEE Computer
Society, Washington DC, pp. 4439–4445.
Tong, C.J., Lau, H.C., Lim, A., 1999. Ant colony optimization for the ship berthing problems. In: Thiagarajan,
P.S., Yap, R. (Eds.), Fifth Asian Computing Science Conference (ASIAN’99), vol. 1742 of LNCS.
Springer, Berlin et al., pp. 359–370.
Vacca, I., Bierlaire, M., Salani, M., 2007. Optimization at container terminals: Status, trends and perspectives.
In: Proceedings of the Swiss Transport Research Conference (STRC). Monte Veritá/Ascona, pp. 1–21.
Vis, I.F.A., de Koster, R., 2003. Transshipment of containers at a container terminal: an overview. European
Journal of Operational Research 147 (1), 1–16.
Zhou, P., Kang, H., Lin, L., 2006. A dynamic berth allocation model based on stochastic consideration. In:
Proceedings of the Sixth World Congress on Intelligent Control and Automation (WCICA 2006), vol. 2.
IEEE Computer Society, Washington DC, pp. 7297–7301.
Zhou, P., Kang, H., 2008. Study on berth and quay-crane allocation under stochastic environments in container
terminal. In: Systems Engineering - Theory & Practice, 28 (1) 161 –169.
Wang, F., Lim, A., 2007. A stochastic beam search for the berth allocation problem. Decision Support Systems
42 (4), 2186–2196.
Ivan Bridi Gimenes Rodrigues ([email protected]),
Rodrigo de Alvarenga Rosa ([email protected])
Programa de Pós-Graduação em Engenharia Civil - Transportes, Universidade Federal do Espírito Santo