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

在精确解算法方面，[Chen et al., 1995] 考虑了一种有多种尺寸箱子的三维装箱问题，并建立一个混合整数规划模型来求解最优解。[Martello et al., 2000] 提出了一种分支定界算法来求解三维装箱问题，并通过数值实验表明 90 个物品以内的问题都可以在合理的时间内获得最优解。另外，还有一些从实际业务中提出的装箱问题的变型问题，例如 [Kang and Park, 2003] 提出了一种可变尺寸的装箱问题，[Khanafer et al., 2010], [Gendreau et al., 2004] 研究了一种考虑物品冲突的装箱问题，[Clautiaux et al., 2014] 对一种考虑易碎物品的装箱问题进行了研究。
另一类装箱问题—条带装箱问题 (Strip packing problem) 与本文提出的新问题比较接近。在一般的条带装箱问题中，若干个长方体物品需要被逐个放入一个给定的条带中，条带的长度和宽度是已知且固定的，长度为无穷大（在二维条带装箱问题中，条带的宽度固定，但是长度为无穷大），优化目标为最小化使用的条带的高度。此类问题在钢铁工业和纺织工业中有很多应用，研究者们也提出了不同类型的求解算法，例如精确解算法 ([Martello et al., 2003]，[Kenmochi et al., 2009])，近似解算法 ([Steinberg, 1997])，启发式算法 ([Bortfeldt and Mack, 2007], [Bortfeldt, 2006], [Hopper and Turton, 2001]) 等。
2.2 DRL 方法在组合优化问题中的应用研究
虽然机器学习和组合优化问题已经分别被研究了数十年，但是关于机器学习方法在求解组合优化问题方面的研究却比较少。其中的一个研究方向是使用强化学习的思想来设计超启发式算法。[Burke et al., 2013] 在一篇关于超启发式算法的综述论文中对于一些基于学习机制的超启发式算法进行了讨论。[Nareyek, 2003] 使用了一种基于非平稳强化学习的方法来更新启发式算法被选择的概率。除此之外，强化学习思想在超启发式算法中的应用研究还包括二元指数补偿 ([Remde et al., 2009])、禁忌搜索 ([Burke et al., 2003]) 和选择函数等 ([Cowling et al., 2000])。