Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/331235
Type: TESE DIGITAL
Degree Level: Doutorado
Title: Recent advances on the berth allocation problem = Avanços recentes ao problema de alocação de berços
Title Alternative: Avanços recentes ao problema de alocação de berços
Author: Barbosa, Flávia, 1989-
Advisor: Yamakami, Akebo, 1947-
Abstract: Resumo: O transporte de mercadorias por navios aumentou ao longo dos anos. Neste contexto, o Problema de Alocação de Berços (BAP) surge e torna-se fundamental para garantir a eficiência dos terminais marítimos, ao decidir onde e quando alocar o navio no horizonte de planejamento, levando em consideração restrições de tempo e espaço. Uma vez que o problema foi provado ser NP-hard, este estudo propõe um método exato e uma análise de muitas metaheurásticas para resolvê-lo. Primeiro, considerando o BAP como um problema de sequenciamento de tarefas de máquinas paralelas, uma abordagem é proposta com base em uma Metaheurística Evolutiva, com o objetivo de encontrar várias soluções de boa qualidade em uma única rodada do algoritmo, considerando explicitamente o BAP com múltiplos objetivos. Um limitante inferior baseado em um problema de fluxo máximo foi derivado para avaliar a qualidade das soluções. Em seguida, com base em um problema de roteamento de veículo com janelas de tempo, um algoritmo de decomposição Benders e suas variantes são revisados e aplicados ao BAP. Então, um algoritmo híbrido com base no Algoritmo Genético e Busca Dispersa é desenvolvido e a Análise Envoltória de Dados é adotada para escolher a combinação eficiente de operadores para o algoritmo proposto. Como a maioria dos trabalhos na literatura usa em seus experimentos computacionais dados gerados aleatoriamente, dificultando as comparações entre pesquisas, esta tese também propõe um gerador de dados para o BAP, permitindo que a geração de problemas-teste que sejam comumente usada, padronizando as comparações em trabalhos futuros. Os dados são gerados usando diferentes parâmetros e a dificuldade de resolver o BAP com esses dados é analisada através do CPLEX. Finalmente, as instâncias classificadas como as mais difíceis são resolvidas através de duas metaheurísticas

Abstract: The intermodal transportation of goods by vessels has increased over the years. In this context, the Berth Allocation Problem (BAP) arises and becomes fundamental to guarantee the efficiency of the maritime terminals, deciding where and when to allocate the vessel over a planning horizon taking into account constraints of time and space. Once the problem is proved NP-hard, this study proposes a exact method and analyzes many metaheuristics for tackling the problem. First, considering the BAP as a parallel-machine scheduling problem, an approach for this problem is proposed based on an Evolutionary Metaheuristic, aiming to find several good quality solutions in a single round of the algorithm, considering explicitly the BAP with multiple objectives. A lower bound based on a maximal flow problem was derived in order to evaluate the quality of the solutions. Next, based on a heterogeneous vehicle routing problem with time windows a basic Benders Decomposition algorithm and its variants are reviewed and applied to the BAP. Then, a hybrid optimization procedure based on Genetic Algorithm (GA) and Scatter Search (SS)is developed, and data envelopment analysis (DEA) is adopted to choose the efficient combination of the operators for the algorithm proposed. Because most papers in literature use in their experiments data generated randomly, making comparisons between researches difficult, this thesis proposes a problem generator for the BAP, allowing the generation of appropriate test problems to be commonly used with specific desired properties and under controlled conditions. The data are generated using different parameters and the difficulty of solving the BAP with such data is analyzed through the resolution using the CPLEX. Finally, the instances classified as more difficult are solved through two metaheuristics implemented
Subject: Problema de alocação de berços
Meta-heurística
Programação matemática
Language: Inglês
Editor: [s.n.]
Citation: BARBOSA, Flávia. Recent advances on the berth allocation problem = Avanços recentes ao problema de alocação de berços. 2018. 1 recurso online (136 p.). Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação, Campinas, SP. Disponível em: <http://www.repositorio.unicamp.br/handle/REPOSIP/331235>. Acesso em: 3 set. 2018.
Date Issue: 2018
Appears in Collections:FEEC - Tese e Dissertação

Files in This Item:
File SizeFormat 
Barbosa_Flavia_D.pdf3.92 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.