Research And Implementation Of No-fit-polygon-based Irregular Nesting Algorithm

Research on two-dimensional irregular packing problem was presented in this thesis,this problem mainly exists in many fields of modern manufacturing industry, such asmachinery manufacturing, garment manufacturing, microelectronics layout etc. Minor impro-vement in packing efficiency can save a large amount of raw materials, and result in increa-sing of economic benefit and easing the environmental stress caused by resources shortage.Since the irregular shape of packing parts, the difficulty of soving the two-dimensionalirregular packing problem is manifested in the collision detection of irregular parts and theoptimization combination of packing sequence, packing orientations and packing positions. Inthe respect of collision detection, this thesis uses the collision detection method basedon No-Fit-Polygon, adopts the thoughts of sliding algorithm proposed by Burke et al togenerates No-Fit-Polygon, and proposes a time optimization method based on PossibleCollision Zone to make an effective time optimization on the original algorithm. Theoreticalanalysis shows that, when the solving problem’s average number of edges e is greater than acertain value, the time optimization was established, and time optimal ratio increased withthe increase of e value.16benchmark test results have proved the correctness ofthe theoretical analysis. In all tests, the average value of positive time optimization ratio is20.45%, and the highest time optimization ratio is50.29%.In the aspect of packing algorithm, this thesis proposes a packing strategy based ongravity NFP and Edge Fitness, namely GEF heuristic pacing algorithm, and based on thispacking strategy, this thesis combins it with the FFDA option strategy and Weiler-Atherton polygon clipping algorithm to proposes the GEF heuristic packing algorithm. Thispacking algorithm has been tested on16benchmark, and in contrast to the11benchmark testswith two commercial softwares, this algorithm achieved7/11relatively optimal utilize-tion rate, which fully proved the nesting ability of GEF heuristic packing algorithm. Meanwhile, this thesis dopts the main idea of the GATS hybrid intelligent algorithm proposed bySun Yanfeng, and combines it with the GEF heuristic packing algorithm proposed by this thesis, which lead to the research and implementation of GEF hybrid meta-heuristic packingalgorithm. In all16benchmark tests, all test results of this algorithm is superior to the GEFheuristic packing algorithm, the average improved ratio of layout utilization rate is10.97%. While in contrast with4proposed excellent meta-heuristic packing algorithm, theaverage layout utilization rate of GEF hybrid intelligent packing algorithm is close tothese algorithms’, but has a certain gap in terms of optimal layout utilization rate whilecomparing with the best performers. Comprehensivly evaluating the test results, the GEFhybrid meta-heuristic packing algorithm proposed by this thesis has good nesting ability.