Research On Incomplete No-Fit-Polygon For 2D Packing Problem

Two-dimensional packing problem refers to the process that polygon parts are placed on the plate to seek out excellent nesting results.It is extensively applied in processing and manufacturing and can be deemed as one of the important links in the company's production process.With regards to the irregular polygon packing problem,the complex and varied shapes of the parts make it difficult to solve the discharge position and sequences.This paper optimizes the way of choosing the sliding direction in the sliding collision method.It simplifies the merging process among polygons to solve the packing problem,proposes the concept of incomplete No-Fit-Polygon,and reduces the processes of sliding collision by decreasing the generation of sides in No-Fit-Polygon.Finally,it studies the application of genetic algorithm in the packing problem and proposes the dual population genetic algorithm to solve the discharge sequences.This paper designs the packing experiment using the test cases provided by the ESICUP,verifying that the incomplete No-Fit-Polygon algorithm can improve the packing efficiency,as well as the effectiveness of the dual population genetic algorithm in solving the discharge sequences.