Alocação de navios em portos marítimos: aplicação de metaheurísticas

A alocação de navios nos cais marítimos é uma das principais tarefas do processo de gestão de um porto marítimo. Por essa razão, o número de estudos relacionados com o problema de alocação de navios aumentou drasticamente nos últimos anos. A resolução deste problema permite ao porto marítimo melhorar a eficiência de utilização do seu cais, a satisfação dos clientes e aumentar o rendimento do próprio porto, conduzindo assim a um aumento da sua competitividade. Tendo em conta que o problema de alocação de navios do tipo contínuo é considerado um problema NP-difícil, foram tidas em consideração três heurísticas construtivas que, dada uma sequência de inserção, inserem os navios no diagrama tempo-espaço que representa graficamente qualquer solução admissível do problema de alocação de navios. Duas dessas heurísticas, Upper Allocation e Intermedium Allocation, foram desenvolvidas com base na tradicional heurística Bottom-Left. Apesar das heurísticas construtivas desenvolvidas permitirem obter rapidamente uma solução admissível para o problema de alocação de navios e, em particular, a heurística Upper Allocation melhorar os resultados obtidos pela heurística tradicional Bottom-Left, estas não possuem parâmetros aleatórios que permitam obter diferentes soluções. Posto isto, foram desenvolvidas duas metaheurísticas, a Squeaky Wheel Optimization e a Tabu Search with Full Memory, cujo principal objetivo consiste em obter melhores soluções através da construção de diferentes sequências de inserção. Com base nos resultados computacionais obtidos, concluiu-se que a metaheurística Tabu Search with Full Memory apresentou melhores resultados do que a metaheurística Squeaky Wheel Optimization, quer para instâncias de pequena e média dimensão quer para instâncias de maior dimensão.