DQN深度强化学习解决三维在线装箱问题

物流公司在流通过程中，需要将打包完毕的箱子装入到一个货车的车厢中，为了提高物流效率，需要将车厢尽量填满，显然，车厢如果能被100%填满是最优的，但通常认为，车厢能够填满85%，可认为装箱是比较优化的。 设车厢为长方形，其长宽高分别为L，W，H；共有n个箱子，箱子也为长方形，第i个箱子的长宽高为li，wi，hi（n个箱子的体积总和是要远远大于车厢的体积），做以下假设和要求：

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

（1）箱子到来后，根据车厢的实际空间情况，按照策略选择放置点；

（2）当摆放箱子时，以6种姿态摆放，并对其进行评估，使用评估值最高的姿态将箱子摆放在选中的角点上；

（3）重复以上步骤，直到摆放完毕。

在车厢内部设置坐标系，靠近驾驶室并位于下端的一个角的坐标为（0,0,0），相交于原点的车厢长边、宽边和高边分别为x轴，y轴和z轴方向，L、W、H分别为车厢的长、宽、高。箱子具有六种摆放姿态，分别以箱子的长宽、长高、宽高平面为底，旋转90°可以得到另外三种摆放姿态。

本算法将角点作为车厢内部空间中箱子的摆放位置，每次放入新箱子后搜索新生成的角点，当向车厢中放入第一个箱子时，假设车厢中只有原点一个角点，当一个箱子放入后，会产生新的角点，再放置箱子后，又会产生新的角点。 建立箱子可放置点列表，表示箱子i到来时，车厢内部所有可选的摆放位置，在放置新箱子后更新可放置点列表，并记录已放置箱子到车厢顶部距离，用于后续的奖励函数。

（1）设置一些超参数，包括ε-greedy使用的ε，折扣因子γ，目标网络更新频率，经验池容量等。

（2）由于给定的箱子数据较少，为了增加模型训练数据数量，将给定的箱子数据打乱，以随机的形式生成并保存，作为训练数据，训练网络模型。

（3）奖励函数 使用x-y平面中两个最大剩余矩形面积（如下图）之和与箱子到车厢顶部的距离作为奖励值R，奖励函数表示如下：

（4）动作-价值函数网络和目标动作-价值函数网络设置为包含6层卷积层的CNN。对当前状态和动作建模，使其能够输入到价值网络Q和Q’中。以车厢的底面为基准，建模L*W的矩阵，每个元素代表该点放置的箱子最大高度。

（5）动作选择 根据当前的状态（当前车厢的属性，包括尺寸、放置的所有箱子、H矩阵、可放置点列表等），使用ε-greedy方法选择具有最大Q值的动作或随机选择动作（动作是箱子的放置点和摆放姿态）。

（6）经验重放

将所有文件夹放置在同一目录下，train.py用于模型训练，cnn.pth是已经训练好的模型，在eval.py中导入后直接运行eval.py即可。

1、填充率

一般认为车厢填充率高于85%，认为装箱算法是较优的，本实验设计的装箱方案填充率较低，在60%-80%间，分析原因可能在于强化学习网络的参数不够合适，算法有待优化。 改进的方向：调整强化学习网络的参数，选择更加合适的参数。

2、运行时间

本实验的代码时间消耗较高，难以满足实时性要求。该算法在在放置货物时需要遍历每个可放置点，每个可放置点需要进行碰撞检测，时间复杂度很高，导致代码运行时间较长。 后续通过改进代码或者更换编程语言，减少时间复杂度以提高运行速度，改进算法，减少遍历箱子的数量，提高运行速度。