Two-Dimensional Irregular Graphics Nesting Based On Virus-Evolutionary Genetic Algorithm

Two-dimensional irregular shapes nesting optimization is a typical combinational optimization problem. Its goal is to find the best solution to parts layout on a given plate, improving the plate utilization and nesting efficiency. Because the problem exists widely in many manufacturing industries, such as machinery, clothing, shipbuilding, sheet metal, furniture, leather processing, studying has great value.In theory, two-dimensional irregular shapes nesting problem is NP-complete problem. It has high computational complexity and it is difficult to solve. Exploring high-quality and efficient solving algorithms is a goal many researchers all aspire to.This thesis mainly aims at dealing with these four parts of two-dimensional irregular packing problem. Major contributions made by this essay are as follow:Formal description and mathematical model of optimal layout of two-dimensional irregular parts are analyzed and built. The complexity of the problem is analyzed; optimization strategies and solution procedure are proposed.Collision detection method. No Fit Polygon (NFP) algorithm is the neck factor for the development of2D nesting algorithms, due to the lack of precise, stable and fast NFP algorithm for a long time, some problems such as optimization of piece’s location, piece’s rotation and holes in plate are still not resolved. On the other hand, because the intelligent optimization algorithms have a relative slow convergence speed and need a large amount of iterative search procedure, defects of existing NFP algorithms have been the main obstacle for the development of implementation of intelligent algorithm on nesting problem. Due to the importance and fundamental function of NFP, this thesis proposed an improved and more efficient algorithm to calculate No fit polygon, it is based on the orbital approach presented by Burke. The new algorithm greatly decreases the problem geometry complexity.Strategy to place items into the board. Combined with NFP, a bottom-left placing strategy has been adopted in this text. This strategy can reduce the boundary height and improve the layout density. A meta-heuristic approach to improve packing results. An algorithm based on Virus-Evolutionary Genetic Algorithm has been provided to optimize packing sequences. Strategies mentioned before are used as evaluating method in this algorithm.After that, we can get the optimal solution or near-optimal solution for the problem and through the example we can verify its feasibility.