二维不规则零件自动排料的优化算法

　　自动排料一直是国内外非常活跃的研究课题,它是将计算机辅助设计技术应用于排料工作中,以减轻工人劳动强度、提高排料速度和最大限度节省材料,并使整个排料过程中无需人的干预。材料利用率的最大化一直是人们追求的目标。由于在许多工业部门使用材料的数量非常大,材料利用率的微小提高即可获得较高的经济效益;同时,自动排料问题具有高度的复杂性,属于组合优化问题和NP完全问题,实现自动排料系统具有相当的难度,因此对优化排料问题进行深入研究具有重要的科研和应用价值。

　　1　排料的分类、求解复杂性

　　排料问题按维数可分为一维、二维、三维排料,其中二维排料问题在机械制造、轻工、船舶、家具以及服装等行业中应用十分广泛。实际生产中矩形件毛坯占很少一部分,大部分二维零件毛坯是任意多边形,通常将矩形之外的其余形状图形归类为二维不规则排料。二维不规则排料属于最复杂的组合优化问题之一,其复杂性主要由多边形的不规则几何形状和不同的次序组合引起,由于零件形状不规则,所以不同零件之间的靠接,判交等处理比较复杂,计算复杂度高,不同的次序组合、旋转角度都可能导致不同的排料结果。下面主要针对常见的二维不规则排料进行分析研究,并对数控火焰切割中的排料进行验证。

　　2　不规则零件的排料

　　2.1　排料预处理

　　2. 1. 1　最小包络矩形的求取

　　求取零件的最小包络矩形是排料算法的要求。所谓最小包络矩形就是能够包含零件的所有矩形中面积最小者。资料表明:只有当零件的包络矩形与零件的外轮廓多边形中的一条边平行或重合时,此包络矩形才有可能是最小包围络形。据此,我们得到了求零件最小包络矩形的方法:对零件外轮廓多边形进行操作,分别求得与多边形平行或重合的最小包络矩形,找出其中的最小者即为零件最小包络矩形,如图1所示,此后,在排料时还需恢复零件原形。

　　2. 2. 2　聚合矩形的求取

　　为了提高板材利用率,需要对零件进行一定程度的聚合,然后求取聚合后零件的最小包络矩形,称之为聚合矩形。零件的聚合就是使零件相互接触,但不重叠,以达到包络矩形的面积最小。在排料过程中,由于零件可以任意方向旋转,两个零件的聚合问题就显得尤为复杂,但根据文献中的研究结果[1],

　　两个相同的零件进行聚合,只有当两个零件相差180°时,才能产生最小包络矩形,因此,在零件聚合过程中,可以只考虑相差180°时的情况。图2表示了零件聚合过程,其聚合过程如下: