Apresentações
Problema do carregamento de contentores pelo método GRASP
Hugo Duque Caldeira
— ISEP, INESC Porto
José Soeiro Ferreira
— FEUP, INESC Porto
O problema de carregamento de contentores (empacotamento 3D) consiste, no essencial, na afectação de objectos paralelepipédicos (as caixas que constituem a carga) a objectos paralelepipédicos maiores (contentores/camiões), de modo a optimizar o espaço utilizado, atendendo a exigências geométricas. Outros aspectos estão normalmente associados a estes problemas, como a ordem de entrega (de encomendas), a distribuição do peso da carga no contentor, o equilíbrio da carga, a orientação de caixas e o número mínimo de contentores. A resolução deste tipo de problemas encontra aplicações muito diversificadas, entre empresas industriais que diariamente expedem os seus produtos em camiões ou contentores, até empresas de serviços de transporte de mercadorias.
Existem várias publicações neste âmbito, em que a abordagem aos problemas é suportada em técnicas ‘clássicas’ de optimização inteira ou heurísticas dedicadas e outros, mais recentes, em que começam a ser usadas meta-heurísticas, como por exemplo, pesquisa tabu e algoritmos genéticos.
Problemas de carregamento complicados, que envolvem várias condições e funcionalidades práticas são descritos e tratados neste trabalho. O método GRASP - Greedy Randomized Adaptive Search Procedure é proposto para a sua resolução.
Tendo em conta a complexidade computacional destes problemas, a escolha do GRASP como método-tentativa para os resolver pareceu adequada, atendendo, nomeadamente, a alguma facilidade de adaptação e implementação e ao reduzido número de parâmetros que necessitam de ser inicializados e afinados – deixando mais disponibilidade para o desenvolvimento de estruturas de dados eficientes, por forma a obter mais rapidamente soluções.
O GRASP é um processo iterativo em que cada iteração consiste em duas fases: uma fase construtiva, em que é produzida uma solução admíssivel através de um algoritmo semi-guloso, e uma fase de melhoramento, onde se tenta melhorar a solução obtida com um algoritmo de pesquisa local. Depois das iterações pretendidas estarem concluídas, a melhor solução é apresentada.
Em linhas gerais, a forma como o método foi desenvolvido passa pela construção de soluções com a utilização de duas listas, uma de espaços livres e outra de caixas ainda por colocar no contentor. Inicialmente a lista de espaços livres tem um número de elementos igual ao número de contentores pretendido, em que as dimensões são iguais às dimensões dos contentores vazios. À medida que as caixas são seleccionadas para serem colocadas, avaliam-se todas as orientações permitidas da caixa em todos os espaços livres onde a caixa cabe. A caixa é colocada num espaço livre em que o volume de espaço desperdiçado resultante seja o menor possível e que respeite outras condições práticas que se queiram implementadas (ordem de entrega, distribuição de peso,...).
Finalmente, o método de resolução seleccionado será também ilustrado com soluções de problemas reais disponíveis bem como serão apresentados resultados computacionais relativos a instâncias conhecidas, de forma a proceder a uma avaliação possível.
Palavras-chave
Carregamento, Optimização combinatória, GRASP.