高 勃，张红艳，朱明皓

(1.北京交通大学 计算机与信息技术学院，北京 100044;2.北京交通大学 经济管理学院，北京 100044)

0 引言

二维零件排样是实际应用中最常见的排样问题，广泛应用在机械制造、轻工、服装和印刷业等行业中。排样就是在给定原材料区域内将多个零件按照一定的工艺需求以恰当的方式进行排列，最终使得原材料获得较高的利用率，并且要求排样零件之间不能交叉或重叠。排样问题主要分为规则件排样和不规则零件排样两类。在规则件排样中，矩形件排样是排样问题的基础，研究最为广泛，由于矩形件形状简单，可以较快地进行碰撞检测，并且排样方式只有横排或竖排两种，规则零件排样计算复杂度较低，实现起来相对容易。而不规则零件边数为多边形，零件凹凸性不定且形状复杂，并且可以任意角度旋转，因此，在零件定位以及零件之间碰撞检测判断方面时间复杂度较高。随着工业生产规模的不断扩大，针对不规则零件排样问题，综合考虑板材利用率以及耗时情况找到有效的解决方法，对企业尤为重要。另一方面，由于排样问题属于典型的NP完全问题，不规则零件排样问题求解的重点和难点在于如何在尽量短的时间内找到使得原材料利用率尽可能高的排样结果，设计和研究更加高效的不规则零件排样算法具有非常重要的理论研究意义和实际应用价值。

在研究初期，由于不规则件的复杂性，为了化简问……