A two-dimensional bin packing-based split-and-pack approach for decomposing large three-dimensional structures into convex items

Abstract

ABSTRACTIn this study, we present a technique to pack a three-dimensional (3D) structure into bins to minimize bin waste. The proposed approach is different from two-dimensional bin packing (2Dbp) methods: Rather than starting with fixed size items of the 3D structure (with widths or heights smaller than those of the bin), as is done in 2Dbp algorithms, combined items (with widths or heights that can be greater than those of the bin) are utilized. These items are obtained by combining the neighboring items. A method of generating combined items from a 3D structure is first explained. The packing approach for the combined items obtained is then described. Four operators are introduced for combined items’ packing. Packing positions (Pp) on bins are computed by Pp finder. Following this, the orientations of combined items are changed via orientation modifier to find better packing orientations for combined items. Split operator splits combined items during packing if they exceed the bin boundary. Placement d...