一、《基于混合遗传算法的多箱型集装箱装载问题研究》张长勇

本文以实际问题——航空器货物装载为切入点，研究了遗传算法在航空装载问题中的有效性。

1、问题定义：

多箱型集装箱装载问题：

二、《OPTIMIZING THREE-DIMENSIONAL BIN PACKING THROUGH SIMULATION》

这篇文章的发表于2006年，但是它的方法还是比较经典的。文章本身写得确实不咋地，初看的话有些晦涩，因为它很多的方法和细节都没有详细阐述，默认读者是明白的。这种先入为主的写作思想，对于读者来说简直是噩梦。

1、研究问题

文章直接假设物品和容器均为长方体，选取若干的容器装载物品，使得每一个容器的体积利用率最大。在这里，我解读为，物品总体积/使用容器总体积 这个值最小即可。

2、假设条件

（1）物品和容器均为正方体

（2）物品和容器平行装载

（3）物品可以在六个方向随意旋转

需要指出的是，这里没有考虑的限制有很多，比如重心限制，承重限制等

3、约束条件

（1）总重量：每个箱子的载重量有限

（2）大小：放置的所有物品大小不能超过箱子本身

（3）交叉：不同物品间不能交叉放置

4、解决方法

Best Fit

（1）以体积大小为标准，对items和bins做排序。初始放置点为（0，0，0）。

（2）第一个物品放置完毕后，之后每放置一个物品，首先生成一个可放置点，具体方法是：根据上一个物品的放置点，我们可以按照width，depth，height三个方向新生成三个可放置点，这里并不保存，只是选择其中的一个作为可放置点。然后穷尽6个方向放置物品，直到物品可以被放进去。

（3）如果在三个方向上生成的可放置点上都无法将箱子放进去，那么就将该物品放入unfitted items中，先将其他箱子处理完，再来处理该箱子。

3D First Fit Decreasing 

（1）该算法尽量让物品和最长边贴着箱子的最长边放置。比如一个箱子为10X9X8，即width是最长的。有一个物品规格为1X2X3，那么就使其旋转变成3X2X1（或3X1X2），使最长边贴着箱子的最长边放置。

（2）初始阶段，按照箱子width、height、depth的大小顺序，对装载的物品做一个递减排序。比如箱子箱子是10X9X8，即width>height>depth，那么箱子就要按照宽带、长度、深度递减的顺序排列。

（3）假设3X2X1无法放置到箱子，那么再次旋转使其变成2X3X1（或2X1X3），使其第二长边对应箱子放置，以此类推。

作者没有给出该方法的伪代码，有效性和算法的优劣性暂无结论。而且这个也只适用于单个箱子装载物品的场景，当有多个种类和规格不同的箱子进行装载的时候，这个方法没有很方便。

5、实验分析部分

实验分析部分并未给出对比，仅仅做了可视化实验。

三、Issues in the to Development of Approaches Container Loading

这篇文章几乎会被后来的每篇三维装箱主题文章引用，因为它给出了这个领域的标准数据集，并沿用至今。同时，给出了数据集生成算法，以及统一的问题定义，方便后来的学者继续做研究。

数据集链接

研究背景

作者对箱子进行了分类。按照箱子的种类和数量的多少，将装箱问题分为强异构型问题和弱异构型问题。当时的算法，很大程度上取决于问题是强异构类型还是弱异构类型，这个很影响算法的效果。因此，作者想找到一种结合的方法，却解决这个问题。

问题定义：

简单来说，就是给定单个容器和一系列尺寸不一一定数量的箱子，要找到一个恰当的装载方式，使得容器的容积利用率最大。注意，这里并不是要所有物品都被装进去，而是要用算法选定一定的物品进行装载，使得容器的容积利用率最大。

约束条件：

（1）箱子之间不能重叠。（2）方向约束。width、height和depth是否能作为垂直方向的长度。

（3）承载约束。要考虑到箱子单位面积能够承受的重量。

（4）物品放置顺序的约束。比如重的物品要放在地板上，或者不能放太高，方便搬运和卸载。

（5）承载的稳定性。确保货物在运输过程中不能剧烈移动。

（6）物品分组限制。把相同的物品分为一组，放在一起，方便搬运和卸货。

（7）多次卸载限制。货物可能有不同的卸货地点，先卸货的后装载，后卸货的先装载。

（8）货物之间的分离。有一些货物不能放在一起，比如说化学品和食物

（9）完整的物品搬运。（还不太明白）

（10）货物运输的优先级。

（11）装载方法不能过于复杂，这样会导致更大的工作量。

（12）集装箱重量限制

（13）重心限制。整个容器的重心要尽量接近它的几何重心。

以上~会继续更新

四、领域搜索

在三维装箱问题中，启发式算法产生新解的方式：

《三维装箱问题的组合启发式算法》

（1）改变两类箱子的装填顺序

（2）交换某类箱子的任意两个尺寸

《A novel hybrid tabu search approach to container loading》

（1）交换任意两个解在集装箱中的位置

五、Loading pallets with non-identical items 

1、解决的问题

托盘是一个装载货物的器械，和航空装载的ULD类似。给定一定数量，不同种类的物品，要求找到一个装载方案，让物体放置在托盘中，从而最大化托盘的空间利用率。

2、与集装箱装载问题的不同

本文使用的是分层装载的思想

但文章中对“层”的定义描述不清晰