二维不规则零件排样及相关问题研究

【作者】 徐利娜；

【导师】 彭国华；

【作者基本信息】 西北工业大学 ， 系统分析与集成， 2007， 硕士

【摘要】 二维不规则零件的排样问题，在理论上属于NP完全问题，有着较高的计算复杂度，求解很困难。因为对该问题的研究有其理论意义和广泛的应用背景，所以，该问题成为最优化问题中的一个重要的研究分支。研究方法主要基于两种思路：一种是基于规则零件排样处理的矩形化方法，另一种是对不规则零件的直接排样处理。本文在原有矩形近似算法和不规则件直接处理算法的基础上，探索了一种基于两种方法相结合处理不规则零件排样的优化方法，以提高排样效率和材料利用率。 在研究国内外学者提出的算法的基础上，本文主要做了如下工作： 首先对排样问题的复杂性理论进行了分析，指出了有NP难度的二维排样问题在矩形件上的遗传算法改进同样的也适合于不规则件。其次，对遗传算法和模拟退火算法分别进行了介绍，指出两种算法的结合可以有效的减弱遗传算法的早熟现象。最后，提出了二维不规则零件正交排样的概念和一种新的定位启发式方法——占角优先算法，该算法与最低水平线算法进行比较，实例验证表明，新的定位算法在保证排样效果的前提下，运行时间方面优于后者。 在理论研究的基础上，针对项目做了更进一步的应用。结果表明，在处理多约束、多目标的“大型零件的摆放和调运”项目时，达到了预期的排样效果。在本文的最后，设计和实现了一个完整的二维零件的排样和调运系统。更多还原

【Abstract】 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.更多还原