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

本文基于大量实际业务数据对网络模型进行了训练和检验。结果表明，相对于已有的启发式算法，深度强化学习方法能够获得大约 5% 的效果提升。
1. 引言
装箱问题是一类非常经典且重要的优化问题，常被应用于物流系统和生产系统中。装箱问题有很多变型问题，其中最重要且最难求解的是三维装箱问题，在此问题中，需要将若干个不同大小的长方体物品放入箱子中，物品之间不能重叠且不能倾斜，箱子的尺寸和成本已知，优化目标为最小化箱子的使用数量，即最小化总成本。装箱问题一直是学术界非常流行的研究方向之一。除此之外，装箱问题在实际中也有很多应用。有效的装箱算法往往意味着计算时间、装箱成本的大量节省和资源使用效率的大幅提升。
在某些实际业务场景中，我们发现装箱时并不是使用固定尺寸的箱子（例如在跨境电商业务中，大部分是使用柔性的塑料材料，而不是箱子来包装货物），而且由于装箱的成本大部分都由装箱材料成本构成，而装箱材料成本又主要取决于材料的表面积。所以在本研究中，我们提出了一类新型的装箱问题。与传统三维装箱问题不同的是，本问题的优化目标为确定一个能够容纳所有物品的箱子，并最小化此箱子的表面积。
由于寻找装箱问题的最优解非常难，所以相关研究者们提出了不同的近似算法和启发式算法来求解此类问题。但是启发式算法往往有着较强的问题依赖性，一类启发式算法可能只适用于求解某种或某些业务场景中的装箱问题。近些年来，人工智能技术，尤其是深度强化学习 (Deep reinforcement learning, DRL) 技术有着非常快速的发展，并且在某些问题上取得了令人瞩目的成果。而且深度强化学习技术已经被发现在求解组合优化问题方面具有较大的潜力，所以本研究使用了一种基于深度强化学习的方法来求解新型三维装箱问题。本文基于大量实际业务数据训练了深度强化学习模型，并验证了模型的效果。
2. 相关研究介绍
2.1 三维装箱问题相关研究
装箱问题是一类非常经典和流行的优化问题。自从其在 20 世纪 70 年代被提出以来，大量研究者对此类问题进行了研究并获得了许多有价值的成果。[Coffman et al., 1980] 证明了二维装箱问题是 NP-hard 问题，所以作为二维装箱问题的一般化问题，三维装箱问题也是 NP-hard 问题。由于此原因，很多之前的研究都集中于近似算法和启发式算法。[Scheithauer, 1991] 首先提出了针对三维装箱问题的近似算法并分析了其近似比。此外，研究者们还提出了很多不同类型的启发式算法，例如禁忌搜索 ([Lodi et al., 2002], [Crainic et al., 2009]), 引导式局部搜索 ([Faroe et al., 2003]), 基于极点的启发式算法 ([Crainic et al., 2008])，混合遗传算法 ([Kang et al., 2012]) 等。