@[toc]

论文来源：（2013）A goal-driven approach to the 2D bin packing and variable-sized bin packing problems
作者：Lijun Wei 等人

一、Absract 摘要

• 在本文中，我们研究了二维可变尺寸箱包装问题（2DVSBPP），其中的任务是将所有给定矩形包装成各种尺寸的箱，以使使用的箱的总面积最小化。
• 我们将2DVSBPP的搜索空间划分为多个集合，并在集合上施加顺序，然后使用目标驱动方法来利用这个划分的解空间的特殊结构。
• 由于2DVSBPP是二维装箱问题（2DBPP）的推广，我们的方法可以在最小变化的情况下适用于2DBPP。
• 对2DVSBPP和2DBPP的标准基准数据的计算实验表明，我们的方法比文献中的现有方法更有效。

二、Goal-driven approach 目标驱动方法

给定一个初始可行解，优化问题的算法效率取决于其接近最优解的速度（见下图）。对于目标值是离散的许多离散优化问题，目标值的数量与搜索空间相比很小。在2DBPP中，目标值是使用的箱数。

由于存在比不同目标值多得多的解，根据鸽巢原理，在搜索空间中将存在大量具有相同目标值的不同解。事实上，对于任何2DBPP解决方案，我们都可以通过重新排列使用的箱的顺序或更改任何箱中的包装配置来获得具有相同目标值的另一个解决方案。

从概念上讲，我们可以通过解决方案的目标值（使用箱子的总面积）将问题的搜索空间划分为多个集合。下图给出了2DVSBPP的此类分区的示例，其中每组分区表示使用的箱具有相同面积的解决方案：

请注意，不止一个箱的组合可以具有相同的总面积。由于集合中的任何成员都与整个集合中的其他成员一样好，所以我们只需要为集合找到一个可行的解决方案。

一旦我们找到了这样的解决方案，我们就可以消除所有目标值等于或大于的集合（假设求的是最小化问题），这可以大大减少搜索空间。我们的策略是生成搜索路径，为每个集合确定一个可行的解决方案。

实施这一想法有两个挑战：

• 首先，我们不知道最优目标值；这一挑战可以通过对目标值进行二进制搜索来克服（下图显示了二分搜索中考虑的集合）。

• 其次，如果我们考虑的集合不包含可行解（即，集合的目标值小于最优值），那么在该集合上花费的所有搜索努力都注定白费。

因此，我们必须设计一种方法，避免在枚举此类集合中的元素时花费过多的计算工作量。使用下限并不是解决这个问题的有效方法，因为我们可以假设所考虑的集合的目标值大于下限而不失一般性。

在我们的方法中，当试图使用二分搜索找到可行的解决方案时，我们限制了枚举每个集合所花费的搜索努力。然后我们加倍努力，在下一次迭代中再次调用二进制搜索。我们继续加倍努力，直到达到时限。这种二分搜索和迭代加倍的组合先前已被Wei等人应用于二维条形包装。

我们将尝试在[LB，UB]中找到具有目标值的解决方案。2DVSBPP的目标驱动方法（GDA）的总体过程在算法1中给出

• LB的值通过找到2DVSBPP问题的下限来确定（第1行），我们在第5节中描述了细节。
• 我们通过猜测UB的值（第2行）来消除对真实上界的需要
• 如果发现范围[LB，UB]太窄，无法找到可行的解决方案，我们只需扩大范围（第21行）。
• 外部while循环（第4–22行）迭代地使搜索工作量加倍。
• 内部while循环（第6–19行）是二分搜索
• 在每次迭代中将目标值的范围减少一半（第16–19行）。
• 对于给定的范围[LB，UB]，我们首先确定该范围内的所有目标值，这些目标值可以通过一些箱的组合来实现，并按升序对这些目标值进行排序（第5行）。可通过求解背包问题来计算可达到的目标值：

$$ \begin{aligned} A=&\left\{z\mid z=\sum_{i=1}^m W_j H_j x_j, \quad L B \leqslant z \leqslant U B, x_j \in\left\{0,1, \ldots, N_j\right\},\right.\\ &j=1,2, \ldots, m\} \end{aligned} $$

• 对于给定的目标目标值obj，我们通过求解以下背包问题，找到总面积等于obj（第8行）的所有箱子组合：

$$ \begin{aligned} B C S=&\left\{\left(x_1, x_2, \ldots, x_m\right) \mid \sum_{i=1}^m W_j H_j x_j=o b j, x_j \in\left\{0,1, \ldots, N_j\right\},\right.\\ &j=1,2, \ldots, m\} \end{aligned} $$

在最坏的情况下，枚举集合A和BCS的所有元素需要指数时间。然而，在许多实际应用中，料仓类型的数量预计很小。在这种情况下，A和BCS中的元素数量很少，我们可以通过简单的暴力来枚举它们（碰巧基准测试集中的bin类型数量很少）。当箱子类型的数量很大时，我们必须采用更先进的背包算法。

最里面的for循环（第9-15行）只尝试总面积为obj的bin的每个组合，并尝试将所有矩形加载到组合中。对于给定的箱子组合，我们首先通过面积降序对所有箱子进行排序（第10行），然后调用 TabuPack 函数加载尽可能多的矩形（总面积）；参数iter控制 TabuPack 花费的总搜索努力。下一节提供了 TabuPack 的详细信息。如果所有矩形都被打包，那么我们已经找到了一个可行的解决方案，然后我们将尝试通过调用 ImproveSol 函数来进一步改进解决方案（参见第4节）。

为了实现效率，我们维护了一个表，该表包含先前计算的每个obj值的集合BCS。每当我们需要为给定的obj值设置BCS时，我们将首先查阅此表，如果以前没有计算过BCS，则只计算BCS。

请注意，我们可以增量计算集合A。设LB=a，UB=b，设g（a，b）代表集合A。我们可以定义g（a，b）=g（a，c）∪ g（c，b），其中c在[a，b]内。简单来说，要计算大区间的A，我们可以将区间分成更小的区间，计算更小区间的相应集合A，然后合并结果。

在算法1的执行过程中，我们需要计算一系列间隔[LB，UB（1）]，[LB、UB（2）]，[LB、UB（3）]。，其中（k）表示迭代次数。在第k次迭代中，我们使用maxUB（k）表示遇到的最大间隔，使用maxA（k）来表示相应的集合。这些值可以更新如下：

$$ \begin{aligned} &\max U B^{(k)}=\max \left(\max U B^{(k-1)}, U B^{(k)}\right) \\ &\max A^{(k)}=\max A^{(k-1)} \cup g\left(\max U B^{(k-1)}, \max U B^{(k)}\right) \end{aligned} $$

一旦我们有了maxA，对于任何UB <= maxUB，我们都可以通过过滤找到对应的A。

接下来，我们将分析目标驱动方法的最坏情况，并讨论其实际应用的健壮实现。对于具有总面积obj的箱的组合，可能没有可行的解决方案，但存在可用箱的总面积小于obj的可行方案。对于具有总区域obj的每个箱的组合也可能不存在可行方案；我们称这种obj值不可接受。

在极少数情况下，可能存在一个可行的解决方案，其中箱obj1的总面积小于不可接受的obj2；我们称（obj1，obj2）为倒对。一般来说，我们预计反转对的数量会很小，当它们发生时，我们预计obj1和obj2之间的差距会很小（尽管可以构造极端的反例）。

最坏的情况发生在存在总面积为z的可行解时，但在第k次迭代中，我们的二分搜索尝试了一系列不可接受的目标obj（k，1）< obj（k，2）< obj（k，3）... 它们都大于z，并返回一个可行的解决方案，其箱的总面积等于UB。

二分搜索的后续迭代将经过相同的不可接受目标序列，并返回相同的可行解决方案，因为UB没有改变。因此，我们的算法暂停。

如果第k次迭代在没有找到任何可行解的情况下停止，或者有一个总面积小于UB的可行解，那么下一次迭代将尝试不同的目标区域序列。

当停止确实发生时，它可以很容易地检测到，一旦检测到，我们可以简单地在下一次迭代中引入一个小的随机扰动。随机扰动的目的是确保下一次迭代中检查的目标序列与当前迭代不同，从而大大减少所有目标不可接受的机会。

三、TabuPack 包装程序

其尝试使用最佳拟合规则将给定的矩形序列打包成一系列箱。最佳拟合有两种可能的实现方式：

（1）严格按照序列中的顺序加载项目，并将每个项目放置在最佳位置；
（2）评估将项目放置在某个位置的所有可能方式，并在每个步骤中选择并执行最佳放置（即项目和相应位置）。

我们的SequencePack实现了两种策略：第一个物品将使用第一个最佳匹配规则放置，其余项将使用第二个最佳匹配的规则放置。

当ff设置为|R|时，我们将使用第一个最佳匹配策略加载所有项；当ff设置为0时，我们将使用第二最佳匹配策略加载所有项目；当ff设置为|R|/2时，我们将使用这两种策略。我们对ff ∈｛0，|R|/2，|R|｝的每个值应用了三次禁忌搜索。每次禁忌搜索的初始序列是通过按面积递减对矩形集合R进行排序而获得的。

对于每个ff值，我们最多执行iter次禁忌搜索迭代（第6-15行），我们随机选择两个矩形bi和bj。如果（bi，bj）不在禁忌列表中，我们交换它们以生成新的序列。通过这种方式，我们可以生成多达10个非禁忌序列。从这10个非禁忌序列中，我们选择产生具有最高区域利用率的解决方案的序列，并将交换插入禁忌列表中；对于接下来的3n次迭代，其中n是R中的矩形数，此交换被禁止。

如果禁忌搜索无法生成一个所有矩形都被打包的解决方案，那么我们使用一个名为ForcePack的本地搜索子例程，该子例程最后尝试将所有未打包的矩形打包到该序列和ff值的最佳解决方案中；初步实验表明，ForcePack仅在容器具有6个或更多箱时有效。在任何阶段，如果找到了将所有矩形打包到垃圾箱中的解决方案，那么我们立即终止该过程并返回结果。否则，我们将返回在面积利用率方面找到的最佳解决方案。

3.1 SequencePack 子例程

我们的SequencePack程序将矩形序列Seq、一组以固定序列的容器集合B和一个整数参数ff作为输入。

SequencePack子程序的目的是将矩形序列打包到给定的bin序列中。它改编自Wei等人（2011）针对2D矩形包装问题的2DRPSolver启发式。2DRPSolver启发式算法是一种基于天际线的最佳拟合算法，用于将一组矩形打包到单个容器中。每个箱子中的包装图案由天际线表示，放置矩形的候选位置由天际线上的“凹面”点给出（详见第3.1.1节）。然后，该过程根据适合性度量重复选择放置（即，矩形以及某个箱子中的位置），并将所选矩形打包在该位置，直到没有可行的放置（由于没有更多的矩形或者没有更多的位置可以容纳任何矩形）。

为此，我们提出了两项措施。第一个适合度度量（等式（5））尝试根据尽可能在最佳位置按顺序给出的顺序。第二个适合度度量（等式（6））不强调序列，更侧重于将最佳矩形加载到最佳位置。

我们定义一个函数f来测量在候选位置p处填充矩形r的适合度。我们的适应度函数f（r，p）产生一个由七个分量组成的向量。我们说（r，p）比（r0，p0）更适合，f（r，p）在字典序上小于f（r0、p0）（即，我们逐个分量比较两个向量，第一个不同分量的顺序决定了两个向量的顺序）。f（r，p）的七个分量是：

1. ord（r）：输入序列中矩形r的顺序
2. onlyFit（r，p）：如果矩形r是仅存的可以适合p的矩形，则该值为0；否则，该值为1。
3. waste（r，p）：如果将r放置在p，则会产生的相邻浪费空间的总量（不能放置其他矩形）。第3.1.2节给出了更详细的解释。
4. fn（r，p）：与它在天际线中所接触的线段完全匹配的矩形的边数，称为其适合度（详见第3.1.3节）。
5. binOrd（p）：有序集合B中包含位置p的容器的顺序。
6. y（p）：位置p的y坐标。
7. x（p）：位置p的x坐标。

在打包过程中，我们使用上述适应度函数来选择前ff个矩形及其对应的候选位置。剩下的（n-ff）个矩形（及其相应的候选位置）是由稍微不同的适应度函数选择的，如下图所示：

3.1.1 Skyline representation of a packing pattern

常规天际线定义

3.1.2 Local waste 相邻浪费空间总量

第三个组成部分是相邻浪费空间的总量。这是根据下图中给出的四种类型的浪费空间总量计算得出的。设w_min和h_min分别为除r之外的其余矩形的最小宽度和高度。情况（a）中的阴影区域始终被视为浪费空间。如果间隙的长度小于w_min，则情况（b）和（c）中的阴影区域被认为是浪费的。最后，如果间隙小于h_min，情况（d）中的阴影区域将被浪费。这一规则的动机是自然的假设，即如果在过程的每个阶段都尽量减少浪费的空间，那么剩余的未放置矩形将更有可能被放置。

3.1.3 Fitness numbers 适应度

第四个组成部分是适应度。放置的适合度是矩形的边数，与它在天际线中所接触的线段完全匹配。如果矩形的宽度等于$s_j$的长度，则矩形的底侧是完全匹配的。如果矩形的高度等于$s_{j-1}$（分别为$s_{j+1}$）减去$s_j$的y坐标。矩形的任何与纸张左侧、右侧或底部接触的边都不被视为完全匹配，除非它填充了该边上的所有剩余空间。但是，当放置的矩形的上边缘接触到图纸的顶部时，这被视为完全匹配。适应度可以是0、1、2、3或4，如下图所示，其中每个矩形中的数字都是其适应度。这条规则支持这样的放置，即“更平滑”的天际线包含更少的线段，这更有可能允许放置更大的矩形，而不会浪费空间。

3.2 Squeeze operator

我们的ForcePack过程使用了一个称为Squeeze的邻域算子，如算法3所示。给定一个包含一些未打包矩形的解sol，该算子尝试将未打包矩形尽可能多地打包到使用的箱的某个子集B0中。

解sol可以用两个集合表示:集合B = (B1,B2，…，Bk)是使用的箱子的序列，集合R = {U,R1，…，Rk}是矩形的集合，其中Ri, i = 1，…，k是装入箱子Bi的矩形的集合，U是未装入的矩形的集合。

给定一个用过的箱子的子集B’∈B，挤压函数首先从sol中卸载B‘中的箱子中的所有矩形，并将它们追加到未打包的矩形集合集合U中，然后调用TabuPack算法将未打包的矩形尽可能多地打包到B’中的箱子中;禁忌搜索的迭代次数被设置为当前iter值或子问题中的矩形数量，两者取较低的值。然后将该sub-solution与solution重新结合并作为输出返回。

3.3 ForcePack subroutine

在对特定的ff值执行禁忌搜索之后，如果没有找到打包所有矩形的解，那么如果bestSol包含超过5个bin，则对为该ff值找到的最佳解bestSol执行一个名为ForcePack的过程。这个过程可以看作是一个局部搜索，其目标是将所有未打包的矩形打包到解决方案中的现有箱子中。

ForcePack过程由算法4给出。在迭代i中，我们考虑所有由一个bin Bi或两个bin (Bi和{B1，…，Bi-1}中的一个)组成的子问题。对于每个子问题，我们调用Squeeze过程。如果得到的solution较好，我们就保留它，否则就丢弃它。重复这个过程，直到所有的矩形都被包装好，或者所有的组合都被考虑过，但没有发现任何改进。

下图给出了ForcePack如何工作的例子。在下图a所示的初始解中，矩形r未填充。此时，我们可以用B‘ = (B1,B2)调用Squeeze运算符(下图b)。如果这是成功的，例如，如下图c所示，那么我们就有了一个包含所有矩形的解。

四、ImproveSol post-improvement procedure

当找到一个可行的解决方案sol(即，所有矩形都被打包在sol中的给定容器中)，我们使用一个称为improesol(算法5)的过程，它试图减少解决方案中使用的容器的面积。improveSol过程以相反的顺序考虑每个bin Bi，并调用DeleteOrReplaceOneBin过程尝试将Bi中的所有矩形打包到当前解决方案中使用的其他箱子中，或者用一个更小的箱子替换Bi。

在DeleteOrReplaceOneBin过程中，我们首先卸载Bi中的矩形，然后尝试将所有未打包的矩形尽可能多地打包到当前解决方案中使用的其他箱子中。如果所有的矩形都被填充了，那么我们成功地删除了Bi;否则，我们将尝试找到能够包含剩余未打包矩形的最小的箱子。

DeleteOrReplaceOneBin过程在算法5中给出。我们首先卸载bin Bi，然后尝试将解压缩的矩形装入其他每个bin Bj, j = 1，…，k, j - i。这是通过在由Bj组成的子问题上调用Squeeze过程来完成的。

如果解包装矩形的总面积因此减少，则继续使用该解进行搜索，否则丢弃它。

如果Bi中的所有矩形都被消除，我们返回这个解

然而，如果在考虑了所有的箱子Bj - Bi后，我们无法消除Bi中的所有矩形，那么我们将尝试将所有未打包的矩形装入尽可能小的箱子中。

如果我们成功地将解包装的矩形放入面积小于Bi的bin b中，我们将Bi替换为b并返回此解;否则，将返回原始解。

下图显示了DeleteOrReplaceOneBin过程的一个例子。给定当前bin Bi，我们首先解包Bi和B1(下图b)，然后尝试将这些矩形打包到B1中。如果剩下的矩形的面积减少了(如下图c所示)，那么我们继续这个解，否则我们丢弃它。该过程继续进行B2的开箱(下图d)，以此类推。如果Bi中的所有矩形最终都被打包到当前解决方案中使用的其他箱子中(下图e)，那么我们就成功地消除了Bi

五、Computing the lower bound

对于2DBPP，已有文献提出了几种下限测度。

六、Computational experiments

我们在2DBPP和2DVSBPP的现有基准测试数据上测试了我们的GDA方法。我们的算法是用C++编写的顺序算法，并使用GCC 4.1.2编译，没有使用显式多线程。我们的实验是在Intel Xeon E5430上进行的，它具有2.66千兆赫兹（四核）CPU和8千兆字节RAM，运行CentOS 5 linux操作系统。

6.1 Experiments for 2DBPP

对于2DBPP，我们在划分为10个类的500个标准基准测试实例上评估了我们的方法。Classes 1-6 由Berkey和Wang(1987)生成，Classes 7-10 由Lodi等人(1999)生成。每一类实例被进一步分为五组，每组由10个矩形数量相同的实例组成;五组中每个实例的矩形数量分别为20、40、60、80和100。所有的实例都可以在DEIS(2012)中找到。

结果表明，与现有的所有方法相比，GDA在10个类中有8个类平均找到了最佳或联合最佳解，其对所有类的平均利用率为723.4，优于其他所有方法。尽管GDA比现有方法的改进量很小(所有类总共只有两个箱子)，但2DBPP是一个经过充分研究的问题，改进变得越来越难实现。

6.2 Experiments for 2DVSBPP

6.3 Additional analysis

改进后的改进过程占用了GDA的大部分计算时间。只要找到可行解，它就会被调用，无论是通过TabuPack过程还是在计算2DVSBPP的下界时。为了评估improesol过程的有效性，我们使用PS类中的所有实例进行了一个额外的实验。我们不使用improesol程序就运行GDA，并将其与我们的原始版本进行比较。

结果如下图所示，图中绘制了这些实例的平均封装利用率。我们可以清楚地看到，在整个120秒内，带有improveSol的GDA优于未使用该版本的GDA。这种效果在前期迭代中最为明显，在2秒的计算时间内，平均区域利用率的差异超过2%。

七、Conclusions

• 在本文中，我们提出了一种目标驱动的方法来解决二维和变尺寸的仓包装问题。
• 这种方法背后的策略是对目标值执行多次二进制搜索，每次都使搜索工作量加倍。
• 我们的方法包括使用顺序装箱启发式的禁忌搜索，试图将所有未装箱矩形打包在一个接近可行的解决方案中的局部搜索，以及在可行解决方案中减少箱子数量或使用的箱子总面积的后改进过程。
• 我们还提出了2DVSBPP的一个新的下界测度。
• 在基准测试数据上的实验表明，就2DBPP和2DVSBPP的平均解决方案质量而言，我们得到的目标驱动方法(GDA)平均优于所有其他方法。