计算机辅助排样,又称为CAN(Computer Aided Nesting),是广泛应用的计算机辅助技术之一,用于指导各行业处理各种下料问题,以达到节约材料、降低产品成本的目的。下料问题存在于国民经济的许多行业中,其中二维下料应用广泛,而矩形件下料是二维下料的基础,因此,对矩形件的优化下料进行研究是一个具有重大意义的课题。所谓的矩形件下料问题是利用矩形原材料,寻找最优的排样布局下料出所需的全部矩形毛坯,使得原材料的浪费最少的问题。矩形件排样问题按原材料的不同分为两种:原材料矩形板材具有确定的尺寸,需要用最少的板材下料出所需的矩形毛坯的装箱问题(Rectangular Bin Packing Problem)和原材料板材只有确定的宽度而长度无限,需要用最短的板材下料出所需矩形毛坯的矩形件带排样问题(Rectangular Strip Packing Problem)。国内外学者对该问题进行了深入和广泛的研究,并提出了很多算法,如:线性规划方法、遗传算法、模拟退火算法等。近年来,由于蚁群算法的正反馈并行自催化机制,和具有较强的鲁棒性等优点,使其逐渐成为一种应用广泛的元启发式算法。本文针对矩形件排样中的带排样问题这个NP难问题,提出采用蚁群算法进行求解。主要研究包括以下内容:⑴针对该问题提出一种新的排样方案生成算法—基于长度方向最小浪费准则法。该方法可以有效的提高该类问题的利用率。⑵建立该问题的蚁群算法求解模型,给出合适的构建图定义,信息素和启发式信息以及路径构建和信息素更新规则,设计出合适的算法流程。⑶分析蚁群算法中不同的参数取值对问题求解的影响,得出合适的参数来求解该问题。⑷在采用蚁群算法对矩形件带排样问题的处理基础上,对算法进行补充,使其能够处理矩形件装箱问题。⑸最后,设计开发矩形件下料系统。通过对大量的实验进行测试,并将实验结果与其它中文文献以及商业软件的计算结果进行比较和分析,结果表明,本文算法具有较高的材料利用率。因此,本文所提的矩形件下料算法是一种有效的算法。