ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac
Journal of Software, Vol.20, No.6, June 2009, pp.1528−1538 www.jos doi: 10.3724/SP.J.1001.2009.03395 Tel/Fax: +86-10-62562563
© by Institute of Software, the Chine Academy of Sciences. All rights rerved.
∗
二维矩形条带装箱问题的底部左齐择优匹配算法
蒋兴波1,2, 吕肖庆1,3+, 刘成城1
1(北京大学计算机科学技术研究所，北京 100871)
2(第二军医大学卫生勤务学系，上海 200433)
3(北京大学电子出版新技术国家工程研究中心，北京 100871)
Lowest-Level Left Align Best-Fit Algorithm for the 2D Rectangular Strip Packing Problem
JIANG Xing-Bo1,2, LÜ Xiao-Qing1,3+, LIU Cheng-Cheng1
1(Institute of Computer Science and Technology, Peking University, Beijing 100871, China)
2(Faculty of Health Services, Second Military Medical University, Shanghai 200433, China)
3(National Engineering Rearch Center of New Technology in Electronic Publishing, Peking University, Beijing 100871, China)
+ Corresponding author: E-mail: lvxiaoqing@icst.pku.edu
Jiang XB, Lü XQ, Liu CC. Lowest-Level left align best-fit algorithm for the 2D rectangular strip packing
problem. Journal of Software, 2009,20(6):1528−1538. www.jos/1000-9825/3395.htm
Abstract: In this paper, a heuristic placement algorithm for the two-dimensional rectangular strip packing
problem, lowest-level left align best fit (LLABF) algorithm, is prented. The LLABF algorithm is bad on the
论点论据论证best-fit priority principle with overall consideration of veral heuristic rules, such as full-fit first rule, width-fit first
rule, height-fit first rule, joint-width-fit first rule and placeable first rule. Unlike the bottom-left (BL), the
improved-bottom-left (IBL) and the bottom-left-fill (BLF) heuristic placement algorithms, LLABF algorithm
dynamically lects the best-fit rectangle for packing. The computation result shows that 2DR-SPP can be solved
more effectively by combining the LLABF algorithm with the genetic algorithm (GA).
Key words: lowest-level left align best fit (LLABF) algorithm; genetic algorithm; 2D rectangular strip packing
problem; heuristic placement algorithm
摘要: 针对二维矩形条带装箱问题提出了一种启发式布局算法，即底部左齐择优匹配算法(lowest-level left align
best fit，简称LLABF). LLABF算法遵循最佳匹配优先原则，该原则综合考虑完全匹配优先、宽度匹配优先、高度匹
配优先、组合宽度匹配优先及可装入优先等启发式规则.与BL(bottom-left),IBL(improved-bottom-left)与
BLF(bottom-left-fill)等启发算法不同的是,LLABF能够在矩形装入过程中自动选择与可装区域匹配的下一个待装
矩形.计算结果表明,LLABF结合遗传算法(genetic algorithm，简称GA)解决二维条带装箱问题更加有效.
关键词: 最低左对齐最佳匹配(LLABF)算法；遗传算法；二维矩形条带装箱问题；启发式布局算法
中图法分类号: TP18文献标识码: A
二维矩形条带装箱问题(2D rectangular strip packing problem，简称2DR-SPP)是一个典型的组合优化问题,
∗ Received 2008-02-29; Revid 2008-04-15; Accepted 2008-06-03
蒋兴波等：二维矩形条带装箱问题的底部左齐择优匹配算法1529
其应用相当广泛，如工业领域中的新闻组版、布料切割、金属下料等.2DR-SPP通常是指将若干个不同规格的矩形{π1,π2,…,πn}装入宽度W固定、长度L不限的矩形容器C中，要求装完所有矩形后占用高度H packing最小，从而达到节省材料的目的.在矩形的装入过程中，要求满足:①πi,πj互不重叠,i≠j,i,j=1,2,…,n;②πi必须装入在矩形容器C内，即矩形在装入过程中不能超出容器C的宽度W;③πi的边必须与矩形容器C的边平行,πi可以90°旋转.
2DR-SPP是一个NP完全问题，其计算复杂度随着问题规模的增大呈指数增长.针对该类问题，国内外相关学者作了大量的研究.Hifi[1]给出了一种基于分支定界方法(branch-and-bound procedure)的精确算法，适用于解决中小规模的2D装箱问题;Lesh等人[2]针对2D矩形完美装箱问题，提出了基于分支定界的穷举搜索算法，该算法已证明对于低于30个矩形的装箱是有效的.
为了解决大规模的矩形装箱问题，一些启发式算法也相继提出来.Zhang等人[3]提出了一种启发式递归算法HR(heuristic recursive algorithm)，该方法基于启发式策略和递归结构，实验结果表明，该算法能够在较短时间内获得较为理想的装箱高度，但其平均运行时间却达到了O(n3).陈端兵等人[4]根据先占角后占边的原则，提出了一种针对矩形装箱的贪心算法.Chen等人[5]给出了一种two-level搜索算法来求解2DR-SPP.Cui[6]给出了一种启发式递归分支定界算法HRBB(heuristic recursive branch-and-bound algorithm)，该算法将递归结构和分支定界技术结合在一起来求解2DR-SPP，取得了较好的实验结果.Beltrán等人[7]按照随机搜索原则设计的GRASP(greedy randomized adaptive arch procedur
e)算法与VNS(variable neighbourhood arch)结合在一起来求解2DR-SPP.而Alvarez-Valdes等人[8]提出了Reactive GRASP算法，该算法分为构建和改进两个阶段，其测试结果优于文献[7].张德富等人[9]则提出了一种有效的砌墙式启发式算法PH，实验结果表明，该算法对规模较大的2DR-SPP能够获得较好的装箱效果.
针对2DR-SPP，目前广泛采用的是遗传算法GA(genetic algorithm)、模拟退火算法SAA(simulated annealing algorithm)等搜索算法与BL(bottom-left)、IBL(improved BL)、BLF(bottom-left-fill)等启发式布局算法相结合的方式.Bortfeldt[10]采用了无任何编码的遗传算法来解决矩形装箱问题.Jackobs[11]提出了一种混合算法，通过GA 与BL启发式布局算法相结合，从而将矩形的装箱问题转换成相对简单的装入序列问题.由于BL算法容易出现即使穷举所有情况仍不能得到最优解的现象，因此,Liu[12]提出了一种IBL算法，并与GA相结合，取得了优于文献[11]的装箱效果.Yeung等人[13]针对布料切割问题提出了一种布局算法LFLA，该布局算法的计算复杂度为O(n)，相对于BL算法(其复杂度为O(n2))，效率上有了较大的提高.Zhang等人[14]针对矩形装箱问题给出了meta-heuristic算法，该算法主要基于启发式递归策略和SAA.Dereli等人[15]则采用SAA与递归布局方法相结合来解决2DR-SPP.针对不同数量及不同类型的矩形排样,Hopper[16]分别使用了BL,BLF启发式布局算法和GA,NE(naïve evolution),SA,HC(hill-climbing),RS(random arch)启发式搜索算法相结合的方式进行求解.
迄今为止，虽然对2DR-SPP进行了大量的研究，但从相关文献给出的测试结果来看，该问题仍然有进
一步研究的必要.例如,BL,IBL,BLF,LFLA以及贾志欣等人[17]提出的最低水平线LHL(lowest-horizontal-line)等常见的启发式布局算法，它们在对矩形装入的过程中严格按照矩形的某个排列序列进行，容易产生较大的空洞，浪费空间，因此装箱效果不够理想.相对于BL而言,BLF算法可以取得较好的装箱效果，但其算法的时间复杂度却达到了O(n3)[18]，不适宜解决规模较大的2DR-SPP.
本文针对上述问题设计出一种启发式布局算法，即底部左齐择优匹配算法(lowest-level left align best fit，简称LLABF).本文第1节重点介绍LLABF算法设计.第2节介绍GA+LLABF算法的实现.第3节主要对标准数据集进行模拟测试，并与相关文献结果进行对比分析.第4节给出结论.
1 LLABF算法设计
1.1 定义
设容器宽度所在方向为横坐标X，长度方向为纵坐标Y，容器的左下角为坐标原点(0,0).容器的底部在y=0处，容器可以在Y轴正方向无限延伸.
1530 Journal of Software软件学报 V ol.20, No.6, June 2009
队列I={π1,π2,…,πn}表示n个矩形的某个装入序列，其中,πi是矩形编号,πi∈[1,n]，对任意i,j∈[1,n]，当i≠j时, πi≠πj.设I(i)表示队列I中第i个位置上对应的矩形，它由五元组构成，即I(i)={x,y,w,h,θ}，其中,I(i).x,
I(i).y分别表示该矩形装入后，其左下角的横、纵坐标;I(i).w,I(i).h,I(i).θ分别表示该矩形的宽度、高度和旋转角度.
设队列E={e1,e2,…,e m}表示装入过程中产生的轮廓线集合，元素e k为水平线线段(与X坐标轴平行)，它由三元组构成，即e k={x,y,w}，其中,e k.x,e k.y表示第k个水平线线段的左端点坐标(起点坐标);e k.w表示第k个水平线线段的宽度；并且对任意0<k<m，有e k.x<e k+1.x，即按轮廓线起点的x坐标从小到大排列.队列E具有以下特征：其y坐标具备唯一性，如果相邻线段具有相同的高度y，则进行合并；所有线段在X坐标上的投影不重叠；所有线段的宽度之和刚好等于矩形容器宽度W.
最低水平线定义为队列E中其y坐标最小的水平线.
最优高度H opt表示穷举所有可能情况得到的最小装箱高度，也称为最优解.
装箱高度H packing表示根据当前装入序列，按照布局算法将所有矩形装入矩形容器C内所得到的最小高度.
空洞是指在装箱过程中，由矩形或者矩形与容器边界(如x=0,y=0,x=W或者y=H packing)围成的空白区.空洞越多，材料浪费的程度就越严重.
1.2 LLABF启发规则设计
1.2.1 基本思想
儿童故事有哪些一般情况下，对NP难问题很难直接构造出一个最优解或满意解，所以只能通过搜索的方法在整个解空间中寻找最优解或者满意解.当问题规模较大时，这种盲目搜索或者遍历就变得十分困难，甚至根本不可行.因此，相关学者常利用问题解本身的某些结构特征来构造出一些启发式规则，并按照该规则设计出启发式算法，由该算法求得问题的一个满意解.
对于矩形条带装箱问题，它有以下几个可以利用的结构特征:做梦拉屎
(1) 面积较大的矩形装入后产生的空洞较大，面积较小的矩形装入后产生的空洞较小;
南翔古猗园
(2) 面积较大的矩形装入后产生的空洞常常可以装入面积较小的矩形;
(3) 装入过程中产生的轮廓线越规整，即组成轮廓线的水平线数量越少，就越有利于后期矩形的装入.
本文中,LLABF启发式算法利用了矩形条带装箱问题的3个结构特征，采用了动态选择方法.该方法遵照最佳匹配优先原则来动态选择下一个待装矩形，使得在矩形装入的每一步都尽可能地获得一个较优的装箱结果.重复执行，直至最终获得整体较优解.
最佳匹配优先原则(best-fit priority，简称BFP)即在矩形的装入过程中，优先考虑与当前可装入区域宽
度或高度相匹配以及可装入的未排矩形，它包括完全匹配优先、宽度匹配优先、高度匹配优先、组合宽度匹配优先以及可装入优先这5种启发式规则.
5种启发式规则中完全匹配优先、宽度匹配优先以及组合宽度匹配优先可以减少空洞的产生，特别是在装入初期，由于用来与可装区域进行比较的矩形较多，因此，其匹配的概率越高，就越不容易产生空洞；完全匹配优先以及高度匹配优先使得装箱轮廓相对规整；高度匹配优先以及可装入优先可以将较小矩形延后装入.5种启发式规则结合起来不但可以使矩形装入后产生的空洞数量较少，而且所有的空洞总面积相对也较小.
倾1.2.2 启发规则设计
完全匹配优先(full-fit first，简称FFF). 在可装入的轮廓线中选取最低的水平线e k，如果有多个线段，则优先选取最左边的一段.从待装矩形中按照装入序列依次将矩形与e k进行比较，如果存在宽度或者高度与该线段宽度e k.w相等且装入后刚好左填平或者右填平的矩形则优先装入.完全匹配优先能够减少装入后产生的轮廓线数量，使得装入轮廓朝着顶部平齐的方向发展.
宽度匹配优先(width-fit first，简称WFF). 在装入过程中，优先装入宽度或者高度与最低水平线e k等宽的矩形，如果存在多个匹配矩形，则优先装入面积最大的.与完全匹配优先规则不同的是，宽度匹配优先并不要求装入后能够实现左填平或者右填平；同时，该规则使得较小矩形有推迟装入的趋势.另外,W
FF不会增加装入轮廓线数量.
蒋兴波 等：二维矩形条带装箱问题的底部左齐择优匹配算法
1531
高度匹配优先(height -fit first ，简称HFF ). 在待装矩形中，按照装入序列查询宽度或高度不大于最低水平线e k 宽度且装入后能够实现左填平的矩形，若存在则装入查询到的首个矩形.与FFF 和WFF 不同,HFF 可能会在最低水平线上产生新的、更小的可装入区域，但却增加了轮廓线e k −1的宽度.
组合宽度匹配优先(joint -width -fit first ，简称JWFF ). 按装入序列对两个矩形进行组合，如果组合后的宽度与最低水平线宽度e k 相等，则优先装入组合序列中的首个矩形.例如，存在两种组合I (i 1).w +I (j 1).w =e k .w , I (i 2).w +I (j 2).w =e k .w ，如果I (i 1)的面积大于I (i 2)，则首先装入I (i 1)，否则装入I (i 2).
JWFF,FFF 与WFF 规则避免了在最低水平线e k 上产生新的、更小的可装入区域，从而减少了整个装箱过程产生空洞的可能性.为了保证时效性，算法中设置了查询范围archNum ，即从当前位置开始，最多可以进行archNum ×archNum 次连续矩形的两两组合查询.
可装入优先(placeable first ，简称PF ). 在一定范围内，从待装矩形件中按照装入序列依次查找宽度或
高度不大于最低水平线e k 宽度的矩形，若存在，则将其装入；若存在多个，则装入面积最大的矩形.PF 可能在最低水平线上产生新的、更小的可装入区域，同时使得较小矩形延迟装入.
在矩形的装入过程中，满足FFF,WFF,HFF 以及JWFF 规则的矩形可能并不存在，此时就必须考虑PF.如果满足PF 规则的矩形仍不存在，那么必然会在最低水平线上产生空洞.与BL,IBL,LFLA 以及LHL 算法不同，该空洞是在一定范围内由于不存在可装入的矩形而产生的，因此其面积更小.与BLF 算法不同,LLABF 算法并不需要保存新产生的空洞.
图1给出了按照最佳匹配优先原则的部分启发规则实现矩形装入的示意图，其中，矩形的装入序列是4 2 7 6 5 1 8 3.图1(a)表示已经装入了4个矩形，产生了由4个线段e 1,e 2,e 3,e 4组成的装入轮廓，其中,e 2为最低水平线，其对应的区域是接下来首先要考虑的区域.图1(b)采用完全匹配优先：与最低水平线e 2等宽的矩形有1号和3号，但由于只有3号矩形装入后能够实现左填平，因此首先选择该矩形装入.图1(c)采用宽度匹配优先：满足该条件的矩形有1号和3号，但由于1号矩形面积较大，所以优先装入.图1(d)采用高度优先:1,8,3这3个矩形都满足其宽度不大于e 2.w ，但只有8号和3号矩形装入后能够实现左填平，且8号矩形位置在3号之前，所以优先装入.
(a) (b)
(c) (d)
Fig.1 Packing result according to BFP principle
图1 按BFP 原则的装箱结果图
1.3 LLABF 算法的实现用英语怎么说表白
LLABF 算法是按照BFP 原则进行装箱的启发式布局算法，其算法实现如下所示.
1532 Journal of Software软件学报 V ol.20, No.6, June 2009
LLABF (input: I; output: H packing)
begin
InitContours(E); InitCoordinate(I); H packing
=0; // 初始化;H packing：装箱高度
① for (ii=1; ii≤n; ii++)
begin
②if (I(ii).x>−1) goto ①; // 当前矩形件已被装入
在E中取最低水平线e k;
j=−1; //
记录用于装入的矩形件所在序列号FullFitFirst(ii,I,e k,j); if (j>−1) goto ④;
//
完全匹配FFF
WidthFitFirst(ii,I,e k,j); if (j>−1) goto ④; //
宽度匹配WFF
HeightFitFirst(ii,I,e k,j); if (j>−1) goto ④; //
高度匹配HFF
JointWidthFitFirst(ii,I,e k,7,j); if (j>−1) goto ④; // 组合宽度匹配JWFF
PlaceableFirst(ii,I,e k,n/6,j); if (j>−1) goto ④; //
exerci的用法
可装入优先PF
③合并E中的边，转②;
④将I集合中第j位元素对应的矩形件I(j)装入在E中的最低水平线e k上；如果未旋转，则
H packing=max(H packing,I(j).x+I(j).h)，否则,H packing=max(H packing,I(j).x+I(j).w)；更新集合I和E；如果j>ii,
则转②;
end
end
其中,InitCoordinate(I)是对所有矩形块的坐标x,y进行初始化.在初始阶段，由于所有的矩形都未进行装入, InitCoordinate(I)将其坐标x,y全部初始化为−1，即对任意i∈[1,n],I(i).x=I(i).y=−1.
InitContours(E)对装箱轮廓线进行初始化.在初始阶段，由于容器C未被装入，因此，其轮廓线仅由一个水平线线段构成，即E={e1}，其中,e1={0,0,W},W为容器C的宽度.
FullFitFirst,WidthFitFirst,HeightFitFirst,JointWidthFitFirst,PlaceableFirst分别表示按照FFF,WFF,HFF, JWFF以及PF等启发式规则在队列I中第ii位开始向后依次查找与最低水平线e k相匹配矩形的查询过程，其返回值为j.其中,JointWidthFitFirst,PlaceableFirst中的查询范围分别设置为7,n/6，为多次实验后取得的经验值.
1.4 LLABF算法举例
图2(a)是5个矩形构成的一个完美装箱图，其装箱高度H packing等于最优高度H opt，空间的利用率为100%.对于BL,IBL,LFLA以及LHL算法，要实现图2(a)的完美装箱(不考虑旋转)，其装入序列就必须为1 2 3 4 5.对于序列为1 3 4 5 2和1 3 2 4 5，其装箱结果分别如图2 (b)和图2(c)所示，这两种装入序列都会产生较大的空洞.
(a)
过我的生活
(b) (c)
Fig.2 Packing result according to BL, IBL, LFLA or LHL algorithm
图2 BL,IBL,LFLA或LHL算法的装箱结果图
对于同样的装入序列，采用LLABF算法则能得到如图2(a)所示的完美装箱.图3显示了装入序列为1 3 4 5
