Similar articles

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.

大规模不规则排样问题的分级算法

[1]Albano A, Sapuppo G, 1980. Optimal allocation of two-dimensional irregular shapes using heuristic search methods. IEEE Trans Syst Man Cybern, 10(5):242-248.

[2]Al Theeb NA, Hayajneh MT, Jaradat MY, 2021. New strategy to improve the dotted board model for solving two dimensional cutting and packing problems. Comput Ind Eng, 159:107467.

[3]Baker BS, Coffman EG, Rivest RL, 1980. Orthogonal packings in two dimensions. SIAM J Comput, 9(4):846-855.

[4]Binkley KJ, Hagiwara M, 2007. Applying self-adaptive evolutionary algorithms to two-dimensional packing problems using a four corners’ heuristic. Eur J Oper Res, 183(3):1230-1248.

[5]Chazelle B, 1983. The bottom-left bin-packing heuristic: an efficient implementation. IEEE Trans Comput, C-32(8):697-707.

[6]Chen M, Huang WQ, 2007. A two-level search algorithm for 2D rectangular packing problem. Comput Ind Eng, 53(1):123-136.

[7]Cheng SK, Rao KP, 2000. Large-scale nesting of irregular patterns using compact neighborhood algorithm. J Mater Process Technol, 103(1):135-140.

[8]Costa MT, Gomes AM, Oliveira JF, 2009. Heuristic approaches to large-scale periodic packing of irregular shapes on a rectangular sheet. Eur J Oper Res, 192(1):29-40.

[9]Dowsland KA, Dowsland WB, Bennell JA, 1998. Jostling for position: local improvement for irregular cutting patterns. J Oper Res Soc, 49(6):647-658.

[10]Francescatto M, Júnior AN, 2025. Two-dimensional bin packing, cutting stock, and open dimension problems: a survey of practical requirements. Comput Oper Res, 183:107209.

[11]Guerriero F, Saccomanno FP, 2023. A hierarchical hyper-heuristic for the bin packing problem. Soft Comput, 27(18):12997-13010.

[12]Guo BS, Wang YC, Wang Z, et al., 2025. Irregular multi-plate packing based on the dotted board model. Comput Ind Eng, 209:111439.

[13]Hopper E, 2000. Two-Dimensional Packing Utilising Evolutionary Algorithms and Other Meta-Heuristic Methods. PhD Dissemination, University of Wales, Cardiff, United Kingdom.

[14]Lai XJ, Hao JK, Yue D, et al., 2025. A heuristic algorithm with multi-scale perturbations for point arrangement and equal circle packing in a convex container. Comput Oper Res, 181:107099.

[15]Lee WC, Ma H, Cheng BW, 2008. A heuristic for nesting problems of irregular shapes. Comput-Aided Des, 40(5):625-633.

[16]Liu DQ, Teng HF, 1999. An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles. Eur J Oper Res, 112(2):413-420.

[17]Liu HY, He YJ, 2006. Algorithm for 2D irregular-shaped nesting problem based on the NFP algorithm and lowest-gravity-center principle. J Zhejiang Univ-Sci A, 7(4):570-576.

[18]Liu X, Ye JW, 2011. Heuristic algorithm based on the principle of minimum total potential energy (HAPE): a new algorithm for nesting problems. J Zhejiang Univ-Sci A, 12(11):860-872.

[19]Liu YL, Zheng L, 2025. Using helical polyhedron for online irregular strip packing problem with free rotations. Eur J Oper Res, 327(2):407-419.

[20]Stoyan YG, Pankratov AV, 1999. Regular packing of congruent polygons on the rectangular sheet. Eur J Oper Res, 113(3):653-675.

[21]Zhou JR, He K, Zheng JZ, et al., 2024. Geometric batch optimization for packing equal circles in a circle on large scale. Expert Syst Appl, 250:123952.