Research On Two-dimensional Packing Optimization Algorithm Based On Improved No-fit-polygon Method

The two-dimensional(2D) packing problem belongs to the layout optimization problem of two-dimensional space. The problem concerns how to pack a set of given parts or polygons onto regular or irregular plate materials in a certain way, and maximize the utilization rate of the materials. The two-dimensional packing problem exists widely in many modern manufacturing industries, such as shipbuilding, garment processing, mold manufacturing, etc.The research of the problem has important theoretical and practical significance.This dissertation focused on optimization algorithms for irregular packing problem,which is the most popular form of two-dimensional packing problem. To solve some shortcomings of existing algorithms for the two-dimensional irregular packing problem, the dissertation proposed some improved methods for some key problems in packing process.The main points of research and innovation of this dissertation can be summarized as follows:1. Research on improvement of the no-fit-polygon(NFP) generation algorithm. NFP generation is the basic geometric computation of 2D packing problem, and also the bottleneck that restricts research of the 2D packing problem. Inspired by on the feature of the NFP, the thesis introduced the concept of “vector line”, and designed a method based on composition of vector lines. The proposed method could not only solve the limitations of traditional NFP algorithm, such as the collision method, the Minkowski sum method and the convex and division method, but also improve the computation efficiency of NFP generation algorithm.2. Research on improvement of the packing strategy for parts. To solve the shortcomings of the traditional packing strategies like BL and BLF, we proposed an improved packing strategy based on heuristic criterions. This strategy decided the next part to be packed and the packing position of the part by introducing a set of specific evaluation criterions. The strategy made the matching degree between parts’ contours as packing evaluation parameters, which helped form graphic complementation and solve the concave problem of irregular parts, so as to improve the utilization rate of material. We combined this packing strategy with the positioning method of parts based on no-fit-polygon and inner-fit-rectangle to solve the whole packing problem. The proposed algorithm had obvious advantages in searching for the possible packing positions of parts under the premise of avoiding overlap, out-of-bound andmaking full use of the material.3. Exploratory research on packing problem for irregular materials. In the study of 2D packing problem, most of the available literatures considered the packing problem for rectangular materials, which had regular contour. In some practical applications, however, the contours of the materials are not always rectangular, and there may be areas unable to be packed(the so-called holes) within the material. This thesis made an exploratory study on the packing problem of irregular material. The concept of internal NFP was introduced for handle packing problems with such feature, and the vector line method was expanded to calculate the internal NFP. On this basis, we combined the method of calculating the external NFP of the holes and the method of calculating internal NFP of irregular material, so as to implement packing parts onto arbitrary irregular material with holes.