论文拾萃|用带改进下界的Branch-and-Bound 算法求解Block Relocation Problem

用带改进下界的Branch-and-Bound 算法求解Block Relocation Problem

论文拾萃

原文：

[1]Shunji Tanaka and Kenta Takii "A Faster Branch-and-Bound Algorithm for the Block Relocation Problem." IEEE Transactions on Automation Science & Engineering, Volume 13, Issue 1, January 2016, Pages 181 - 190.

参考文献：

[2] K. H. Kim and G.-P. Hong, “A heuristic rule for relocating blocks,” Computers & Operations Research, Volume 33, Issue 4, April 2006, Pages 940-954.

[3] W. Zhu, H. Qin, A. Lim, and H. Zhang, “Iterative deepening A* algorithms for the container relocation problem,” IEEE Transactions on Automation Science & Engineering, Volume 9, Issue 4, October 2012, Pages 710–722.

The block relocation problem 简介

集装箱码头在物流链中发挥着重要的作用，它提供了一个集装箱的临时储存场所。通过船只、卡车或火车运到集装箱码头的集装箱被储存在集装箱堆场，它们被竖直堆放，形成几个堆垛（stacks）。在这个场景下，衍生出了三种常见的问题：

The container stacking problem：为了方便未来的取出操作，合理地确定blocks在码头的适当存储位置。例如，较重的集装箱应该被堆放在高层，因为它们在被装载上船时应该提前被取出且放置在低层。

The remarshalling and premarshalling problem：在blocks的存储位置确定后，考虑重新分配和预分配问题，在集装箱堆场内重新分配位置，为将来的取出操作做准备。

The block relocation problem：也叫container relocation problem，是为了找到一个最佳的操作顺序来按照给定的顺序从集装箱堆场取出block。

本文研究的是第三种问题。如图1所示，在集装箱堆场中，通常使用龙门吊车来移动block，龙门吊车只能移动最上面的block。当我们想从堆场中取出的block不在stack的顶部，那么就应该把它上面的集装箱移到其他stacks，再取出目标block。减少这种操作在集装箱运营决策中是至关重要的。因为起重机的吞吐量是影响整体效率的关键因素之一。

问题描述

考虑S个stacks（stack 1，…, stack s），其中最大高度不超过T。总共有N个大小相同的blocks，stack i 的block数量表示为

，即

stack i 的第j层放置的block标记为block（i,j），每个block有给定的检索优先权

为整数，

越小代表block（i，j）应该越先被取出，于是取出blocks的顺序已知。

为了按给定顺序取出集装箱，会进行以下两种操作：

1. Relocation:将stack i 的顶部block移动到stack j 的顶部。

2. Retrieval: 当前最高优先级且处于顶部的block被移除。

我们的目标是找到这两种操作的最佳序列操作的最佳序列，使所需操作的数量最小化。其中retrieval操作的次数一定等于block的数量，此问题为NP-hard问题。

对于取出blocks的优先级，则又可以划分为两类问题，即有不同优先权的问题和有重复优先权的问题。前者意味着唯一的取出顺序，而后者只规定了集合之间的优先级关系。在另一种问题分类中，受限问题表示只有包含下一个要取出的block的stack的最顶层block才是可重定位的，而在非限制问题中没有上述限制。

本文研究受限唯一优先级问题和受限重复优先级问题。图2可以帮助读者们更好地理解。

值得注意的是，在有重复优先级的限制性问题中，可能存在不止一个具有最高优先级的block，即下一个要取出的block不是唯一确定的。因此，我们假设一旦它被确定为下一个要取出的block，就不能改变，直到它被取出。

我们将stack i 中优先级最小（要最先被取出）的block看作stack i的优先级。

现有的下界（lower bound，简称LB）

文章的创新性之一在于提出了更快的分支定界算法，而其中最大的秘诀就是使用了更优化的lower bound。文章首先介绍了其他2篇文章提出的LB，再提出自己改进过后的LB。在这三篇文章中提出LB都是在前人的基础上进行优化的，因为找到更加严格的LB，可以使加快求解的速度。

A. Lower Bound by Kim and Hong

首先我们先定义一个概念，考虑block(i,j)，如果block(i,j)下方存在block(i,k)（1≤k≤j-1）使得

，那么为了先取出block(i,k)，block(i,j)至少需要被移动一次。在这种情况下，block(i,j)叫做blocking block，而LB1就是blocking blocks的数量。这种lower bound适用于两种优先级问题。

B. Lower Bounds by Zhu et al.

这篇文章改进了LB1。假设block(s,t)是目标block，需要计算在目标block上的

的LB。因为这些block为blocking blocks，因此他们必须被移动到其他stacks。如果其中的某个block(s,k)即使在relocated后还是blocking block，则在计算LB的时候就需要 2而不是 1。这种计算方式就定义为LB2。即LB1可以通过满足以下条件的

的数量来增加：

即在其他的高度没有达到T的stacks（这些stacks就是移动block时可选的目的地stack）中找到优先级最大的stack，如果block(s,t)的优先级大于该stack的优先级，则记录这些block的数量N。LB2 = LB1 N。

除了对目标block之上的blocks，通过对其他blocks应用同样的方式，可以进一步改善LB2。首先，像上述说明的那样计算LB2，再将这些blocks和目标block一起移除。然后确定新的目标block，并计算其上面的blocks的LB。这个过程重复进行，直到所有的block都被移除。通过将这些LB相加，我们得到一个LB3。

在图3中，blocking blocks有block(1,3) block(3,3)，因此LB1 = 2.计算LB2时，对当前的目标block(1,2)，他的blocking blocks为block(1,3)，因为block(1,3)在移动到stack 2或stack3后还是blocking block，于是可以计算他的lower bound为2（而不是在LB1中计算为1），于是在当前配置中，LB2为3。最后，因为其他的blocking block (3,3)的lower bound也是2，所以LB3 = LB2 1 = 4.

值得注意的是，LB3不适用于优先级重复问题，因为计算LB3的过程要求目标block唯一。

本文提出的LB4

A. Distinct Priorities问题的Lower Bound

由图4(a)计算可得，blocking blocks 为block(1,2) (1,3)，LB1 = 2；因为stack 2 的优先级为6，不满足条件（即block(1,2) (1,3)移动后不再是blocking block），所以LB2为2。然而，它没有考虑到因移动而引起的stack 2优先级的变化。如果block(1,3)像图4(b)那样移动，则stack 2 的优先级从6变到了3，则block(1，2)无论移动到stack2 还是 stack 3都仍然是blocking block。如果像图4(c)那样移动，block(1,3)移动后还是blocking block。于是在两种可能的情况中，在block(1,2)(1,3)中至少有一个block在移动后仍然是blocking block，因此LB2应该是3而不是2。从这个观察中我们可以看出，通过考虑目标block上方blocks的目标stacks的组合，有可能改善LB2，但是我们必须找到使移动后blocking blocks数量最小的组合。

由于列举这些情况很耗时，我们将提出一种更有效的算法来寻找最佳情况。

假设目标block是block(s,t)，我们将其上方的blocks按照一定的顺序移动，使移动后变成blocking blocks的数量最少。首先，我们松弛高度未达到上限的stacks的高度限制，即如果一开始这个stack中已经有T个blocks，那么这个stack就不能变成其他block移动后的目的地，但是其他的stacks可以容纳的blcoks数量不受限制。这样规定下的可以成为目的地的stacks表示为

。如果我们将

移动到

，且满足

, 于是

成为了blocking block，不影响

的优先级，而且这说明将

移动到其他的

将也是不改变他们的优先级的（因为我们会移动到优先级最大的stack），于是我们不需要列举出目的地stack，因为没有区别。如果将

移动到

，且满足

, 此时

不是blocking block，文章指出，此时我们只需要考虑满足

中

最小的stack作为目的地stack。这一点在原文中有详细证明，考虑篇幅限制这里就不再赘述。

通过定理可知，即使我们用下式来限制目标stack，也可以实现移动后的最小数量的blocking blocks。

所以在移动block时，我们只需要考虑以下两种情况：

在移动后还是blocking block，此时将

移动到候选stacks中任意一个都没有差别；

2. 当

成立，block(s, )在移动后不是blocking block，此时将

移动到

，且

更新为

。

对

都只需考虑上述两种情况，于是只需要列

种情况，比原来的

改进了许多。

在实践中，一般通过depth-first branch-and-bound algorithm来找到使blocking block最少的移动情况。计算搜索树中每个节点的lower bound的伪代码见图6和图7。

如果我们不只计算目标block上的blocks，而是像LB3改进LB2一样将上述方法应用在其他的blocks，就得到了LB4.

B. Duplicate Priorities问题的Lower Bound

LB3和LB4都不适用于Duplicate Priorities问题，但是在一个目标block集合中考虑所有可能的取出顺序又很费时间，所以作者用了一个简单的方法来使LB3和LB4都不适用于Duplicate Priorities问题，我们通过图8的例子来解释。

在图8(a)中，blocks的最高优先级是1，目标blocks集合是由三个block（1，2）、（2，3）和（2，1）组成。为了计算block（1，2）上方block（1，4）和（1，3）的lower bound，将图8(a)转换为图8(b)中所示，其中block(2, 3)和(2, 1)以及上方的block(2, 2)和(2, 4)被移除。同样地，将图8(a)转换为图8(c)来计算block(2, 3)上方的block(2, 4)的lower bound，其中block（1，2）以及块（1，3）和（1，4）被移除。此时不必要考虑block（2，1），因为它在block（2，3）下面。最后，图8(d)来计算block(2, 1)上方的block(2, 2)。然后，移除目标block集合中的所有blocks和它们上方的blocks。这个过程重复进行直到所有的block都被移除。此时LB3和LB4就可以以这种方式扩展到有重复优先级的问题，分别称为LB3e和LB4e。

Branch-and-Bound Algorithm

我们在上面几节中只是说明了如何计算LB4和LB4e，本节中来讲讲整个的Branch-and-Bound Algorithm。算法的思路如下：

1. 在初始配置中计算LB、UB（upper bound），令

2. 通过分支定界算法来寻找目标值不大于

的解。如果过程中发现更严格的上界，则更新UB

3. 如果

，则此时的解为最优解，停止算法。否则令

，并继续第1步

A. Branching

在本问题的分支定界算法搜索树中，一个节点的深度代表在移动k个block并取出尽可能多的blocks后得到的配置，它的子节点是通过为要移动的block选择一个可行的目标stack而生成。图9解释了分支的规则。

在这个例子中，有两种可能从根节点(A)生成，(A)通过将block(1, 2)移动到stack 2(B)或stack 3(C)。在B和C中，block（1，1）是可以取出的，而且在B中block（3，2）在block（1，1）取出之后也可被取出，于是应将这些可以被取出的block取出。对于有重复优先级的问题，当目标block还没有确定时，要移动的block不能被唯一地确定。在这种情况下，子节点是由首先固定目标block，然后将可移动的block移动到某个候选stack来生成的。在图9（b）的例子中，B是通过选择block（1，1）作为目标block，将block（1，2）移动到stack 3，然后取出block（1，1）生成的。C和D是通过选择block(2, 1)作为目标block，并将block(2, 3)移动到stack1(C)或stack 3(D)生成的。

分支是以深度优先的方式进行的。

B. Lower Bounding

在搜索树的每个节点上，都会计算出相应的lower bound。如果