Hierarchical algorithm for large-scale irregular packing problems

Abstract

To address the challenge of large-scale packing problems, this paper proposes a novel hierarchical algorithm based on the geometrical classification of parts. The algorithm begins by classifying parts into three levels based on their area and fullness and then applies distinct packing strategies to each category. An innovative "shape matching" method is introduced, which, together with the "box stacking" (for rectangular parts) and "gravity packing," forms a comprehensive hierarchical packing system. Level-1 comprises large rectangular parts, which are arranged using the box stacking algorithm. By aligning the corner points of the parts' bounding boxes, this method avoids the hooking issue commonly encountered in gravity packing. Level-2 includes both large, irregular parts and medium-sized parts. They are first processed using the shape matching algorithm, where rotation and translation are applied to achieve contour complementarity. The quality of the match is evaluated using the shape matching coefficient (SMC). If the SMC fails to reach the preset quality threshold, the system switches to box stacking (for large, irregular parts) or gravity packing (for medium-sized parts). Level-3 comprises the remaining smaller parts and those that failed to pack in the previous two levels. For these parts, shape matching is attempted first, and the system resorts to gravity packing in case of failure. The experimental and comparative results demonstrate that the proposed hierarchical algorithm achieves higher material utilization than the traditional gravity packing algorithm. This improvement is facilitated by the box stacking and shape matching strategies, which promote a more orderly and compact arrangement of parts.

Keywords

Large-scale packing / Hierarchical algorithm / Box stacking / Shape matching / Gravity packing / Principle of minimum potential energy

RIGHTS & PERMISSIONS

The Author. Published by Zhejiang University Press Co., Ltd.