有瑕疵材料二维下料问题的研究和应用

【作者】 辛征；

【导师】 常发亮；

【作者基本信息】 山东大学 ， 控制理论与控制工程， 2006， 硕士

【摘要】 下料问题，就是给定一个布局空间和若干待下物体，将待下物体合理地摆放在布局生间中，满足必要的约束条件，并使材料利用率达到最高。自动下料问题由来已久，对于自动最优下料问题在应用上可以提高生产效率，节约成本，理论上它又是NP完全问题，具有巨大的挑战性，可以认为它是人类到目前为止遇到的最困难问题的典型代表之一，具有重要的研究价值。不规则图形的自动下料问题，一直受到广泛的重视和研究，而对原材料的约束条件更是对此问题提出了挑战，研究方法涉及了组合优化、人工智能、计算几何学等各种理论。 由于自动下料问题属于NP完全问题，随着布局物体数量的增加，解空间呈指数倍数的扩大，出现组合爆炸现象，而动态规划、分支定界等基于穷举思想的算法只能解决数量较少的图形组合形式因而无法解决此类问题，采用启发式搜索的方法，神经网络，遗传算法等求解自动布局问题得到了广泛的认同。 本文所要解决的问题在此基础上更对原材料进行了约束，即带有瑕疵的原材料的自动下料问题。针对此类下料问题，在原有算法的基础上提出了一种改进的基于启发式搜索策略的自动下料算法，充分考虑人工下料时的经验信息，提出了对原材料的瑕疵和待下料图形的初始化方法以及基于分组的定序规则算法，不但提高了材料利用率，而且使自动下料图更易于进行交互式的修改；移动算法采用了启发式搜索策略，可以很快确定待下料图形和瑕疵的位置；对于小块图形，进行插空下，提高了材料利用率；靠接算法通过待移动区域确定可能发生碰撞的实体，先大步长移动，然后微调，从而减少大量的盲目检测，提高了下料的精度。 本文主要采用的是改进的启发式搜索算法和碰撞检测算法对图形进行优化排样，同时结合计算机图形处理软件Autocad2000与其二次开发软件ObjectARX进行编程。主要应用了矩形包络算法和旋转对排法来处理不规则图形和瑕疵处理，然后调用初始化程序和定序规则算法对图形进行处理，最后采用改进的启发式搜索算法和碰撞检测算法对处理后的图形进行优化排样。 实验结果证明，改进算法对瑕疵的处理具有可行性，与原算法相比，在面积优先的前提下，对方正度趋近于1或者经过变换后方正度趋近于1的下料图形能够取得较好的效果；并且在经过改进与没有经过改进的算法相比，大大减少了累积更多还原

【Abstract】 Packing problems arise from a variety of situations including pallet loading, textile cutting, container stuffing and placement problems. Such problems are optimization problems that are concerned with finding a good arrangement of multiple different-sized objects in a large containing region without overlap. In order to solve the subject about time and energy, which appears in alternate marker, the classic packing algorithm is brought forward in the thesis. That is the classical algorithm in the artificial intelligence. Conventional genetic algorithms (GAS) alone perform no better than traditional artificial intelligence approaches such as heuristic search or operations research methods such as First Fit. At the same time, Solutions to many packing problems does not match to be adjust by hand. Heuristic search has been proved to be an effective way to resolve packing problems.In this paper, we present an optimized heuristic search based packing algorithm with minor fault in the materials. We also present a two dimensional collision detection algorithm, the probable collision objects are obtained according to the region where the mobile object will go by to avoid blind detection; Put forward to the minor faults of the original material with treat descend anticipate sketch of the beginning start to turn a method. Motion is done first in large step then in small step to improve layout efficiency. More over, the solutions to this heuristic based algorithm can be easily adjusted to improve the utilization.The papers mainly adopt improved heuristic search arithmetic and collision detection arithmetic to optimize and arrange the figures. In the meantime, the text combined computer figures processing software Autocad2000 and its two development software ObjectARX to program. In the text, the rectangle encircled arithmetic and revolving reverse arithmetic are adopted to handle the irregular figures and minor faults processing, then transfer the initialization programmer and regulating order programmer to handle the figures, at last adopt improved heuristic search arithmetic and collision detection arithmetic to optimize and arrange the figures.The result of test certificate: the improved arithmetic is successful to handle the更多还原