O problema de empacotamento de itens irregulares com balanceamento da carga é encontrado no carregamento de aviões, caminhões e navios. O objetivo é empacotar itens irregulares utilizando o menor número de recipientes possível de forma que os recipientes estejam balanceados, que os itens não se sobreponham e estejam inteiramente contidos no recipiente. Neste trabalho, propomos três heurísticas bases com três variações cada para o problema com recipientes retangulares e irregulares. As heurísticas utilizam abordagens diferentes para representar os itens e para fazer o balanceamento. Uma das heurísticas utiliza malha para representação dos itens e faz o balanceamento dividindo o recipiente em quadrantes e revezando a alocação dos itens entre eles de forma que o balanceamento é feito de forma indireta. Tal heurística resolve o problema tanto para recipientes retangulares quanto irregulares. A segunda heurística utiliza a representação dos itens por polígonos e impossibilita a sobreposição de itens utilizando a técnica do nofit polygon. A heurística constrói a solução item por item, sem posições fixas e a cada item alocado, os itens são deslocados em direção ao centro de gravidade desejado do recipiente. Esta heurística resolve apenas problemas com recipientes retangulares. A última heurística é uma adaptação da heurística anterior para a resolução do problema com recipientes irregulares, de forma que o problema é resolvido em duas fases. Cada heurística base possui três variações cada, totalizando nove heurísticas. As heurísticas foram comparadas com outro trabalho da literatura e conseguiram melhorar os resultados para nove das dezenove instâncias testadas. / The irregular bin packing problem with load balancing is found in the loading of airplanes, trucks and ships. The aim is to use as few bins as possible to pack all the items so that all bins are balanced, items do not overlap and are fully contained in the bin. In this work, we propose three base heuristics with three variations each for the problem with rectangular and irregular bin. The three heuristics use different approaches to represent the items and to balance the bin. One of the heuristics uses a grid to represent the items and does the balancing by dividing the container into quadrants and alternating the allocation of items between them so that the balancing is done indirectly. Such heuristic solves the problem for both rectangular and irregular bins. The second heuristic uses the representation of items by polygons and uses the nofit polygon technique. The heuristic constructs the solution item by item, with no fixed positions and with each item allocated, the items are shifted towards the desired center of gravity of the bin. This heuristic only solves problems with rectangular bins. The last heuristic is an adaptation of the previous one to solve the problem with irregular bins, so that the problem is solved in two phases. Each base heuristic has three variations, totaling nine heuristics. The heuristics were compared with other work in the literature and managed to improve the results for nine of the nineteen instances tested.
| Identifer | oai:union.ndltd.org:IBICT/oai:teses.usp.br:tde-05102017-170921 |
| Date | 21 June 2017 |
| Creators | Raquel Akemi Okuno Kitazume da Silva |
| Contributors | Marina Andretta, Thiago Alves de Queiroz, Elsa Marília da Costa e Silva, Franklina Maria Bragion de Toledo |
| Publisher | Universidade de São Paulo, Ciências da Computação e Matemática Computacional, USP, BR |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da USP, instname:Universidade de São Paulo, instacron:USP |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0021 seconds