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; iB 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 iB 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 iB, 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