Artigo: Berth allocation planning in the public berth system by
genetic algorithms
Akio Imai, Etsuko Nishimura, Stratos Papadimitriou, 2.001
Analisando a parte introdutória
Características:
Até então considera-se que no DBAP cada berço atende somente um navio
por vez;
Na realidade ele pode atender múltiplos navios desde que o total do
comprimento dos navios seja inferior ao total do comprimento do berço (já
considerando uma margem de sobra);
Lj
Lj
Berço i
QLi
Onde: QLi é comprimento do berço i e Lj é o comprimento do navio j

A escolha do uso do Algoritmo Genético foi devido este ser utilizado para
problemas do tipo NP-hard.

Chan e Imai (1996) desenvolveram uma heurística utilizando o Algoritmo
Genético para BAP.

O artigo de estudo em questão aplica o GA ao BAP com atendimento de
múltiplos navios e para isso emprega 2 diferentes tipos de representações
de cromossomos, sendo um deles utilizado no trabalho de Chan e Imai.

Objetivo do DBAP é minimizar o tempo total de serviço;

O DBAP considera que:

Cada navio deve ser atendido somente uma vez em um berço;


Os navios devem ser atendidos com condições físicas aceitáveis dos
berços, tais como profundidade do calado e comprimento do mesmo;
O tempo de manipulação de cada navio é dependente do berço onde
são atendidos, além da localização dos contêineres que serão
carregadas no navio.
Formulação do problema
Min    m j  Aj  Cij  xij
•Minimizar o tempo
gasto pelos navios;
iB j V
total
 1  j V ;
Cada navio é atendido uma
única vez em um berço;
m j  Aj  0  j V ;
•Os
navios
devem
ser
atendidos após sua chegada;
x
iB
ij
Onde:
i(=1,...,I) є B é o conjunto de berços;
Aj é o momento de chegada do navio j;
j(=1,...,T) є V é o conjunto de navios;
WDi é a profundidade d’água no berço i;
Cij é o tempo de manipulação do navio j no berço i;
QLi é o comprimento do berço i;
Dj é a altura do navio j (profundidade do calado) incluindo a distância vertical de segurança para
aberçamento;
Lj é o comprimento do navio j incluindo o comprimento horizontal de segurança;
Xij=1, se o navio j é atendido no berço i; 0, em caso contrário;
Yjz=1, se o navio j inicia seu serviço quando o navio z está sendo atendido no mesmo berço; 0, em
caso contrário;
Mj é o momento de início do atendimento do navio j.
 WD  D  x
i B
i
j
ij
 0  j V ;


 QLi   LzY jz xiz  L j  xij  0  j V ;

i B 
z V  j

•Garante que a altura do
navio
(profundidade
do
calado)
seja
menor
a
profundidade
d’água
do
berço;
•Garante que a soma dos
comprimentos dos navios
não
ultrapasse
o
comprimento do berço onde
estão sendo manipulados;
Onde:
i(=1,...,I) є B é o conjunto de berços;
j(=1,...,T) є V é o conjunto de navios;
Aj é o momento de chegada do navio j;
WDi é a profundidade d’água no berço i;
Cij é o tempo de manipulação do navio j no berço i;
QLi é o comprimento do berço i;
Dj é a altura do navio j (profundidade do calado) incluindo a distância vertical de segurança para
aberçamento;
Lj é o comprimento do navio j incluindo o comprimento horizontal de segurança;
Xij=1, se o navio j é atendido no berço i; 0, em caso contrário;
Yjz=1, se o navio j inicia seu serviço quando o navio z está sendo atendido no mesmo berço; 0, em
caso contrário;
Mj é o momento de início do atendimento do navio j.

 

 mz   Ciz xiz  m j  *  m j   Cij xij  mz  y jz xiz  0  i  B, j V , z V   j ;
i B
i B

 


 

 mz   Ciz xiz  m j  *  m j   Cij xij  mz  * 1  y jz xiz   0  i  B, j V , z V   j ;
i B
i B

 

•Estas duas restrições apresentam o relacionamento entre os navios j e z
sendo atendidos no mesmo berço.
Onde:
i(=1,...,I) є B é o conjunto de berços;
j(=1,...,T) є V é o conjunto de navios;
Aj é o momento de chegada do navio j;
WDi é a profundidade d’água no berço i;
Cij é o tempo de manipulação do navio j no berço i;
QLi é o comprimento do berço i;
Dj é a altura do navio j (profundidade do calado) incluindo a distância vertical de segurança para
aberçamento;
Lj é o comprimento do navio j incluindo o comprimento horizontal de segurança;
Xij=1, se o navio j é atendido no berço i; 0, em caso contrário;
Yjz=1, se o navio j inicia seu serviço quando o navio z está sendo atendido no mesmo berço; 0, em
caso contrário;
Mj é o momento de início do atendimento do navio j.


 m j   Cij xij 
i B




 mz   Ciz xiz 
i B


•Representa a partida do navio j


 m j   Cij xij  mz 
i B




 mz   Ciz xiz  m j 
i B


Representa a partida para o navio z
•(1) Diferença entre o momento de início do
atendimento do navio z e o momento de partida do
navio j;
•(2) Diferença entre o início do atendimento do navio j
e o momento de partida do navio z.
Onde:
i(=1,...,I) є B é o conjunto de berços;
j(=1,...,T) є V é o conjunto de navios;
Aj é o momento de chegada do navio j;
WDi é a profundidade d’água no berço i;
Cij é o tempo de manipulação do navio j no berço i;
QLi é o comprimento do berço i;
Dj é a altura do navio j (profundidade do calado) incluindo a distância vertical de segurança para
aberçamento;
Lj é o comprimento do navio j incluindo o comprimento horizontal de segurança;
Xij=1, se o navio j é atendido no berço i; 0, em caso contrário;
Yjz=1, se o navio j inicia seu serviço quando o navio z está sendo atendido no mesmo berço; 0, em
caso contrário;
Mj é o momento de início do atendimento do navio j.
•Se o navio j terminar o serviço antes do início do navio z, Equação (1) é
negativa e Equação (2) é positiva; se forem atendidos na ordem inversa, a
Equação (1) é positiva e a Equação (2) é negativa.
•Exemplos;
•Modelagem no GAMS;
•E por fim,
xij 0,1 iB, j V ;
y jz 0,1  j, z  V ;
m j é INTEIRO  j  V ;
Esboço do procedimento de solução
•Para resolver o DBAP o problema foi dividido em N sub-problemas (SUBs)
de alocação de berços como um fator temporário, conforme a figura abaixo:
Subproblema 1
CHEGADA
Navio1 Navio2 Navio3
Subproblema 2
Navio4
Navio5 Navio6 Navio7 Navio8
Tempo
ABERÇAMENTO
Berço1
Berço2
Berço3
Navio2
Navio1
Navio6
Navio3
Navio7
Navio4
Navio5
Navio8