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.

1. Introduction

Packing problems involve the optimal arrangement of parts of varying shapes and sizes on raw materials, such as metal sheets, fabrics, and wood, to maximize material utilization while satisfying process constraints, including orientation and gap requirements (Francescatto and Júnior, 2025). This process is widely employed in industries such as sheet metal processing, garment manufacturing, and furniture production, and directly affects both material costs and production efficiency.

The trend in manufacturing is increasingly leaning toward ever-larger scales. Taking the shipbuilding industry as an example, the larger a vessel’s deadweight tonnage is, the lower its unit manufacturing and cargo transportation costs. This trend toward large-scale manufacturing presents three primary challenges for packing problems: (1) a large quantity of parts; (2) irregular part geometries; (3) the use of multiple sheets (raw material plate). However, no existing studies have effectively tackled all three issues in an integrated manner. While Zhou et al. (2024) and Lai et al. (2025) focused on the large-scale packing problem of regular parts (with the number of circles reaching 1000), research on the packing of irregularly shaped parts (Stoyan and Pankratov, 1999; Cheng and Rao, 2000; Costa et al., 2009; Al Theeb et al., 2021; Liu YL and Zheng, 2025) is limited to a maximum of 450 parts and one single sheet. Guo et al. (2025) investigated the packing of irregular parts on multiple sheets, but their study only considered a maximum of 130 parts.

This paper proposes a new packing algorithm that can pack 1400 irregular parts across multiple sheets while maintaining the computation time suitable for engineering applications. The algorithm classifies parts by area and fullness and employs a combination of “box stacking,” “shape matching,” and “gravity packing” strategies. Among these, box stacking is essentially a form of rectangular packing, gravity packing refers to an algorithm developed over the past decade, and shape matching is a novel method introduced in the present work. Before presenting the proposed approach, it is helpful to briefly review traditional algorithms for rectangular and irregular part packing. In certain engineering applications, the area of rectangular parts constitutes a significant proportion of the total area. For instance, in shipbuilding, the presence of a parallel mid-body results in a large number of parts that are approximately rectangular in shape (hereinafter referred to as “box-like parts”), with the remaining parts being irregular.