Artigo: The dynamic berth allocation problem for a container port
Akio Imai, Etsuko Nishimura, Stratos Papadimitriou, 1.999
Analisando experimentos computacionais e conclusões
Processo Simples: simples modificação na solução do problema, sem efetuar
mudanças nas atribuições navio-berço bem como atribuições navio-ordem
para cada berço.
Procura encontrar o 1º navio insatisfeito na ordem ascendente de serviço, que
é atendido antes de sua chegada. Se um navio insatisfeito é encontrado, seu
serviço é postergado até seu momento de chegada, consequentemente
atrasando o atendimento dos navios sucessores.
Si
N1
N2
N3
Si
N1
N2
N3
Processo Individual: realiza a atribuição de cada berço como no processo
Simples e, se existir um tempo disponível/ocioso no berço entre 2 serviços
adjacentes de navios, um navio que está programado para ser atendido
posteriormente, é encaixado no espaço ocioso.
“ Neste processo nenhum navio é substituído entre os diversos berços.”
Si
N1
N2
Si
N1
N2
Processo que atua sobre o outro: é o mesmo processo Individual porém com
um acréscimo de processo. Se após a aplicação do processo Individual ainda
restar algum tempo ocioso em algum berço, o processo é refeito para ser
usado no serviço de navios programados em outros berços.
Selecionando navios conforme a ordem de chegada, um navio é candidato se
atender a seguinte condição: seu tempo total de permanência no porto e o
tempo resultante de seus sucessores no novo berço é menor que aquele no
berço originalmente atribuído.
Foram resolvidos problemas com 5, 7 e 10 berços cada um contendo
25 e 50 navios, gerando 6 problemas protótipos.
Problem size
(berths
x ships)
Si
5x25
7x25
10x25
5x50
7x50
10x50
SIMPLE
INDIVIDUAL
INTERACT
GAP(%)
CPU(s)
Interation
GAP(%)
CPU(s)
Interation
GAP(%)
CPU(s)
Interation
1
7,1
46,2
200,0
7,1
45,7
200,0
10,8
44,8
200,0
2
0,7
34,4
180,1
0,7
35,3
180,1
1,3
34,0
180,1
3
0,1
9,7
53,8
0,1
8,2
50,7
0,1
8,0
50,7
4
0,0
0,1
1,0
0,0
0,1
1,0
0,0
0,1
1,0
1
19,4
59,8
200,0
19,2
62,4
200,0
27,8
74,8
200,0
2
4,2
51,4
200,0
4,2
52,4
200,0
6,6
50,5
200,0
3
0,5
34,3
160,3
0,5
32,1
160,3
0,9
31,9
160,3
4
0,0
0,1
1,1
0,0
0,1
1,1
0,0
0,1
1,1
1
32,0
81,4
200,0
32,0
81,9
200,0
39,9
85,2
200,0
2
9,2
68,0
200,0
9,2
67,7
200,0
13,1
70,6
200,0
3
2,1
48,6
200,0
2,1
48,9
200,0
4,2
51,3
200,0
4
0,1
0,0
140,8
0,1
30,2
140,8
0,2
31,1
140,5
1
8,1
718,2
200,0
8,0
719,1
200,0
12,3
748,4
200,0
2
0,2
188,6
60,7
0,2
190,5
60,7
0,2
196,1
60,7
3
0,0
1,9
1,0
0,0
1,9
1,0
0,0
2,0
1,0
4
0,0
1,4
1,0
0,0
1,4
1,0
0,0
1,5
1,0
1
25,6
983,0
200,0
25,4
983,3
200,0
46,4
1024,1
200,0
2
2,9
807,2
200,0
2,9
800,9
200,0
7,5
834,9
200,0
3
0,0
67,5
20,9
0,0
67,1
20,9
0,0
69,6
20,9
4
0,0
1,8
1,0
0,0
1,8
1,0
0,0
1,9
1,0
1
53,1
1380,2
200,0
53,0
1438,3
200,0
76,1
1500,5
200,0
2
10,9
1146,8
200,0
10,9
1139,7
200,0
19,9
1209,1
200,0
3
1,2
1113,3
200,0
1,1
947,5
200,0
4,4
1059,0
200,0
4
0,0
122,4
40,8
0,0
123,3
40,8
0,0
130,2
40,8
GAP=(valor da solução factível-limite inferior)*100/limite inferior
Interation= número no qual o processo termina
Os autores tiraram algumas conclusões:
•Melhores soluções são obtidas quando todos Si’s se aproximam do
momento de chegada do último navio;
•Os problemas foram resolvidos com o limite de 200 iterações, porém
nenhuma solução significante foi observada nas últimas 100 iterações;
•Quando o GAP for menor que 1 significa que a solução ótima foi
encontrada;
•De todos os 3 problemas, o processo INDIVIDUAL permitiu menores GAP’s ,
identificando melhores soluções;
•Embora os 3 procedimentos sejam diferentes em complexidade, não há
diferença no tempo computacional entre eles;
•Este artigo propõe um algoritmo para planejar a atribuição navio-berçoordem, entretanto, pode ser útil para tomar decisões em quantos berços
operar.