世界級難題：把不同物品裝進箱子，如何使箱子表麵積最小？

三維裝箱問題是一類經典的組合優化問題，具有巨大的學習研究和實際應用價值。傳統的三維裝箱問題都是給定了箱子的尺寸並以最小化箱子的使用數量為優化目標，但是在某些實際業務場景中並沒有固定尺寸的箱子。

基於此類場景，本文提出了一類新型的三維裝箱問題。在本問題中，需要將若幹個長方體物體逐個放入一個箱子中（物品的擺放位置不能傾斜），優化目標為最小化能夠容納所有物品的箱子的表麵積，因為箱子的表麵積與其成本直接正相關。本文證明了此類新問題為NP-hard問題。對於裝箱問題，箱子的表麵積取決於物品的放入順序、擺放的空間位置和擺放朝向。在這些因素中，物品的放入順序有著非常重要的影響。所以本文基於近些年被提出的、能夠有效解決某些組合優化問題的深度強化學習方法—Pointer Network方法來優化物品的放入順序。

本文基於大量實際業務數據對網絡模型進行了訓練和檢驗。結果表明，相對於已有的啟發式算法，深度強化學習方法能夠獲得大約5%的效果提升。

論文地址：https://arxiv.org/abs/1708.05930

裝箱問題是一類非常經典且重要的優化問題，常被應用於物流係統和生產係統中。裝箱問題有很多變型問題，其中最重要且最難求解的是三維裝箱問題，在此問題中，需要將若幹個不同大小的長方體物品放入箱子中，物品之間不能重疊且不能傾斜，箱子的尺寸和成本已知，優化目標為最小化箱子的使用數量，即最小化總成本。裝箱問題一直是學術界非常流行的研究方向之一。除此之外，裝箱問題在實際中也有很多應用。有效的裝箱算法往往意味著計算時間、裝箱成本的大量節省和資源使用效率的大幅提升。

在某些實際業務場景中，我們發現裝箱時並不是使用固定尺寸的箱子（例如在跨境電商業務中，大部分是使用柔性的塑料材料，而不是箱子來包裝貨物），而且由於裝箱的成本大部分都由裝箱材料成本構成，而裝箱材料成本又主要取決於材料的表麵積。所以在本研究中，我們提出了一類新型的裝箱問題。與傳統三維裝箱問題不同的是，本問題的優化目標為確定一個能夠容納所有物品的箱子，並最小化此箱子的表麵積。

由於尋找裝箱問題的最優解非常難，所以相關研究者們提出了不同的近似算法和啟發式算法來求解此類問題。但是啟發式算法往往有著較強的問題依賴性，一類啟發式算法可能隻適用於求解某種或某些業務場景中的裝箱問題。近些年來，人工智能技術，尤其是深度強化學習(Deep reinforcement learning, DRL)技術有著非常快速的發展，並且在某些問題上取得了令人矚目的成果。而且深度強化學習技術已經被發現在求解組合優化問題方麵具有較大的潛力，所以本研究使用了一種基於深度強化學習的方法來求解新型三維裝箱問題。本文基於大量實際業務數據訓練了深度強化學習模型，並驗證了模型的效果。

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])等。在精確解算法方麵，[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]對一種考慮易碎物品的裝箱問題進行了研究。

另一類裝箱問題—條帶裝箱問題(Strippacking problem)與本文提出的新問題比較接近。在一般的條帶裝箱問題中，若幹個長方體物品需要被逐個放入一個給定的條帶中，條帶的長度和寬度是已知且固定的，長度為無窮大（在二維條帶裝箱問題中，條帶的寬度固定，但是長度為無窮大），優化目標為最小化使用的條帶的高度。此類問題在鋼鐵工業和紡織工業中有很多應用，研究者們也提出了不同類型的求解算法，例如精確解算法([Martello et al., 2003]，[Kenmochi et al., 2009])，近似解算法([Steinberg, 1997])，啟發式算法([Bortfeldt and Mack, 2007], [Bortfeldt, 2006], [Hopper andTurton, 2001])等。

2.2 DRL方法在組合優化問題中的應用研究

雖然機器學習和組合優化問題已經分別被研究了數十年，但是關於機器學習方法在求解組合優化問題方麵的研究卻比較少。其中的一個研究方向是使用強化學習的思想來設計超啟發式算法。[Burke et al., 2013]在一篇關於超啟發式算法的綜述論文中對於一些基於學習機製的超啟發式算法進行了討論。[Nareyek, 2003]使用了一種基於非平穩強化學習的方法來更新啟發式算法被選擇的概率。除此之外，強化學習思想在超啟發式算法中的應用研究還包括二元指數補償([Remde et al.,2009])、禁忌搜索([Burke et al.,2003])和選擇函數等([Cowling et al., 2000])。

近些年來，序列到序列模型(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.1 問題定義

在經典的三維裝箱問題中，需要將若幹個物品放入固定尺寸的箱子中，並最小化箱子的使用數量。與經典問題不同的是，本文提出的新型裝箱問題的目標在於設計能夠容納一個訂單中所有物品的箱子，並使箱子的表麵積最小。在一些實際業務場景中，例如跨境電商中，包裝物品時使用的是柔性的塑料材料，而且由於包裝材料的成本與其表麵積直接正相關，所以最小化箱子的表麵積即意味著最小化包裝成本。

本文提出的新型裝箱問題的數學表達形式如下所示。給定一係列物品的集合，每個物品i都有各自的長(li)、寬(wi)和高(hi)。優化目標為尋找一個表麵積最小且能夠容納所有物品的箱子。我們規定(xi, yi,zi)表示每一個物品的左下後(left-bottom-back)角的坐標，而且(0, 0, 0)表示箱子的左下後角的坐標。決策變量的符號及其含義如表1所示。基於以上問題描述和符號定義，新問題的數學表達形式為：

3.2 DRL方法

在本部分中，我們將介紹用於求解新型三維裝箱問題的DRL方法。在求解三維裝箱問題時，決策變量主要分為三類：

（1）物品放入箱子的順序；
（2）物品在箱子中的擺放位置；
（3）物品在箱子的擺放朝向。

我們首先設計了一種啟發式算法來求解此類新型三維裝箱問題。此種算法的基本思想為：在放入一個物品時，遍曆所有可用的空餘空間和物品朝向，並選擇能夠最小化表麵積的組合。然後再遍曆所有物品，確定一個能夠最小化浪費空間體積（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機製來整合編碼階段和解碼階段的輸出信息。

圖1 神經網絡模型的結構

3.2.2 基於策略的強化學習方法

3.2.3 基準值的更新

在本研究中，我們使用了一種基於記憶重放的方法來不斷地更新基準值。首先，對於每一個樣本點si，通過啟發式算法獲取一個裝箱方案，並計算其表麵積，作為b(si)的初始值。之後在每一步的訓練過程中，通過以下公式來更新基準值：

其中為訓練過程中獲得表麵積的值。

3.2.4 隨機采樣與集束搜索（Beam Search）

在模型的訓練階段，我們從模型預測的概率分布中進行隨機選取作為輸出。但是在驗證階段，我們采用貪婪策略來進行選擇，即在每一步中，我們選取概率分布中概率最大的備選項作為輸出。除此之外，我們還在驗證階段使用來集束搜索的方法來提高模型的效果，即在每一步中不是選擇對應概率最高的備選項，而是選擇概率最高的前k個備選項作為輸出。

通過以上描述，模型的整個訓練步驟總結為：

為了驗證模型的效果，我們基於大量實際業務數據完成了數值實驗。根據實驗過程中每個訂單中物品數量的不同（8，10和12），實驗分為了三個部分，但是每次實驗過程中的超參數均相同。在每次實驗中，我們采用了15萬條訓練樣本和15萬條測試樣本。在實驗過程中，每批訓練的樣本量為128，LSTM的隱層單元的數量為128，Adam的初始學習速率為0.001，並且每5000步以0.96的比例衰減。網絡模型的參數的初始值均從[-0.08, 0.08]中隨機選取。為了防止梯度爆炸現象的出現，我們在訓練過程中使用L2正則方法對梯度進行修剪。在更新基準值的過程中，的取值為0.7。在每次訓練中，我們在Tesla M40 GPU上訓練100萬步，每次的訓練時間大約為12小時。在驗證階段，使用集束搜索方法時，集束搜索的寬度為3。模型主要通過TensorFlow來實現。

數值實驗的結果請見表2。主要評價指標為平均表麵積（Average surface area, ASA）.從表中可以看出，在使用集束搜索的情況下，本文提出的基於DRL的方法在三類測試集上分別可以獲得大約4.89%, 4.88%, 5.33%的效果提升。此外，我們還通過窮舉的方法獲得了對於8個物品測試數據中5000個樣本數據的最優物品放入順序，並計算得到了啟發式算法的結果與最優解的平均差距為10%左右，這說明基於DRL的方法的結果已經與最優解比較接近。

本文提出了一類新型三維裝箱問題。不同於傳統的三維裝箱問題，本文提出的問題的優化目標為最小化能夠容納所有物品的箱子的表麵積。由於問題的複雜性和求解難度，此類問題非常難以獲得最優解，而大部分啟發式算法又缺乏普適性。所以本文嚐試將Pointer Net框架和基於深度強化學習的方法應用到了對此類問題的優化求解中。本文基於大量實際數據對網絡模型進行了訓練和驗證，數值實驗的結果表明基於深度強化學習方法獲得的結果顯著好於已有的啟發式算法。本項研究的主要貢獻包括：第一，提出了一類新型的三維裝箱問題；第二，將深度強化學習技術應用到了此類新問題的求解中。在之後的研究中將會深入探索更有效的網絡模型和訓練算法，並且會嚐試將物品的擺放位置和朝向的選擇整合到模型中。

附錄：

A：三維裝箱問題的啟發式算法

用於求解本文的新型三維裝箱問題的啟發式算法包括最小表麵積（least surface area）算法和最小浪費空間（least wastespace）算法。算法的詳細步驟如下所示：