19fev2025
10:00 Defesa de Mestrado Auditório do IC3
Tema
Uma Heurística de Busca em Árvore para o Problema de Carregamento Tridimensional em um Único Contêiner
Aluno
Lucas Guesser Targino da Silva
Orientador / Docente
Flávio Keidi Miyazawa - Coorientador: Thiago Alves de Queiroz
Breve resumo
O objetivo do problema de carregamento tridimensional em um único contêiner é carregar um contêiner com itens a fim de maximizar o uso do volume. Os itens são paralelepípedos e podem girar, mas somente empacotamentos ortogonais são permitidos. O problema é bastante relevante para a indústria, especialmente logística e cadeia de suprimentos. Devido à sua complexidade, heurísticas continuam sendo as abordagens mais adequadas e amplamente utilizadas. A heurística projetada usa a representação por cobertura com espaços vazios maximais para o espaço residual e a geração de blocos guilhotinados. Ela aloca blocos no canto de ancoragem do espaço vazio com a menor distância manhattan de ancoragem. Os blocos são selecionados usando uma função fitness de dois estágios e uma busca gulosa seleciona os empacotamentos parciais mais promissores. A estratégia de busca utiliza beam search incorporada em um método de esforço duplo. A heurística aprimora quatro aspectos dos métodos existentes. Primeiro, um estudo sistemático identifica as estruturas de dados com melhor desempenho para a representação do espaço residual. Em segundo lugar, emprega-se o pacote irace de configuração automática de algoritmo para otimizar os meta-parâmetros. Em terceiro lugar, evitam-se recálculos de empacotamentos completos com um recurso simples e eficaz de memória na busca gulosa. Por fim, a função fitness de ordenação de blocos é modificada para duas etapas a fim de melhorar sua adaptabilidade. Experimentos computacionais com as 1600 instâncias BR mostram a eficácia das novas propostas. As estruturas de dados melhoram os resultados em 0,21% com um tamanho de efeito de 0,21, o recurso de memória melhora em 0,08% com um tamanho de efeito de 0,08, meta-parâmetros superiores melhoram em 0,24% com um tamanho de efeito de 0,24, a função fitness de dois estágios melhora em 0,03% com um tamanho de efeito de 0,03. A heurística supera o estado da arte em 0,58% com um tamanho de efeito de 0,58 para 30 segundos de limite de tempo e em 0,26% para 10 segundos. Por fim, a análise bayesiana mostra uma confiança geral de 100% na significância dos resultados.
Banca examinadora
Titulares:
| Flávio Keidi Miyazawa | IC/UNICAMP |
| Ignacio Araya Zamorano | INF/PUCV |
| Horacio Hideki Yanasse | ICT/UNIFESP |
Suplentes:
| Fábio Luiz Usberti | IC/UNICAMP |
| Kelly Cristina Poldi | IMECC/UNICAMP |