Research Cutting Nesting Optimization Algorithms Of Two-Dimensional Irregular Graphics

The nesting problem is a common problem in clothing, sheet metal, steel, leather, ship, paper products and stone industries. It is a key component in automation of manufacturing. Dimensional irregular parts by nesting a series of two-dimensional plane figure (or parts) are not mutually overlap placed on a plate, such that have not been covered by the smallest panel, and the parts are arranged on the plate optimal, making the utilization of the plate. Compared to rectangular pieces of nesting, irregular nesting parts and panels for arbitrary polygon, sheet may contain internal holes and increase the angle of the nesting. How to improve sheet utilization, shorten the nesting time, reduce production costs and bring significant economic benefits for the enterprise, is the focus of this study. Therefore, this thesis has some scientific significance and application value.Difficult problems for the two-dimensional nesting problem, this paper studies the irregular parts preprocessing techniques, improved Ghosh slope diagram method to calculate the NFP, proposing the improved genetic algorithm to the two-dimensional irregular parts nesting, and then to develop and implement a system of nesting, the main tasks are as follows:(1) Through the study of irregular parts pretreatment technology to determine the representation of this article irregular shape. And then, according to the sides of the polygon cross product of vectors formula carried out the concavity and convexity of judgments. With improvement of Graeme to convex concave polygon convex hull algorithm, followed by envelope and stitching, to improve the efficiency of the parts envelope, the judgment method of the relationship between point and polygon is given.(2) Put forward improved Ghosh slope diagram method to calculate any two polygons NFP, so as to solve the concave polygons to calculate NFP is easy.(3) Put forward the improved genetic algorithm to solve two-dimensional irregular parts nesting optimization problem. In the nesting problem, as opposed to the traditional single binary or decimal encoding, hybrid coding method is proposed. In the rules of evolution, similarity calculation method is proposed, significantly accelerated the search efficiency of the algorithm.(4) Design a cutting optimal layout system of sheet, including the rectangular pieces nesting and the two-dimensional irregular parts nesting, functional modules of the system, each interface and operating procedures. Finally, several groups of experimental simulation and literature algorithm were compared to verify the superiority of the proposed algorithm.