基于匀质块五块模式的矩形件非剪切排样算法

引用本文 [复制中英文]

张瑞友, 潘卫平, 刘士新. 基于匀质块五块模式的矩形件非剪切排样算法[J]. 东北大学学报:自然科学版, 2018, 39(6): 771-775.

ZHANG Rui-you, PAN Wei-ping, LIU Shi-xin. Non-guillotine Cutting Algorithm of Rectangular Items Based on Five-Homogeneous-Block Mode[J]. Journal of Northeastern University Nature Science, 2018, 39(6): 771-775. DOI: 10.12068/j.issn.1005-3026.2018.06.003.

[复制英文]

基金项目

国家自然科学基金资助项目(71471034, 61573089, 71571037)；中央高校基本科研业务费专项资金资助项目(N160404011)

作者简介

张瑞友(1979-)，男，辽宁朝阳人，东北大学副教授，博士生导师;
刘士新(1968-)，男，辽宁调兵山人，东北大学教授，博士生导师。

文章历史

收稿日期：2017-02-20

Contents Abstract Full text Figures/Tables PDF

基于匀质块五块模式的矩形件非剪切排样算法

张瑞友, 潘卫平, 刘士新

东北大学信息科学与工程学院, 辽宁沈阳 110819

收稿日期：2017-02-20

基金项目：国家自然科学基金资助项目(71471034, 61573089, 71571037)；中央高校基本科研业务费专项资金资助项目(N160404011)。

作者简介：张瑞友(1979-)，男，辽宁朝阳人，东北大学副教授，博士生导师;
刘士新(1968-)，男，辽宁调兵山人，东北大学教授，博士生导师。

摘要：基于匀质块五块排样模式对一类矩形件非剪切排样问题进行了研究.基于动态规划和隐枚举的思想设计了无约束矩形件非剪切排样问题的匀质块五块排样算法.与文献中的矩形件非剪切排样算法的对比试验表明:这种算法能够快速给出问题的最优解, 而且可以降低板材切割工艺难度并减少矩形件的分拣成本.与2种矩形件剪切排样算法的对比进一步表明了引入“非剪切”的经济效益.

关键词：非剪切排样问题五块模式动态规划算法隐枚举

Non-guillotine Cutting Algorithm of Rectangular Items Based on Five-Homogeneous-Block Mode

ZHANG Rui-you, PAN Wei-ping, LIU Shi-xin

School of Information Science & Engineering, Northeastern University, Shenyang 110819, China

Corresponding author: PAN Wei-ping, E-mail: panweipingv@163.com

Abstract: A type of non-guillotine cutting problem of rectangular items was studied based on the use of five-homogeneous-block mode. According to the idea of dynamic programming and implicit enumeration, a five-homogeneous-block cutting algorithm for an unconstrained non-guillotine cutting problem was designed. The comparative experiments with existing non-guillotine cutting algorithms indicated that optimal solutions of the problem could be quickly given by this algorithm, and both the difficulty of plate cutting process and the sorting cost of rectangular items could be reduced. Furthermore, comparisons with another experiment with two guillotine cutting algorithms show the benefits of "non-guillotine".

Key Words: non-guillotine cutting problem five-block mode dynamic programming algorithm implicit enumeration

矩形件二维排样问题, 又称二维背包问题或二维托盘装载问题, 在Waescher等^[1]的排样装填问题分类中属于二维矩形单一容器装填布局问题.此问题在理论上属于NP难问题, 在工业和物流业中有着广泛的应用.

矩形件二维排样问题可以描述为:给定一个尺寸为L⊗W(L和W分别为长和宽)的大矩形(即板材)和m种不同尺寸的小矩形(即矩形件), 其中第i(i=1, …, m)种矩形件的尺寸为l_i⊗w_i, 价值为v_i, 本文假定板材的尺寸和矩形件的尺寸均为正整数; 问题的目标为寻找一个排样方式使得排样价值即板材中排放的矩形件总价值最大化.

二维排样问题可具体细分为4种情形^[2-4]:有约束剪切排样、有约束非剪切排样、无约束剪切排样和无约束非剪切排样.非剪切排样的应用场景主要包括采用等离子体、激光、火焰切割板材, 以及物流业中的集装箱装载布局等.

学术界对无约束剪切排样问题进行了研究.例如, Beasley^[5]基于递归的思想提出了剪切排样问题的一种精确算法; Cui等^[6]提出了一种两阶段动态规划算法, 与线性规划相结合能够较好地解决二维下料问题; 杨传民等^[7]利用整数规划提出了四块排样方式的一种启发式算法; 潘卫平等^[8]提出了一种匀质条带三块排样方式背包算法, 其生成的排样方式切割工艺简单, 材料利用率高.然而, 针对无约束非剪切排样问题的研究还不多.Fekete等^[9]构造了一个与或图, 通过搜索图确定最优排样方式; Egeblad等^[10]建立了该问题的一个整数规划模型, 并基于序列偶的概念构造了一个模拟退火算法.Birgin等^[11]通过扩展托盘装载问题, 提出了无约束非剪切排样问题的递归划分求解算法.上述3种文献算法生成的排样方式结构比较复杂, 不利于实际下料的切割工艺.易向阳等^[12]提出了一种切割工艺简单的基于五块模式的排样算法.但是该算法只能处理单种矩形件排样问题, 无法处理多种矩形件套裁排样问题.

因此, 本文提出矩形件无约束非剪切排样问题的匀质块五块排样算法, 并通过基准案例验证了算法的有效性.本文算法是文献[12]算法的扩展.文献[12]算法是本文算法在只有一种矩形件时的特殊情形.本文算法既能求解单一矩形件排样问题又能求解多矩形件套裁排样问题, 能够作为一个独立模块嵌入多矩形件套裁下料问题.

1 匀质块五块排样方式 1.1 匀质块

匀质块由同种矩形件按规范多级方式排列组成, 条带由一行(列)矩形件组成.匀质块具有条带“块”的结构, 每次可切下一根水平条带或竖直条带.图 1给出了匀质块的一个例子, 其中条带按照切割的先后顺序进行编号, 每个块中包含方向和长度均相同的条带.图 1中有3个块共8根条带, 其中块1~3中分别包含1根竖直条带(条带1)、2根水平条带(条带2，3)和5根竖直条带(条带4~8).

图 1 匀质块例图 Fig.1 An example of homogeneous block

在排样优化问题的求解中, 通常使用规范尺寸以降低算法的时间复杂度.由于匀质块中只排放一种矩形件, 匀质块的规范尺寸与其中所排放的矩形件的尺寸紧密关联.当匀质块中排放第i(i=1, …, m)种矩形件时, 其规范尺寸为

(1)

其中n₁和n₂为非负整数, 且a_i≤max(L, W).对于m种矩形件, 匀质块所有可能规范尺寸组成的规范尺寸集合为A={a|a=a_i, i=1, …, m}.规范尺寸具有如下性质:假设A(x)为小于等于x的最大规范尺寸, 则尺寸为x⊗y的匀质块与尺寸为A(x)⊗A(y)的匀质块最多能排放的矩形件个数相同.

1.2 匀质块排样

匀质块五块排样方式如图 2所示, 以一个四元组(x₁, x₂, y₁, y₂)对板材L⊗W进行划分, 其中0≤x₁≤x₂≤L，0≤y₁≤y₂≤W.该四元组将板材划分为5个矩形区域(每个区域排放一个匀质块), 其尺寸分别为L₁⊗W₁，L₂⊗W₂，L₃⊗W₃，L₄⊗W₄和L₅⊗W₅, 其中L₁=x₁, W₁=W－y₁, L₂=L－x₁, W₂=W－y₂, L₃=x₂－x₁, W₃=y₂－y₁, L₄=x₂, W₄=y₁, L₅=L－x₂, W₅=y₂.

图 2 五块方式的划分 Fig.2 Division of five blocks mode

2 匀质块五块排样算法 2.1 匀质块的价值

对于匀质块x⊗y, 其规范多级方式的形成过程实质是匀质块切割成条带的逆过程, 如图 3所示, 每次总是沿着当前方式的水平边或竖直边拼接上一根条带, 最终形成整个匀质块上的排样方式.

图 3 条带的两种拼接方式 Fig.3 Two kinds of splicing methods of strip (a)—水平拼接一根条带；(b)—竖直拼接一根条带.

称排放第i种矩形件的匀质块为第i种匀质块, 令F_i(x, y)为第i种匀质块x⊗y中所能排放矩形件的个数, 则有

(2)

其中⌊·⌋表示向下取整.令V(x, y)为最优匀质块的价值, 则有

(3)

求解匀质块价值的伪代码如下:

1 For i =1 to m

2 For x = 0 to L

3 For y = 0 to W

4 Let v1 = v2 = 0 and F_i(x, y)=0

5 If y≥w_i then let v1 = ⌊ x/l_i⌋+F_i(x, y－w_i)

6 If x≥l_i then let v2 =⌊ y/w_i⌋ +F_i(x－l_i, y)

7 Let F_i(x, y)=max(v1, v2) and Q_i(x, y)= (v1>v2)？1:2

8 For x = 0 to L

9 For y = 0 to W

10 For i = 1 to m

11 Let V(x, y)=0 and P(x, y)=0

12 If V(x, y) < F_i(x, y)×v_i then let V(x, y)=F_i(x, y)×v_i and P(x, y)=i

求解匀质块价值的伪代码中, 第7行表示按排放矩形件个数最多原则选择匀质块所拼接的条带的方向, Q_i(x, y)记录第i种匀质块x⊗y当前所拼接条带的方向, Q_i(x, y)=1表示拼接一根水平条带, Q_i(x, y)=2表示拼接一根竖直条带; 第12行P(x, y)按照排样价值最大原则记录最优匀质块x⊗y中排放的矩形件的编号.该程序可求解出所有可能尺寸的最优匀质块的排样方式及其排样价值, 算法时间复杂度为O(mLW).由P(x, y)的取值可以得到最优匀质块x⊗y中排放的矩形件的编号, 由Q_i(x, y)的取值可以逆推出最优匀质块中条带的拼接情况, 继而得到匀质块中矩形件的具体排放情况.

2.2 五块排样方式的价值

记五块排样方式的价值为V, 则有

(4)

式中x₁, y₁, x₂和y₂的取值属于规范尺寸集合A.用隐枚举算法计算式(4)的时间复杂度为O(|A|⁴), 其中|A|为集合A的元素个数.分析可知:若不采用规范尺寸, 则该算法时间复杂度为O(L²W²).因为|A|远远小于 , 所以采用规范尺寸可明显减低算法的时间复杂度.

2.3 算法的基本步骤

五块排样算法的步骤为

步骤1 输入板材尺寸L⊗W, 第i种矩形件的尺寸l_i⊗w_i和价值v_i, 其中i=1, …, m.

步骤2 由式(1)确定匀质块的规范尺寸集合A.

步骤3 按照图 4确定V(x, y)，P(x, y)和Q_i(x, y), 其中0≤x≤L, 0≤y≤W.

步骤4 按照式(4)确定最优五块排样方式的价值V及最优划分四元组(x₁, x₂, y₁, y₂), 得到各个块的尺寸L_i⊗W_i(i=1, 2, 3, 4, 5), 确定各个块中的矩形件编号P(L_i, W_i).由Q_{P_{(L_i, W_i)}}(x, y)(0≤x≤L_i，0≤y≤W_i)得到各个块中的矩形件的具体排放情况, 进而得到最优五块排样方式.

五块排样算法中, 步骤2确定匀质块规范尺寸集合的时间复杂度为O(max(L, W)m), 步骤3的时间复杂度为O(mLW), 步骤4隐式枚举所有可能的四元组的时间复杂度为O(|A|⁴).综上, 本文五块排样算法总的时间复杂度为O(max(L, W)m+mLW+|A|⁴).

3 实验与分析

实验采用英特尔酷睿i7-2600 3.40GHz处理器、4GB内存的个人计算机, 软件平台为微软VS 2012.

3.1 与现有无约束非剪切排样算法的对比

基于文献[9]中的13道测试题(gcut1-gcut13), 与文献[9]的两层树搜索算法、文献[10]的模拟退火算法和文献[11]的算法进行对比.其中, 文献[12]中矩形件的方向固定, 文献[10-11]及本文的算法中允许矩形件转向90度排放.表 1列出了与3种现有算法的对比结果, 其中的排样价值提高=(本文算法排样价值-文献算法排样价值)/文献算法排样价值×100%(下同).

表 1 与文献[9-11]的对比 Table 1 Comparison with literature [9-11]

题号	本文		文献[9]			文献[10]			文献[11]
题号	时间 s	排样价值	时间 s	排样价值	提高 %	时间 s	排样价值	提高 %	时间 s	排样价值	提高 %
gcut1	0.002	58136	0.018	48368	20.20	0.010	58136	0.00	2.921	58480	-0.59
gcut2	0.005	61040	0.221	59798	2.08	0.070	60656	0.63	3.015	61146	-0.17
gcut3	0.007	61890	2.637	61275	1.00	0.340	61275	1.00	6.329	61275	1.00
gcut4	0.006	62265	116.328	61380	1.44	5.620	61710	0.90	21.524	61918	0.56
gcut5	0.006	246000	0.019	195582	25.78	0.020	233969	5.14	2.963	246000	0.00
gcut6	0.008	240951	0.161	236305	1.97	0.380	239467	0.62	2.417	243598	-1.09
gcut7	0.009	245866	0.993	240143	2.38	0.240	245306	0.23	2.719	244306	0.64
gcut8	0.026	248832	40.257	245758	1.25	3.540	247462	0.55	36.921	247815	0.41
gcut9	0.007	971100	0.013	939600	3.35	0.010	953293	1.87	2.172	971100	0.00
gcut10	0.011	982025	0.424	937349	4.77	0.170	938036	4.69	2.361	982025	0.00
gcut11	0.063	984448	1.905	969709	1.52	0.120	979580	0.50	4.639	980096	0.44
gcut12	0.092	988694	0.125	979521	0.94	0.010	987674	0.10	20.269	979986	0.89
gcut13	2.691	9000000	280.247	8669457	3.81	64.231	8897979	1.15	34.908	8997780	0.02
平均值	0.226	1088557	34.104	1049557	5.42	5.751	1074196	1.34	11.012	1087348	0.16

表 1 与文献[9-11]的对比 Table 1 Comparison with literature [9-11]

可见, 本文算法给出的13道题的目标值均优于文献[9]的算法, 排样价值平均提高5.42%, 其中一个原因是文献[9]不允许矩形件转向.与文献[10]相比, 本文算法给出的12道题的目标值有所改善, 排样价值平均提高1.34%, 剩余1道题的目标值与文献相同.13道题中, 本文算法的目标值优于、等于、差于文献[11]的测试题数量分别为7, 3和3, 排样价值平均提高0.16%.对于所有13道题, 本文算法的计算时间均明显短于3篇对比文献, 而且计算时间更加稳定, 其中文献[9-11]算法13道题的计算时间标准偏差分别为80.92, 17.65和12.88s, 而本文算法的标准偏差仅为0.74s.

文献[9]前12道测试题中矩形件的平均个数为4.75, 第13道测试题矩形件平均个数未知; 文献[10]未报道排样结果中的矩形件个数; 文献[11]中矩形件的平均个数为3.23.而本文排样结果中矩形件平均个数为2.69, 明显低于文献中报道的数据.因此, 本文所提出的这种方法可降低板材切割工艺难度并减少矩形件的分拣成本.

3.2 与两种剪切排样算法的对比

首先基于文献[6]的20道测试题与文献[6]的两阶段算法进行对比, 其中前10道测试题为文献[6]中第3组的P1~P10, 记为G3-1~G3-10, 板材的长宽均为500;后10道测试题为文献[6]中第4组的P1~P10, 记为G4-1~G4-10, 板材的长宽均为1000.进而基于文献[8]的20道测试题(APT10~APT29)与文献[8]的匀质条带三块算法进行对比.因为上述算法均为确定性算法, 所以只要算法正常执行完毕, 目标值不依赖于计算时间.比较结果见表 2.

表 2 与文献[6]的对比 Table 2 Comparison with literature [6]

题号	本文		文献[6]
题号	时间/s	排样价值	时间/s	排样价值	提高/%
G3-1	0.013	246925	0.003	244756	0.89
G3-2	0.011	245063	0.004	241418	1.51
G3-3	0.016	244822	0.003	241356	1.44
G3-4	0.018	246750	0.002	241090	2.35
G3-5	0.015	246840	0.004	242448	1.81
G3-6	0.016	246800	0.003	242330	1.84
G3-7	0.012	247839	0.005	244428	1.40
G3-8	0.014	247166	0.003	245316	0.75
G3-9	0.015	245984	0.004	241778	1.74
G3-10	0.012	244212	0.002	241402	1.16
G4-1	0.013	982370	0.009	982167	0.02
G4-2	0.026	980802	0.011	956916	2.50
G4-3	0.011	987664	0.008	975456	1.25
G4-4	0.096	986144	0.007	981039	0.52
G4-5	0.011	982208	0.009	963078	1.99
G4-6	0.010	972688	0.009	962454	1.06
G4-7	0.017	980980	0.008	976000	0.51
G4-8	0.012	986992	0.010	979642	0.75
G4-9	0.015	991616	0.011	981105	1.07
G4-10	0.011	982966	0.009	982966	0.00
平均值	0.018	614841	0.006	608357	1.07

表 2 与文献[6]的对比 Table 2 Comparison with literature [6]

由表 2可知, 利用本文算法求解文献[6]算例的平均时间为0.018s, 虽稍长于文献[6]的算法, 但实际应用中可以接受; 类似地, 利用本文算法求解文献[8]算例的时间与文献[8]的算法接近, 平均为0.028s.与文献[6]相比, 本文算法的排样价值平均提高1.07%, 20道题中有19道题排样价值高于文献[6], 剩余1道题排样价值与文献[6]相同.类似地, 与文献[8]相比, 本文算法的排样价值平均提高0.63%, 20道题中有17道题排样价值高于文献[8], 剩余3道题排样价值与文献[8]相同.上述排样价值的提高是引入非剪切排样的结果.

4 结语

本文基于匀质块五块排样模式对一类无约束矩形件非剪切排样问题进行研究.这种排样模式中一张板材最多被切割成5个匀质块, 这有利于下料过程中板材的切割和矩形件的分拣.构造了基于动态规划和隐枚举思想的五块排样算法, 这种算法为低阶多项式时间算法, 计算时间能够满足工程实践的需要.与文献中的现有非剪切排样算法的对比实验表明:这种算法能够稳定地在更短的时间内给出问题的最优解.与文献中的2种剪切排样算法的对比试验进一步验证了引入“非剪切”的效益.本文算法能够为企业开发二维下料软件提供一定的参考.

参考文献

[1]	Wäscher G, Hauner H, Schumann H. An improved typology of cutting and packing problems[J]. European Journal of Operational Research, 2007, 183(3): 1109–1130. DOI:10.1016/j.ejor.2005.12.047
[2]	Cintra G F, Miyazawa F K, Wakabayashi Y, et al. Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation[J]. European Journal of Operational Research, 2008, 191(1): 61–85. DOI:10.1016/j.ejor.2007.08.007
[3]	Cui Y P, Cui Y, Tang T. Sequential heuristic for the two-dimensional bin-packing problem[J]. European Journal of Operational Research, 2015, 240(1): 43–53. DOI:10.1016/j.ejor.2014.06.032
[4]	Lodi A, Monaci M, Pietrobuoni E. Partial enumeration algorithms for two-dimensional bin packing problem with guillotine constraints[J]. Discrete Applied Mathematics, 2017, 217: 40–47. DOI:10.1016/j.dam.2015.09.012
[5]	Beasley J E. Algorithms for unconstrained two-dimensional guillotine cutting[J]. Journal of the Operational Research Society, 1985, 36(4): 297–306. DOI:10.1057/jors.1985.51
[6]	Cui Y, He D, Song X. Generating optimal two-section cutting patterns for rectangular blanks[J]. Computers & Operations Research, 2006, 33(6): 1505–1520.
[7]	杨传民, 王树人, 王心宇. 基于4块结构的斩断切割布局启发性算法[J]. 机械设计, 2007, 24(2): 25–26. ( Yang Chuan-min, Wang Shu-ren, Wang Xin-yu. Heuristic algorithm on layout of chopped cutting based on 4 pieces of structure[J]. Journal of Machine Design, 2007, 24(2): 25–26. )
[8]	潘卫平, 陈秋莲, 崔耀东, 等. 基于匀质条带的矩形件最优三块布局算法[J]. 图学学报, 2015, 36(1): 7–11. ( Pan Wei-ping, Chen Qiu-lian, Cui Yao-dong, et al. An algorithm for generating optimal homogeneous strips three block patterns of rectangular blanks[J]. Journal of Graphics, 2015, 36(1): 7–11. )
[9]	Fekete S P, Schepers J, Van der Veen J C. An exact algorithm for higher-dimensional orthogonal packing[J]. Operations Research, 2007, 55(3): 569–587. DOI:10.1287/opre.1060.0369
[10]	Egeblad J, Pisinger D. Heuristic approaches for the two-and three-dimensional knapsack packing problem[J]. Computers & Operations Research, 2009, 36(4): 1026–1049.
[11]	Birgin E G, Morabito R. Generating unconstrained two-dimensional non-guillotine cutting patterns by a recursive partitioning algorithm[J]. Journal of the Operational Research Society, 2012, 63(2): 183–200. DOI:10.1057/jors.2011.6
[12]	易向阳, 潘卫平, 张俊晖. 基于五块模式的单一矩形件排样算法[J]. 图学学报, 2015, 36(4): 521–525. ( Yi Xiang-yang, Pan Wei-ping, Zhang Jun-hui. Algorithm for generating five block mode cutting patterns of single rectangular items[J]. Journal of Graphics, 2015, 36(4): 521–525. )