产品
1引言
二维不规则零件的排样问题就是将一系列不同形状的不规则零件排放在给定的板材上，选择合适的排样方法，找出零件的最优排布，使得给定板材的利用率最高，以达到节约材料，提高效益的目的。排样技术广泛应用于钣金加工行业。一些产品制造成本中，材料成本占很大比例。特别是在大批量生产中，材料利用率的提高可带来显著的经济效益。因此，研究排样优化，具有重要的现实意义。
理论上排样问题属于非确定型的多项式算法(Nondeterministic Polynomial，NP)完全问题，计算复杂性很高，至今尚未找到有效的多项式算法。但这项研究仍然吸引了众多学者的关注，人们迫切需要利用现代科技找到一个满足生产需要的求解方法。
2排料计算的影响因素及约束条件
排样对象的几何形状和工艺方面的因素，会影响到排样问题的复杂性和算法的设计。
(1)几何因素是指零件具有凸多边形和凹多边形两大类几何形状，有的内部带有不规则的空洞。零件的几何形状越复杂，计算时间复杂度越大，对算法的要求也越高。
(2)加工工艺因素是指零件之间以及零件与材料周边之间留有一定的搭边值，有时对一个排样方案中的矩形件进行切割时，提出满足共边切割的下料工艺要求。
(3)二维不规则零件的排样必须满足的约束条件有：①零件必须置于板材内部；②零件互不重叠；③满足一定的工艺要求。为加快排样的速度，一般约定：①零件在板材上的放置按照最左最低原则进行；②零件按而积从大到小依次排序进行初始排样，保证大零件优先排人。
3排样优化算法的研究和现状
与二维矩形件排样相比，不规则零件的排样增加了排样角度和排样位置的任意性，且板材和零件均有可能为任意多边形，板材和零件的内部还可能包含内部孔洞。所以。不同零件之间的靠接、判交等处理比较复杂。其排样问题在计算几何方而具有较高的复杂度。零件的任意角度和位置的排放使得搜索空间变大，实际排样不可能存在多种精确排样算法。排样研究的算法主要分为两大类：一是局部优化算法，多用于预处理阶段；二是全局优化算法，用于初始排列之后的调整，使材料利用率尽可能高。
3．1局部优化算法
无论排样策略如何，都会面对两个排样零件的相互位置关系的几何问题。具体表现在：两个零件若重叠，沿某个矢量方向的最短距离是多少；一个零件在排样时相对于另一个零件可能排放最佳位置。达到排样利用率最高，其实质是图形求交和定位的问题。排样计算量以及自动化程度也是研究的关键。
(1)矩形包络法
矩形包络法的基本思想是：给定多边形A，任意做一个矩形包络，计算出该包络矩形的面积S1；通过旋转对称轴一个角度△θ，以此新的对称轴作矩形包络，如此重复直到轴旋转90°为止，所有矩形包络中面积最小的包络矩形即为最小包络矩。黄宜军等还提出了最小冗余原则，将两个不规则零件相对转组合后进行矩形包络，提高材料利用率。王淑侠等15提出了最佳包络率的概念，设定最佳包络率的上限α和下限β，对两个或多个多边形的临界多边形(NoFit Polygon，NFP)形成的包络矩形进行筛选。
二维不规则的多边形零件通过矩形包络法转换成矩形(在此二维矩形零件是不规则零件的一种特例)。矩形零件的排样一般采用最左最下原则(Bot-tom-Left)。Jakobsf9I基于"最左最下"原则。提出了"BL算法"，但是该算法不能保证最优排样，材料利用率不高。刘德全在"BL算法"的基础：进行改进，提出了"下台阶算法"，通过己录已排零件的高度轮廓线。更好地解决了将码转换为排样图的问题。贾志欣、邓冬梅认为"BL算法"还存在容易发生板材左侧排放偏高的问题，而"下台阶算法"则容易发生右侧偏高的问题，为此，提出了最低水平线算法，该方法在排入零件时总是先查询拍样图的高度轮廓线的最低水平线。
剩余矩形匹配法按零件的面积排序优先保证大尺寸零件先排，依次按剩余矩形最佳匹配原则排入板料，但该算法很难找到拍样的最优解。匹配算法的基础上提出了矩形匹配分割算法，按照先进行矩形匹配后进行板材分割的原则排样。宋连超等在近似算法的基础上，提出了一种新的排样算法--贪婪算法，既满足实际生产中切割工艺要求，又能够有效的提高板材利用率。崔耀东等提出了一种递归算法，生成矩形毛坯两段排样方式，材料利用率较高。
(2)临界多边形算法NFP
临界多边形的基本思想是：固定多边形A不动，多边形B沿着多边形A环绕一周。同时，多边形B上至少有一点和多边形A的边保持接触，但两个多边形不能重叠、旋转和翻转。在这个过程中，多边形B上的一个参考点P留下的轨迹就是多边形B相对于多边形A的临界多边形NF一列。图1所示的临界多边形给出了所有靠接位置的信息，因此，不规则的排样问题就可以简化为基于临界多边形的定位选优过程。现有的临界算法主要可归纳为4种：
①移动碰撞法
这是通过不断求取下一步的碰撞位置得到临界多边形。根据多边形A和B当前时刻的靠接状态。确定多边形B下一步的移动方向；在该移动方向上，计算出A和B之间的最小碰撞距离(可移动距离)；根据移动方向和移动距离将B移动到新的位置；然后重复以上移动过程，直到回到初始位置。但在多边形B的滑动过程中，无法滑动到边界空腔内部或孔洞内部，很难计算多边形边界空腔和内部孔洞的NFP。这一点严重影响了该算法的应用。此外，该算法的时间复杂度也较高。
②明可夫斯基矢量和法(Minkowski sum)及其派生算法
根据Minkowski矢量和法的定义，NFPAB等于2个凸多边形矢量边首尾连接之和。但是Minkowski矢量和法只适用于凸多边形的NFP求解，当2个多边形中有一个多边形为凹多边形时，边矢量的排序连接方法将不49有效，凹边的遍历次序将会被打乱，从而不能正确合成一个NFP。为此，Bennell等基于矢量和方法提出了斜率图(slope diagram)算法。斜率图算法虽然在时间复杂度上有所改进，但仍然只能处理A、B中最多只含一个凹多边形时的情况，且该NFP算法复杂，边界空腔问题不易处理。Bennell、Xiang Songm在此基础上进行改进，通过Minkowski矢量和法求出多边形A和B的所有边，得到Minkowski和的边列表；根据列表，采用轨迹追踪的方法寻找出正确的NFP边界。这种方法解决了凹多边形和边界空腔不易处理的问题。
③凹多边形凸化分割法同
该方法将凹多边形划分为若干个子凸多边形。然后应用Minkowski矢量和法求子凸多边形的NFP，再对多个子NFP进行合并，得到最终的NFP。凹多边形的凸化分割算法有三角划分、凹点划分、角平分线分割、延长线分割、星形分割法等，但是这种分割算法的复杂度已经大于碰撞法的复杂度。多边形分割可能会产生冗余多边形，从而增加子NFP的计算量。另外该算法还需要进行分割后凸多边形之间的NFP求解，以及多个子NFP的合并，因而进一步增加了计算的复杂度。
④基于轨迹计算的NFP法
该法通过求解多边形顶点相对另一多边形的轨迹线，然后求解轨迹线集合所形成的外包多边形和内部顺时针环，得到的多边形即为NFP，由此很好地解决了凹多边形和内部空腔问题。算法采用基于网格的线段索引方法来加快线段之间的求交计算，提高NFP的求解计算速度。刘胡瑶等提出了基于重心NFP的最低重心零件放置原则，使得零件在排放时达到当前最低莺心，无需对不规则多边形进行矩形包络，提高了材料的利用率，但也增加了时间复杂度和计算量。
(3)平移算法
平移算法的基本思想是：计算放入多边形的平移矢量，当多边形沿平移矢量移动时。对其他已放入的各多边形以及区域边界进行碰撞测试，根据测试结果计算下一步移动的平移矢量，直至达到最终位置。平移算法可有效提高部件靠接与定位的速度，基于这个技术有很多研究。王浩宇等对传统的平移算法进行了改进，提出了一种新的优化算法并进行了验证。以该算法为核心的排料系统除可完成一般的卷料、条料、板料：的单排、双排和对头排外，还可求解嵌套排料问题，具有计算速度快、优化效果明显、结果可靠等优点。雷贺功等在普通多边形顶点算法基础上，提出了一种多边形顶点射线算法。该算法克服多边形顶点算法通用性差的局限，能高效准确得出常规单件排样方式的最优解。李爱平等闭在多边形顶点算法的基础上，提出了基于包容矩形的排样算法，只在初始毛坯图的包容矩形内进行计算就可得到排样的步距、料宽等关键参数，省略多边形等距放大搭边值A／2操作，简化了排样算法和计算量，提高运行速度。
3．2全局优化算法
为了能寻求全局最优解，一些学者尝试将人工智能的方法与局部优化算法结合。人T智能方法具有良好的全局搜索能力，克服局部优化算法在求解空间的搜索局限。基于全局优化思路的算法有遗传算法、模拟退火算法、粒子群算法和蚁群算法。
(1)遗传算法
遗传算法(Genetic Algorithms，GA)是1975年由Michigan大学Holland提出的一种借鉴生物界自然选择思想和自然遗传机制的全局随机搜索算法。GA的思想是把问题的可行解构成种群，把每一个可能的解看作种群的个体，在整个求解空间内随机搜索，按一定的评估策略(或适应度函数)对每一个体做出评价。通过不断地使用选择、交叉、变异这三种遗传算子，使问题的解不断进化，直至产生最优解。在利用该算法进行状态空间搜索时。适应度的计算量最大，而计算的效率关键在于解码算法的好坏。其主要优点是简单、通用，适用于并行分布处理；但该方法存在局部寻优能力较差、容易早熟等缺点。贾志新等将遗传算法用于二维零件的排样问题，对其解码方法进行了研究。证明遗传算法是求解排样问题的一个有效方法，但求解的效率和精度还有待提高。李明等针对上述问题，在选择算子、解码算法方面进行改进，提高了算法的伞局收敛性和精度。洪灵等引入零件之问的顶点碰撞特性，减少零件水平右移时的计算量，通过板料基线策略，避免了与基线以下的零件的判交运算，使解码时问和排样零件数量之问的关系近似线性，提高了解码速度。
(2)模拟退火算法
模拟退火算法(Simulated Annealing Algorithms，SAA)．是由Metropolis等人于1953年提出的。SAA的思想是借用固体物质作退火处理时，先升高温度使其融化，再冷却，在一定条件下可使之达到最低能量的基态。将能量函数应用于优化问题的目标函数，进行寻优。通过研究解和邻域跳出局部最优，从理论上保证算法收敛到全局最优解，具有较强的局部搜索能力。但模拟退火算法把握搜索过程的能力不强，从而使得其运行效率不高，运算时间无限延长。
基于遗传算法与模拟退火算法在拍样过程中具有互补作用，往往将两者结合应用。局部搜索能力加强，提高衍化速度，利用遗传模拟退火算法的全局搜索能力，寻找最优的排样次序和零件各自的旋转角度，结合启发式算法，提升算法的实用性。冯美贵等例从遗传模拟退火算法混合优化策略的构造点出发，融合小生境技术的思想，提出了基于小生境技术的遗传模拟退火算法(Niching Genetic Simulated Annealing Algorithm。NGSA)，也可加强全局和局部搜索能力，通过新的选择和变异机制，提高遗传算法的稳定性和收敛速度。
(3)粒子群算法
粒子群优化(Particle Swarm Optimization，PSO)算法是由Eberhart和Kennedy在1995年首先提出的一种进化计算方法旧。PSO起源于对鸟群觅食行为的模拟，它与人工生命理论关系密切，是一种基于群智能的优化算法。PSO算法和其他进化算法主要区别在于：其解(称为粒子)与其运动速度有关，通过粒子之间的相互影响，根据各自的速度和位置搜索求解。PSO中，每个优化问题的解都是解空间中的一个粒子。所有的粒子都追随当前的最优粒子，通过迭代在解空间中找到最优解。在每一次迭代中，粒子通过跟踪两个极值更新自己。一个是粒子本身所找到的最优解，这个解称为个体极值；另一个极值是整个种群目前找到的最优解，这个极值是全局极值。
李明等通过先将二维不规则零件的排样问题转化为矩形件的排样问题，利用粒子群算法优化求解，在求解过程中运用自适应调整策略对零件的排样位置进行微调，但它侧重纵向搜索，可能陷于局部最优。黄建江等在经典PSO算法基础上，提出了最大速度线性收缩策略(MVCS)，给出了新的排样组合优化算法(MVCS-PSO)的粒子构造方法和零件排样过程，排样初期呈现较强的全局搜索能力，后期具有较强的局部收敛能力，时间复杂度和收敛性能都优于SAGA。宋佩华等通过用置换子和置换系列构造一种离散粒子群优化矩形件排样算法，排样时间和排样利用率高于在同样条件下用遗传算法获得的结果，但如何有效设置离散粒子群的参数以便提高求解效率还没有更好解决。
(4)蚂蚁算法
蚂蚁算法(Ant Algorithm，AA)是Dorigo提出种源于大自然中生物世界的新的仿生类算法。通用型随机优化方法，它的基本原理来自昆虫中蚂蚁的行为特性，蚂蚁在寻找食物源时。能在过的路径上释放一种蚂蚁特有的分泌物，使得一定范围内的其他蚂蚁能够察觉到并由响它们以后的行为。当一些路径上通过的蚂蚁越来越多时，其留下来的信息素轨迹也越来越多，信息素强度增大，蚂蚁选择该路径的概率也越高，这种选择过程被称为蚂蚁的自催化作用。AA具有通用性、鲁棒性、并行性等优点；但AA对于规模较大的问题，其性能迅速恶化，另外，由于AA是一种正反馈算法，所以容易陷入局部优化。
黄红兵闭等尝试用蚂蚁算法来求解矩形件优化排样问题，通过实例表明用蚂蚁算法得到的排样利用率高于遗传算法，证明了该算法求解排样问题的可行性和有效性。蚂蚁算法作为一种新型的模拟进化算法，其研究刚刚开始，目前理论还不完善。
4排样优化算法的发展方向
不规则零件的排样算法已有大量新的研究，但距离实际应用还有差距。研究的发展可以归纳以下几个方面：
(1)研究高效的局部优化排样算法。利用矩形包络法进行排样，容易出现空白区域，降低排样利用率；而利用临界多边形法(NFP)进行排样，计算的复杂度很高，影响算法效率。材料利用率的高低受不规则零件的几何形状、排样工艺、生产要求等因素的影响，如何更有效的解决不规则零件排样问题有待进一步研究。
(2)改进和综合多种有效算法。目前已有将遗传算法和模拟退火算法组合成混合算法，取得不错的排样效果，采用混合智能排样算法也是未来的一个研究方向。在智能算法中使用多参数控制，需要经验和经过大量的实验来确定，所以，还需更深入地研究这些参数在排样过程中的动态控制。
(3)结合人工智能、机器人视觉、图像识别等领域知识，期望能模拟人工排料的直觉判断行为。一些所谓的"自动排料系统"往往需要人工干预，有很大的局限性，不一定得到最优解。如果能够使得计算机也可以做出某些类似直觉的判断，那么再结合计算机本身的高速计算能力，将可以在优化排料领域做出突破性的贡献。
5结束语
不规则零件的排样问题是属于NP完全问题，其排样效果受零件的几何形状、工艺、生产要求等因素的影响。国内外学者对优化排样算法进行大量研究，开发了各种各样的排样软件，但在实际应用中仍然存在不足。随节能型、效率型加工方式的深入，期待研究出高效、通用、简便的自动排样算法。本文根据对这个领域掌握的研究资料，综合分析了当前这一技术的最新研究和发展的动态，期望对同行有所帮助。
155-2731-8020
