基于临界多边形的不规则件启发式排样算法

汤德佑　周子琳

摘要：

为提高不规则件启发式排样的材料利用率，提出一种基于重心临界多边形和边适应度的不规则件启发式排样算法GEFHNA。首先，定义了边适应度以衡量排样过程中原材料与不规则件间贴合程度，在此基础上给出了将边适应度与重心NFP（GNFP）相结合的排放策略以减少排样过程中可能产生的空隙面积；其次，给出了基于WeilerAtherton多边形裁剪算法的剩余原材料求解方法，重用排样过程中产生的孔洞，减少孔洞面积；最后，给出了基于上述排样策略和材料重用策略的启发式排样算法GEFHNA，给出了与智能算法和同类软件的实验比较。对欧洲排样问题兴趣小组提供的基准测试用例的实验结果表明，GEFHNA的耗时约为基于智能算法的排样方法的千分之一，同时在与两款商业软件NestLib和SigmaNest的11个基准测试的对比中，GEFHNA获得了7 / 11个相对最优的排样面积利用率。

关键词：

二维不规则件；排样；临界多边形；启发式方法

中图分类号：

TP301.6

文献标志码：A

Abstract：

To raise the material utilization ratio of heuristic nesting for irregular shapes， a Gravity NoFitPolygon （NFP） and Edge Fitnessbased Heuristic Nesting Algorithm （GEFHNA） was proposed. Firstly， the definition of Edge Fitness （EF） to measure the fitness between the material and irregular shape produced in the process of packing was defined， and a packing strategy combining Gravity NFP （GNFP） with edge fitness was proposed to reduce the area of gap generated in packing. Secondly，a WeilerAthertonbased algorithm was presented to compute remained materials and add holes produced in each round of packing to the list of materials. The heuristic packing algorithm prefered the holes in next rounds of packing to reduce proportion of holes in released layout. Finally， a heuristic algorithm based on the previous packing strategy and reuse strategy was put forward and the comparison experiments of GEFHNA with intelligent algorithm and similar softwares were presented. Experimental results on the heuristic packing algorithm with benchmarks provided by ESICUP （EURO Special Interest Group on Cutting and Packing） show that GEFHNA only has about 1/1000 time consumption of intelligent algorithmbased nesting scheme and achieves 7/11 relatively optimal utilization rate in contrast with two commercial softwares NestLib and SigmaNest.

英文關键词Key words：

twodimensional irregular； packing； NoFitPolygon （NFP）； heuristic method

0引言

排样（Nesting/Packing/Stock Cutting Problem）是组合优化过程，已被证明为NP（Nondeterministic Polynomial）完全问题[1]。二维不规则件排样需要旋转样件以找到最佳摆放位置，解空间巨大，求解复杂度高。启发式排样算法设定样件选择策略与排放策略的规则集合，根据规则完成样件的排样，速度快，是解决二维不规则件排样问题的常用方法。

启发式排样重点需要解决碰撞检测、选件策略（样件被排放的顺序）和样件排放策略（确定样件的旋转角度和排放位置）等问题。零件选择策略常采用First Fit（FF）、Best Fit（BF）和DJD（Djang and Finch heuristic）方法[2]。FF和BF应用了贪心的思想，DJD则在排序的基础上增加了组合小样件以求最大化利用未排空间。排放策略中最常用的是BL（BottomLeft，BL）策略[3]，该策略采用“靠左靠下”的原则，在保证零件不重叠的情况下，向下向左移动，直至不能再移动为止，到达“BL稳定位置”。BL算法在排样过程中容易出现排样结果左侧偏高的现象，且排放过程中会产生一些面积较大的空白区域，常对其改进再应用[4]，如下台阶策略[5]、BLF（BottomLeft Filling）策略[6]等。CA（Constructive Approach）系列策略[7]根据当前原材料上零件排放的位置情况，给定几个排放位点，待排零件从给定位点中选择最优的一个位点进行排放。

临界多边形（NoFitPolygon，NFP）[8]是研究不规则件排样算法的重要分支，可用于碰撞检测或确定排放位置。Dowsland等[9]给出了基于NFP的不规则件BL排样算法，在排放当前零件时，采用当前零件相对于原材料中所有已排零件的NFP进行“BL稳定位置”的判断和选择。基于重心NFP的排放策略[10]以零件的重心作为生成NFP的参考点，对样件的每一个旋转角度生成一个内部NFP，对比所有角度下生成的NFP的顶点，选择其中的最低点进行排放。

研究表明，对启发式排样，样件形状与原材料的特征吻合度直接影响排样效果[2]。本文提出“边适应度（Edge Fitness，EF）”的概念来衡量排样过程中不规则样件与原材料的贴合程度，并结合重心NFP[10]的思想，提出了基于重心NFP与边适应度的排样策略。给出了基于WeilerAtherton多边形裁剪算法[11]的剩余原材料求解方法以减少原材料浪费，将排样中产生的孔洞加入原材料列表并在后续排样中优先使用。在此基础上结合FFD选件算法，给出了一种基于重心NFP与边适应度的启发式排样算法GEFHNA（GravityNFP and Edge Fitnessbased Heuristic Nesting Algorithm）。测试表明，GEFHNA耗时是基于智能算法的排样算法的千分之一，并在与商业软件NestLib和SigmaNest的11个基准测试对比中获得了7/11个相对最优的排样面积利用率，排样效果较好。

通过生成临界多边形，能够根据参考点与临界多边形间的位置关系快速地对不规则零件进行碰撞检测：

1）当B的参考点位于NFPAB上时，B和A刚好接触；

2）当B的参考点位于NFPAB内部时，B和A重叠；

3）当B的参考点位于NFPAB外部时，B和A分离。

临界多边形的碰撞检测的时间复杂度为O（n），其中n为临界多边形的边数，且给出了多边形A和B之间的所有刚好接触的位置集合。在此情况下，只需要对全部可能的接触位置作出优化选择，即可确定零件合理的排放位置。

重心NFP[10]是将多边形B的重心设为参考点，以此求得的多边形B相对于多边形A的NFP，记为GNFP。二维不規则样件的重心位置是样件的大部分面积所在的位置，可使评价函数对实际的排放效果反映更准确，提高材料使用率。不规则样件的重心可采用多边形分割法求解。设不规则样件p分解为n个子部分，则使用多边形分割后样件p的重心计算公式如下：

x=∑Aixi/∑Ai

y=∑Aiyi/∑Ai； 1≤i≤n（1）

其中：Ai为第i个子部分的面积，xi和yi分别为第i个子部分的重心的X坐标与Y坐标位置。对任意多边形，面积可采用梯形法求解，在给定旋转角度下的重心可以利用多边形分割法及式（1）进行求解。求得样件p的重心后，将该重心设为样件p的参考点并进行NFP的求解，即可求得样件p相对于给定多边形在当前旋转角度oi下的GNFP，计算方法见文献[10]。

2基于GNFP与边适应度的排放策略

给定待排原材料和样件，排样策略给出样件的摆放位置及摆放角度，本节首先定义边适应度（Edge Fitness， EF）值及计算方法，最后给出基于GNFP和EF值的排放策略。

2.1边适应度

对二维排样而言，最佳效果的排样是排样后零件间处于贴合状态，零件间无孔洞，此时材料利用率将最高。因此，排样中边的贴合情况可作为启发式排样的重要规则。

定义EF值：给定边集为E的不规则样件p，轮廓边集为e的原材料A，对任意Ei∈E，ej∈e，若排放后Ei和ej贴合，记贴合长度为f（ej，Ei），称p所有和原材料轮廓边界重合的长度之和为边适应度，简称EF值，即：

EF（A，p）=∑1≤i≤m，1≤j≤nf（ej，Ei）（2）

EF值反映了样件与原材料或已排样件的贴合程度，EF值越大说明边贴合得越多，排样密度更大。如图2中，在零件重心Y坐标值相同的情况下，图2（b）拥有比图2（a）更大的EF值，选择图2（b）排放可能产生更好的排样效果。

计算边适应度需要将待排样件p进行“预排放”，即将样件p摆放到按照GNFP求得的候选点，然后计算在候选点的EF值。在实际计算EF值时，样件的边与原材料的内部轮廓边均按顺时针或逆时针存放，只需比较其中的部分边对，计算时间为O（m+n）。

2.2排放策略

基于GNFP和边适应度的排放策略的主要思想是：对当前待排样件p，求出其在所有可旋转角度oi（测试数据集包含了所有可能的旋转角度）下的相对于原材料内部轮廓边界的内部GNFP，记为GNFPi。对比所有GNFPi的左下点和右下点，筛选出最下最左点和最下最右点，记为BestBL和BestBR，设所对应的旋转角度为OBL和OBR。根据OBL和OBR以及位置点BestBL和BestBR，对样件p进行预排放并求出在这两种排放状态下的EF值，保留EF值最大的排放状态作为样件p排放时的旋转角度和排放位置，完成对样件p的排放。单个样件的排放算法如下：

Algorithm PackingI（int indx， Panel * pPanel， Part * p）

//描述：根据样件序号可查样件类型、样件类型对应可旋转数、在旋转角度o下的样件形状，旋转角度o按从小到大保存，为零表示未旋转，本算法根据待排样件序号在原材料上完成排样，输出排样完毕后的样件图形数据。

//输入：待排样件序号indx，当前原材料图形数据pPanel；

//输出：排放完毕后的样件图形数据p；若样件能够排放在pPanel返回1，否则-1。

1）初始化BestBL和BestBR为pPanel左上和右上点，取得p的类型、旋转角度等数据，取一个旋转角度下的图形数据。

2）计算在当前旋转角度下样件图形相对于pPanel内部轮廓边界的GNFP，若成功计算则转3）；否则取下一个旋转角度下的图形，继续2）；若所有角度均已计算则转5）。

3）判定当前计算出的GNFP的左下点/右下点是否优于已记录的BestBL和BestBR，若优则更新BestBL和BestBR，并记录对应的旋转角度。

4）取下一个旋转角度，转2）。

5）若BestBL和BestBR更新过，取出产生对应点的旋转角度和图形数据，预排放到pPanel，分别计算其EF值；否则返回-1。

6）比较BestBL和BestBR处排放所产生的EF值，保留EF值较大的预排放，输出p，返回1。

设两多边形分别有m和n条边，样件具有k个旋转角度，步骤2）的执行时间为k*T（G），其中T（G）为计算GNFP的时间渐近复杂度，其下界为Ω（mn）；而计算EF值的时间复杂度为O（m+n），对算法性能影响小。

3启发式排样算法

3.1二维排样问题的归一化

工业应用中二维不规则件排样问题可分为二维装箱排样问题（TwoDimensional Bin Packing Problem， 2DBPP）和二维条带排样问题（TwoDimensional Strip Packing Problem， 2DSPP）。装箱问题中原材料的横向宽度和纵向高度都是限定的，且原材料的数量可能大于1；条带排样问题中，原材料的纵向高度是不限的，只限定横向的宽度。为使原材料具备封闭形状的特性，方便剩余原材料的求解，对二维条带排样，本文在排样初始化阶段对其初始原材料设定一个安全的初始高度H，使其具有封闭形状。安全初始高度H的设定方法为：求出所有待排样件的包络矩形，对第i个样件的包络矩形，设其高为hi，宽为wi，则安全高度H为：

H=∑1≤i≤nmax（hi，wj）（3）

3.2剩余原材料的求解

应用临界多边形完成二维不规则排样时，在排放完一个待排样件后，需求解出当前剩余原材料的内部边界轮廓，以排放下一个样件。目前，多数研究人员采用将已排多边形的外部轮廓与原材料的内部轮廓边界融合，形成剩余原材料的轮廓边界的方式[12]，忽略了新排样件与原材料轮廓之间的间隙，容易造成原材料的浪费。

为提高材料利用率，本文基于WeilerAtherton多边形裁剪算法实现了一个剩余原材料求解算法。待排原材料或剩余原材料以列表存储，将排样过程中新排样件与原材料之间可能产生的空洞作为新的原材料加入到原材料列表中，并优先使用这些原材料。算法将排样过程中待排视作裁剪多边形B，将当前排入的原材料视作被裁剪多边形A，且两多边形均为顺时针方向，求解得到的多边形A不在多边形B中的部分（外裁剪部分）即为排样后产生的原材料列表。

剩余原材料的求解算法具体如下：

Algorithm WACompute（Part * p， Panel * pPanel）；

//描述：计算样件p排样后的剩余原材料，运算过程中数组Q用于保存裁剪产生的孔洞。

//输入：原材料pPanel和样件p及对应顶点数组aArray和bArray；

//输出：排样完后的原材料列表result。

1）将原材料pPanel与样件p设为顺时针方向。

2）求出两多边形的交点，更新aArray和bArray，同时将aArray中与原p重叠的点替换为bArray中的点。

3）顺时针扫描aArray，若在交点处进入B则标记为“入”点，离开B则标记为“出”点，更新aArray。

4）从aArray中任取一个“出”点，记为R，令S=R，并初始化点集Q为{S}。

5）顺时针遍历aArray数组，在遍历过程中，若点未標记，则存入结果数组Q中，重复5）；若点标记为“入”，记为T，并转6）。

6）找到T在bArray数组中的位置，开始逆时针遍历bArray数组，设遍历到的点为X，若X未标记，则加入Q，重复6）；若X=S，转7）。

7）停止遍历数组bArray，结果数组Q中的点即组成一个外裁剪多边形区域，计算点集构成的多边形cShape，将其加入到result。

8）令S=T在aArray中的后继，若S=R，返回result；否则转令Q={S}，转5）。

步骤2）、3）中，为求得外裁剪部分，首先需要求得A和B的交接关系。根据排放的特点，排放后A和B交接关系有6种，下文对照图3予以说明：

1）B边与A边重叠，交点为B的端点，如b10、b11、b13、b14等，其中含两种特殊情况：

①A和B有连续多条边重叠，此时重叠范围内A和B的端点均不计入交点，并将这些重复点从A和B原点集中消除，如a5或b5；

②两边有一个端点重叠，如b14与a9或b13同记为交点。

2）A边交B端点，如交点b1。

3）A端点交B边，如交点a7。

4）A和B端点内交，如交点a6或b8。

5）A和B端点外交，如交点a3或b3。

图3对应排放在步骤2）结束后aArray为{a1，a2，b3，a4，b4，b6，b8，a7，a8，b10，b11，b13，b14，b1}，bArray为{b1，b2，b3，b4，b6，b7，b8，b9，a7，b10，b11，b12，b13，b14}。

步骤3）中，对情形1和2，每个交点将标记为“入”或“出”，对情形3～5，交点需先标记为“入”，再标记为“出”。如图3中对应aArray中b1～a5间端点集更新后：{b1（入），b1（出），a1，a2，b3（入），b3（出），a4，b4（入）}。

设取出多边形A顶点集的第一个出点为b1，在上述结果集上应用算法的步骤4）～8）后可得到{b1，a1，a2，b3，b2}和{b3，a4，b4}两个孔洞。aArray中选择b1（出）后依次取未标记顶点a1和a2，遇到b3（入）后转bArray中逆时针查找得到b2，继续查找时遇到本轮起点b1，产生了第一个孔洞。下一次查找从b3（出）开始，产生孔洞{b3，a4，b4}。

给定分别具有m和n条边的被裁和待裁多边形，算法中的顶点数组aArray和bArray的长度为m+2～m+2n或n+2～2m+n。设待裁多边形顶点与被裁多边形接触的个数是等概率事件，即pi=1/n，则aArray的平均长度为：

la=1n∑ni=1（m+2i）=m+（n+1）/2（4）

同理可求bArray的平均长度为lb=n+（m+1）/2，因此扫描顶点数组的平均时间复杂度为O（m+n）。算法为保持完整性将求交点置于步骤2），实际上，在计算EF值时可同步求出交点，复杂度为O（m+n），因此WACompute算法复杂度为O（m+n）。

3.3启发式排样算法

排样过程划分为四个阶段：1）初始原材料的前处理，将任意二维的排样问题归一化为二维装箱问题；2）利用FFD策略选择一个样件，利用排样策略排放该样件；3）对剩余原材料进行后处理，得到可应用下一次排样策略的原材料列表；4）重复2）～4）步，直到剩余原材料列表不能排放任何样件或样件已经排放结束。基于GNFP和EF值的启发式排样算法GEFHNA）如下：

Algorithm GEFHNA（Part * pPart， Panel * pPanel）

//描述：采用FFD选件策略，优先排放面积小的原材料。

//输入：待排样件列表pPart，原材料列表pPanel；

//输出：排样完后的原材料列表pPanel，剩余样件列表pPart。

1）初始化原材料列表数据、样件数据等。

2）对pPart中的样件按面积大小降序排序。

3）将pPanel中的原材料归一化，并按照面积大小升序排序。

4）取当前最大的未试排样件。

5）取pPanel中的第一个原材料p。

6）若样件面积不小于原材料面积，转9）；否则调用PackingI，若返回1则转7），否则转9）。

7）调用WACompute计算排样后的剩余原材料R，更新pPanel，删除p，并将R中面积大于当前最小未排样件面积的原材料加入到pPanel。

8）取下一个未试排样件，若存在转5），否则转10）。

9）从pPanel中取下一个原材料，若成功转6），否则转4）。

10）計算材料利用率，返回。

设原材料数为m，待排样件数为n，原材料和样件最多边数为t条。上述算法中步骤1）需O（m+n）步操作，步骤2）和3）需O（m log m+ n log n）步操作，与PackingI算法相比这些操作对排样算法性能影响较小。设每次排样后产生的孔洞个数是等概率的，则每次排样后增加的平均孔洞数为（t+1）/2个，在不考虑步骤6）的优化条件下，GEFHNA对i个样件排样时调用PackingI的最多次数为：

cpanel=m-（i-1）+（i-1）（t+1）/2=

m+（i-1）（t-1）/2（5）

设样件成功与失败排放和成功排放在某各原材料上均是等概率的，则对i个样件排样时调用PackingI的平均次数为：

acpanel=12cpanel∑cpanelj=1（j+cpanel）=（3cpanel+1）/4（6）

排放n个样件共需调用PackingI的平均次数为：

∑ni=1acpanel=3mn+n4+3n（n-1）（t-1）16（7）

由式（7），综合PackingI和WACompute算法的复杂度，GEFHNA算法的平均时间复杂度为O（mntk） *T（G），其中k为样件最大旋转角度数，T（G）为计算GNFP的时间渐近复杂度。由于步骤6）的优化，算法实际效率可以得到大幅提高。

4测试结果与分析

本文以欧洲排样问题兴趣小组ESICUP[13]提供的基准问题作为测试算例，对本文提出的GEF启发式排样算法的排样效果和性能进行测试。

测试环境：Intel Core2 Duo CPU T6570 @2.10GHz，2GB RAM，Windows 7旗舰版。

测试方法：每个基准问题均运行10次，排样时间取10次运行的平均排样时间。

针对时间性能的GEF启发式排样算法的测试结果如表1所示。因合理结合遗传算法和禁忌搜索算法可有效抑制早熟，同时提高收敛速度，与单一算法比较效果更好[15]，本文将启发式算法与之对比。表中混合智能算法为作者结合遗传算法和禁忌搜索算法实现的智能排样算法的排样密度和排样时间。从表1可以看出，虽然启发式算法排样密度较智能算法有较大差距，但用时仅为智能算法的千分之一左右。在排样密度方面，当排样长度较小时（100单位以内），通过计算可得启发式算法与智能算法的排样密度相比平均高5%左右，说明在排样局面较为简单的情况，启发式排样不但速度快，排样密度也较高。

5结语

本文提出了一种基于GNFP与边适应度的启发式排样算法——GEFHNA。利用ESICUP提供的基准测试算例，GEFHNA算法在与智能算法及商业软件的对比中均取得了较为满意的结果。限于启发式算法对规则的依赖，面对较为复杂的排样局面，GEFHNA在排样密度方面与智能算法相比效果有待提高。另外，虽然增加了剩余原材料的处理，但从测试结果看个别案例提升效果不明显，下一步将结合A*算法的思想，考虑样件的形状特征，减小排放一个样件后再排后续样件可能产生缝隙的大小。

参考文献：

[1]

DYCKHOFF H. A typology of cutting and packing problems [J]. European Journal of Operational Research， 1990， 44（2）： 145-159.

[2]

LPEZCAMACHO E， OCHOA G， TERASHIMAMARN H， et al. An effective heuristic for the twodimensional irregular bin packing problem [J]. Annals of Operations Research， 2013， 206（1）： 241-264.

[3]

BAKER B S， COFFMAN E G， RIVEST R L. Orthogonal packings in two dimensions [J]. SIAM Journal on Computing， 1980， 9（4）： 846-855.

[4]

ALLEN S D， BURKE E K， KENDALL G. A hybrid placement strategy for the threedimensional strip packing problem [J]. European Journal of Operational Research， 2011， 209（3）： 219-227.

[5]

LIU D Q， TENG H F. An improved BLalgorithm for genetic algorithm of the orthogonal packing of rectangles [J]. European Journal of Operational Research， 1999， 112（2）： 413-420.

[6]

HOPPER E， TURTON B C H. An empirical investigation of metaheuristic and heuristic algorithms for a 2D packing problem [J]. European Journal of Operational Research， 2001， 128（1）： 34-57.

[7]

UDAY A， GOODMAN E D， DEBNATH A A. Nesting of irregular shapes using feature matching and parallel genetic algorithms [C]// GECCO 2011： Proceedings of the 12th Annual Conference Companion on Genetic and Evolutionary Computation. New York： ACM， 2001： 429-434.

[8]

ALBANO A， SAPUPPO G. Optimal allocation of twodimensional irregular shapes using heuristic search methods [J]. IEEE Transactions on Systems， Man and Cybernetics， 1980， 10（5）： 242-248.

[9]

DOWSLAND K A， VAID S， DOWSLAND W B. An algorithm for polygon placement using a bottomleft strategy [J]. European Journal of Operational Research， 2002， 141（2）： 371-381.

[10]

刘胡瑶.基于临界多边形的二维排样算法研究[D].上海：上海交通大学，2007：65-81.（LIU H Y， Research of two dimensional nesting algorithm based on no fit polygon [D]. Shanghai： Shanghai Jiao Tong University， 2007：65-81.）

[11]

LAMBERT M， MARIAM T， SUSAN F. Weiler—Atherton Clipping Algorithm [M]. Beau Bassin： Betascript Publishing， 2010：35-61.

[12]

OLIVEIRA J F， GOMES A M， FERREIRA J S. TOPOS–a new constructive algorithm for nesting problems [J]. ORSpektrum， 2000， 22（2）： 263-284.

[13]

ESICUP. EURO Special Interest Group on Cutting and Packing [EB/OL].[20151224]. http：//paginas.fe.up.pt/～esicup/tikiindex.php.打不开

[14]

刘虓.基于HAPE的二维不规则零件排样算法及其性能研究[D].广州：华南理工大学，2011：52-63.（LIU X. Twodimensional irregular packing algorithm based on HAPE and its performance study [D]. Guangzhou： South China University of Technology， 2011： 52-63.）

[15]

孫艳丰.基于遗传算法和禁忌搜索算法的混合策略及其应用[J].北京工业大学学报，2006，32（3）：258-262.（SUN Y F， A hybrid strategy based on genetic algorithm and tabu search[J]，Journal of Beijing University of Technology ， 2006， 32（3）： 258-262.）