Research Of Two-dimensional Irregular Layout Problem Based On No-Fit Polygon

Two-dimensional irregular layout problem is a kind of spatial layout optimization problem.It refers to the problem that under certain constraints,a certain number of irregular parts are discharged onto the designated raw materials to maximize the utilization rate of raw materials.The two-dimensional irregular layout problem is widely existed in mechanical manufacturing,printing and typesetting,cloth cutting and other industries,and is an important link in the manufacturing automation production process.The research on two-dimensional irregular layout mainly focuses on two aspects:the positioning strategy of parts and the discharge sequence ofparts.By learning and researching,this paper has obtained the following research results:Firstly,the mathematical model of two-dimensional irregular layout problem is constructed.Then,by comparing and analyzing the related algorithms of two-dimensional irregular layout problem,the vector graph method is selected to represent two-dimensional irregular parts,and the critical polygon tool is used as an important means to solve the overlap judgment and geometric connection of parts.Secondly,based on the trajectory sliding method proposed by Burke et al.,an improved algorithm for generating no-fit polygons of sliding orbits is proposed.The algorithm is mainly improved from the determination of sliding direction and the calculation of minimum collision distance,and the running time and stability of the algorithm are tested by 8 two-dimensional irregular layout benchmark problems.Experimental results show that the improved algorithm can effectively optimize the time complexity of the no-fit polygon generation algorithm.Thirdly,by analyzing the application of the critical polygon tool in the two-dimensional irregular layout problem and the positioning rules of parts in TOPOS algorithm,a hybrid layout positioning strategy based on the barycentric no-fit polygon is proposed to select the appropriate discharge position.The proposed hybrid positioning strategy sets the priority of three factors,namely,the principle of minimum center of gravity,the fit between parts and the overall layout effect.Compared with the single positioning strategy,it has better layout effect.Finally,by analyzing the application of genetic algorithm in two-dimensional irregular layout problem,a parallel crossover genetic algorithm was proposed to simulate the evolution process of biological hybridization on two independent islands.The experimental test was carried out through a number of test cases provided by the European layout interest group.The experimental results show that the parallel crossover genetic algorithm has better global search capability and faster convergence rate than the traditional genetic algorithm in the two-dimensional irregular layout problem.