Study On Two-dimensional Irregular Packing Algorithm Based On Mixed Integer Programming

The two-dimensional irregular packing problem(2D-IPP)is a classic plane combination optimization problem,which is widely used in advanced manufacturing industries such as aerospace,automobiles,and shipbuilding.The main goal of packing is to maximize the utilization of raw materials.Research on efficient packing algorithms can effectively reduce the consumption of raw materials,improve the automation and intelligence level of the manufacturing industry,and have significant economic and social benefits.Therefore,it is of great significance to study the 2D-IPP.There are two main factors that affect the results of 2D-IPP,one is the positioning of the parts,and the other is the filling order of the parts.For the positioning part,the existing positioning method is not efficient in positioning calculation,and it is easy to miss a cavity or a concave area,resulting in a waste of space.For the filling sequence part,a single heuristic sequence optimization algorithm is easy to make the solution converge at the local optimum.In order to promote the effective solution of the 2D-IPP in actual production,this thesis conducts research on the 2D-IPP.In response to the above problems,this paper studies the positioning algorithm and sequence optimization algorithm proposes a 2D-IPP model based on mixed-integer programming,and designs a hybrid heuristic algorithm for the proposed model.The main content of the paper is as follows:(1)Analyze the common construction and expression methods of contour graphics in actual blanking production,study the principle of reading and transferring CAD files,establish a data structure for complete expression of parts with cavities,and design part contour reading and saving based on DXF files The algorithm and the polygonal approximation algorithm of arbitrary curve contours ensure that the part contour can be effectively combined with packing positioning and sequencing strategies after preprocessing.(2)Analyzing the problem of low positioning efficiency and easy missing cavities in the 2D-IPP,a no-fit polygon(NFP)solution algorithm based on vector superposition is proposed,which can quickly find all possible docking positions of the part,and solves the problem that the traditional NFP algorithm is easy to miss the cavity or concave region,and realizes the rapid and accurate positioning of the part.(3)Aiming at the problem that a single heuristic filling sequence optimization algorithm is easy to fall into the local optimal solution,a two-dimensional irregular packing model based on mixed-integer programming is proposed to analyze the constraints of the 2D-IPP.Based on the framework of genetic algorithm,a hybrid heuristic algorithm combined with model constraints was designed to solve the model.(4)Research cross-platform application development technology,based on the concept of "front-end Electron,back-end Java",based on Electron and Java,two-dimensional irregular packing system software development,by adjusting the parameters of the packing experiment,the packing example diagram and the packing result parameters are obtained.Verify the correctness of the proposed packing algorithm and feasibility of the packing system.