Abordagens do algoritmo genético de chaves aleatórias viciadas para o problema de alocação em berços
Fernanda Bia Peteam
TESE
Português
T/UNICAMP P441a
[Approaches of the biased random key genetic algorithm for the berth allocation problem]
Campinas, SP : [s.n.], 2024.
1 recurso online (193 p.) : il., digital, arquivo PDF.
Orientador: Kelly Cristina Poldi
Tese (doutorado) - Universidade Estadual de Campinas (UNICAMP), Instituto de Matemática, Estatística e Computação Científica
Resumo: O presente trabalho considera o Problema de Alocação de Navios em Berços (PAB), para determinar a ordem, o local e o horário de atendimento dos navios quando chegam ao porto, com o modelo base utilizado baseado no Problema de Roteamento de Veículos com Janela de Tempo (PRVJT), proposto na...
Ver mais
Resumo: O presente trabalho considera o Problema de Alocação de Navios em Berços (PAB), para determinar a ordem, o local e o horário de atendimento dos navios quando chegam ao porto, com o modelo base utilizado baseado no Problema de Roteamento de Veículos com Janela de Tempo (PRVJT), proposto na literatura, com o objetivo de minimizar o tempo total de permanência dos navios no porto. Propusemos uma adaptação do modelo (PRVJT-O) para passar a considerar o tempo de ociosidade dos berços, uma perspectiva de interesse do porto e não somente dos clientes (donos dos navios). Para resolver os PABs sem e com ociosidade propusemos um modelo de Algoritmo Genético de Chaves Aleatórias Viciadas (BRKGA) com uma decodificação que define a ordem e o local de atracação (berços) de maneira independente, e uma implementação vetorizada buscando um melhor desempenho. Testamos diferentes estratégias para melhorar os resultados obtidos pelo BRKGA, como rodar múltiplas vezes e adotar a melhor solução, utilizar a ferramenta OPTUNA para busca de melhores hiper parâmetros e aplicar \textit{clusterização} na escolha dos pais na fase do cruzamento para uma maior variabilidade nos herdeiros, mas mantendo a característica elitista da fase. Além disso, testamos a utilização das soluções obtidas pelo BRKGA como solução inicial para o CPLEX, ou seja, para a resolução exata do modelo, uma vez que as soluções encontradas pelo BRKGA proposto foram factíveis para o problema. Pudemos comparar diferentes estratégias de resolução utilizando o BRKGA e o BRKGA + CPLEX. Dos testes foi possível concluir que utilizar o resultado de uma única execução do BRKGA ou o CPLEX apenas com limite de tempo não são as melhores opções. Com relação ao tempo computacional e qualidade de solução, concluímos que, para os modelos sem e com ociosidade de berços, as estratégias de combinação com a clusterização e as múltiplas execuções em paralelo com parâmetros fixos foram as estratégia com melhores equilíbrio. No presente trabalho, trazemos também um resumo sobre o Problema de Alocação de Navios em Berços, junto com uma revisão bibliográfica, um pouco sobre a teoria de Algoritmos Genéticos, de Algoritmos Genéticos de Chaves Aleatórias e Algoritmos Genéticos de Chaves Aleatórias Viciadas, assim como sobre clusterização
Ver menos
Abstract: This work considers the Berth Allocation Problem (BAP), to determine the order, location and service time of ships when they arrive at the port, with the base model used based on the Vehicle Routing Problem with Time (PRVJT), proposed in the literature, with the objective of minimizing the...
Ver mais
Abstract: This work considers the Berth Allocation Problem (BAP), to determine the order, location and service time of ships when they arrive at the port, with the base model used based on the Vehicle Routing Problem with Time (PRVJT), proposed in the literature, with the objective of minimizing the total time spent by ships in port. We proposed an adaptation of the model (PRVJT-O) to consider the idle times of berths, a perspective of interest to the port and not just the customers (ship owners). To solve BAPs without and with idleness, we proposed a Biased Random Key Genetic Algorithm (BRKGA) model with a decoding that defines the order and berthing location (berths) independently, and a vectorized implementation, aiming better performance. We tested different strategies to improve the results obtained by BRKGA, such as running multiple times and adopting the best solution, using the OPTUNA tool to search for better hyper parameters and applying clustering in the choice of parents in the crossing phase for greater variability in the heirs, but maintaining its the elitist characteristic. Furthermore, we tested the use of the solutions obtained by BRKGA as an initial solution for CPLEX, that is, for the exact resolution of the model, since the solutions found by the proposed BRKGA were feasible for the problem. We were able to compare different resolution strategies using BRKGA and BRKGA + CPLEX. From the tests it was possible to conclude that using the result of a single execution of BRKGA or CPLEX with only a time limit are not the best options. Regarding computational time and solution quality, we concluded that, for the models without and with idle time of berths, the combination strategies with clustering and multiple executions in parallel with fixed parameters were the strategies with the best balance. In this work, we also bring a summary of the Berth Allocation Problem, along with a bibliographical review, a little about the theory of Genetic Algorithms, Random Key Genetic Algorithms and Biased Random Key Genetic Algorithms, as well as about clustering
Ver menos
Requisitos do sistema: Software para leitura de arquivo em PDF
Aberto
Poldi, Kelly Cristina, 1979-
Orientador
Bressan, Glaucia Maria
Avaliador
Cantane, Daniela Renata
Avaliador
Moretti, Antonio Carlos, 1958-
Avaliador
Abordagens do algoritmo genético de chaves aleatórias viciadas para o problema de alocação em berços
Fernanda Bia Peteam
Abordagens do algoritmo genético de chaves aleatórias viciadas para o problema de alocação em berços
Fernanda Bia Peteam