论文拾萃|带新下界算法和支配规则的精确式算法解决非限制性集装箱翻箱问题

1引言

对集装箱翻箱问题[Container Relocation Problem(CRP)/Block(s) Relocation Problem (BRP) ]的背景及问题描述，在以下这篇文章中已详细展开（只用看前言及问题描述部分）：

集装箱翻箱问题的整数规划模型系列一（BRP-Ⅰ、BRP-Ⅱ及代码）

本文同样遵循“允许retrieval和relocation操作同时发生”

BRP问题可以从两个角度上进行分类：

1. Block的优先级是否唯一（或取走箱子的顺序是否绝对唯一）？若是，则称之为唯一优先级(distinct priorities)；若不是,则称之为重复优先级(duplicate priorities)；
2. 是否只能移动当前最高优先级的block所在的堆的顶部的箱子？若是，则称之为限制性的(restricted)；若不是,则称之为非限制性的(unrestricted)；

可以看到，唯一优先级是重复优先级的特例，即每个优先级的block只有一个；限制性条件则是限制的加强。因此，能够解决重复优先级的问题就意味着能解决唯一优先级的问题，而非限制性的解空间包含了限制性的解空间，即其解不会比限制性的解差。

本文中的算法是针对重复优先级的非限制性问题而设计的，因此其同样适用于唯一优先级的非限制性问题。

2问题模型

将一个bay看作一个二维区域，用表示所有堆的集合，其中个堆从左到右编号为1,...,，层从下往上编号为1,...,。位于第堆、第层的存储空间称为。一开始，共个、编号为1,...,的集装箱分布在bay中，每个集装箱都有一个整数优先级，用表示。这些优先级在1到的范围内，所以这些集装箱可以划分到个优先级组中。优先级数目越小，优先级越高。

在取回箱子的过程中，每一种可能的集装箱摆放方式都称为一个布局(configuration)，用表示。对于一个给定的布局：

• 用表示堆的高度，即堆内集装箱的个数；
• 用表示布局内的集装箱数；
• 若内存在集装箱，则其优先级可以用表示；
• 用表示集装箱的质量(quality)，含义为堆的下面层中优先级的最小值，即；
• 假设，用表示堆的质量；
• 用表示箱子的“好坏”，若一个集装箱的优先级比它下面所有集装箱的优先级都高，即，则它是个“好箱子”，用表示；否则它是“坏箱子”，用表示。
• 用表示坏箱子的总数。

下文中，若考虑的布局是明显的，则省略“”

当前存在最高优先级的集装箱称为目标集装箱。如果目标集装箱位于堆的顶部，则可以被取走。相应地，在取走所有可以取走的集装箱后的布局为。如果布局没有可以取走的集装箱，则称它是最小化的。注意到立即取出可以取走的集装箱总是最优的，因此，我们假设只对最小化的布局移动箱子。

将集装箱从堆移到堆的移位操作可以表示为三联体。当且仅当：是最小化的、集装箱位于堆顶部、堆和堆不同且堆未满时，这个操作可行。对布局进行操作后的布局表示为。

对于任意给定的问题实例，我们总是以其最小化形式作为其初始布局。从初始布局开始，如果对任意，移位操作对和都可行，移位操作序列称为一条路径。一条将初始布局转化为空布局的路径称为一个解。CRP问题的目标即为找到移位操作数目最小的最优解。

根据以上定义，CRP的状态空间可以通过以下方式通过有向图建模：每个顶点对应一个可能的中间布局，每条边对应着对中间布局的移位操作和由此引起的取走操作。即从顶点向外的边将指向顶点。因此，解决CRP问题等价于在图中寻找从初始布局到空布局的最短路径。

3整体算法流程

伪代码如下：

如图，算法建立迭代加深搜索的框架之上。

其中，LowerBound是下界函数，用于评估布局所需的移位数的下界；Probe是启发式的探测函数，用于快速求得布局的较优解（包括第4行中的初始最优解），并以此作为其所需的移位数的上界。若下界与上界相等，则说明求得的上界所对应的解即为最优解。因此，在搜索的过程中，我们将不断提高下界、降低上界，从而找到最优解。

第8行中，Search函数是搜索函数值为下界的最优解的函数，是一种深度限制搜索。它的返回值是布尔变量，表示是否搜索到最优解，是在搜索过程中动态变化的当前最优解。如果没有能够搜索到，那就说明真正的下界会大于当前的下界，因此使自加1并再次进行搜索。

这种搜索方式结合了深度优先搜索和最佳优先搜索的特点，由于其限制了搜索的深度，因此相较于深度优先搜索占用的空间小，不会往一个方向过深地搜索；同时使用了优先队列，加快了实际运行过程中找到最优解和近似最优解的速度。缺点是每次搜索都从根节点开始，重复搜索会浪费一些时间。

4深度限制搜索

伪代码如下：

如图，函数的参数包括：到布局的路径、布局、下界和当前最优解。

首先，对布局的所有可行移位：

• 若移位后路径被支配规则剔除，则将其排除；
• 若移位后的布局为空布局，则移位后路径即为最优解；

支配规则共有11条，旨在避免相同或等价的布局被重复搜索，详见后文。

接着，用下界函数估计得到移位后的布局所需移位数的下界，并计算得到经过该节点达到目标的路径的函数值下界。

• 若，那么在当次搜索中便不会从这里往下搜索。
• 若，则将布局代入探测函数，并将得到的路径与合并得到较优解。若解优于当前最优解，则更新（上界）、并根据其函数值是否与相等，判断其是否为最优解。

此处的条件设置，一方面保证了每个节点只被探测函数计算一次，避免了重复计算，另一方面延后了计算，减少了不必要的计算。实验证明，对一个节点值的计算结果与其子节点的结果较为接近，这证明了延迟计算的合理性。

然后，将移位放入集合中。遍历完所有移位后，按照以下三个条件按字典顺序排序：

1. 较小的；
2. 较大的；
3. 较小的；

最后，按照顺序逐个搜索。递归过程

搜索层次如图：

“”区域：当前迭代中被探测（代入探测函数）的节点； 左下：搜索阈值每次迭代加1（迭代加深）； 右上：当前迭代中访问到的节点（分枝定界）； “”区域：当前迭代中没有访问到的节点；

5探测函数

探测函数通过启发式算法快速求得较优解，并以此动态更新上界。

采用的启发式算法有两个：JZW、SM-2。它们在与其他启发式算法相比有突出的优势，但二者之间在不同的算例上各有优势。鉴于启发式算法计算时间较短，因此让二者分别对同一个布局进行计算，取较优的结果。

6下界函数

下界函数通过对下界的估计，减少较差的节点的访问，提高求解速度。中心思想是通过快速求解松弛后的问题（除去某些约束后的问题）来估计下界，即实际函数值不可能比下界函数求得的差。

前文提到好箱子和坏箱子的概念。因为坏箱子下面有比它高优先级的箱子，所以坏箱子至少需要被移位一次。若坏箱子在移位一次后需要再次移位，则称再次移位为额外移位。对应的，对好箱子的所有移位都是额外移位。由此，布局的下界相当于坏箱子数加上额外的移位数。下面将通过一种寻找阻塞层的方式来估计额外的移位数。

虚拟层

虚拟层是个分别来自不同堆的集装箱组，用向量表示其由集装箱组成。如果没有一个集装箱属于多个虚拟层，则称这些虚拟层是不重叠的。

阻塞层

对虚拟层，若：

• 虚拟层中的最小优先级大于虚拟层的最小质量，即；
• 虚拟层中坏箱子的最小优先级大于虚拟层中层数小于的箱子的最大质量，即；

则这个虚拟层是一个阻塞层，至少需要一个额外移位。

第一个条件保证在取走虚拟层内的箱子前，必须被移位一次；若移动的是好箱子，则产生了额外移位；第二个条件保证移动坏箱子后，坏箱子仍然是坏箱子，即也会有额外移位。

如图，橙色框内是一个阻塞层：

若有个不重叠的阻塞层，则至少需要个额外移位。

接下来，我们将通过两种不同的方式寻找阻塞层。

层扫描方法(LB-TS)

层扫描方法严格地按照从高到低的顺序寻找阻塞层，这意味着层于层之间不会相交，一个找到的阻塞层会完全高过或低过另一个。

伪代码如下：

如图，初始虚拟层为。第9行在每一个堆处检验其是否满足阻塞层条件，若不满足，则将其层数减1并重新开始循环。若找到一个虚拟层，则下一次搜索从开始。当存在时，搜索结束。

这种搜索方式的时间复杂度为。由于其从上至下的搜索方式，以下情况中只能搜索到一个阻塞层：

因此，我们需要优先级扫描来解决这个问题。

优先级扫描方法(LB-PS)

伪代码如下：

为方便算法的描述，我们先引入两个概念。

对一个集装箱：

• 用表示其需求值。若这个集装箱是坏箱子，则；否则，。集装箱的需求值反映了其避免额外移位的难度。
• 用表示其资源值。若，则；否则，。集装箱的资源值反映了其支持其他箱子变为好箱子的能力。

由这两个概念，判定阻塞层的第二个条件可以改写为：对一个给定的虚拟层，其最小的需求值比其最大的资源值大，即。

优先级扫描方法来源于计算几何学中的扫描线算法。对每一个集装箱，都有一个左闭右开的区间。相应地，判定阻塞层的第二个条件等价于：对一个给定的虚拟层，对，区间相互重叠。我们可以用一条虚拟的扫描线来表示扫描的过程。

以上一节中Fig. 4的布局为例：

活跃集包含了所有区间被扫描线穿过的集装箱，即，因此从中取出的任意一个虚拟层必定满足判定阻塞层的第二个条件。等待集包含了所有没有扫描到的集装箱，初始时等待集包含所有集装箱。

每次迭代中，用表示中的最大资源值，用表示等待集中的最大需求值。对于空集，其最大值记为。

• 若，扫描线将停在，并将中需求值为的箱子移入。
• 若，扫描线将停在，先调用提取函数从提取出尽可能多的阻塞层，这些阻塞层的最大资源值等于；再将中资源值等于的箱子移除。

提取函数首先检查是否可以至少从选取来自每个堆的至少一个箱子。如果不能，则说明从中不能提取任何一个阻塞层，于是返回空值。

接着，计算辅助量，其意义为在每个堆上必定有属于的好箱子的质量大于，或在每个堆上必定有属于的坏箱子的质量不小于。在此基础上，我们定义集合。对任意的坏箱子，在中必有一个满足判定阻塞层的第一个条件的虚拟层。

由的定义，对任意，存在集装箱满足。这个不等式说明了是这些集装箱中质量最小的，而且其中的好箱子的质量严格大于。根据定义，一个虚拟层中最小质量的箱子是坏箱子符合判定阻塞层的第一个条件，因此虚拟层满足判定阻塞层的第一个条件。

我们选择中资源值最大的集装箱作为，因为这个集装箱会最先因为扫描线的移动而移出活跃集。如果多个箱子的资源值相同，我们可以任意选择，因为这样不会对后续过程造成任何影响。对在每一堆中的箱子，我们选择满足且资源值最大的箱子。当资源值相同时，优先选择好箱子，即最大的箱子。

最终，我们得到了一个同时满足两个判定阻塞层的条件的虚拟层。如果这个阻塞层中的最大资源值不等于，函数返回空值，将该层留给后续的迭代（等待更好的组合）；否则，函数返回该虚拟层。

继续以刚刚的布局为例，如下图：

• 第1~5次迭代中，扫描线轮流停留在,12,11,10和9处，此时活跃集 (1,1),(1,2),(1,3),(2,1),(3,1),(3,2),(3,3),(4,1),(4,3);
• 第6次迭代中，扫描线停留在处，一个阻塞层(1,1),(2,1),(3,1),(4,3)从中取出(如左下图)；接着，由于，集装箱(1,2)也被取出。此时活跃集 (1,3),(3,2),(3,3),(4,1);
• 第7~9次迭代中，扫描线轮流停留在,6和5处，此时活跃集 (1,3),(2,2),(2,3),(3,2),(3,3),(4,1),(4,2);
• 第10次迭代中，扫描线停留在处，另一个阻塞层(1,3),(2,3),(3,3),(4,2)从中取出(如有下图)；接着，由于，集装箱(2,2)也被取出。此时活跃集 (3,2),(4,1);
• 第11~13次迭代中，扫描线轮流停留在,2和1处，但没有识别到任何阻塞层。在这之后，活跃集变为空集。
• 所有箱子都扫描过后，算法终止。

这种搜索方式的时间复杂度为。

阻塞层的继承

虽然两种扫描方式的速度都已经足够快了，然而，在树搜索的过程中，我们需要在每个节点进行计算，导致数百万次下界函数的调用。注意到一次移位不会造成显著的布局变化，为了加快下界函数的计算，我们将重新利用父节点的计算结果。具体来说，我们将继承阻塞层，即除非阻塞层中的箱子被移位或取走，这个阻塞层不会被破坏。

回顾前文提到的深度限制搜索。对当前布局和由对当前布局可行的移位产生的它的一个子布局，它们之间的差别仅存在于被移位的箱子和被取走的箱子。因此，在布局中确定的阻塞层可以完全或部分在子布局中重新利用。

假设为在布局中确定的阻塞层的集合，存在以下两种情况：

• 如果被移位的箱子不属于任意中的阻塞层，根据判定阻塞层的第一个条件，在中的阻塞层的箱子不会被取走。因此，中的阻塞层仍是布局中不重叠的阻塞层。在这种情况下，我们定义；
• 如果被移位的箱子属于中的阻塞层，其他的中的阻塞层仍是布局中不重叠的阻塞层。在这种情况下，我们定义。

由此，在深度限制搜索中，对布局调用下界函数之前，我们可以先计算其“继承下界”。首先，如果已经超过搜索阈值，则这个分枝可以立即剪去。其次，根据定义，不重叠的虚拟层的数量受限于最矮的堆的层数。换言之，和都不超过。因此，若，那么可以看作是。在这两种情况下，下界函数都不需要被调用，从而可能在一定程度上提高了搜索的效率。

需要注意的是，在第二种情况下，对于优先级扫描方法，可能出现的情况（下届函数是启发式函数，不能确保搜索到所有的阻塞层）。由此，对继承阻塞层可以起到维持下界强度的作用。然而，如果使用层扫描办法，则不会出现这种情况。由于搜索过程是从上至下的，层扫描办法总是能从布局中识别相同数目的阻塞层，且层数不少于继承的阻塞层的数量。

7支配规则

在搜索的过程当中，有很多相同的顶点会被搜索到。一种避免重复访问相同节点的方法是使用缓存，但这种方法占用空间太大，与使用迭代加深搜索的初衷相悖。

因此，我们通过使用支配规则来判定并淘汰走向等价或非最优布局的路径。这些支配规则需要保持一致性，避免所有等价的情况被不同的支配规则淘汰，造成过度剪枝。

字典序支配规则

我们用来表示集装箱存在于布局中。对于移位操作，如果这个操作是可行的或，则称这个移位是容许的。实现一个容许的而不可行的操作不会对布局造成任何改变，即若,。

对应地，从初始布局开始（假设它是最小化的），如果对任意，移位操作对和都是容许的，移位操作序列称为一个容许序列。在实现一个容许序列的过程中，实际被执行的移位子序列称为其实际路径。

对于布局和布局，如果存在的一个排列，使得布局的堆的所有集装箱以相同的堆叠顺序存在于布局的堆中，则称布局是布局的一个子布局，用表示。在这种情况下，布局可能与布局等价，也可能是与布局的等价布局取走若干个集装箱后的布局。

对于容许序列和路径，若向量字典序上小于向量，则称字典序小于，用表示。

由此，对于一个给定的路径和容许序列，令和分别为和实现后的布局。若满足以下条件，则称路径被容许序列支配：

• 或

以下规则均对路径，沿该路径的布局分别用,...,表示，其中为初始布局。

传递移位规则

传递移位简单来说就是对同一个箱子的两次移位。若这两次移位合并为一次移位后没有实质性的影响，则存在传递移位的路径将被合并后的路径所支配。移位的合并发生在前后均可。类似地，若这两次移位最后的终点堆相同而中间堆不同，且中间堆的不同没有造成影响，则字典序大的路径将被淘汰。由此，有以下3条支配规则：

规则1：对路径，若存在整数满足以下条件，则该路径被淘汰：

规则2：对路径，若存在整数满足以下条件，则该路径被淘汰：

规则3：对路径，若存在整数和堆满足以下条件，则该路径被淘汰：

独立移位规则

独立移位简单来说就是两个不会互相影响且与其他移位互不影响的移位操作。若两条路径在不同位置含有相同的独立移位，除此之外完全相同，则字典序大的路径将被淘汰。由此，有以下支配规则：

规则4：对路径，若存在整数满足以下条件，则该路径被淘汰：

“取回”规则

如果在进行一个移位操作后，使得前面移位过的一个箱子可以被直接取走，且这个情形与前面的移位操作无关，那么前面的移位就显然是多余的。类似地，如果在进行一个移位操作后，使得前面移位过的一个箱子可以被直接取走，且这个情形与前面的移位操作有关，那么前面的移位中字典序大的将被淘汰。由此，有以下2条支配规则：

规则5：对路径，若存在整数满足以下条件，则该路径被淘汰：

规则6：对路径，若存在整数和堆满足以下条件，则该路径被淘汰：

空堆规则

当有多个空堆时，将箱子往任何一个空堆移位是等价的。因此在这种情况下，字典序大的路径将被淘汰。由此，有以下支配规则：

规则7：对路径，若存在整数和堆满足以下条件，则该路径被淘汰：

同组移位规则

这部分规则适用于含重复优先级的布局。

如果将一个箱子移位到某个堆后，将同组的另一个箱子补回了原来箱子的位置，在不产生其他影响的条件下，可以将两次移位合并为直接将后者移动到前者的目标堆。这样一来路径将变短，因此前面的路径应该被淘汰。同样地，合并可以视情况提前或延后进行。

类似地，如果将两个相同优先级的箱子分别从不同的堆移动到不同的堆，在不产生其他影响的条件下，可以交换两个箱子的初始堆或目标堆。在交换后字典序大的路径将被淘汰。

由此，有以下4条规则：

规则8：对路径，若存在整数满足以下条件，则该路径被淘汰：

规则9：对路径，若存在整数满足以下条件，则该路径被淘汰：

规则10：对路径，若存在整数满足以下条件，则该路径被淘汰：

规则11：对路径，若存在整数满足以下条件，则该路径被淘汰：

以上即为算法的全部内容，你看明白了吗？

本文源代码获暂不开放！！

参考文献：

原论文：

[1] An exact algorithm for the unrestricted container relocation problem with new lower bounds and dominance rules", Bo Jin*, Shunji Tanaka, European Journal of Operational Research, Available online 8 April 2022. https://doi.org/10.1016/j.ejor.2022.04.006

-The End-

文案&排版：吕其乐（华中科技大学管理学院本科一年级）

指导老师：秦虎老师 （华中科技大学管理学院）

如对文中内容有疑问，欢迎交流。PS：部分资料来自网络。 如有需求，可以联系： 秦虎老师（华中科技大学管理学院，微信号43340630） 吕其乐（华中科技大学管理学院本科一年级：1286550580@qq.com）

欢迎大家加入数据魔术师粉丝群，我们的活动将会通过粉丝群优先发布， 学习资料将通过粉丝群分享。

欲入群，请转发此文，然后扫描下方二维码联系数据魔术师小助手