Meta-heurística VNS para o problema de carregamento de paletes do distribuidor
Resumo
Resumo : Neste artigo o "Problema de Carregamento de Paletes do Distribuidor" (Distributor’s Pallet Loading Problem - DPLP) de uma grande empresa do setor alimentício é abordado. Uma meta-heurística é utilizada para resolver o problema, considerando uma transformação do DPLP em 2 sub-problemas: o Bin Packing, onde camadas completas de caixas semelhantes formam os itens, e os paletes representam os bins, e um problema de carregamento em duas dimensões com as caixas restantes. Um algoritmo de Busca em Vizinhanc¸a Variável (VNS) foi desenvolvido para resolver o Bin Packing, e uma heurística gulosa para o carregamento 2D. Resultados computacionais indicam que o VNS proposto encontra soluções ótimas para grande parte do conjunto de instâncias do BPP do repositório OR-Library de forma rápida, e representações gráficas dos padrões de carregamento para a heurística 2D indicam um bom aproveitamento da área dos paletes. Também foram realizados testes em instâncias do estudo de caso, indicando que o método é eficaz para a utilização prática na empresa Abstract : This article addresses a real case of the Distributor’s Pallet Loading Problem (DPLP) in a large company in the food sector. The approach adopted starts from the transformation of DPLP into 2 other problems: a Bin Packing, where complete layers of similar boxes form the items whereas the pallets represent the bins, and a two-dimension loading problem with the remaining boxes. A Variable Neighborhood Search (VNS) algorithm was developed to solve the Bin Packing and a greedy heuristic was designed to solve the 2D loading. Computational results indicate that VNS finds optimal solutions for a large part of the Bin Packing instances from the OR-Library repository in a low computational time (seconds), and graphical representations of loading patterns for the 2D heuristic indicate good use of the pallet area