Research And Application Of Two-dimensional Irregular Packing Problem Based On Genetic Algorithm

The nesting problem has a wide application, for example, in garment industry, in leather industry, in machinery industry. Improving utilization of material will reduce production cost, which will bring economic benefits to enterprise. So, the research of nesting problem has important economic value. The problem of two-dimensional irregular nesting has very high complexity and it is a NP complete problem. So, the research of nesting problem has important theoretical value.Genetic algorithm (GA) is a kind of global optimization meta-heuristic algorithms, which can avoid searching in local optimum through crossover and variation. GA complete population evolutionism through individual fitness, and don't need derivative information of objective function and constraint function in the optimum model, so GA has the characteristic of robustness, and can solve many optimum problem. The paper introduces GA from background, principle and convergence theory in detail.Applying GA to two-dimensional irregular nesting problem in this paper, and result is good. Considering shapes are with circular arc and circle, the paper puts forward the algorithm of automatic getting shape data and the algorithm of getting approximate polygon.How to find the positions shapes are not overlapping and are contacted is one of crucial technologies of optimization problem during automatic nesting calculation. To reduce calculation of overlapping judge and improve the algorithm efficiency, algorithm of no-fit polygon(NFP) is applied and improved in the paper. This is mainly two concave polygons' NFP, firstly make one concave polygon convex, second get NFP of concave polygon and convex polygon, and change convex edges into concave edges corresponding, finally get two concave polygons' NFP. At most time we can need many materials in the production, so the paper considered nesting of materials.Besides, the paper designs some algorithms which are related with graphic algorithms in nesting algorithm, for example hull algorithm and composite polygon algorithm. Based on the research of above-mentioned algorithms, the paper has designed automatic nesting system of two-dimensional irregular shapes, and the system has friendly interface. System may directly handle AutoCAD drawing paper, and nesting drawing is automatically drawed through the determination of stock parameter and selection of shapes.