论文摘要
下料问题,就是给定一个布局空间和若干待下料物体,将待下料物体合理地摆放在布局空间中,满足必要的约束条件,并使材料利用率达到最高。自动下料问题由来已久,自动最优下料问题在应用上可以提高生产效率,节约成本,理论上它又是NP完全问题,即为非确定型的多项式完全问题,具有巨大的挑战性,可以认为它是人类到目前为止遇到的最困难问题的典型代表之一,具有重要的研究价值。自动下料问题一直受到广泛的重视和研究,而对原材料的约束条件更是对此问题提出了挑战,研究方法涉及了组合优化、人工智能、计算几何学等各种理论。由于自动下料问题属于NP完全问题,随着布局物体数量的增加,其解空间呈指数级增长,出现组合爆炸现象。动态规划、分支定界等基于穷举思想的算法只能解决数量较少的图形组合形式而无法解决此类问题,而采用启发式搜索的方法,模拟退火算法、人工神经网络、遗传算法等智能优化算法求解自动布局问题得到了广泛的认同。本文主要针对矩形件和不规则件的二维下料问题进行了研究,并在此基础上对原材料进行了约束,即有瑕疵材料的二维下料问题。针对此类下料问题,分析讨论了目前常用的二维下料算法,重点研究了目前在此类问题上应用较多的遗传算法,分析比较了目前提出的基于遗传算法的各种排样算法,提出了自己的改进和创新。针对矩形件和不规则件的下料问题,分别提出了基于全局最低水平线搜索算法的排样算法,和有碰撞的全局最低水平线搜索算法的排样算法;对不规则待下料图形的初始化方法以及改进的遗传算法的解码算法不但提高了材料利用率,而且使下料程序的运算效率得到提高;借助于AutoCAD强大的图形处理功能,使得碰撞检测更加容易实现,通过不规则零件之间的碰撞,压缩占用空间,提高了利用率;对材料有瑕疵情况下的矩形件排样做了初步研究,提出了基于全局最低水平线搜索算法的瑕疵处理方法,取得了良好的效果。本文主要应用遗传算法和改进的排样算法及碰撞检测方法对图形进行优化排样计算,结合计算机图形处理软件AutoCAD2002与其二次开发函数库ObjectARX,在Visual C++6.0环境下进行开发,完成了二维优化排样软件的程序设计。程序可对矩形件及不规则件进行自动优化排样计算,输出为适宜后续处理的AutoCAD排样图文件,能够得到较高的利用率,并可在原材料有瑕疵的情况下,实现对矩形件的自动优化排样,也取得了较高的利用率。实验结果证明,遗传算法与改进的排样算法结合应用对矩形件和不规则件进行排样能够取得良好的效果,得到较高的材料利用率,并且在材料有瑕疵的情况下,对矩形件排样也保持了较高的材料利用率。