1、第 卷第期计算机集成制造系统 年月 ：收稿日期：；修订日期：。；基金项目：浙江省重点研发计划资助项目（）；国家自然科学基金资助项目（，）。：，（），（，）设计知识驱动的不规则多边形排样算法及应用冯毅雄，钟锐锐，张志峰，黄城，李中凯，胡炳涛，洪兆溪，谭建荣，（浙江大学 流体动力与机电系统国家重点实验室，浙江杭州 ；浙江大学 设计工程及数字孪生浙江省工程研究中心，浙江杭州 ；中国矿业大学 机电工程学院，江苏徐州 ）摘要：为高效解决实际生产制造中的二维不规则多边形排样问题，提出一种设计知识驱动的启发式算法。利用临界多边形判定多边形之间的相对位置，并建立局部适应度数学模型用于衡量多边形的贴合程度；根据
2、设计知识建立数学模型来评价多边形待摆放位置，利用基于局部搜索的贪心算法完成排样。通过对国际通用基准用例进行实验测试并与现有智能优化算法进行对比，证明了所提算法在排样质量与时间性能上不但具有一定优势，而且稳定性高。通过实际生产中样片数据的实验测试证明了所提算法的实用性。关键词：不规则排样问题；临界多边形；知识驱动；启发式算法中图分类号：文献标识码：，（，；，；，）：，（），：；计算机集成制造系统第 卷引言近年来，随着信息化技术的高速发展，数字化、智能化、网络化等前沿技术广泛应用于制造行业，智能制造技术推动着现代制造业走向全新的发展阶段。不规则多边形排样是现代智能制造中的一项关键技术，这是一种常见
3、的布局优化问题，排样要求将一定数量的多边形对象按照一定的摆放规则约束全部放到一个纵向距离固定、横向距离不定的区域中，摆放结果要求纵向填满，横向尽量缩短，而且所有多边形之间没有重叠或从容器中突出。不规则多边形排样问题在机械制造业的许多领域均有重要应用，例如家居沙发、纺织服装、汽车内饰、气模复合材料、钣金加工等行业都需要处理排样问题。在这类机械制造行业中，原材料通常以卷的形式提供，排样问题更有效的解决方案可以产生显著的经济和环境效益，尤其在纺织行业，经济效益提升得更加突出，当前纺织行业布匹原材料成本占 左右，因此不规则多边形排样问题是一个重要的研究领域。通常，计算机自动生成多边形布局方案比人工手动
4、排样能够获得更加优异的面料利用率，然而不规则多边形排样问题属于 难问题，大规模多边形样片可能无法在有限时间范围内获得最佳布局，目前最为广泛的研究思路是将不规则多边形排样问题细化为不规则多边形摆放策略问题与不规则多边形摆放顺序优化问题，分而治之后获取不规则多边形的最终排样方案。不规则多边形摆放策略问题需要确保不规则多边形的摆放位置符合规范，不规则多边形之间不允许发生碰撞并需要摆放在矩形板材内部。针对不规则多边形的几何特征复杂这一特点，部分学者采用简化不规则轮廓的方式降低碰撞检测和轮廓定位的计算复杂度，虽然能够有效降低计算复杂度，但是在实际应用过程中会受计算机硬件性能影响且产生浪费，存在一定局限性
5、。因此，等提出一种高效且稳定的临界多边形（，）求解算法来获取各种复杂形状裁片的 轮廓；周 鑫 等将 一 种 改 进 轨 迹 线 法 应 用 于 求 解 ；刘玲玲等 提出一种左下临界多边形（，）定位规则，能够有效利用裁片中的孔洞；等 提出一种基于几何相似性特征搜索和 自由格式布局的模糊匹配方法，能够有效提高填充率；饶运清等 提出一种基于无碰撞区域的混合启发式定位规则，综合考虑了不规则裁片之间的重合率、左下（，）定位规则以及无碰撞区域可能出现的特殊情况，通过板材动态边界搜索有效解决了超边界约束条件下的排样问题。不规则多边形排样问题的另一难点在于如何求解出最优的摆放顺序，高质量的摆放顺序能够显著提升
6、最终布局方案的排样利用率。目前多采用启发式算法结合智能优化算法来解决不规则排样问题，并且往往结合多种智能优化算法，或者对原有智能优化算法进行改进，使其更适合解决不规则排样问题。等 利用偏随机键遗传算法完善交叉变异机制，对不规则裁片排样顺序进行迭代优化，获得了更高质量的布局方案；王静静等 对遗传算法进行改进来求解不规则排样问题，算法收敛速度较快且具有优异的全局寻优能力；杨卫波等 提出基于改进实数编码的量子进化算法来确定不规则裁片的排样顺序和摆放旋转角度；等 提出结合波束搜索与禁忌搜索的混合算法，能够在短时间内求解出高质量的布局方案；高勃等 提出基于蚁群学习的排样顺序优化方法，能够有效满足实际生产
7、需求。综上所述，针对不规则多边形摆放策略问题一般采用 策略、左下填充（，）策略和重心 策略等，这类策略虽然简单高效，应用比较广泛，但是仅考虑待摆放多边形自身特性去确定最佳的摆放位置，没有考虑待摆放多边形与其他多边形之间的贴合情况，容易错过更优解。解决不规则多边形摆放顺序问题一般采用智能优化算法，智能优化算法能够有效提升排样利用率，但是缺点很明显：计算复杂度较高，意味着迭代次数更多，算法所需要的时间也更多；由于智能优化算法的优化过程存在随机因素，导致算法稳定性不高，文献中常通过计算平均利用率来衡量算法的稳定性。然而，实际生产过程中往往要求在短时间内获取排样结果，并要求算法稳定性较高。本文针对实际
8、生产环境的需求，提出一种设计知识驱动的启发式算法（，）来解决排样问题，这种启发式算法不仅能够确定多边形的摆放策略，还能用简单而高效的策略调整多边形的摆放顺序，以达到优化排样效果的目的，并且算法整体所需排样时间少于智能优化算法，更适合实际生产环境。通过求解欧洲第期冯毅雄 等：设计知识驱动的不规则多边形排样算法及应用切割与布局特殊兴趣研究组织（，）提供的基准测试用例并与几种有效的智能优化算法的测试结果进行对比，验证了算法具有良好的排样效果，同时利用实际生产中的样片数据进行实验测试，证明算法具有实际生产应用价值。不规则多边形排样问题不规则多边形排样问题是一个二维排样问题，排样要求将一定数量的多边形对
9、象有效地放置在一个矩形面料中，矩形面料具有固定宽度和可变长度。排样问题要求任意两个多边形之间没有重叠，而且所有多边形都被摆放在矩形面料内部，其目标是获得一个多边形布局方案，使矩形面料的利用率最大化，即最小化矩形面料的长度。本文设计算法支持对多边形进行任意角度的旋转，算法将根据实际需求提前设置多边形可旋转角度。在实际应用中，通常仅允许多边形旋转有限的一组角度，可能包括，等离散值，例如在纺织行业中，因为纺织品具有纹理而且可能存在可拉伸图案，所以旋转通常限制为 。对于具有条边的多边形，可以用一组有序坐标顶点表示为（，），（，），（，），（，），而对于具有曲线轮廓的不规则物料，物料上的曲线轮廓可以通过
10、多段折线去拟合，再通过不规则多边形点集约减的预处理方法降低整体计算复杂度，进而转换为不规则多边形排样问题。具有个 多 边 形 的 原 始 多 边 形 集 合 表 示 为 ，由于矩形面料也是一个多边形，将其定义为，并将矩形面料左下角点作为坐标原点，以保证将多边形的摆放位置限制在第一象限内。以原始多边形为例，在将其旋转特定角度后，平移指定距离所得到的最终摆放位置也可以用一组有序坐标顶点表示。因此，对于输入的具有个多边形的原始多边形集合 ，最终的布局方案可表示为 ，。定义为矩形面料的固定宽度，用于限制多边形在轴方向的摆放位置；为矩形面料的长度，即所有多边形最终摆放位置的各个顶点中在轴方向上的最大值；
11、为多边形集合中所有多边形的总面积；为矩形面料的利用率，即多边形的总面积除以矩形面料的面积。综上，建立不规则多边形排样问题的数学模型：（）；（）（，），。（），；（），。（）其中：目标函数（）表示最大化矩形面料的利用率；目标函数（）表示最小化矩形面料的长度；几何约束（）表示任意两个多边形之间没有重叠；几何约束（）表示所有多边形必须摆放在矩形面料内部。图所示为一种合理的不规则多边形排样结果。设计知识驱动策略的启发式算法 临界多边形生成方法多边形的定位策略是不规则多边形自动排样算法设计中的关键。在摆放多边形之前，首先要获取多边形的可摆放位置及对应的旋转角度。直接在矩形面料的可行域空间利用枚举法搜索多
12、边形的位置坐标和旋转角度，并对所枚举多边形的摆放情况进行重叠判断，虽然能够保证获取多边形摆放情况的所有可行解，但是计算复杂度很高，只适用于多边形数量较少的情况。为了降低多边形定位策略的复杂度，本文采用 工具获取多边形可摆放位置所构成的可行域轨迹，其中 由 等提出的滑动碰撞法生成，相比其他现有 生成算法，滑动碰撞法的时间复杂度更低，算法稳定性更高。临界多边形的主要作用在于描述两个多边形的靠接情况。如图所示，给定两个多边形和，将作为固定多边形，作为移动多边形，选取一个参考点，可以是任意点，但要求跟随多边形移动并保持与多边形之间的相对位置，如图 所示；多边形围绕固定多边形 移动一周，移动过程中计算机
13、集成制造系统第 卷保证多边形 和 始终接触但不相交，如图 所示；定义参考点在跟随多边形移动过程中构成的轨迹为 ，如图 所示。借助 可以获取多边形的可行域轨迹，且无需考虑多边形之间是否相交，因此多边形的定位过程就转变为在 轨迹中求取最优摆放位置，大大降低了计算复杂度。局部适应度数学模型常见的定位策略有 策略、策略和重心 策略等，这类定位策略虽然简单高效，应用较广，但是因为仅考虑待摆放多边形自身特性去确定最佳摆放位置，没有考虑待摆放多边形与其他多边形之间的贴合情况，所以容易错过更优解。本文提出一种局部适应度函数，该函数不仅考虑了待摆放多边形的自身特性，还考虑了待摆放多边形与已摆放多边形的贴合程度，
14、采用该函数确定多边形的最佳摆放位置。局部适应度函数的设计思路如图所示，其中：利用待摆放多边形与已摆放多边形外扩后轮廓的相交面积来衡量多边形之间的贴合程度，如所示；仅考虑多边形之间的贴合程度容易出现极端情况，多边形倾向于摆在能与更多多边形接触的位置，从而不会被摆放在靠近矩形面料边界的位置，因此还应考虑待摆放多边形的外扩多边形超出矩形面料的面积，来表示多边形与矩形面料边界的贴合程度，如所示；相比原轮廓，多边形外扩后多出的面积被用作平衡指标，如所示。引入贴合指标函数，其与多边形外扩距离的计算公式如下：；（）；（）；（）式中：为 多边形之间外扩轮廓的相交面积，为多边形外扩后超出矩形面料的面积，越大，多
15、边形之间的贴合程度越高；为多边形外扩后多出的面积，将其作分母，可以消除大面积多边形与小面积多边形在贴合指标对比的“不公平性”，贴合指标的取值范围大致控制在；为 多边形边长的平均长度；为多边形的周长；为多边形的顶点数；为常数系数。另外，需要考虑多边形摆放位置对整体利用率的影响，即考虑多边形自身的特性，根据多边形摆放后对矩形面料使用长度的影响设计位置指标函数。如图 所示，当多边形摆放的位置坐标大于矩形面料原本已使用的长度时，将位置指标的值设为与的比值，越大该位置被选中的概率越低；如图 所示，当多边形摆放的位置坐标小于矩形面料原本已使用的长度时，将位置指标的值设为固定值，确保在该情况下位置指标的值大
16、于前一种情况，同时将位置指标的取值范围控制在。位置指标公式如下：，；，。（）最终局部适应度函数 通过综合考虑贴合指标与位置指标获得。在排料初始阶段，通过贴合指标摆放多边形，以使多边形之间贴合得更紧密；当面料已使用长度超过一定数值后，再考虑位置指标。位置指标是真正影响最后结果利用率的指标，而贴合指标是为了让多边形更加贴合，因此将排料过程分成两部分，前一部分考虑多边形的贴合指标，后一部分综合考虑多边形的贴合指标与位置指标，局部适应度计算如式（）所示，其值越大，该位置被选中为待排多边形摆放位置的概率越大。（），；，。（）第期冯毅雄 等：设计知识驱动的不规则多边形排样算法及应用式中：为面料利用率为 时对应的面料使用长度；为所有多边形的总面积；为矩形面料的固定宽度；为局部适应度函数；为常数系数。设计知识驱动策略及其数学模型局部适应度函数可以很好地解决多边形定位问题，却无法解决多边形定序问题。在多边形排样过程中，多边形的定序策略对排样结果会产生重要影响。利用传统智能优化算法虽然能够迭代生成优秀的摆放序列，但是迭代过程的随机性导致算法稳定性不高，而时间复杂度较高。为解决多边形排样的定序问题，本文采用