Artigo: The dynamic berth allocation problem for a container port
Akio Imai, Etsuko Nishimura, Stratos Papadimitriou, 1.999
Analisando a formulação para o sistema dinâmico de alocação de berços
Minimizar T  k  1 Cij  Si  Aj  xijk   (T  k  1)Yijk
iB jV kO
iB jWi kO
i(1,..., I ) B
j(1,...T ) V
k (1,...T )O
Si
conjunto deberços
conjunto de navios
conjunto deordens de serviços
momentoem queoberçoi setorna disponível para o planejamento de alocação deberços
A
momento dechegada do navio j
j
Ci j
xi
jk
tempo de manipulação gasto pelo navio j noberçoi
1 seo navio j é atendidocomo o kth navio noberçoi
0 emcaso contrário
Pk é o subconjunt o de O talque Pk 
p/p kO
Wi é o subconjunt o de navioscom A j Si
Yijk é o momentodisponível do berço i entre a partidado k  1navioe a chegadado kth navioquando o navio j é atendidocomoo kth navio
Sujeito à:
 x
iB kO
x
jV
i jk
ijk
 j V
1
1
 i  B, k  O
xijk 0,1 i  B,
 (C x
lV mPk
• Cada navio deve ser atendido por um
berço em uma seqüência de atendimento.
il ilm
• Cada berço atende um navio por vez.
j V , k  O
 Yilm )  Yijk  ( Aj  Si ) xijk  0
i  B, jWi , k  O
• Assegura que os navios devem ser
atendidos depois de suas chegadas.
• O primeiro termo da esquerda
representa o tempo de duração entre Si e
o momento quando o último de seus
predecessores deixa o porto; ou seja, é o
tempo de duração entre Si e o início do
serviço do navio j.
Atribuição de navios ao berço i
Si
Yi11 A1
xi11
Yi42
A4
xi42
Yi53
A5
A2
A3
xi53
xi24
xi35
Exemplificando:
Para o caso DBAP: 3 navios e 1 berço;
T=3;
k=3;
i=1;
C11=120min;
C12=240min;
C13=180min;
S1=8:20h
N1 8:30h
N2 8:40h
N3 14:30h
t
Ver resolução no GAMS
Como ordenar o
atendimento dos navios?
Solução GAMS:
S1=80
Y111=10
O1
90
O2
O3
210
N1
210
100
450
N2
450
370
630
N3
Z=730
Y111=10 ( tempo ocioso do berço 1 antes de atender o navio 1 na ordem 1).
Exemplificando:
Para o caso DBAP: 3 navios e 2 berços;
T=3;
k=3;
i=2;
C11=120min;
C12=240min;
C13=180min;
S1=8:20h
C21=110;
C22=200;
C23=170;
N1 8:30h
N2 8:40h
t
Como ordenar o
atendimento dos navios?
N3 14:30h
S2=8:20h
Ver resolução no GAMS
Solução GAMS:
S2=80
O1
Y112=10
O2
90
O3
200
N1
370
Y133=170
550
N3
S1=80
Y223=20
100
340
N2
Z=520
Y212=10 ( tempo ocioso do berço 1 antes de atender o navio 1 na ordem 2);
Y233=170 (tempo ocioso do berço 1 antes de atender o navio 3 na ordem 3);
Y123=20 (tempo ocioso do berço 2 antes de atender o navio 2 na ordem 3).
Comparando o métodos SBAP x DBAP:
• No SBAP com j=3 e i=2, onde todos os navios chegavam juntos e
neste mesmo momento os berços se tornavam, ambos, disponíveis,
obteve-se uma solução com Z=600, enquanto no método DBAP com
j=3 e i=2, onde cada navio chegava em um momento diferente do
outro, mesmo gerando tempo ocioso nos berços, a solução foi de
Z=520.
Próximo Assunto:
• Relaxação Lagrangeana do DBAP.