Research And Application Of Irregular Parts Packing Problem With Two Kinds Of Boundary Constraints

The irregular packing problem is to place several parts on a given sheet under the premise of satisfying certain constraints.The optimization objective is to maximize the utilization of the sheet.The packing problem widely exists in various manufacturing industries and spatial layout optimization problems,and its research has important practical application value.Based on the actual needs of the project,the irregular packing problem with closed and open boundary constraints is studied in this paper.Firstly,after analyzing the advantages and disadvantages of common algorithms for generating no-fit polygon(NFP),an improved moving collision method is proposed to calculate the NFP between polygons.Then,the NFP and inner-fit polygon(IFP)are used to extract the feasible positioning points of the parts to be nested.And the concept of collision free region(CFR)is introduced to ensure the feasibility of the layout scheme.Secondly,according to the basic nature of NFP,the feasible positioning points are screened,thereby reducing the geometric calculation of the part positioning process effectively.After,a hybrid heuristic positioning algorithm based on CFR is proposed considering the overlap rate and BL layout strategy,as well as the degradation of CFR into points or line segments,and it is proposed as a part positioning algorithm with closed boundary constraint.Aiming at the packing problem of single type parts on irregular sheet,an improved layout strategy based on the search for the initial azimuth of the sheet and the rotation angle of the first layout part is proposed.Thirdly,the part positioning algorithm for dynamic boundary search of sheet is proposed after analyzing the influence of the open boundary constraint on solving the packing problem.And the calculation method of the expanding distance of the sheet boundary is explained.The basic principle and application of the sparrow search algorithm are analyzed.By discretizing the intelligent behavior of the sparrow population,a discrete sparrow search algorithm is proposed to optimize the layout order of parts.Combined with the positioning algorithm proposed in this paper,the layout result is optimized.The experimental test results show that the packing algorithm proposed in this paper is feasible and effective.Finally,according to the actual needs of the project,on the basis of the full text of theoretical research,an automatic layout software for irregular parts was developed by applying software development technology.The packing software has been successfully applied in national defense research projects and can be used to optimize and simulate the layout of carrier-based aircraft on aircraft carriers.