装箱问题

from. 武汉大学国家网络安全学院

1 问题描述

物流公司在流通过程中，需要将打包完毕的箱子装入到一个货车的车厢中，为了提高物流效率，需要将车厢尽量填满，显然，车厢如果能被100%填满是最优的，但通常认为，车厢能够填满85%，可认为装箱是比较优化的。

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

长方形的车厢共有8个角，并设靠近驾驶室并位于下端的一个角的坐标为（0,0,0），车厢共6个面，其中长的4个面，以及靠近驾驶室的面是封闭的，只有一个面是开着的，用于工人搬运箱子；
需要计算出每个箱子在车厢中的坐标，即每个箱子摆放后，其和车厢坐标为（0,0,0）的角相对应的角在车厢中的坐标，并计算车厢的填充率。

问题分解为基础和高级部分

基础部分：

所有的参数为整数；
静态装箱，即从n个箱子中选取m个箱子，并实现m个箱子在车厢中的摆放（无需考虑装箱的顺序，即不需要考虑箱子从内向外，从下向上这种在车厢中的装箱顺序）；
所有的箱子全部平放，即箱子的最大面朝下摆放；
算法时间不做严格要求，只要1天内得出结果都可。

高级部分：

参数考虑小数点后两位；
实现在线算法，也就是箱子是按照随机顺序到达，先到达先摆放；
需要考虑箱子的摆放顺序，即箱子是从内到外，从下向上的摆放顺序；
因箱子共有3个不同的面，所有每个箱子有3种不同的摆放状态；
算法需要实时得出结果，即算法时间小于等于2秒。

2 实验环境

项目	描述
主机系统	Windows 10 家庭中文版64位
主机处理器	AMD Ryzen 5 PRO 2500U
主机内存	20.0 GB
Python环境	Python 3.7
Python库	sys, time, itertools, maplotlib, numpy, warnings, math, mpl_toolkits

3 算法介绍

本实验采用基于块装载的启发式方法，通过块的选择和装填，完成装箱任务。具体介绍如下：

在本实验的装箱问题中，所有物品都是与坐标轴平行的长方体，每种物品具有四个属性，即长、宽、高和数量，而车厢作为容器，具有三个属性，即长、宽、高。因此，使用三个列表，即container、box_list、num_list可以描述一个三维装箱问题，其中container描述车厢，box_list列出所有箱子，而num_list则列出了对应所有箱子的数目。

块是本实验中装载中使用的启发式算法中，装载的最小单位，是一个包含一个或多个箱子的长方体，装箱后，一个可行块将会被切割，剩余空间将会被组织为堆栈，并考虑是否可以并入到堆栈中的其他空间，从而形成新的可行块。

所谓块，需要使用块生成算法进行生成，在块生成算法中，最简单的是简单块，是由同一朝向的同种类型的箱子堆叠而成的，箱子和箱子之间没有空隙，堆叠结果为一个长方体，如下图所示：

而复合块是通过不断复合简单块得到的，定义为：

（1）简单块是最基本的复合块；

（2）有两个复合块 a 和 b。可以按 3 种方式进行复合得到复合块 c ：按 x 轴方向复合，按 y 轴方向复合，按 z 轴方向复合。c 的大小是包含 a 和 b 的最小长方体。

关于情况（2），如下图所示：

按照前面的定义，复合块的数量将是箱子数目的指数级，而且生成块中可能有很多未利用空间，非常不利于装载. 所以对复合块施加一定的限制是必要的，生成的复合块必须满足下面7个条件：

(1) 复合块的大小不大于容器的大小；

(2) 复合块中可以有空隙，但它的填充率至少要达到MIN_FILL_RATE；

(3) 受复合块中空隙的影响，复合块顶部有支撑的可行放置矩形可能很小，为了进一步的装载，我们限定可行放置矩形与相应的复合块顶部面积的比至少要达到MIN_AREA_RATE；

(4) 为控制复合块的复杂程度，定义复合块的复杂度如下：

简单块的复杂度为0，其它复合块的复杂度为其子块的复杂度的最大值加1。块结构的 times域描述了复合块的复杂程度，限制生成块的最大复杂次数为MAX_TIMES；

(5) 按x轴方向、按y轴方向复合的时候，子块要保证顶部可行放置矩形也能进行复合。在按z轴方向复合时，子块要保证复合满足稳定性约束，即禁止箱子悬空。具体的复合要求和结果如下表所示；

(6) 拥有相同3边长度、箱子需求和顶部可行放置矩形的复合块被视为等价块，重复生成的等价块将被忽略；

(7) 在满足以上约束的情况下，块数目仍然可能会很大，生成算法将在块数目达到MaxBlocks时停止生成；

在每个装载阶段一个剩余空间被装载，装载分为两种情况：有可行块或无可行块。在有可行块时，算法按照块选择算法选择可行块，然后将未填充空间切割成新的剩余空间。在无可行块时，当前剩余空间被抛弃，若其中的一部分空间可以被并入当前堆栈中的其他空间，则进行空间转移重新利用这些空间。

在块选择时候，可以使用贪心算法，选择当前最大的可行块进行装填。

4 实验结果

4.1 基本实验结果

首先需要对数据进行读取，如下函数所示，下面进行了实验中容器和箱子的读取，并返回为box_list、num_list和container_list，同时，考虑到要求，对小数点进行了处理。

接下来，将所有读取到的数据，循环进行处理，如下所示：

由于结果较长，因此将结果输出到同目录下output.txt文件中，方便记录，同时会记录放置完成后的利用率。

首先，说明对有效性的实验结果，实验取所给数据中第一组数据，如下所示：

设定show_picture = True，运行代码，可以获取利用率和运行时间结果，其中关于时间部分，后文将有更为详细的说明，此外，还展示了放置位置的示意图，如图所示：

在output.txt文件中，显示了所有箱体坐标，以及最后的利用率，由于最终结果较长，此处分为三个文件截图，组合在一起可以确定所有文件内容，如图所示：

由以上内容可以确定当前算法的有效性。

4.2 实验要求结果说明

基础部分

1. 所有的参数为整数：

正常完成，从以上对第一组实验数据的实验结果可以证明，循环相同步骤，读取不同数据，可以完成每一组整数数据的读取和处理。

2. 静态装箱，即从n个箱子中选取m个箱子，并实现m个箱子在车厢中的摆放（无需考虑装箱的顺序，即不需要考虑箱子从内向外，从下向上这种在车厢中的装箱顺序）：

正常完成，本实验算法步骤为使用箱子装入可行块中，也就是从箱子中选取箱子进行摆放。

3. 所有的箱子全部平放，即箱子的最大面朝下摆放：

正常完成，但实际上完成了高级部分的要求，即可以对箱子摆放状态进行调整，因此此条要求作废。

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

正常完成，实际运行时候可以实时获取结果，运行时间以秒为单位，且在放弃部分使用率的情况下可以更为快速，具体说明在高级部分要求的说明中提供。

高级部分

1. 参数考虑小数点后两位：

正常完成，以下以第一组实验数据为例，将第一组实验数据数值分别进行除以10、除以100的操作，如下所示：

完成三次运行，得到摆放示意图、使用率、运行时间结果如下所示：

可以看到三次运行结果完全一致，证明在两位小数情况下，本算法依旧正常进行，而运行时间略有缩短，猜测为系统对相似数据进行了优化，使得运行时间得以缩短。

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

由于算法限制，本条要求没有实现。

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

正常完成，在算法进行阶段，使用的是可行块进行操作，而可行块也是从内部向外进行扩展的，分割开的空间，如果周围没有其他空间满足复合块的要求，则无法并为块，也就是无法进行装箱。此外，所有箱子的摆放，可以保证从内到外、从上到下进行，从最终结果也可以看出，箱子没有悬空的，全部放置在其他箱子之上或者直接放置在车厢上面。

4. 因箱子共有3个不同的面，所有每个箱子有3种不同的摆放状态：

正常完成，且关于此条内容，我认为箱子虽然有3个不同的面，但是由于每个面有两种摆放方法（长×宽和宽×长），因此一共是6种摆放状态，所以一共需要考虑6种情况而不是3种情况，如下所示（由于截图长度限制，此处展示3种状态的完整代码，另外3种状态进行了折叠）：

对于该条要求，需要进一步说明的是，本实验算法采用块进行填充，在每一次对块进行填充的最优解，不一定意味着总体的最优解，也就是说，多使用某种状态，使得当前块可以被这种状态填充，不一定会比缺少考虑这种状态，而使用原始状态填充，得到的解更优，不过实际实验中，实现较多种类放置状态的时候，比没有进行旋转变换，大多数情况下能取得更好的结果，如下所示，下面展示了1种、3种、6种放置状态下得到的结果：

当然，有一种较为简便的取得较高的使用率的方法，也就是对每个种类数目放置情况进行遍历，取使用率最高情况，换言之，分别进行1种、2种、3种、4种、5种、6种的算法运行，取最好结果，作为算法的最终结果。下面展示了1次（1种）、3次（1种、2种、3种）、6次（1种、2种、3种、4种、5种、6种）算法运行后取最好结果的结果：

当然，多次运行势必也会增加整体运行时间，基本以倍数形式增加，从算法复杂度角度来讲，这算是一个常数复杂度，因此可以不予考虑。

5. 算法需要实时得出结果，即算法时间小于等于2秒：

基本实现，此处需要说明的是，虽然在4条件中，可以看到后续运行时间较长，但这是因为算法进行了多次循环的缘故，从复杂度角度来讲，这样的常数类型是可以忽略的，且另一个需要注意的点是，运行时间与当前电脑配置、电脑运行状态等因素有关，并不是十分准确的东西，而本次实验使用的电脑是四年半前的轻薄本电脑，其本身性能也不算突出，到现在性能更可以说较为落后，因此我认为此处如果使用配置更好的电脑，是可以实现运行时间的减少的，同时，如果设定合理的参数，例如将状态类型设置为3，而不追求获得多种状态类型下使用率最高的情况，那么整体运行时间，即便在本主机上，也基本在2秒以内，如下图所示（使用的即为上文比较中的状态类型为3的截图）：

且在同样的条件下，另一次运行结果如下所示：

可以看到所有例子均在2秒以内，因此，综合来看，我认为这一个要求基本进行了实现。

4 文件说明

本目录下主要包含以下文件：

main.py：实验代码；
data.txt：给出的数据，复制到了txt中方便读取，其中前三组数据的后两组是第一组数据添加小数点之后的结果；
output-1.txt：不改变状态，单次运行，本实验获取的结果；
output-3.txt：3种放置状态，单次运行，本实验获取的结果；
output-6.txt：6种放置状态，单次运行，本实验获取的结果；
output-321.txt：使用3次运行（1种、2种、3种放置状态）得到的最好结果，结果在output-best.txt和output-no-rotate.txt之间；
output-654321.txt：使用6次运行（1种、2种、3种、4种、5种、6种放置状态）得到的最好结果，也是本实验能够获取的放置的最好结果。

5 参考文献

[1] 张德富,彭煜,张丽丽. 求解三维装箱问题的多层启发式搜索算法[J]. 计算机学报, 2012, 35(012):2553-2561.

[2] 张德富,魏丽军,陈青山,等. 三维装箱问题的组合启发式算法[J]. 软件学报. 2007,(9).

[3] 张德富,彭煜,朱文兴,等. 求解三维装箱问题的混合模拟退火算法[J]. 计算机学报. 2009,(11).

[4] 彭煜. 求解三维装箱问题的启发式分层搜索算法[D]. 福建:厦门大学, 2009.

[5] 求解三维装箱问题的启发式深度优先搜索算法(python)[EB/OL]. https://blog.csdn.net/weixin_37522117/article/details/125376144

Jack1203187498/PackingProblem