Research On Two-dimensional Irregular Parts Packing Optimization

The packing problem of two-dimensional irregular shapes belongs to one of the NP-hardproblems. It is very important and difficult to solve. It has great complexity of computation.For this problem, it hardly can be solved. But, because of the great theoretical and practicalsignificance for the problem, it has become an extremely important branch in the optimizationproblem. So far, the solving methods for the problem has two ways: the first is directlyirregular parts nesting processing in the material, the second is turning the irregular parts intoregular parts (rectangular parts), and then nesting. The paper uses the second method, themain work in the paper is as follows:The main research object in the paper is two-dimensional irregular parts, so we have tochange the irregular parts to regular parts. Based on using the rectangular envelope method,we put forward another two methods: Tri-rectangle method and trap-rectangle method.Tri-rectangle method’s main idea is making two or several same triangle parts turn toparallelogram, and then turning the parallelogram into rectangle; In comparison, the researchobject for the trap-rectangle method is relatively broad, it can be quadrilateral, pentagon,polygon and so on. For this method, first, turn the irregular parts to the smallest trapezoidal,and then turn the two or several same trapezoidal to rectangle. As above, this will make all theirregular parts can be carried out in accordance with the rectangle parts, it will reduce the timefor packing, improving the efficiency.After the regularization of irregular parts, the paper does research on the nestingalgorithms. These algorithms mainly include: BL algorithm, searching algorithm based on theminimum horizon and remaining rectangle matching algorithms. After comparing to thesealgorithms, we select the remaining rectangle matching algorithm to pack the regular partsafter regularization.The nesting algorithms above are algorithms given the sequence of the parts. It isdifficult to directly get the optimal or satisfactory renderings; so we must combine thealgorithm and the algorithm that has the global search ability, only this, can we get the result we want. The genetic algorithm is created based on the Darwin’s biological evolution theory.In this paper, it uses the roulette strategy for selection and chooses the cross-operating throughthe two-point crossover operator. In addition, it use exchange variation, rotation variation andposition variation. After that, we can get the optimal solution or near-optimal solution for theproblem and through the example we can verify its feasibility.