| In theory, the packing problem of two-dimensional irregular shapes belongs to the NP-hard problems. It is very difficult to find the optimal solution for such a problem because of the high complexity of computation. There are two methods to resolving the problem, one is approximately rectangle solution method based on regular shapes packing, the other is to deal with the irregular shapes directly. This paper presents a new method about the packing space based on the combination of the two methods. Using this algorithm, we can improve the packing efficiency and the using ratio of material.First of all, the complexity theory of packing problem has been analyzed. It point out that the packing problem of two-dimensional irregular shapes is NP hard, and the improvement of algorithm is fit for not only regular but also irregular. In the next place, the genetic algorithm (GA) and the simulated annealing algorithm (SA) have been introduced, respectively. And the two algorithms have been combined, so that both advantages of them could be used efficiently to avoid the phenomenon of prematurely convergence and solve the packing problem of irregular shapes. Further, the new concept has been presented, that is the orthogonal packing problem of two-dimensional irregular shapes. At last, the new heuristic algorithm called the Corner-occupying action First principle is put forward. This new algorithm compared with Lowest Horizontal Line algorithm. In several instances, it is proved that solutions achieved by this algorithm excelled this achieved by the latter in both effect of packing and operation time.Based on the algorithm presented above, farther applications have been brought forward in an item. In the one of optimized problems with multiple goals restraining, named the putting and transporting the large-scale accessory, solution shows that the validity and efficiency of the algorithm. Finally, the two-dimensional automatic packing system is designed and implemented. |
PDF Full Text Request