@[toc]

论文来源：（2022）A goal-driven ruin and recreate heuristic for the 2D variable-sized bin packing problem with guillotine constraints
作者：Gardeyn 等人

一、Abstract 摘要

• 本文讨论了具有一刀切约束的二维装箱问题。该问题需要从更大的矩形（称为箱）中切割一组矩形项目，同时只使用边到边（一刀切）切割。目标是尽量减少切割所有所需物品所需的总箱面积。
• 本文还讨论了允许90° 物品的旋转和/或一组不同的箱子。提出了一种新的启发式方法，该方法基于破坏和重建范式，结合目标驱动方法。
• 当将所提出的启发式算法应用于文献中的基准实例时，它在所考虑问题的所有变体的解决质量方面优于当前最先进的算法。

二、Introduction 介绍

此处省略超级多字。。。（常规二维装箱问题和一刀切约束的介绍，有兴趣可以看看原文~）

三、Solution representation 解决方案的表示

如图2所示，每个切割方案都表示为根树。树由三种不同类型的节点组成。有项目（深灰色）、剩余（浅灰色）和结构节点（白色）。

叶子总是项目或剩余节点。所有非叶节点以分层方式定义切割图案的结构，并表示为垂直（V）或水平（H）。节点的方向对应于其子节点的切割方向。该方向对于级别的每个节点都是相同的，并且每个新级别与上一级别相比都会切换方向。

正如Fleszar（2013）所指出的，这种表示方式始终满足一刀切的约束，从不允许项目重叠。

注意，数据结构没有定义任何坐标。它只描述了物品和剩余的相对位置。与由一组物品及其位置定义切割模式的刚性结构相比，这种树形数据结构可以更简单地插入或移除物品（或物品组）。

正如Gilmore&Gomory（1965）首次描述的那样，在现实世界场景中，可能的阶段的数量通常是有限的。一个阶段包括一个或多个水平或垂直切割，但绝不是两者的混合。从一个阶段到另一个阶段需要旋转切割方向。因此，级数表示切割图案所需的叶片旋转次数。在该表示中，由于切割方向在每个级别都进行了切换，因此每个级别表示一个阶段。虽然不是本文的重点，但限制此数据结构中的阶段数只需要定义树的最大深度。

由于启发式的性质，需要能够表示不完整的解决方案。

因此，解S={C，E}不仅包含一组切割方案C（已打包的项目），还包含一组排除项E（未打包的项目）。如果包含所有项（E=∅ ).

四、Ruin and recreate heuristic 破坏和重建启发式

图3提供了启发式的高级概述。在本地搜索的每次迭代中，解决方案都会被部分破坏并重建，以寻求改进。每次找到新的有限解时，都会减少仓面积限制。

第4.1节讨论了这背后的总体思路。第4.2节和第4.3节详细解释了破产和重建程序。之后，对修改后的解决方案进行了评估，并有可能被接受。第4.4节涵盖了这一点。整个过程将重复进行，直到达到给定的时间限制。

4.1 Goal-driven approach 目标驱动方法

在2BP中，解决方案的质量取决于包装所有物品所需的箱子面积之和。由于问题的性质，导致相同总箱面积的所有可行解决方案被视为质量相等。这意味着一旦找到了具有一定总箱面积的完整解，则对具有相等（或更大）总箱区域的解不再感兴趣。

Wei等人（2013）提出了一种目标驱动方法（GDA），用于具有可变尺寸料仓的2BP。它生成总面积介于下限和上限之间的所有组合箱，按面积对其进行排序，并尝试找到产生可行解决方案的最佳组合。使用二进制搜索遍历排序列表。在每次迭代中，GDA启发式必须使用特定的箱组合。虽然这种特殊的算法不包含断头台约束，但一般的想法是适用的。

与GDA类似，提议的方法也可以被视为目标驱动。

重建阶段，负责重建被破坏的解决方案，必须遵守一定的存储箱面积限制。只有当容器的总箱面积低于此阈值时，才能打开新箱。因此，在大多数情况下，重新创建阶段将无法将所有项目放入可用的存储箱，并将产生不可行的解决方案。成本函数将启发式方法引导到能够适合所有项目的解决方案。

图4表示了一段时间内启发式的一个可能过程。在任何时候，目标都是找到一套能够包装所有物品的切割方案，总箱面积低于当前限制。每当找到一个新的可行解（用 “f” 表示）时，就将限制降低到该新解的总箱面积。在第4节末尾的算法3中给出了完整GDRR启发式算法的形式化描述以及箱面积限制是如何收紧的。

与Wei等人（2013）不同，搜索并非每次都从头开始，而是在再次满足箱面积约束之前销毁解决方案。因此，当限制降低时，可以保留以前解决方案中的高质量方案。这可以节省大量的计算时间。然而，当解决方案已经紧密堆积时，启发式算法可能更容易陷入局部最优。

另一个区别在于可用容器的组合。GDA试图用固定的箱组合做出可行的解决方案。相比之下，GDRR可以自由使用根据成本函数产生良好结果的任何组合。GDRR只需要确保总箱面积低于当前限制。此外，有时可能会发生这样的情况，即对于箱a的组合有可行的解决方案，但对于箱B的组合却没有可行的解决办法，尽管a的总箱面积小于B。这种情况最常见于包含小箱（每个箱很少有物品）或具有极端尺寸的物品的情况。由于GDA的二分搜索性质，这些组合可能无法访问。

应该清楚的是，根据设计，启发式方法大部分时间都会处理不可行的解决方案。起初，这可能会适得其反，但与将容器面积纳入成本函数相比，这种策略有两大优势。

• 首先，解决方案中未包含的项在每次迭代时都有新的机会被插入。这大大增加了找到更好解决方案的可能性。如果不是这样的话，就不太可能用更少的料仓面积达成完整的解决方案，尤其是在切割模式复杂的情况下。
• 其次，如图4所示，排除项目的总面积可以作为解决方案质量的一个非常渐进的指标。这与使用容器面积作为成本因素时的突然下降形成鲜明对比。

总之，尽管所提出的启发式方法也是目标驱动的，但它与Wei等人（2013）提出的方法有着显著的不同。他们只是在某种程度上限制了箱的使用。

4.2 Ruin 破坏过程

破坏程序从解决方案中删除了许多节点。所有项目和结构节点都是要删除的候选节点。遗留的节点不合格，因为删除它们不会产生任何影响。它们只能在删除父节点后删除。

图5显示了节点移除的三种情况。这些图说明了移除节点之前（左侧）和之后（右侧）的情况。在每个示例中，带有粗体边的节点都是选择删除的节点。

在第一个示例中，删除了包含项3的节点。结果，剩余节点被扩展为已释放空间的ac-count。

在第二个示例中，删除了第一级结构节点。这导致项目2和项目3被重新移动，因为它们是孩子。

最后一个示例显示了要删除的根节点。这将导致整个切割方案被移除。应该清楚的是，单个移除的影响可以从单个项目到整个切割方案。结构节点离树的根越近，移除它的影响就越大。

允许移除结构节点有两个主要动机。

• 首先，移除这些节点会产生大面积的相邻剩余空间。这反过来又为重建阶段提供了更多的灵活性，从而产生了不同的相邻解决方案。
• 第二个主要优势在于，一些被移除的物品很可能会在其他位置再次形成良好的方案。例如，在第二个示例中，项目2和3可能再次形成紧凑的图案，因为它们共享相同的宽度。这在搜索的后期尤其明显，此时解决方案的质量已经相当好。可以将其视为相关移除的一种形式。

然而，严重破坏解决方案会阻碍找到更好解决方案的机会。过于频繁地彻底破坏解决方案会导致大量时间浪费。因为影响最大的节点最接近树根，所以与树底部影响较小的节点相比，它们的数量较少。由于破坏法随机选择节点，具有重大影响的破坏发生的可能性较低（因为靠近根节点的节点数较少）。这可以看作是一种内置的平衡机制。

算法1提供了破坏阶段的伪代码。

• 要删除的节点数量 $i$ 是均匀随机化的（∈ R），并在μ处取平均值（第3行）。
• 在删除i个节点或修改后的解决方案的总箱面积超过箱面积限制 $A_{lim}$（第4行）之前，程序将继续破坏。
• 对于每次移除，随机均匀地选择切割方案 $c$（第5行）。
• 从 $c$ 中选择随机项或结构节点 $n$ （第6行和第7行）。
• 此节点从 $c$ 中删除，生成 $c'$ （第8行和第9行）。
• 最后，与修改的解决方案 $S'$ 更新（第10-13行）。

4.3 Recreate 重建过程

在重建阶段，需要重建（被破坏的）解决方案。这是通过将项目插入到剩余节点或新的容器中来完成的。当然，由于箱子面积的限制，很难插入所有物品。

算法2为重新创建阶段提供伪代码。在此阶段，所有当前排除的项目都有机会插入解决方案（第3行和第4行）。集合~E对应于所有尚未获得插入机会的项目。在每次迭代中，最受限制的项被选择为下一个插入候选项（第5行）。项目的限制性取决于其可能插入位置的数量：可插入的位置数量越多，限制就越小。

当多个项目被视为受到同等限制时，选择一个随机项目。除了如何计算成本外，第4.3.1节还提供了插入选项的定义。

对于所选项目emr，所有插入选项被生成（第6行）。如果没有可用选项（第7行），则尝试打开新的容器（第8–12行）。只有不会导致超出箱柜面积限制 $A_{lim}$ 的箱柜才可取（第8行和第9行）。

如果可能，将使用随机可取的箱创建新的空切割方案（第10行和第11行），并更新插入选项集（第12行）。如果可以插入项目（第13行），则评估所有选项（第14行），最终将项目插入解决方案（第15–18行）。大多数时候，最划算的选择是以贪婪的方式选择的，但有时最好的选择会被忽略。

眨眼的概念在第4.3.2节中进行了解释。无论是否成功插入，项目emr都将从~E中删除，因为它现在有机会插入（第19行）。一旦每个项目都有机会插入，重新创建的解决方案 $S'$ 返回（第20行）。

4.3.1 Insertion options 插入选项

插入选项定义了如何准确地将项插入到剩余节点中。如果允许90°旋转，则每个项目有两个可能的方向。由于断头台约束，剩余节点中项目的每个可行方向又会根据第一次切割的方向（垂直或水平）生成两个插入选项。因此，最多有四种不同的方式将项目插入到剩余节点中。这四种可能性的示例如图6所示。对于每一个排除的项目，都会考虑能够适合该项目的所有剩余节点（剩余空间）。

所有插入选项都有相关成本。该成本被用作期望合理性的度量，并使用等式（1）计算。插入项目不仅消耗现有的剩余节点，还生成新的节点。插入选项的成本与插入前后总剩余价值的差异相对应。因此，每个剩余节点具有相应的值（等式（2）），其目的是最小化由插入引起的值损失。

$n^u_o$：插入选项o使用的剩余节点

$N^c_o$：由插入选项o创建的剩余节点集

$\alpha$：剩余面积值指数

如等式（2）所示，剩余节点的值相对于面积呈多项式增加。这是为了鼓励启发式方法保留较大的相邻剩余区域，而不是许多较小的区域。一般来说，将项目打包到少数但更大的剩余节点中比打包许多小节点更容易。在图6中，选项（b）的成本最低，因为它保留了最大的剩余价值。

指数α的值对算法的行为有影响，因为它定义了插入选项的顺序。将此值设置得太大可能会导致创建非常少的大小合适的剩余区域。它将忽略许多中型遗留节点，而只关心少数大型节点。另一方面，将α值设置得太小可能会对预处理的大型剩余区域有害。

4.3.2 Blinks 眨眼策略

总是选择最佳选项将导致决定性的重建阶段，并可能导致一次又一次做出同样的错误决定。为了解决这个问题，有时需要对插入选项视而不见。眨眼的概念最早由Christiaens&Vanden Berghe（2020）以最先进的启发式方法引入，用于解决车辆路线问题。然而，一般的想法也适用于这里。

在纯最佳拟合中，始终选择最佳选项。但随着眨眼，一个选项被忽略的可能性很小。眨眼率β定义了跳过选项的可能性。等式（3）显示了根据其等级 r 选择选项的可能性。例如，β值为0.05意味着每个选项被忽略的可能性为5%。

眨眼表现出与Bresina（1996）引入的具有指数偏差函数的启发式有偏随机抽样相同的行为。然而，正如Christiaens&Vanden Berghe（2020）所指出的，眨眼更有效，因为它不需要根据选项的适合程度对选项进行排序。

4.4 Evaluation 评估

在每次破坏和重新创建迭代之后，需要对解决方案进行评估。这是通过确定问题解决方案的质量来实现的，如第4.4.1节所述。基于此质量，使用第4.4.2节所述的“延迟接受-爬山”元启发式方法来接受或拒绝解决方案。

4.4.1 Solution quality 解决方案质量

由于箱面积限制，重新创建阶段很可能无法将所有项目合并到解决方案中。因此，目标是引导启发式方法找到可行的解决方案。等式（4）描述了两个解决方案如何相互比较。

$E_S$：解决方案S中排除项的集合

$N^l_S$：解决方案S中C中切割模式的剩余节点集

如果排除了较少的项目区域，则解决方案总是更好的。如果两个解决方案包含相同的项目区域，则总剩余价值最高的方案更为优越。因此，剩余价值可以被视为解决方案评估中的决定性因素。注意，尽管目标是最小化总仓面积，但成本函数中并未明确包含该因素。只要垃圾箱总面积低于限制，它就无关紧要。如第4.1节所述，每次达到新的可行解决方案时，限制都会降低。

4.4.2 Late acceptance Hill–Climbing 延迟接受爬山算法

GDRR采用Burke&Bykov（2017）引入的延迟接受爬山（LAHC）元启发式算法。当候选解决方案在一定数量的迭代之前优于最佳解决方案时，该局部搜索算法接受非改进移动。算法3中的伪代码显示了如何实现LAHC。

使用LAHC的主要论点是其规模独立性。鉴于LAHC对目标函数的规模不敏感，元启发式不需要在特定实例的基础上进行调整。这是与使用冷却方案（如模拟退火）的元启发式相比的一个主要优势。

此外，由于解决方案是基于其相对于先前解决方案的优先级来接受的，因此不需要绝对的成本差异。唯一的要求是能够比较两种成本。不需要增量值。这允许轻松使用牵线器，例如第4.4.1节中概述的牵线器。在牵线器中，包含的项目面积始终占剩余价值的主导地位。

使用LAHC的最后一个论点是只有一个参数需要调整：历史长度（$L_h$）。此参数定义评估解决方案时要向后看的距离。

算法3提供了GDRR的高级概述。如第4.1节所述，启发式将不断尝试将所有物品放入箱子，同时遵守箱子面积限制。每当启发式方法能够构造可行的解决方案时，该限制就会降低。

LAHC适应度阵列最初完全填充了启动解决方案（第2行）。此阵列跟踪最后一个 $L_h$ 最佳解决方案。在每次局部搜索迭代过程中，根据第4.2节和第4.3节中描述的程序，解决方案被部分破坏和重建（第6行和第7行）。索引 $v$ 对应于适应度数组中第一个元素的索引。每次接受新的解决方案时，不必移动适应度阵列的所有元素，而是移动阵列的头部（第8行）。这类似于循环缓冲区的工作方式。为了获得修改的解决方案（$S'$）要被接受，它必须优于或等于L h迭代前的最佳解（$S_v$），或改进局部最优解（$S^*$) （第9行和第10行）。仅使用改进值更新适应度数组（第11行和第12行）。LAHC的实施与Burke&Bykov（2017）中概述的类似，但有一个主要例外。计数器i仅在接受解决方案时递增（第13行）。这与Burke和Bykov的原始LAHC形成对比，其中计数器始终递增。这个决定背后的主要动机是避免启发式算法在后期成为纯粹的爬山算法，从而容易陷入局部最优。

如果获得的解决方案没有排除项目（第14行），GDRR已达到其当前目标。当出现这种情况时，更新最佳完整解决方案 $S_{best}$（第15行），即新的箱面积限制 $A'_{lim}$ 是根据 $S_{best}$ 的总箱面积计算的（第16行），并创建下一个目标 $S_{next}$ 的起始解决方案，该解决方案符合新的限制（第17行）。最后，GDRR被“重启”下一个目标（第18行）。一旦满足停止标准，则返回最佳完整解决方案（第19行）。

从本质上讲，启发式算法不断地通过迭代降低箱面积限制来寻求可行性。为了启动优化，可以使用空 $S$（无切割模式和排除所有项目）调用算法3，并将$A_{lim}$设置为∞ . 不需要单独的算法来创建初始解决方案。

4.5 Multithreading 多线程（增加结果多样性）

多线程可以帮助提高启发式算法的性能，并利用现代处理器的功能。每个线程都运行自己单独的GDRR实例，但所有线程共享一个全局bin区域限制。这意味着一旦一个线程达到可行的解决方案，所有线程的限制都会降低。相反，解决方案本身并不在线程之间共享。这主要是为了保持多样性。

多线程实现在很大程度上类似于算法3。唯一的主要区别是，当启发式算法达到可行的解决方案时（第12–14行），而且当任何线程达到当前极限的可行解决方案时，bin区域限制都会降低。不用说，所有线程中最好的可行解决方案都被保存了。

线程几乎是完全独立的，只会间接地相互影响。例如，没有明确的机制来避免重复搜索区域。由于巨大的搜索空间和包含大量随机元素（例如眨眼）的启发式，因此不需要这样的机制。

多线程主要用于保持多样性，而不一定是为了加快执行速度。多线程的使用对于具有许多不同容器的实例尤其有益。在优化的后期阶段，解决方案往往过于固定，无法显著改变所用垃圾箱的组合。多线程有助于解决这一问题，因为不同的线程可以有质量相近的解决方案，但由非常不同的箱组合组成。只有一个线程很难实现这种多样性，因为它需要非常极端的破坏过程。

五、Computational results

为了评估GDRR的性能，在文献中的多个不同基准上测试了该算法。这些基准包含具有相同和不同箱集的数据集。Oliveira、Gamboa和Silva（2019）为文献中的大量切割和打包数据集提供了中央存储库。存储库中包含的所有数据集都采用相同的结构，这在跨多个不同基准测试时节省了大量时间。

5.1 Parameters

GDRR有许多必须配置的参数。这些参数的调整是使用Ortmann等人（2010）的数据集进行的。之所以选择此数据集，是因为它包含大量实例并具有可变大小的箱。

异构仓使解决方案质量的逐步提高变得可见。当优化600秒和8个线程时，所有参数都经过优化以获得最佳结果。参数是固定的，并且一个接一个地变化，以检查它们对算法行为的单独影响。然而，历史长度（$L_h$）和移除节点的平均数量（μ）作为一对进行了调整，因为它们之间的关系非常密切。在整个实验中使用以下参数：

5.2 Results for 2BP|O|G

为了比较2BP的GDRR性能，使用了Berkey&Wang（1987）（1-6级）和Lodi等人（1999）（7-10级）的著名实例，该2BP具有锯齿形切割和无旋转项目。每个类有10个实例，分别为20、40、60、80和10个0项。因此，数据集总共包含500个实例。

六、Conclusion

本文介绍了GDRR，这是一种启发式方法，用于解决具有剪切机约束的二维料仓包装问题。问题的变体，具有一组异质箱（可变大小）和90° 还支持项目的循环。启发式包含一个破坏和重建过程，该过程反复尝试改进解决方案。搜索可以被描述为目标驱动的，因为它不断努力创建可行的解决方案，并不断减少可用存储箱面积的限制。为了避免局部最优，GDRR采用了晚期接受山-攀登元启发式。与此问题的大多数其他启发式方法不同，重点主要在于改进阶段，而不是建设性方面。它能够在文献中的几个基准中始终产生解决方案质量方面的最佳结果。

未来的研究可能包括探索没有断头台约束的2BP变体以及具有现实世界约束的其他切割和包装问题。最后，调查目标驱动方法在其他类型问题中的适用性也是很有意思的。