一种带剪切约束的启发式二维装箱算法

姚　怡， 赖朝安

(1. 华南理工大学工商管理学院，广东 广州 510640；2. 广西大学计算机与电子信息学院，广西 南宁 530004)

一种带剪切约束的启发式二维装箱算法

姚怡1,2， 赖朝安1

(1. 华南理工大学工商管理学院，广东 广州 510640；2. 广西大学计算机与电子信息学院，广西 南宁 530004)

提出一种满足剪切约束的启发式二维装箱算法，通过价值修正策略提高箱的空间利用率，进而减少箱的使用数量。该启发式算法将较难装箱的物品赋予较高的价值及装箱优先权；并通过延展或融合剩余零散空间，将未用的空间合并到剩余相邻空间，以改进空间利用率。基于标杆测试数据集的仿真实验证明了该算法的有效性和相较于其他二维装箱算法的优越性。

二维装箱；价值修正；剪切方式；启发式

二维装箱(two-dimensional bin packing，2DBP)问题作为一个典型的组合优化问题吸引了大量集中于数学模型或算法的研究，近期的研究则更加关注大规模的装箱问题，对此通常不是采用系统的、精确的方法追求问题的最优解，而是采用确定性算法对解的生成方式加以一定的限制，在可接受的时间内获取较优解[1-2]；或者采用各种启发式算法[3-10]，通过不断尝试逐步趋优的方法，达到有效合理的目标，取得足够满意的解。2DBP的研究主要关注输出(价值)最大化与输入(价值)最小化两项指标，以达到装箱效率的最大化。本文研究以输入最小化为目标的2DBP多箱问题，该问题可描述为：给定固定尺寸的多个二维矩形箱，其宽度为W，高度为H；存在大量在尺寸上差异较大的二维矩形物品，现需寻找能装入所有物品的、且保证物品不重叠并呈现正交摆放形式的装箱方案，达到所使用的箱数量最小化的目标。

定向与剪切这两种约束的组合产生4种2D装箱方式：OF、RF、OG和RG[3]。O是指矩形物品只能定向装箱(orientated，O)，R则相反，允许物品旋转(rotatable，R)；G是指物品必须采用类似剪床的“一刀切”工艺的摆放布局，即剪切方式(guillotine-cut，G)；而F则相反，允许物品自由摆放。本文研究2种情况：2DBP-OG和2DBP-RG。

2002年Lodi等[7]针对4种2DBP类型(OF、RF、OG和RG)提出了一种启发式算法，同时设计了一个统一的禁忌搜索算法，在邻域的探索中通过改变启发性规则去适应装箱类型的变化。1999年Lodi等[3]提出了背包装填算法(knapsack problem，KP)，采用了基于所产生子问题的另一个层装填策略。在(两值)背包问题中，必须选择n个元素的一个子集，每个元素有相应的利润和重量，使总重量不超过给定的容重并且总利润达到最大。2009年Polyakovsky和M′Hallah[8]提出了基于代理的智能算法(agent-based，A-B)，以剪切型左下原则(guillotine bottom-left，GBL)做物品的基础装填，并设置了物品的代理机制，每个代理拥有自己的参数、适应度和判定过程，通过代理间的相互影响，决定物品的最佳装填位置。2011年Charalambous和Fleszar[9]针对带剪切约束的2DBP提出了一个启发式算法，采用平均面积的策略选择物品并逐个箱子装填，有效避免了因单纯追求箱子的面积利用率而导致小物品的过度使用。2013年Fleszar[10]针对2BP-OG/RG问题构造了3个插入型启发式算法，通过树型结构去描述物品布局以及物品的各种插入操作，并设计了新的判定规则用于改善算法效果。

1　本文算法

针对装箱过程中，由于某些物品过度使用而产生局部最优而非全局最优的现象，Belov提出顺序价值修正策略(sequential value correction，SVC)。通过不断修正物品价值来达到全局优化的目的，并将该方法成功运用于一维下料问题[11]和带排样问题[12]，取得较好的效果。本文的二维装箱算法借鉴了Belov提出的价值修正策略，具体如下：

(1) 对每个物品设定初始价值，形成价值不等的候选物品集合A；

(2) 从集合A中选择要填充的若干物品形成集合B，并沿高度方向ih对物品非增序排列，采取左下角原则做基础填充，形成阶梯状的物品填充布局P；

(3) 选择位于阶梯上方的某个矩形空间s，对其进行装箱；

(5) 每当一个箱子装满了或剩余空间已经无任何利用价值时，就打开另一个新的空箱继续装填直至剩余物品为0，此时获取一个装箱方案C；

(6) 采用价值修正公式对每个物品价值进行修正，形成附带新价值的物品集合，重新装箱，获得新的装箱方案，经过若干次的迭代，选取最优装箱方案作为结果。

主算法伪代码如下：

算法1. Main()

1.1物品初始价值设定

价值修正策略是为了在迭代过程中能更快更好地逼近最佳结果，在每一次迭代开始时，将前一次迭代的结果传递过来，作为参数调节本次迭代的初始值。本文方法在每轮装箱方案生成后均对所有物品重设价值，采用价值修正的方式调整装箱布局，使得难装的物品(价值大)先行填充。衡量每个箱子的装箱布局的好或坏，不再是单纯的面积利用率，而是改成所装物品总价值最大化。在首轮装箱方案中，需要给每个物品一个初始价值。根据经验，一般面积越大的物品填充难度越大，因此直接设置物品面积为初始价值。设箱子尺寸为HW×，需对矩形物品集合A=进行装箱。装箱之前，根据式(1)赋予每个物品 ai一个初始价值 vi：

1.2空间填充方法(pack(r,B))本文算法除了定义物品集合A，还定义了空间集合用来存放当前箱子中可供填充的各种矩形空间信息。为方便描述，将已有或即将有物品填充的矩形空间称为填充区域。对每个新打开的箱子，集合S默认拥有一个面积为H×W的填充区域s00∈s0，随着填充操作的持续进行，会有分裂出来的剩余子空间集不断加入集合S。当或S集合元素无利用价值，即任意 sij都无法容纳任意的 ai时，一个箱子的填充操作结束，允许打开新箱继续填充。每次的填充操作都选择一个填充区域和若干物品，将物品沿空间宽度W方向按照 hi从高到低的原则依次排列填充，填充操作完毕后将生成子空间集(如图1所示)，对空间 s00进行填充后，生成包含4个子空间的集合

图1　填充操作后剩余子空间的生成

算法2. pack(r,B)

1.2.1空间的选择(sele_area(S))

填充操作每次只针对一个矩形区域空间，对新打开的箱子，默认只有一个面积为H×W的填充区域，无需进行选择。当对某个填充区域进行阶梯状填充操作之后，在每个物品上方均一对一生成小的矩形区域空间sij左下角坐标与物品左上角坐标重叠，右上角坐标与当前填充区域右上角坐标重叠，因此下一轮的填充操作必须进行空间选择。在如图 1所示的首轮填充操作后，物品1(2、3、4)对应区域空间A(B、C、D)，4个区域空间形成空间集合S中的一个子集，即各区域空间尺寸、面积各有差异。本文算法按照面积从大到小进行空间选择，每个空间子集 si只选择一个空间成为填充区域。如图1所示的空间子集 s1，优先选择面积最大的区域 A进行下一轮的物品填充。如果区域 A由于形状的缘故无法容纳候选物品集合中的任何物品，则选择面积次大的区域 B进行下一轮的物品填充，以此类推，按面积大小进行填充区域选择。如果所有空间均无法容纳物品，且无法与其他区域合并空间，则在集合S中删除该子集 s1j。

算法3. sele_area(S)

1.2.2物品的选择(selete(ai,r))

在进行填充操作时，首要步骤是从候选物品集合中挑选合适的物品形成B集合，用于填充当前的面积为H×W的矩形区域，使得填充区域价值最大，然后再考虑剩余空间的利用。此时，物品的挑选实际上是一个经典的0-1背包问题。0-1背包问题描述如下：有n件物品和一个容量为V的背包，第i件物品的重量是 c[i]，价值是w[i]，求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。0-1背包问题可以用递归法、动态规划法、贪心法和分支界限法等多种方法解决，本文选用动态规划法。动态规划的指导思想是先要有效地找出子问题，并通过其子问题推出原问题的解，通常子问题与原问题是相同的，只是规模上的缩小，直到遇见问题的界限。对于0-1背包问题，也可以找出满足动态规划的子问题：如果不放第i件物品，那么问题就转化为“前i−1件物品放入容量为v的背包中”，价值为如果放第i件物品，那么问题就转化为“前i−1件物品放入剩下的容量为v−c［i］的背包中”。此时能获得的最大价值就是再加上通过放入第i件物品获得的价值因此状态转移方程为：

在进行如图 1所示的物品填充时，由于只允许正交方式摆放，不允许重叠，且物品上下两个方向均无其他物品，因此可看成一次沿着填充区域的宽度方向的一维填充操作。此时物品的选择过程就与经典0-1背包问题存在一一对应关系：

(1) 填充区域的宽度W——一个容量为 V的背包；

(2) 物品价值 vi——物品价值w[i]；

(3) 物品宽度wi——物品的重量是 c[i](OG方式)；

(4) 物品宽度wi或长度hi——物品的重量是c[i](RG方式)。

在物品选择过程中，对于OG方式，只能正放不能倒放，因此，凡是物品过大放不进指定区域即满足的物品自然淘汰，不在选择范围内；而对于RG方式，则需要从正放和倒放两个方向进行考虑，是选择物品宽度wi(正放)，还是选择长度 hi(倒放)作为沿填充区域宽度W填充的对象，主要依据以下判断规则：

(1) 如果该物品宽度小于等于高度且正放倒放均能放进区域内即wi≤hi&&wi≤W&&wi≤H&&hi≤W&&hi≤H，则选择物品宽度wi；

(3) 如果该物品宽度大于高度且正放倒放均能放进区域内即wi＞hi&&wi≤W&&wi≤H&&hi≤W&&hi≤H，则选择物品高度hi；

(5) 其他情况的物品属于无论正放还是倒放都超出区域的情况，做淘汰处理，不参与物品选择。

算法4. selete(ai,r)

1.2.3子空间的生成

图2　3个子空间集s上　、s左　和s下的生成

当子空间集均不为空时，添加到空间集S的末尾成为候选空间。如此循环，处理剩余空间。为防止无效空间集的循环生成，设置终止条件：当某个子空间集中所有矩形区域均属于无效空间时，禁止生成下级空间集并删除当空间集S=φ时，表示当前箱子已完成填充操作，允许打开新的箱子继续填充。

剩余空间离散化意味着可选择的物品种类会变少，因此有必要进行空间扩张或空间融合，这有利于提高空间利用率。当然，采取措施的前提是保证剪切方式的正确实施，因此在做腾挪操作时，应以对应物品的填充宽度作为移动步长。当某个子空间集被定义为无效空间集时，允许其向剩余的相邻空间集输送空间。输送的次序依照空间集S的次序，假设当前空间集如图3(a)所示。当空间集因无合适物品而被定义为无效空间集时，依照顺序，需向右腾挪后被安排给空间集如图3(b)所示；然后再向上腾挪后被安排给空间集，如图3(c)所示；当与空间集相邻的空间集个数为0时，删除空间集的所有信息。

图3　空间合并示例

1.3价值修正

物品的价值决定了物品在装箱过程中的优先级别，对于面积较大的，或形状独特的，或大部分剩余空间均难以将之容纳的物品应赋予更高的价值，提升其优先级别。

本文算法通过多次迭代提高解的质量，每次迭代均根据上一次的装箱方案C对各物品价值 vi进行修正，以达到让难装的物品先行填充的目的。设：在当次迭代产生的装箱方案C中，物品 ai所在的那个箱子一共填充了m个物品，则面积利用率设置两个常数g∈(0,1)和 ρ＞1，g为修正价值的权值系数；ρ为控制参数，实验中可尝试不同的值使得物品的价值更趋向于合理。本文设计价值修正公式为：

式(3)中，通过权值系数g来调节物品的原价值在新价值中所占的比例；存在的意义在于：箱子中物品个数越多，意味着小尺寸物品较多，且易于和其他物品形成互补关系提升填充率，应该降低该类物品的价值。

通过上述价值公式的修正，使得算法在构造一个解决方案时充分考虑了每个物品的使用频率，每次迭代生成的装箱方案都参考了上一次方案的参数，根据参数重新修正物品价值。不再单纯以面积利用率作为衡量装箱效果的唯一标准，而是以箱子物品的总价值作为装箱优劣的判断准则，这种修正机制赋予了难装物品更高的优先权，有效避免了较差方案的生成。

2　实验结果

本文算法(value correction heuristic，VCH)采用二维装箱实验中常用的500个标准算例进行验算，并与其他算法结果进行比较。500个算例共分为10个classes，每个class包含50个小题。每个小题提供的箱子均为正方形，物品尺寸在小于箱子尺寸范围内随机生成，算法采用C#编程，Microsoft visualstudio 2010进行编译。为了节约运行时间，本文算法读取了二维装箱算法下界(lower bound，LB)数据，其中，2BP|O|G 调用了 Fekete和Schepers[5]给出的下界，2BP|R|G调用了Clautiaux等[6]给出的下界。实验中设置g=0.45;ρ=1.2，经200次迭代计算上述500个标准算例，SH算法取得数据为：2BP|O|G共需7 309个箱子，平均用时0.236 s；2BP|R|G共需 7 059个箱子，平均用时0.255 s。表1显示本文算法(VCH)与其他启发式算法进行比较的结果，数据显示VCH算法在箱子消耗总数上占有优势。

表2显示了A-B，CHBP，CFIH+J4算法和本文算法(VCH)的细节数据的对比，同时列出下界(LB)数据作参考。数据表明VCH算法在第5组中表现特别优秀，其他组也取得不错的结果，无论是O|G方式还是R|G方式，500题的箱子消耗总数比其他算法都要少。

表1　本文算法与其他算法的性能对比数据

表2　4种算法的分段数据对比(箱子个数)

表3　取不同迭代次数的运算结果(箱子个数)

3　结 束 语

本文提出了一个应用于剪切方式的启发式二维装箱算法，对当前剩余空间设计了有效划分和填充，相邻小空间的合并有效提高了面积利用率。该算法通过修正物品价值调整物品的填充次序，多次迭代使解逐步趋优。实验表明，相比其他启发式算法，本文算法取得了较好的装箱结果。由于其需要多次调用0-1背包子算法，因此耗费时间较多，在时间性能上没取得更好的结果。基于这个问题，未来可采用并行编程技术，或时间复杂度更低的背包算法，提高时间效率。

[1] 潘卫平, 陈秋莲, 崔耀东, 等. 基于匀质条带的矩形件最优三块布局算法[J]. 图学学报, 2015, 36(1): 7-11.

[2] 易向阳, 潘卫平, 张俊晖. 基于五块模式的单一矩形件排样算法[J]. 图学学报, 2015, 36(4): 521-525.

[3] Lodi A, Martello S, Vigo D. Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems [J]. INFORMS Journal on Computing, 1999, 11(4): 345-357.

[4] Wäscher G, Haußner H, Schumann H. An improved typology of cutting and packing problems [J]. European Journal of Operational Research, 2007, 183(3): 1109-1130.

[5] Fekete S P, Schepers J. A general framework for bounds for higher dimensional orthogonal packing problems [J]. Mathematical Methods of Operations Research, 2004, 60(2): 311-329.

[6] Clautiaux F, Jouglet A, Hayek J E. A new lower bound for the non-oriented two-dimensional bin-packing problem [J]. Operations Research Letters, 2007, 35(3): 365-373.

[7] Lodi A, Martello S, Vigo D. Recent advances on two-dimensional bin packing problems [J]. Discrete Applied Mathematics, 2002, 123(1-3): 296-379.

[8] Polyakovsky S, M′Hallah R. An agent-based approach to the two-dimensional guillotine bin packing problem [J]. European Journal of Operational Research, 2009, 192(3): 767-781.

[9] Charalambous C, Fleszar K. A constructive bin-oriented heuristic for the two-dimensional bin packing problem with guillotine cuts [J]. Computers & Operations Research, 2011, 38(10): 1443-1451.

[10] Fleszar K. Three insertion heuristics and a justification improvement heuristic for two-dimensional bin packing with guillotine cuts [J]. Computers & Operations Research, 2013, 40(1): 463-474.

[11] Belov G, Scheithauer G. Setup and open-stacks minimization in one-dimensional stock cutting [J]. INFORMS Journal on Computing, 2007, 19(1): 27-35.

[12] Belov G, Scheithauer G, Mukhacheva E A. One-dimensional heuristics adapted for two-dimensional rectangular strip packing [J]. Journal of the Operational Research Society, 2008, 59: 823-832.

A Heuristic Algorithm for Two-Dimensional Bin Packing with Guillotine Constraints

Yao Yi1,2,Lai Chaoan1
(1. School of Business Administration, South China University of Technology, Guangzhou Guangdong 510640, China; 2. College of Computer and Electronics Information, Guangxi University, Nanning Guangxi 530004, China)

A heuristic approach for two-dimensional bin packing problems with guillotine constraints is proposed to minimize bin usage by maximizing space efficiency through the strategy of value correction. This heuristic algorithm firstly assigns higher values and packing priorities to items considered more difficult to pack into residual spaces, then selects packing spaces in descending order of unused area, and finally expand or merge residual small spaces and add unusable space to the residual adjacent space set, so as to improve the utilization rate. Simulation experiments on benchmark test sets suggest that the approach can work effectively and rivals existing other 2DBP methods.

two-dimensional bin packing; value correction; guillotine cut; heuristic

TP 391

A

2095-302X(2015)06-0879-08

2015-06-25；定稿日期：2015-07-08

国家自然科学基金面上项目(71371058)；国家自然科学基金地区科学基金项目(61363026)

姚怡(1975–)，女，广东阳江人，副教授，硕士。主要研究方向为组合优化算法。E-mail：yaoyi@gxu.edu.cn

赖朝安(1973–)，男，广西钦州人，副教授，博士。主要研究方向为制造信息化、创新方法。E-mail：chalai@scut.edu.cn