Research Of Two Dimensional Nesting Algorithm Based On No Fit Polygon

Research on two dimensional (2D) nesting problems was presented in this thesis. 2D nesting is a kind of planar layout optimization problem with object of arranging a number of pieces inside a given plate, and in the same time, following restrictions must be satisfied: (1) pieces should be nested inside the plate; (2) each piece should not overlap with another; (3) certain restrictions on manufacture should be fulfilled. The optimization object of 2D nesting problem is to find an arrangement for pieces, and minimize the wasted material, in other words, the material usage ratio should be maximized. Nesting problem has a significant influence on the industries such as ship-building, costume making, and mold-manufacture.According to the key problems and difficulties existed in nesting problem, the thesis presented a fundamental researching and proposed corresponding algorithms and resolutions. The main research objects of 2D nesting problem include geometric calculation, rectangular nesting, 2D irregular nesting and the application of intelligent optimization on nesting problem. Detailed research achievements and creative ideas are listed below:(1) Research on No Fit Polygon algorithm: The basic geometric calculation problems were detailly analysised and researched, especially for the key algorithm of nesting problem– No Fit Polygon (NFP) algorithm. NFP algorithm is the neck factor for the development of 2D 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 perfectly resolved. On the other hand, 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 presented a new fast NFP algorithm,that converted the problem of collision between two polygons to the calculation of trace line segment for vertices and edges, and it can deal with the special conditions such as inner cavity holes and inner contacting NFP. The basic principle of the new NFP algorithm is: (1) computing the trace line segment between vertices of one polygon and edges of another polygon; (2) Finding out the enclosure polygon and inner clockwise loops formed by all trace line segments, then the resulted enclosure polygon and inner loops are the final NFP. The new NFP algorithm adopted one grid-based index algorithm for line segments to speedup the computation on interaction between line segments. Experiment results show that the new NFP algorithm can perfectly resolve the problems such as inner NFP, cavity on edges, holes inside plate at the same time. At the same time its calculation speed is up to hundreds times faster than existing NFP algorithms. In addition, 2D nesting related geometric algorithms, such as polygon boolean operations with tolerance and determination on polygon's wise, are also analyzed and enhanced in this thesis.(2) Research on 2D rectangular nesting algorithm: Mainly include the piece placement algorithm and heuristic nesting algorithm. Firstly the mathematic model of rectangular nesting problem was analyzed, and then the two key technology of rectangular nesting problem– piece placement policy and heuristic algorithm were researched. Principle and technical character of existing placement algorithm were analyzed, and NFP based rectangular placement policy was proposed. Based on the achieved NFP, the piece was placed on the left and bottom point of NFP. Compared with other placement policy, the time complexity of NFP based placement algorithm is low (O(N)), and it can globally search the feasible placement points, hence it effectively reduced the material waste caused by inner cavity, therefore the material usage ratio is increased. Secondly on the heuristic algorithm for nesting problem, this thesis proposed a heuristic nesting algorithm based on fitness evaluating, in this heuristic algorithm, material usage ratio, area changing and lowest Y coordinates were integrated to evaluate the fitness which be used as a heuristic rule, and based on this heuristic rule, the pieces was nested in order while piece with higher fitness was nested first. On the other hand, this thesis proposed a multi-plates nesting algorithm, it adopted a revised NFP placement algorithm based on single plate NFP algorithm, and achieved an ideal result. The experiment results show that the NFP based rectangular placement algorithm can obviously increase the nesting quality while its time complexity is low (nesting quality increase by about 20% in dataset 3-1 and 3-2).(3) Research on irregular nesting algorithm: Piece placement algorithm and heuristic algorithm in irregular shaped nesting problem were researched. Due to the irregular in shape of pieces and plate, specific placement policy and heuristic algorithm should be researched. Firstly in the placement policy for irregular shaped pieces, this thesis using a NFP and multi-rotation hybrid method, and proposed a new piece placement policy which based on lowest center of gravity rule, with gravity center of piece as the reference point, the gravity center NFP can be calculated; Secondly from all the gravity center NFPs which caused by different rotation, the lowest gravity center can be find. Secondly on the heuristic algorithm for irregular nesting, in order to reduce the waste caused by holes, this thesis proposed an order-based recursive nesting algorithm, in the procedure of recursive nesting algorithm, the nesting order of pieces was adjusted when large holes was detected. Finally experiments on the benchmark dataset was presented to compare the new algorithm and existing ones, the experiment results show significant improvement in algorithms proposed by this thesis (dataset 4-1~4-4).(4) Research on intelligent nesting algorithm: Genetic algorithm and annealing algorithm implementation in nesting problem were researched. Adopted intelligent algorithms can work for both rectangular nesting problem and irregular nesting problem. Nesting problem is a typical combination optimization problem, so it is suitable to introduce intelligent algorithm such as SA, GA and TA etc. into nesting problem. This paper adopted GA and SA algorithm in nesting problem. In the aspect of SA: firstly the basic principle, technical characters and procedure were described, then according to the specialty of nesting algorithm, the implementation and key parameters were designed, such as encode and decode for nesting pattern, design for domain function and initial temperature, design for temperature decreasing rate, and experiments on benchmark datasets were conducted to compare the new algorithms with the existing best know nesting algorithms (dataset 5-1~5-2). In the aspect of GA: individual encode and decode, fitness calculation, the selection of individuals, crossover and mutation operations and the probability for crossover and mutation were researched. At the end, comparing experiments on benchmark datasets were conducted (dataset 5-3~5-5). The experiments results show that the runtime of intelligent algorithm is longer than that of heuristic algorithms, but intelligent algorithms achieved more effective nesting pattern than heuristic algorithms.