On the three-dimensional bin packing using rotations
Authors
Abstract
One of the most interesting variations of the problem of the 3-Dimensional Bin Packing problem (3BPP) is the determination of the minimum number of three-dimensional rectangular bins that are required for orthogonally allocating a given set of three-dimensional rectangular items without overlap and minimizing the occupied space: the 3BPP--min problem. This is, of course, yet another NP-Hard multi-criteria combinatorial optimization. One of the most obvious applications for this problem is the one that occurs daily in warehouses management systems, either by using manual or automatic packing.We present a new approach for the 3BPP--min problem where 90 degrees rotations are allowed in order to allow for a more compact packing. Most of the known heuristic solutions for this type of packing are based on the well-known works of Martello, Pisinger and Vigo. Boschetti has recently introduced new lower bounds specifically tailored for packing using the possibility of rotations of items that we used for designing the new heuristic algorithm. This algorithm uses both this new lower bounds and the theory of non-dominated solutions for deciding on the best packing for a 3BPP--min instance. Computational results show the effectiveness of the new approximation algorithm That shows to be faster and achieve lower occupation of space, thus, better compaction.