Heurística GRASP para o Problema de Alocação de Navios em Berços

Abstract

O presente trabalho tem por objetivo, tratar o Problema de Alocação de Navios em Berços usando a metaheurística GRASP. Tal problema tem sido objeto de estudo de muitos pesquisadores nos últimos anos, como em [1], [2] e [4], tendo em vista o forte impacto do setor de transporte marítimo no comércio mundial. O Problema de Alocação de Navios em Berços consiste em atribuir navios em determinados locais, denominados berços, decidindo o horário e em qual berço o navio devera´ atracar. O problema foi aqui tratado como discreto, onde o porto e´ dividido em vários berços cujo atendimento e´ dado a um navio por vez, e dinâmico, isto e´, são dados os horários de chegada de cada navio e estes só´ poderão ser atendidos a partir desses horários dados, mesmo que cheguem antes ao porto. Deve-se ainda, obedecer os horários de abertura e encerramento de cada berço, bem como o horário limite que cada navio tem para permanecer atracado no berço. Além disso, como em [3] e [4], o problema foi formulado como um Problema de Roteamento de Veículos de Mutilas Garagens com Janela de Tempo, onde os navios são vistos como veículos e os berços como garagens. Os autores, [3] e [4], propõem heurísticas para resolução de uma formulação relaxada, na qual as restrições relacionadas a` janela de tempo são penalizadas e incluídas na função– objetivo, resultando em uma formulação equivalente a um Problema de Roteamento de Veículos Sem Janela de Tempo. Neste trabalho propomos uma heurística baseada no Greedy Randomized Adaptive Search Procedures, GRASP, [5], [6] para obter uma solução do Problema com sua formulação original, sem penalização. Dessa forma, apresentamos uma abordagem diferente das encontradas em [3] e [4]. O GRASP consiste de duas fases, a primeira, construtiva e a segunda de busca local. Para a primeira fase, foi elaborada uma estratégia para obtenção de uma solução viável para o problema original. A cada etapa, é construída uma lista de navios candidatos a serem alocados em um dos berços. A seleção de navios para compor a lista de candidatos é feita através de uma função de mérito, introduzida neste trabalho, que visa quantificar a urgência de atendimento de cada navio, ponderando tempo de atendimento e de espera, custo associado ao navio, horários de funcionamento dos berços e a janela de tempo de cada navio. Obtido um conjunto de soluções viáveis, são então selecionadas as de menor custo e acionado um processo de intensificação, visando obter, a partir desta solução, um ótimo local. A heurística para a fase construtiva foi ja´ testada computacionalmente. Realizamos testes com 7, 10, 20, 40, 60 navios para serem alocados em, respectivamente, 2, 3, 5, 8, 13 berços.  Em todos os testes obtivemos uma porcentagem alta de soluções viáveis com tempo médio de 0.1 segundo. A fase de intensificação esta´ em elaboração.