Covering, corner-searching and occupying: A three-stage intelligent algorithm for the 2d multishape part packing...

Area of Science:

• Industrial Engineering
• Operations Research
• Computer Science

Background:

• Traditional 2D rectangular packing algorithms are insufficient for modern industrial tasks involving heterogeneous shapes.
• Industrial needs, such as express packing and exoplanet ore collection, require advanced solutions for non-rectangular items.
• Minimizing trim loss and maximizing raw material utilization are critical objectives in packing problems.

Purpose of the Study:

• To propose a novel three-stage method, covering, corner-searching, and occupying (C,S&O), for the two-dimensional multishape part packing problem.
• To address the challenge of packing heterogeneous shapes efficiently, ensuring maximum material use and minimal trim loss.
• To develop an algorithm that operates online, processing parts immediately upon arrival without buffering or readjustment.

Main Methods:

• The C,S&O method hybridizes concepts from the game Go and machine vision corner detection.
• Stage 1: Matrix representation of the bin and part to generate packing position matrices.
• Stage 2 & 3: Machine vision techniques and environment matching degree calculation for optimal placement and orientation.

Main Results:

• The algorithm effectively solves the two-dimensional multishape part packing problem.
• Experimental results demonstrate the method's effectiveness using rectangular, circular, and triangular parts.
• The study presents the first layout method specifically designed for multishape manufacturing parts.

Conclusions:

• The proposed C,S&O method offers an effective solution for the complex two-dimensional multishape part packing problem.
• This approach significantly improves material utilization and reduces trim loss in industrial packing scenarios.
• The algorithm represents a significant advancement in packing methodology for heterogeneous manufacturing parts.