Research Of Two-dimensional Irregular Nesting Algorithm Based On No Fit Polygon

The two-dimensional(2D)irregular nesting problem belongs to the problem of planar layout optimization.It can be described formally as that a list of given pieces is to be placed onto a given plate,with no overlap between any two pieces.The objective of the problem is to find an optimal nesting solution and improve the utilization of plate.Nesting problem is widely exists in many industries such as sheet metal,leather,clothing,wood,stone,aerospace,etc.To improve the utilization of plate is of great significance for improving economic efficiency and alleviating the environmental pressure caused by resource shortage.This dissertation analyzes and studies the key issues in the 2D irregular nesting problem.The main research achievements and creative ideas are as follows:No fit polygon(NFP)generation algorithm based on vector segments: the NFP algorithm is a key fundamental problem in 2D nesting problem,and it is also a bottleneck in the development of 2D nesting algorithm.In this dissertation,the NFP generation algorithm based on vector segments is proposed.The sliding collision between polygons is transformed into the "angle-edges" touch judgment.The vector segments set is generated from the set of "angleedges",and the minimum rotation angle strategy is used to extract NFP from it,and the algorithm deals with special conditions such as degeneration points and degradation lines.The proposed algorithm effectively sovles the calculation of NFP,while its calculation speed compared with the collision method is greatly improved.Research on nesting algorithm based on hybrid heuristic nesting algorithm: firstly,analyzes the role of NFP in the nesting algorithm,and extracts feasible candidate placement points by NFP and IFR for the piece to be placed next.Then,reviews the TOPOS algorithm,three LAO evaluation criteria are proposed to evaluate the nesting result.Based on the three criteria,three hybrid strategies are designed to choose the next piece to be placed and to choose the best fit point from the candidate placement points.Research on nesting algorithm based on genetic algorithm with random keys(RKGA): analyzse the characteristics and the flow of RKGA,combines with the characteristics of 2D irregular nesting problem,RKGA is used to optimize the order of arrangement,rotation angle,and positioning rules.The individual encode and decode,fitness function,the selection of individuals,crossover and mutation operations in RKGA are designed.The experimental results show that the algorithm has a strong global optimization and can obtain a better nesting result than the heuristic algorithm and niche genetic algorithm.Research on nesting algorithm for defective irregular plate: analyzes the mathematical model of nesting on defective irregular plate.The concept of internal no fit polygon(INFP)is introduced,and vector segments method is extended for calculating INFP.For the irregular defect plate,the NFP and INFP are used to extract the candidate placement points to avoid defects.The hybrid heuristic algorithm and RKGA are respectively improved to apply to nesting problem for defective irregular plate.The experimental results show that the algorithm can make pieces compactly placed inside the plate and avoid the defect area.The improved RKGA can achieve better plate utilization than the improved hybrid heuristic algorithm.