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

近些年来，序列到序列模型 (sequence-to-sequence) 的一系列研究突破激发了研究者们对于神经组合优化 (neural combinatorial optimization) 方向的兴趣。其中注意机制 (attention mechanism) 对于加强神经网络模型在机器翻译 ([Bahdanau et al., 2014]) 和算法学习 ([Graves et al., 2014]) 方面的效果中扮演了重要决策。[Vinyals et al., 2015] 提出了一种带有特殊注意机制的网络模型—Pointer Net，并使用有监督学习的方法来通过此模型求解旅行商问题 (Travelling Salesman Problem)。[Bello et al., 2016] 提出了一种基于强化学习思想的神经组合优化 (neural combinatorial optimization) 框架，并使用此种框架求解了旅行商问题和背包问题 (Knapsack Problem)。
因为此种框架的有效性和普适性，本研究在求解新型装箱问题中主要使用了此种框架和方法。
3. 针对三维装箱问题的 DRL 方法
3.1 问题定义
在经典的三维装箱问题中，需要将若干个物品放入固定尺寸的箱子中，并最小化箱子的使用数量。与经典问题不同的是，本文提出的新型装箱问题的目标在于设计能够容纳一个订单中所有物品的箱子，并使箱子的表面积最小。在一些实际业务场景中，例如跨境电商中，包装物品时使用的是柔性的塑料材料，而且由于包装材料的成本与其表面积直接正相关，所以最小化箱子的表面积即意味着最小化包装成本。
本文提出的新型装箱问题的数学表达形式如下所示。给定一系列物品的集合，每个物品 i 都有各自的长 (l_i)、宽 (w_i) 和高 (h_i)。优化目标为寻找一个表面积最小且能够容纳所有物品的箱子。我们规定 (x_i, y_i, z_i) 表示每一个物品的左下后 (left-bottom-back) 角的坐标，而且 (0, 0, 0) 表示箱子的左下后角的坐标。决策变量的符号及其含义如表 1 所示。基于以上问题描述和符号定义，新问题的数学表达形式为：