Research Of Two Dimensional Irregular Nesting Algorithm Based On No Fit Polygon

The two-dimensional(2D) pattern nesting problem, a layout optimization problem,concerns how to find best position in sheet of materials while satisfying the following constraints:(1) located inside the plate;(2) do not overlap between the parts; and(3) meet certain technical requirements. Two-dimensional nesting problem is widely existed on shipbuilding, garment processing,mold manufacturing and other industrial production.The main research objects of 2D nesting problem include how to get no-fit-polygon, two dimensional Boolean operations research, the irregular parts positioning strategy and positioning standard, as well as intelligent optimization algorithms used in typesetting problem,etc. Research and innovation can be summarized as follows:(1) Research on no-fit-polygon algorithm: improved no-fit-polygon algorithm base on Convex segmentation, exceptional circumstances and on the basis of the traditional Boolean operations, aiming typesetting process may encounter, such as grooves phenomenon, degradation and overlapping point problem, improve the existing algorithm, and design algorithms to solve all the problems.(2) Research on Positioning Strategy: The algorithm is base on no-fit-polygon and inner-fit-rectangle, and has a higher ability to search, completely solve the holes problem. The NFP and IFR information can be reused and reduce time complexity.(3) Research on positioning Standards: BL standards has Great defects. A new standards named LOR has been proposed. Not only considering left and bottom, but also considering the fit between the components, and contribute to improve the utilization of the plate.(4) Intelligent Optimization: Traditional Optimization algorithms, such as genetic algorithms, simulated annealing algorithm, ant colony algorithm, has its limitations and defects. In this paper,we proposes a new method named limited branch tree search. Limited branch tree search algorithm considering advantages of intelligent algorithms and heuristics optimization, avoid falling into local optimum. In this way,we can obtain better result.