Two-dimensional polygon classification and pairwise clustering for pairing in ship parts nesting - Na, Gun Yeol; Yang, Jeongsam (Journal of Intelligent Manufacturing, 2024)
In the shipbuilding industry, nesting is arranging the cutting patterns of ship parts to increase the utilization rate of steel sheets and reduce the scrap rate. The nesting complexity is high because of the large number of ship parts with complex shapes and various sizes. Arrangement algorithms for minimizing steel-sheet wastage cannot be readily applied to nesting without pairing the two parts to reduce the nesting complexity because of the considerable computation time involved. This study proposes a pairing method to reduce nesting complexity. Ship parts were classified, and pairwise clustering was applied for pairing. A method in which a deep neural network architecture learns polygons without rasterization for classifying ship parts and a method for pairing ship parts of different shapes for pairwise clustering were proposed. Using 265 actual ship parts, the proposed method was compared with pairing methods involving shape-based matching algorithms currently employed by shipbuilding companies. Subsequently, 82 more parts were paired, and the average pairing time, arrangement time, and scrap rate decreased by 44.1%, 47.5%, and 11.0%, respectively. Pairing based on deep learning classifiers and pairwise clustering can rapidly and accurately pair ship parts, thereby improving nesting efficiency.
Keywords: 2d polygon classification; Cutting plan; Deep learning; Irregular strip packing problem; Nesting problem; Pairing; Pairing method; Pairwise clustering; Scrap rate; Strip packing problem; 2D polygon classification; Cutting plan; Deep learning; Irregular strip packing problem; Nesting problem; Pairing