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

其中，
表示第 i 个物品在第 j 个物品的左边，
表示第 i 个物品在第 j 个物品的下边，
表示第 i 个物品在第 j 个物品的后边。
表示物品 i 的摆放朝向为正面朝上，
表示物品 i 正面朝下，
表示物品 i 侧面朝上，
表示物品 i 侧面朝下，
表示物品底面朝上，
表示物品底面朝下。
约束条件中的 (9), (10), (11) 表示物品在不同的朝向情况下占用的空间的长宽高；约束条件 (1), (3), (4), (5) 表示物品之间没有重叠，约束条件 (6), (7), (8) 保证了箱子容纳了所有物品。
基于以上的数学模型，我们使用了优化引擎，例如 IBM Cplex 等来直接求解此问题。但是对于一般规模的问题（例如物品数量大于等于 6），很难在合理的时间内获得最优解。而且我们还证明了此类问题是 NP-hard 问题。证明过程请见附录。
表 1 决策变量符号及含义
变量名
类型
含义
连续型变量
箱子的长度
连续型变量
箱子的宽度
连续型变量
箱子的高度
连续型变量
物品的左下后角的x坐标
连续型变量
物品的左下后角的y坐标
连续型变量
物品的左下后角的z坐标
0-1二元变量
第i个物品是否在第j个物品的左边
0-1二元变量
第i个物品是否在第j个物品的下边
0-1二元变量
第i个物品是否在第j个物品的后边
0-1二元变量
第i个物品是否是正面朝上
0-1二元变量
第i个物品是否是正面朝下
0-1二元变量
第i个物品是否是侧面朝上
0-1二元变量
第i个物品是否是侧面朝下
0-1二元变量
第i个物品是否是底面朝上
0-1二元变量
第i个物品是否是底面朝下
3.2 DRL 方法
在本部分中，我们将介绍用于求解新型三维装箱问题的 DRL 方法。在求解三维装箱问题时，决策变量主要分为三类：
物品放入箱子的顺序；
物品在箱子中的摆放位置；
物品在箱子的摆放朝向。