基于宽容分层策略的启发式排样算法

梁利东,贾文友

0 引言

Packing问题的排样优化方法是工程设计及制造领域中的研究热点,广泛应用于机械制造、印刷业排版、木材加工、玻璃切割、家具下料、服装裁剪等行业中,高效排样算法的研究对提高生产效率和经济效益具有重要的实际意义。二维(2D) Packing问题是寻找平面最优布局的优化问题,即将一系列零件不可相互重叠地合理布置在原材料中,使原材料的利用率达到最大。作为组合优化领域中计算复杂性最高的一类非确定性多项式完全(Nondeterministic Polynomial Complete, NPC)问题[1],排样方法涉及计算机科学及数值优化理论的核心问题,因此具有深刻的理论研究价值。

通常的优化排样问题(以矩形件为例)的数学模型可表示为:

(1)

s.t.Pi(Δxi,Δyi)∩Pj(Δxj,Δyj)=∅,i≠j

(2)

0≤xim(θi,Δxi,Δyi)≤L,m=1,2,…,ni

(3)

0≤yim(θi,Δxi,Δyi)≤W,m=1,2,…,ni

(4)

其中：ti为参与排样因子,表示零件i是否参与排样,取值为1或0;xim和yim为零件i上第m个顶点的坐标。约束式(2)表示零件与互不重叠,约束式(3)～(4)表示所有零件不能排在原材料之外。由于面积Si是一个与位置无关的参数,因此上面的优化排样模型中,其决策变量为θi、Δxi、Δyi、ti。

排样问题的求解包括排序方法和定位规则两个方面,目前研究的算法主要分为三类:精确算法、启发式算法和元启发式算法(meta-heurisic methods)。精确算法如树搜索、分枝定界法等[2-3],算法的计算复杂度太高、耗时较大,对于排样规模也有局限;而启发式算法源于数值计算理论的有效性,可在合理的时间范围内获得近似较好的解而得到广泛运用,典型的启发式定位算法如表1所示。

随着智能优化算法,如模拟退火算法(Simulated Annealing, SA)、遗传算法(Genetic Algorithm, GA)、人工神经网络(Artificial Neural Network, ANN)、粒子群优化(Particle Swarm Optimization, PSO)及蚁群优化(Ant Colony Optimization, ACO)算法等方法的日益成熟,元启发式算法则是利用智能算法实现排样次序的优化,并结合基本启发式算法来求解Packing问题。如Jiang等[16]结合遗传算法提出了GA+底部左齐择优匹配(Lowest-Level Left Align Best Fit, LLABF)算法，Liu等[17]提出了GA+IBL(Improved Bottom Left)算法,二者都是在BL算法的基础上对其进行改进;基于最小浪费的思想,Zhang等[18]提出了GA+IHR(Improved Heuristic Recursive)算法;Hopper等[19]将BLF与GA和SA等智能算法相结合,提出了GA+BLF、SA+BLF等算法,也都是基于BL算法所进行的优化;基于BF(Best Fit)的思想,Burke等[20]分别结合禁忌搜索(Tabu Search, TS)、SA和GA算法,实现并比较了BF+TS、BF+SA和BF+GA这三种算法的性能,取得了比BF算法更好的结果,同时发现,BF+SA可以取得最好的效果;Borfeldt[21]结合遗传算法给出了基于层的该问题的SPGAL(Strip Packing Genetic Algorithm based on Layer)。

表1 启发式排样算法

上述启发式算法在求解矩形件Packing问题中大都取得不错的结果,特别是LSBF算法[15]和LLABF算法[16]均采用了择优匹配的定位方法,并通过枚举建立矩形匹配的适应度评价值,获得部分Benchmark的完美排样。但两种算法的匹配优先原则都侧重于完全匹配(Full Fit, FF)和部分匹配类型,如宽度匹配(Width Fit, WF)、高度匹配(Height Fit, HF)和组合匹配(Joint Fit,JF),而对于可能出现的多种可排入匹配(Placeable Fit, PF)的一般情形,由于缺乏排入匹配的评价机制,对全局排样布局将产生不同的影响。文献[10]的砌墙启发式算法中通过设定绝对基准砖高度来约束每层的排样空间,可有效控制最低排样高度,但该算法与择优匹配思想存在一定矛盾。

综合以上算法的优劣,本文基于多目标宽容分层规划思想,提出一种宽容分层的启发式算法(Forbearing Stratified Heuristic Algorithm, FSHA),该算法构造择优匹配优化模型及评价函数,以此来设计排放矩形的优先规则,并针对一般排放情况,引入宽容参数,实现矩形定位的优化过程。

1 FSHA模型

1.1 问题的描述及定义

Packing问题的最优求解是寻求诸多几何体在不能重叠和超出边界的约束下在给定板材区域中的最优图形组合,以获得最小排样高度或最大排样密度。在矩形排样中,假设初始板材区域宽度为W,高度为H,待排n个矩形表示为pj(xj,yj,wj,hj),j∈{1,2,…,n}。其中:(xj,yj)表示pj的左下角坐标;(wj,hj)表示的宽度和高度。建立笛卡儿坐标系,相关定义如下:

1)排样空间。表示当前m个空闲矩形区域,可表示为Si(sxi,syi,swi,shli,shri),i∈{1,2,…,m},其中(sxi,syi)为该空间左下角坐标,swi为该空间的宽度,(shli,shri)分别表示该空间左壁和右壁的高度。若空间左壁(或右壁)为板材边界,则shli=H或shri=H,如图1所示。

2)可行空间。若存在待排矩形,使得wj≤swi,则该空间为可行空间；否则为不可行空间。

3)合并空间。当存在不可行空间,该空间则与相邻空间进行合并产生新的空间。

图1 排样空间的定义

排样矩形与排样空间建立参数匹配关系,并以此设计矩形放置规则,定义如下:

1)宽度匹配值fwij，表征可行空间Si的宽度与排入矩形pj的宽度的匹配程度,其中当swi=wj时,宽度匹配最佳。计算公式如下:

(5)

2)高度匹配值fhij表征可行空间的高度与排入矩形高度的匹配程度,其中,当Δhlij=0(左平齐)或Δhrij=0(右平齐),则fhij=1,高度匹配为最佳。计算公式如下:

(6)

基于以上排样空间的划分及匹配值的定义,选定最低排样空间,遍历所有待排矩形与该空间进行匹配排放。图2为不同的匹配类型,基本涵盖了待排矩形的全部可排放情景,其中假设shr≤shl;反之情况类似。

图2 不同匹配值

1.2 匹配函数模型及适应度

当前矩形的匹配择优过程可视为宽度匹配值和高度匹配值最大化的多目标优化问题,优化函数的数学模型表示如下:

V-maxFij=max [fwij,fhij]

(7)

s.twj≤swi

hj≤H

从图2的4种匹配类型中,只有完全匹配为多目标目标函数的当前最优解,其他匹配情形均无法获得最优,因此可根据不同匹配情况,设计其目标函数(或称匹配适应度)的计算方法及排放规则:

1)完全匹配。待排矩形的宽度等于可排空间宽度即fwij=1,且高度等于可排空间高度(包括左高平或右高平)即fhij=1。匹配适应度值Fij=fwij+fhij=2,为最佳匹配。若存在多个完全匹配情形时,矩形高度hj小者优先入排。

2)部分匹配。只满足宽度匹配或高度匹配即fwij=1,fhij<1或fwij<1,fhij=1,匹配适应度值Fij=max(fwij,fhij)=1,排入规则:

① 若多个矩形同时符合宽度匹配或高度匹配,以入排次序进行排放;

② 若多个矩形仅符合宽度匹配,矩形hj小者优先入排;

③ 若多个矩形仅符合高度匹配时,矩形宽度小者优先且向高度平齐一方靠接排放。

3)可排入匹配。待排矩形的宽度小于可排空间宽度即fwij<1,且高度与可排空间高度不相等即fhij<1,匹配适应度值为Fij=c1fwij+c2fhij,其中c1、c2(c1,c2∈(0,0.5])分别为宽度和高度宽容值,即当存在多个矩形同时满足可排入匹配时,两个宽容值决定宽度和高度匹配的选择权重(在起始阶段,初始空间通常对于所有矩形均为可排入匹配,且H视为无限高,第一个入排矩形的选择根据排放序列确定)。设置宽容值旨在对两个匹配分目标的实现分层优化策略。注意:当排样空间左(或右)边为板材边界时,则采用占角规则[14]。

可见,最优化匹配适应度函数取决于排样空间三个匹配参数的关系,即:Δw为排样区域宽度与入排矩形宽度的绝对差值;Δhl为排样区域的左边(壁)高度与入排矩形高度的绝对差值;Δhr为排样区域的左边(壁)高度与入排矩形高度的绝对差值。表2给出匹配适应度及参数关系说明。

表2 匹配适应度评价及参数说明

注:匹配类型可通过矩形旋转实现择优匹配。

2 FSHA流程

FSHA是依据匹配适应度值和择优匹配优先原则实现分层定位布局的启发式算法,其算法设计如下。

输入 板材的宽度W和高度H(无限高),n个待排矩形pj(xj,yj,wj,hj),j∈{1,2,…,n}。

输出 排样高度或排样密度,其中

FSHA()

{

for(j=1;j<=n;j++) initialize (RectList[]);

//初始化矩形入排序列

设置宽容参数c1,c2

for(i=0;i<可行排样空间数目,i++){

for(j=1;j<=n;j++) {

if (S(i)为不可行空间); break;

//选择下一个最低空间

Function_FitType(i,j)

//判断匹配类型

if (Δw=0, Δh=0,)Fij=2 break;

//完全匹配类型

Else if(Δw=0, Δh>0)Fij=1;

//宽度匹配类型

Select(min(hj));

//选择高度最低矩形

Else if(Δw>0, Δh=0)Fij=1;

//高度匹配类型

Select(min(wj));

//选择宽度最小矩形

Else if(Δw>0, Δh>0) {

可排入匹配类型,计算当前匹配适应度Fij

Select(max(Fij));

//选择适应度最大矩形

}

}

Pack(i,j); 在空间i排入矩形RectList[j]

更新排样空间S(i),并以空间最低原则排序

}

计算输出排样适应度(排样高度或排样密度)

}

基于以上算法的实现过程,FSHA的流程示意如图3所示。

图3 FSHA流程

3 FSHA应用举例

算例1 给定5个待排矩形,如不考虑旋转,可存在4种最优排样布局,其排样高度均为最优高度,排样密度达到100%,如图4所示。要获得一个最优布局(以图4(a)为例),对于序列模式{1,2,*,*,*} (“*”表示未列出的矩形编号),LLABF、LSBF及砌墙式算法得到排样布局都出现空洞现象,如图5所示。

图4 算例1的最优排样结果

图5 LLABF、LSBF及砌墙式算法的排样布局

采用FSHA匹配原理及评价方法,只要矩形1为第一个入排矩形,均可获得如图4(a)的最优排样布局,算法步骤如下:

1)初始化排样空间和参考位置原点,初始空间为S0(0,0,W,H)。

2)起始阶段,所有零件均属于可排入匹配情况,直接入排矩形1,选择最低空间S。

3)依照算法的匹配规则,矩形2为当前最低空间S唯一可排入矩形,且满足宽度匹配,F=1,宽度匹配不受排样高度约束,故排入2,更新最低空间S。

4)遍历未排矩形,矩形4和5都满足高度匹配,maxF=1,依据宽度小者优先和匹配边靠接原则,选择4排入。

5)依次类推,可依次排入矩形3和5,构成最佳排样布局,如图6所示。

可以看出, FSHA对于排序模式{2,*,*,*,*}、{5,*,*,*,*}、{3,*,*,*,*},也均可获得其他最优布局如图4(b)、(c)和(d)。

图6 算例1的排样过程

算例2 假设板材宽度W=100,高度H不限,取6个矩形,并任意给定各矩形的宽度和高度,矩形序列P可表示为{p1(42,30),p2(40,18),p3(40,26),p4(40,10),p5(16,44),p6(44,8)},如图7(a)所示。可以发现,无论怎样排放均无法获得理想的最优布局,此为大规模排样中常见的一般情形,因此,快速寻求较好的有效解是设计排样算法的关键。

以{1,*,*,*,*}排入模式为例(暂不考虑旋转),根据本文算法规则首先排入矩形1,确定最低空间S,由于不存在完全匹配和部分匹配,按照式(5)～(6)分别计算剩余待排矩形{p2,p3,p4,p5,p6}与S的匹配适应度,Fi=c1fwi+c2fhi。取c1=c2=0.5,可得:F2=0.644 8,F3=0.778 2,F4=0.511 5,F5=0.404 6,F6=0.512 6。若调整宽容参数为c1=0.5,c2=0,1,可得F2=0.404 8,F3=0.431 5,F4=0.378 1,F5=0.191 2,F6=0.406 0。可知maxF=F3,故选择矩形3排入。依次类推,排完所有待排矩形,可得到排放序列{1,3,5,2,6,4},排样高度Hpack=48,排样密度为93.25%,此为较好的有效解,如图7(g)所示。对于排入模式{1,2,3,4,5},LLABF和砌墙式算法,得到排样结果如图7(h)和(i)所示。若要获得更好解,还需进行排序优化。

4 GA+FSHA

FSHA的匹配规则虽对排序进行了局部优化,但随排样规模的增加仍依赖于矩形序列的全局寻优,本文采用遗传算法GA与FSHA结合方式来求解二维矩形条排样优化问题。由GA确定种群规模、编码方式并随机生成初始矩形集合的排序,利用FSHA决定矩形的排放规则,通过遗传操作和适应度评价来实现矩形排样的最优化过程。

4.1 编码及适应度函数

对于矩形Packing问题,通常采用序号编码方式进行编码设计,个体染色体序号编码可表示为Ek={1,2,…,n}。编码中序号对应入排零件,正负表示矩形旋转与否。例如编码{1,3,-2,4,-5},表示矩形排入顺序为13 245,其中矩形2和5需旋转90°。

设给定板材的规格尺寸(宽度W和高度H为定值),个体的适应度评价分两种情况:

1)如果所有待排矩形均可排入,优化目标为最低排样高度或最大排样密度,个体适应度函数表示为Fit=1/Hpack,其中Hpack为个体的矩形排样高度。

2)如果所有待排矩形不可能全部排入,根据匹配适应值和个体排序的不同,可导致即使同一块板材,多次排样结果所包含的零件数量和种类亦不相同。因此,排样目标为每个入排矩形匹配值求和的最大值,个体适应度函数如下表示:

(8)

4.2 遗传操作

1)选择运算。对种群中所有个体的适应度值从大到小排序,优选首位基因不同的m个最优个体(视种群规模而定)直接作为下一代个体,其余n-m个体以轮盘赌方式[18]进行选择。该选择方法是基于匹配定位规则的局部排序优化,实现个体的最优保存和种群多样性策略。

2)交叉运算。本文采用两点交叉,以一定的概率pc交换两个体的基因片断而产生新个体的过程。即在区间[1,n]内生成两个不等的随机数p和q作为交叉位,设p

3)变异运算。采用双变异方式,即按照变异概率pm对个体的排序和旋转进行操作。其中排序变异是对随机产出的两变异点(α1,α2)的矩形互换位置;旋转变异则是对变异点r的矩形旋转角度90°。如:选择个体为{1,2,3,4,5},变异点(α1,α2)=(3,5),r=4,经过变异操作后产生的新个体表示为{1,2,5,-4,3}。

5 实验与分析

本文开发环境为VB 6.0+SQL Server 2000,实验平台为Intel CPU 2.4 GHz, 4 GB RAM, Windows 10。设定种群规模为20,预设宽容系数c1=c2=0.5,交叉概率pc=0.8,变异概率pm=0.5。

实验1 对两组理想排样布局进行算法测试,其中一组以200×200的板材随机划分生成算例数据,如表3所示。另一组来自文献[19]的C1P1(Category1 Problem1)问题(W×H=20×20, 16 items),运用FSHA运行10次,均获得最优排样布局如图8所示。

表3 随机算例的测试数据

图8 实验1的最优排样布局

实验2 为验证算法的有效性,根据问题规模的不同,本文对benchmark的7类数据[19]分别进行测试,不同算法的实验对比结果如表4所示。

表4 算例的测试数据的 Gap 值 %

表4中:Gap表示为排样的相对高度,即Gap=(Hpack-H*)/H*,其中H*为理想高度。可以看出,本文算法对于小规模问题均可获得满意的最优解,随着问题规模的增加,相对于A1及LLABS算法,Gap的平均值降低了2%。注意:以上测试结果在FSHA求解中,是通过随机调整不同的宽容值c1和c2而获得的最优结果。实验发现,宽容系数c1和c2的不同取值对实验结果具有一定的影响:c1越大,宽度匹配越优先于高度匹配，反之亦然；其大小的选择往往随着排样问题和排样规模的不同而需测试调整。

实验3 针对不同矩形类型入排的一般情况,本文从benchmark的7类数据中随机选择两组数据进行测试,GA迭代次数为50,最优排样结果如图9所示。其中,一组数据取自C1P1+C3P1中的33个矩形,设置板材宽度为20,高度不限(水平方向),计算排样高度为24,排样密度为93.35%;另一组数据从C2～C7中任选66个矩形,设置板材宽度为100,高度不限,计算排样高度为339,排样密度为91.28%。

图9 实验3的最优排样布局

实验4 FSHA方法也可应用于异形件排样,数据取自某船舶零件,设置板材规格W*H=2 000*6 000。排样过程采用了异形件的矩形化包络和组合填充的预处理操作,在每个包络零件排入后再进行正交靠接。图10为不经过排序优化由初始序列一次得到排样结果,可排入65个零件,排样密度达到87.37%,其中排样密度为排入零件的面积之和与板材面积的比率。排样结果的板材利用率虽不算太高,但可以说明该算法在异形件排样过程中的有效性。基于异形零件图形的不规则特征,可结合相关不规则件排样算法进行研究探索。

图10 异形件的排样布局

6 结语

本文针对二维矩形Packing问题,提出了基于宽容分层规则及匹配函数评估的优化算法FSHA,并给出了算法的思想、模型，以及具体实现方法。实验结果表明,该算法的定位宽容分层匹配策略明确了不同匹配类型的划分和优先放置规则,可有效优化排样结果,并可结合碰靠算法应用于异形件packing问题的求解。由于宽容值的大小设定直接影响排样定位规则和最优布局,宽容参数的取值决定了宽度匹配和高度匹配的优先程度,如何将其与排放矩形和排样空间的图形属性建立关系,将是下一步研究的重点。

参考文献(References)

[1] LODI A, MARTELLO S, MONACI M. Two-dimensional packing problems: a survey[J]. European Journal of Operational Research, 2002, 141(2): 241-252.

[2] LESH N, MARKS J, MAHON A, et al. Exhaustive approaches to 2D-rectangular perfect packings[J]. Information Processing Letters, 2004, 90(1): 7-14.

[3] MARTELLO S, MONACI M, VIGO D. An exact approach to the strip-packing problem [J]. INFORMS Journal of Computing, 2003, 15(3): 310-319.

[4] BAKER B, COFFMAN E, RIVEST L. Orthogonal packings in two dimensions [J]. SIAM Journal on Computing, 1980, 9(4): 846-855.

[5] CHAZELLE B. The bottom left bin packing heuristic: an efficient implementation [J]. IEEE Transactions on Computers, 1983, C-32(8): 697-707.

[6] HOPPER E, TURTON B. An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem[J]. European Journal of Operational Research, 2001, 128(1): 34-57.

[7] LESH N, MITZENMACHER M. BubbleSearch: a simple heuristic for improving priority-based greedy algorithms [J]. Information rocessing Letters, 2006, 97(4): 161-169.

[8] BURKE E, KENDALL G, WHITWELL G. A new placement heuristic for the orthogonal stock-cutting problem[J]. Operations Research, 2004, 52(4): 655-671.

[9] BORTFELDT A, GEHRING H. New large benchmark instances for the two-dimensional strip-packing problem with rectangular pieces[C]// Proceedings of the 39th Hawaii International Conference on Systems Sciences. Washington, DC: IEEE Computer Society, 2006: 30.

[10] 张德富, 韩水华, 叶卫国.求解矩形Packing问题的砌墙式启发式算法[J]. 计算机学报, 2008, 31(3) : 509-515.(ZHANG D F, HAN S H, YE W G. A bricklaying heuristic algorithm for the orthogonal rectangular packing problem[J]. Chinese Journal of Computers, 2008, 31(3): 509-515.)

[11] 姚怡, 吴金波, 赖朝安. 采用分层搜索填充策略的启发式带排样算法[J]. 武汉大学学报(工学版), 2014, 47(6): 854-859.(YAO Y, WU J B, LAI C A. Heuristics for rectangular strip packing problem based on hierarchical search filled strategy[J]. Engineering Journal of Wuhan University, 2014, 47(6) : 854-859.)

[12] 何琨, 姬朋立. 求解二维矩形Packing面积最小化问题的动态规约算法[J]. 软件学报, 2013, 24(9): 2078-2087.(HE K, JI P L. Heuristics for solving the 2D rectangle packing area minimization problem basing on a dynamic reduction method[J]. Journal of Software, 2013, 24(9): 2078-2087.)

[13] HUANG W, CHEN D, XU R. A new heuristic algorithm for rectangle packing[J]. Computer & Operations Research, 2007, 34(11): 3270-3280.

[14] CHEN M, HUANG W. A two-level search algorithm for 2D rectangular packing problem[J]. Computer & Industrial Engineering, 2007, 53(1): 123-136.

[15] 张怀宇, 杨根科, 白杰. 二维Strip Packing问题的嵌套启发式算法[J]. 系统仿真学报, 2012, 24(8): 1601-1605, 1623.(ZHANG H Y, YANG G K, BAI J. Nested heuristic algorithm for two-dimensional strip packing problem[J]. Journal of System Simulation, 2012, 24(8) : 1601-1605, 1623.)

[16] JIANG X, LU X, LIU C. Lowest-level left align best-fit algorithm for the 2D rectangular strip packing problem[J]. Journal of Software, 2009, 20(6): 1528-1538.

[17] LIU D, TENG H. An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles[J]. European Journal of Operation Research, 2006, 172(3): 814-837.

[18] ZHANG D, CHEN S, LIU Y. An improved heuristic recursive strategy based on genetic algorithm for the strip rectangular packing problem[J]. Acta Automatica Sinica, 2007, 33(9): 911-916.

[19] HOPPER E, TURTON B. An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem[J]. European Journal of Operational Research, 2001, 128(1): 34-57.

[20] BURKE E, KENDALL G, WHITWELL G. Metaheuristic enhancements of the best-fit heuristic for the orthogonal stocking cutting problem: NOTTCS-TR-2006-3[R]. Nottingham: University of Nottingham, 2006.

[21] BORTFELDT A. A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces[J]. European Journal of Operational Research, 2006, 172(3): 814-837.

This work is partially supported by the National Natural Science Foundation of China (51576001).