论文拾萃|利用GLAH算法解决集装箱翻箱问题

利用GLAH算法解决集装箱翻箱问题

前言

大家好呀，好久不见！

几个月前我们团队曾经介绍了集装箱翻箱问题的整数规划模型：

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

今天小编继续为大家介绍相关内容，关于利用改进的贪婪前瞻启发式解决CRP（container relocation problem）问题。本文的内容参考了深圳大学金波老师的论文。

问题描述

考虑了从一个港口中回收集装箱的问题。港口由编号为1，...，S的堆叠组成，每个堆叠都有T层。每个堆叠的高度s由h(s)表示，h(s)不得超过T层的高度上限。初始布局包含N个集装箱，它们属于G组，编号为1，...，G，每一组优先级相同，详细见后文。

根据上一篇推文，我们定义了以下几个术语：

1、block：堆叠在某一区域的同质化的物品，可以简单地看成一个个集装箱。

2、slot：在这一区域中，block可以放置的位置。

3、relocation：指的是在这一区域中的一个block的一次移动，即从一个slot移动到另一个slot。每一次relocation只能将一堆叠中最上层的block移动到另一个堆的上面，且移动后任何堆叠的高度都不能超过T。

4、retrieval：一次访问库存，相当于将区域中的一个block 拿到区域外的目的地中，如移动到卡车上等。

如图，每一格就是一个slot，每一个内部有数字的格子（也就是集装箱）就是一个block。将block从一个格子移动到另一个格子就是一次relocation，将block移出到库存中就是retrieval。

我们对不同的block的优先度进行排序，由1，...，N组成，其中1优先度最大。若CRP问题中，若一个优先度仅对应一个block，则被分为simplex instances。反之若可能对应多个block，则称为grouping instances。上图案例中的情况就是simplex instance。本文我们研究grouping instances。

在定义了优先度后，我们将relocation表示为

，其中C表示被移动的block的优先度，

表示该block从

堆的顶部移动到了

。我们将retrieval表示为

，与relocation的区别在于将block C从

移动到了最终目的地。

CRP问题的要求就是按照优先度依次将堆叠的blocks通过relocation和retrieval全部取出，要求relocation的次数最少。

算法介绍（Greedy look-ahead heuristic）

本文采用greedy look-ahead heuristic (GLAH)来解决CRP问题。

将GLAH算法分为三个层次:基于贪婪算法的循环机制（The greedy mechanism）、前向搜索（The look-ahead procedure）、启发式评价函数（The evaluation heuristic）。

GLAH的运行机制是：在顶层算法每一次循环中都调用中间层算法，在中间层算法的每一次循环中调用底层算法。最终随着顶层算法循环结束，得到最终的结果。

顶层算法：基于贪婪算法的循环机制

这一基于贪婪算法的循环机制相对其他两层并不复杂。其思想是一个循环：利用中间层的前向搜索得到并执行一步relocation。若执行后目标block（即当前优先度最大的block）已经处于堆叠的顶部则将该目标移动至目的地。一直执行该循环直到当前箱子被清空。

伪代码如下图。

其中，LowerBound函数表示在不深究如何重新摆放错误放置的集装箱的情况下，先计算要正确摆放所有箱子（使当前布局仅通过retrieval就能够将所有集装箱搬运至最终目的地）所需步骤数的下限，即假设当前处于最优情况，只需要一次relocation就能够永远解决一个防止错误的箱子。若当前解的数量加上计算所得的下限已经大于最优解的步骤数，则不用继续计算即可判断当前解非最优解。

中间层算法：前向搜索（The look-ahead procedure）

前向搜索的目的就是提供给顶层的贪婪算法一个relocation的建议。

为了方便在搜索的过程中进行筛选，将所有relocation分类成4类：Bad-Good(BG), Bad-Bad(BB), Good-Good(GG), Good-Bad(GB)。其中good指当前箱子的下方没有比它优先级更大的箱子，类似的，bad指当前箱子的下方有比它优先级更大的箱子。

为了研究移动是否高效，需要知道relocation是否有助于减少放置在比目标更高层的阻塞箱子的数量。因此我们将Bad-X relocation中成功使目标block处于该堆叠中最顶层的，标为freeing target (FT) Bad-X，而将没能成功将目标解放的移动，标为non-freeing target (NF) Bad-X。

因此总共可以将relocation分成6类：FT-BG, NF-BG, FT-BB, NF-BB, GG and GB。

也许有小伙伴会感到疑惑，为什么还要考虑GG、NF-BB、GB？这几类似乎并不能帮助我们整理箱子的位置，有的甚至是在捣乱，能够将原本Good的箱子变成Bad。

小编这里引用论文中的例子为大家解释一下它们各自的用处：

如图，移动<2:1→3>就是一个典型的GG relocation。假若只有三个堆叠（三列）可以放置箱子，当前目标是1号箱子，若直接移动1号上面的4号和5号，则在取走1号后又至少需要再移动一次4号和5号。因此此时的最优解是将号移动至堆叠3，为4、5号腾出空间。

类似地，在上例中，为了为7、8、9号箱子腾出位置，移动3号箱子，即<3:1→3>为GB移动。

同理，在上图中最优解先将3、4号箱子移开，为11、10、9、8号箱子移动提供空间。即<4:1→3>，为NF-BB relocation。

为了在各类中筛选出更有价值的relocation，我们对6类移动进行指标定义：

对于FT-BG和NT-BG，这两类移动将目标堆叠的最小优先度从原先的

变为被移动的箱子g(c)，因此我们将两者之差

作为一次移动的指标。我们希望最小优先度的变化越小越好，因为这意味着优先度相近的箱子被放在了一个堆叠上，且优先度最高的被放在了最上面，是较为理想的情况。根据这一指标对所有FT-BG和NT-BG的移动进行升序排列。

同理，对于FT-BB与NT-BB，仍然计算两优先度之间的差，但是由于这两类是BB relocation，移动后堆叠最上方的必定不是优先度最高的箱子，因此最小优先度并没有改变，仍然是

。因此指标定义为

。根据这一指标对所有FT-BB与NT-BB的移动进行升序排列。

对于GG relocation，不管是移动前还是移动后，被移动的箱子都是优先度最大的，因此我们比较两个堆叠除被移动箱子外的最小优先度：

。该指标应降序排序。同理对于GB，采用

的降序进行排序。

对所有relocation类别排序后，每个种类X都选取前

个relocation，将它们都归入relolist，若数量不足，则该种类全部选取。

中间层算法思想：

这是一个递归函数，每一次递归，搜索树深度（d）增加一层。为了防止搜索树在递归的过程中一直递归下去，造成时间和内存的浪费，我们对搜索树的深度做出限制。没有满足在搜索树深度还没有达到限制时（或箱子全部被清空前），对于每一个解对应的relolist中的所有relocation，均被看作不同的枝叶，为了充分利用目标箱子和目标s堆叠最小优先度之间的gap，故在执行X-Good(Good-Good或是Bad-Good)操作前，我们在第三层The evaluation heuristic过程中判断在执行relolist中relocation前，是否进行一步其他的操作（该操作未包含在当前relolist中），对未来的relocation有益，即可以有效减少relocation的次数，再将该操作加入到relolist中去，之后新的枝叶继续往下深度搜索。伪代码如下：

底层算法：启发式评价函数（The evaluation heuristic）

在中间层每一个枝丫发展到深度限制时，都需要调用底层的评价函数来最终确定那一步relocation是最优的，最终将最优的relocation输出到顶层算法中。底层算法就是大致评估一个叶子节点走到箱子全都被清空需要多少步，选取其中步数最短的作为最优relocation推荐给顶层算法。

底层算法思路如下：在每一步都确定一个紧急目标c*（当前目标优先度可能有多个箱子，因此要确定一个具体的紧急目标），然后在c∗上的所有放置错误（优先级比目标低）的箱子必须逐个执行relocation操作到特定的目的地堆叠。这样，c*就能够被顺利retrieval。接下来，继续确定下一个目标直到所有箱子被清空，计算其最终步数。

伪代码如下：

大致思路虽然简单，但是实际操作中还是有很多值得注意的地方。

首先，选取紧急目标c*时规定应当选取所有目标中上面block最少的箱子。

其次，那些处于紧急目标c*上方的放置错误的箱子最终会被放到哪里呢？我们分四种情况进行讨论。

情况一：若存在能够使箱子正确放置（使被移动箱子成为目标堆叠优先度最大）的堆叠，则选择其中最小优先度最小的。

情况二：若不存在能够使箱子正确放置的堆叠，我们考虑能否另外移动一个箱子为其腾出空间。

检查是否存在满足以下条件的堆栈s’及其顶部箱子c’:

1. 顶部箱子c’目前是堆栈s’中优先级最大的箱子

2. 存在一个堆叠

能够放置c’

3. 被移动的箱子c能够成为堆栈s’中优先级最大的箱子

在辅助堆栈

的帮助下，我们可以首先将c’从堆栈s’迁移到堆栈

，然后将c从原堆栈迁移到堆栈s’。

若存在这样的情况，则s’的选择由所有候选堆栈中顶部箱子优先级最小的堆栈决定，而辅助堆栈的选择由所有候选堆栈

中最小优先度最小的堆栈决定。

情况三：若以上两种情况都不存在，则要考虑用FT-BB来移动箱子c。假设堆叠s’为最小优先度最大的堆叠，若它满足以下条件：

1. 堆叠s’只有一个空的slot。

2. 被移动的箱子c不是该堆叠中优先度最小的。

若满足，则目标堆叠将被重新选择为最小优先度第二大的堆叠作为目标堆叠。

情况四：若以上情况都不满足，则直接选择最小优先度最大的堆叠作为移动的目标堆叠。

根据以上四种情况进行判定，就可以有规则地判定紧急目标c*上方的放置错误的箱子应该放在哪里。

以上就是GLAH算法的全部内容

GLAH算法

对于大规模实例来说是很好的求解方法

最后总结一下

GLAH是一个三层的启发式算法

-它的顶层遵循“贪婪机制”，在每个阶段都对当前布局执行一次relocation，直到箱子被清空。

-中间层，即“前向搜索”，用树搜索为顶层的算法提供relocation的建议。

-底层，制定一套启发式的移动规则，对中间层树的每一个叶子节点进行评估。

欲下载本文相关代码，请移步留言区

参考文献：

原论文：

[1] Solving the container relocation problem by an improved greedy look-ahead heuristic. Bo Jin,  Wenbin Zhu, Andrew Lim, European Journal of Operational Research 240,2015. Pages 837–847.

-The End-

文案：王思涵、朱正雄（华中科技大学管理学院本科二年级）

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

排版：程欣悦（荆楚理工学院本科四年级）

如对文中内容有疑问，欢迎交流。PS：部分资料来自网络。

如有需求，可以联系：

秦虎老师（华中科技大学管理学院，tigerqin1980@qq.com）

王思涵（华中科技大学管理学院本科二年级：2278159431@qq.com）

朱正雄（华中科技大学管理学院本科二年级：2627889552@qq.com）

程欣悦（荆楚理工学院本科四年级：1293900389@qq.com）

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

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