Irregular bin packing considering loading balancing

Author(s)

Raquel Akemi Okuno Kitazume da Silva

• Document type: Master's Dissertation
• Press: São Carlos.
• Institution: Universidade de São Paulo (USP). Instituto de Ciências Matemáticas e de Computação (ICMC/SB)
• Defense date: 2017-06-21

Examining board members

Maristela Oliveira dos Santos; Thiago Alves de Queiroz; Elsa Marília da Costa e Silva; Franklina Maria Bragion de Toledo

• Advisor: Marina Andretta

Abstract

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. (AU)

• FAPESP's process: 15/16298-4 - Irregular bin packing considering loading balancing
• Grantee: Raquel Akemi Okuno Kitazume da Silva
• Support Opportunities: Scholarships in Brazil - Master