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

In 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 (P_p) on bins are computed by P_p 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 decision-maker (Pd-maker) determines which combined item is placed on which packing position via a cost function attaining lower values if packing produces less waste. A shipbuilding problem is utilized throughout the paper to explain the proposed method. A given ship hull is packed into bins, and experiments show that the proposed approach is advantageous in terms of minimizing bin waste.