程 晖，唐明浩

（东华大学 信息科学与技术学院，上海 201620）

在服装行业制衣过程中，要想降低产品成本，提高原材料的利用率是一个非常重要的手段。服装排样就是按照某种算法合理地在原料上排放要切割的衣服样件，从而达到节约原材料的目的。传统的排样方法是由排样者凭借经验采用模板试切的方式进行的，一方面效率低下，而且排样方案的优劣完全取决于排样者的经验程度，这样就造成了很大的局限性。

在现代工业生产实际中，排样一般为不同形状样件的混合排样，这个属于NP完全问题，随着样件数量的增加，并将样件形状、角度等因素考虑在内，会使问题更加复杂化。本文提出一种启发式算法，同时将遗传模拟退火算法相结合，并应用到服装行业的服装样件的排样，以解决服装样件的混合排样问题。

1 基于BL策略的启发式排样算法

本文采用遗传模拟退火算法，通过全局优化概率搜索来产生最佳的排样次序和每个排样件的旋转角度，然后用启发式排样算法进行定位，实现自动排样。启发式算法采用众所周知的左下角（BL）策略[1]，每一个排样件从板料的右上角开始向板料的左下角平移，重复水平和垂直方向的移动直至无法再向左或者向下移动。启发式思想的本质是模拟人的智能行为，而排样对象的几何表达方式则是算法实现的关键。

1.1 排样对象的几何表达

不规则形状的排样件及样板的几何轮廓由直线段和曲线段组成，因为曲线段可以按一定的精度离散成直线段，所以排样对象最终为可能带有内孔特征或者无效区域的多边形。……