2022202210117 吴梦洁

物流公司在流通过程中，需要将打包完毕的箱子装入到一个货车的车厢中，为了提高物流效率，需要将车厢尽量填满。

设车厢为长方形，其长宽高分别为L，W，H；共有n个箱子，箱子也为长方形，第i个箱子的长宽高为li，wi，hi（n个箱子的体积总和是要远远大于车厢的体积），做以下假设和要求：

1. 长方形的车厢共有8个角，并设靠近驾驶室并位于下端的一个角的坐标为（0,0,0），车厢共6个面，其中长的4个面，以及靠近驾驶室的面是封闭的，只有一个面是开着的，用于工人搬运箱子；

2. 需要计算出每个箱子在车厢中的坐标，即每个箱子摆放后，其和车厢坐标为（0,0,0）的角相对应的角在车厢中的坐标，并计算车厢的填充率。

基础部分：

• 所有的参数为整数；

• 静态装箱

• 所有的箱子全部平放，即箱子的最大面朝下摆放；

• 算法时间不做严格要求，只要1天内得出结果都可。

高级部分：

• 参数考虑小数点后两位；

• 实现在线算法，也就是箱子是按照随机顺序到达，先到达先摆放；

• 需要考虑箱子的摆放顺序，即箱子是从内到外，从下向上的摆放顺序；

• 因箱子共有3个不同的面，所有每个箱子有3种不同的摆放状态；

• 算法需要实时得出结果，即算法时间小于等于2秒。

额外功能

• 可视化装箱

传统的从左下最深处开始装箱的Deepest Bottom Left with fill（DBLF）启发式方法总是寻找具有最小x（最深）坐标的空间来放置当前箱子，它使用z（底部）和y（左）坐标依次作为排序标准。这种启发式有两个缺点：第一，只有一个坐标轴(x)在选择候选空间中起主导作用；其次，箱子或空间被首先确定，然后根据特定的优先级规则选择对应项。

本项目采用启发式方法，找到近似解。启发式装箱过程利用最大空余空间的概念来管理箱子中的自由空间，并根据匹配标准选择箱子的位置。

• 6种箱子摆放方向方向

• 6种箱子位置关系

• 4种限制条件

  • 箱子空间上不重合限制

  • 车厢容量限制

  • 不悬空限制

  • 摆放方向限制（静态装箱）

会根据6种相对位置和摆放方向遍历可能的坐标点，并且检查是否符合限制条件，得到备选坐标

我们使用空最大空间（EMSs）的概念来表示箱子中的自由空间，下图说明了这个概念。黑色框架提供了目前可用的装载空间。当一个蓝色的方框放在角落里时，它会产生三个最大空闲空间，用黄色的立方体表示。

我们通过以下规则定义空最大空间的优先级：对于两个顶点最小坐标 和 的最大空闲空间。我们首先比较两个顶点的最小坐标值，小的顶点会给高优先级，如果他们相同，我们比较第二小的值和赋予较小的高优先级，如果两个值仍然相同，我们比较第三小的值，也就是最大的值。例如，比较两个顶点（3、5、4）和（6、3、3），首先先比较坐标中的最小值3和3，因为相同，所以比较第二小的值4和3，因为3 < 4，所以第二个定点的优先级更高。这种优先级化背后的原因是，我们希望先把盒子放在容器的一个角落及其相邻的两侧，然后是它的内部空间。每次更新EMSs后，我们根据上面定义的优先级对每个箱子中的空闲空间进行排序。

放置选择是通过对几个可能的候选安置位应用一个选择标准来确定的。在每次迭代中，找出箱子所有可放置的位置以及相应的旋转方向。然后首先选择填充比最大的（box，最大空闲空间）对进行放置。当一个箱子子在车厢中有几个可行的位置时，选择一个边界最小的位置。这可以通过按以下计算方法来实现：空间的尺寸为 ，将旋转后盒子的尺寸定义为 ，两个向量相减，得到 。然后，定义放置的优先级与选择最大空闲空间的优先级相同。

(a) 的边际为（1.45,1.75），(b) 的边际为（0,3.25）。我们的策略将选择在(b)中的位置，因为它在一个方向上产生更少的边际。

如果没有合适的位置，这将箱子移入unfitted列表，否则，总是找到一个或多个可行的放置分配，并选择一个填充比最大的分配。然后，将该项目放置在所选的空闲空间中，从未放置的箱子列表中删除该箱，并更新EMSs。如果未放置的箱子列表中没有元素，算法将以找到的解终止。

1.  将所有箱子按体积大小降序排序，依次放入车厢。

2. 如果是第一个放入车厢的箱子，则将箱子放入(0,0,0)位置，方向选择模块选择最佳的放置方向。

3.  如果不是，遍历已放置盒子的6种位置关系的坐标点，找到所有可行的坐标以及对应的放置方向。

4. 根据最大空闲空间优先级选择最佳位置坐标。

5. 找出所有的（box坐标，最大边际）对作为比较的参数。

6. 根据给出的比较参数，选择最佳的放置方向。

7. 放入车厢中。

python main.py --mode static --visualize

mode：static/online

可视化：需要可视化加上--visualize

具体数据在代码内调整

可视化效果

3D-Bin-Packing-Problem

3D-bin-packing

[1] Li X, Zhao Z, Zhang K. A genetic algorithm for the three-dimensional bin packing problem with heterogeneous bins[C]//IIE Annual Conference. Proceedings. Institute of Industrial and Systems Engineers (IISE), 2014: 2039.

[2] Dube E, Kanavathy L R, Woodview P. Optimizing three-dimensional bin packing through simulation[C]//Sixth IASTED International Conference Modelling, Simulation, and Optimization. 2006.