Two-dimensional Layout Optimization Based On Rectangle Envelope

Two-dimensional irregular pattern packing is widely used in glass,steel plate,wood,leather and other industries.It refers to the arrangement of a variety of parts with different sizes on a given plate,so that these parts can reduce the occupied area of the plate as much as possible and improve the utilization rate of raw materials under the condition that they do not overlap each other and do not exceed the boundary of the plate and other related constraints.Two-dimensional packing is a typical plane layout optimization problem,which belongs to NP complete problem in theory and is very difficult to solve.Therefore,the research on this problem has a wide application background and important theoretical and practical significance.Based on the existing research,this thesis studies the preprocessing,nesting algorithm and system development of parts.The specific contents are as follows:In the part preprocessing,the rectangular envelope method is used to transform the two-dimensional irregular parts into regular parts.For curved edge parts,the method of defining tolerance extension polygon is used to transform them into straight edge parts,and then envelope them with rectangle.Then the best rectangular envelope rate of the enveloped parts is calculated,and judge whether the parts need to be combined envelope according to the size of the envelope rate.In the aspect of part packing algorithm,the mainstream packing algorithm is analyzed and studied,and the combination of heuristic algorithm and intelligent optimization algorithm is proposed to solve the problem.First,the residual rectangle matching algorithm is used to make the packing rules and determine the packing mode of parts.Then,genetic algorithm is used to search the layout scheme to find the optimal layout scheme.In the aspect of system development,taking MATLAB as the development platform,the whole process of system development and implementation,including user interface development,main program design and database configuration,is studied,and the system is applied to the two-dimensional cutting link of J company to verify its feasibility.The experimental results show that the system improves the utilization rate of the parts from 78% to 88.23%,and the improvement effect is significant.In this thesis,the residual rectangle matching algorithm and genetic algorithm are combined to solve the two-dimensional packing problem,which can significantly improve the utilization of raw materials,improve the nesting efficiency and reduce the production cost for the enterprise.The research on the two-dimensional irregular packing problem has important theoretical and practical significance.