, 刘士新东北大学 信息科学与工程学院, 辽宁 沈阳 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-xinSchool 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 problemfive-block modedynamic programming algorithmimplicit enumeration
矩形件二维排样问题, 又称二维背包问题或二维托盘装载问题, 在Waescher等[1]的排样装填问题分类中属于二维矩形单一容器装填布局问题.此问题在理论上属于NP难问题, 在工业和物流业中有着广泛的应用.
矩形件二维排样问题可以描述为:给定一个尺寸为L?W(L和W分别为长和宽)的大矩形(即板材)和m种不同尺寸的小矩形(即矩形件), 其中第i(i=1, …, m)种矩形件的尺寸为li?wi, 价值为vi, 本文假定板材的尺寸和矩形件的尺寸均为正整数; 问题的目标为寻找一个排样方式使得排样价值即板材中排放的矩形件总价值最大化.
二维排样问题可具体细分为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)
 | 图 1 匀质块例图Fig.1 An example of homogeneous block |
在排样优化问题的求解中, 通常使用规范尺寸以降低算法的时间复杂度.由于匀质块中只排放一种矩形件, 匀质块的规范尺寸与其中所排放的矩形件的尺寸紧密关联.当匀质块中排放第i(i=1, …, m)种矩形件时, 其规范尺寸为
 | (1) |
1.2 匀质块排样匀质块五块排样方式如图 2所示, 以一个四元组(x1, x2, y1, y2)对板材L?W进行划分, 其中0≤x1≤x2≤L，0≤y1≤y2≤W.该四元组将板材划分为5个矩形区域(每个区域排放一个匀质块), 其尺寸分别为L1?W1，L2?W2，L3?W3，L4?W4和L5?W5, 其中L1=x1, W1=W－y1, L2=L－x1, W2=W－y2, L3=x2－x1, W3=y2－y1, L4=x2, W4=y1, L5=L－x2, W5=y2.
图 2(Fig. 2)
 | 图 2 五块方式的划分Fig.2 Division of five blocks mode |
2 匀质块五块排样算法2.1 匀质块的价值对于匀质块x?y, 其规范多级方式的形成过程实质是匀质块切割成条带的逆过程, 如图 3所示, 每次总是沿着当前方式的水平边或竖直边拼接上一根条带, 最终形成整个匀质块上的排样方式.
图 3(Fig. 3)
 | 图 3 条带的两种拼接方式Fig.3 Two kinds of splicing methods of strip (a)—水平拼接一根条带；(b)—竖直拼接一根条带. |
称排放第i种矩形件的匀质块为第i种匀质块, 令Fi(x, y)为第i种匀质块x?y中所能排放矩形件的个数, 则有
 | (2) |
 | (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 Fi(x, y)=0
5 ?????? If y≥wi then let v1 = ? x/li?+Fi(x, y－wi)
6 ?????? If x≥li then let v2 =? y/wi? +Fi(x－li, y)
7 ?????? Let Fi(x, y)=max(v1, v2) and Qi(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) < Fi(x, y)×vi then let V(x, y)=Fi(x, y)×vi and P(x, y)=i
求解匀质块价值的伪代码中, 第7行表示按排放矩形件个数最多原则选择匀质块所拼接的条带的方向, Qi(x, y)记录第i种匀质块x?y当前所拼接条带的方向, Qi(x, y)=1表示拼接一根水平条带, Qi(x, y)=2表示拼接一根竖直条带; 第12行P(x, y)按照排样价值最大原则记录最优匀质块x?y中排放的矩形件的编号.该程序可求解出所有可能尺寸的最优匀质块的排样方式及其排样价值, 算法时间复杂度为O(mLW).由P(x, y)的取值可以得到最优匀质块x?y中排放的矩形件的编号, 由Qi(x, y)的取值可以逆推出最优匀质块中条带的拼接情况, 继而得到匀质块中矩形件的具体排放情况.
2.2 五块排样方式的价值记五块排样方式的价值为V, 则有
 | (4) |
2.3 算法的基本步骤五块排样算法的步骤为
步骤1 ??输入板材尺寸L?W, 第i种矩形件的尺寸li?wi和价值vi, 其中i=1, …, m.
步骤2??由式(1)确定匀质块的规范尺寸集合A.
步骤3??按照图 4确定V(x, y)，P(x, y)和Qi(x, y), 其中0≤x≤L, 0≤y≤W.
步骤4??按照式(4)确定最优五块排样方式的价值V及最优划分四元组(x1, x2, y1, y2), 得到各个块的尺寸Li?Wi(i=1, 2, 3, 4, 5), 确定各个块中的矩形件编号P(Li, Wi).由QP(Li, Wi)(x, y)(0≤x≤Li，0≤y≤Wi)得到各个块中的矩形件的具体排放情况, 进而得到最优五块排样方式.
五块排样算法中, 步骤2确定匀质块规范尺寸集合的时间复杂度为O(max(L, W)m), 步骤3的时间复杂度为O(mLW), 步骤4隐式枚举所有可能的四元组的时间复杂度为O(|A|4).综上, 本文五块排样算法总的时间复杂度为O(max(L, W)m+mLW+|A|4).
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(Table 1)
 表 1 与文献[9-11]的对比Table 1 Comparison with literature [9-11]
| 表 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(Table 2)
表 2 与文献[6]的对比Table 2 Comparison with literature [6]
| 表 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.) |
