阿里IJCAI2017Workshop论文：使用深度强化学习方法求解一类新型三维装箱问题(6)

我们首先设计了一种启发式算法来求解此类新型三维装箱问题。此种算法的基本思想为：在放入一个物品时，遍历所有可用的空余空间和物品朝向，并选择能够最小化表面积的组合。然后再遍历所有物品，确定一个能够最小化浪费空间体积（least waste space）的物品。算法的详细步骤请见附录。在本文中，我们使用 DRL 方法来优化物品的放入顺序，在确定了物品的放入顺序之后，选择物品的摆放位置和朝向时使用和以上启发式算法相同的方法。所以本研究的重点在于使用 DRL 方法来优化物品的放入顺序。在未来的研究中，我们将会把物品的放入顺序、摆放位置和朝向统一纳入深度强化学习方法框架中。
3.2.1 网络结构
本研究主要使用了 [Vinyals et al., 2015] 和 [Bello et al., 2016] 提出的神经网络结构。在 Vinyals 和 Bello 等人的研究中提出了一种名为 Pointer Net (Ptr-Net) 的神经网络来求解组合优化问题。例如，在求解旅行商问题时，二维平面中每个点的坐标被输入到网络模型中，经过计算之后，模型的输出为每个点被访问的顺序。这种网络结构与 [Sutskever et al., 2014] 提出的序列到序列模型非常相似，但是有两点不同：第一，在序列到序列模型中，每一步的预测目标的种类是固定的，但是在 Ptr-Net 中是可变的；第二，在序列到序列模型中，在解码阶段通过注意机制将编码阶段的隐层单元组合成为一个上下文向量信息，而在 Ptr-Net 中，通过注意机制来选择（指向）输入序列中的一个来作为输出。
本研究中使用的神经网络模型的结构如图 1 所示。网络的输入为需要装箱的物品的长宽高数据，输出为物品装箱的顺序。网络中包含了两个 RNN 模型：编码网络和解码网络。在编码网络的每一步中，首先对物品的长宽高数据进行嵌入表达（embedded），然后再输入到 LSTM 单元中，并获得对应的输出。在编码阶段的最后一步，将 LSTM 单元的状态和输出传递到解码网络。在解码网络的每一步中，在编码网络的输出中选择一个作为下一步的输入。如图 1 所示，在解码网络中的第 3 步的输出为 4，则选择（指向）编码网络的第 4 步的输出，将其作为解码网络下一步（第 4 步）的输入。此外，在每一步的预测过程中还使用了 [Bello et al., 2016] 提出的 Glimpse 机制来整合编码阶段和解码阶段的输出信息。