三維裝箱問題是一類經典的組合優(yōu)化問題，具有巨大的學習研究和實際應用價值。傳統(tǒng)的三維裝箱問題都是給定了箱子的尺寸并以最小化箱子的使用數(shù)量為優(yōu)化目標，但是在某些實際業(yè)務場景中并沒有固定尺寸的箱子。
基于此類場景，本文提出了一類新型的三維裝箱問題。在本問題中，需要將若干個長方體物體逐個放入一個箱子中（物品的擺放位置不能傾斜），優(yōu)化目標為最小化能夠容納所有物品的箱子的表面積，因為箱子的表面積與其成本直接正相關。本文證明了此類新問題為NP-hard問題。對于裝箱問題，箱子的表面積取決于物品的放入順序、擺放的空間位置和擺放朝向。在這些因素中，物品的放入順序有著非常重要的影響。所以本文基于近些年被提出的、能夠有效解決某些組合優(yōu)化問題的深度強化學習方法—Pointer Network方法來優(yōu)化物品的放入順序。
本文基于大量實際業(yè)務數(shù)據(jù)對網絡模型進行了訓練和檢驗。結果表明，相對于已有的啟發(fā)式算法，深度強化學習方法能夠獲得大約5%的效果提升。
論文地址：https://arxiv.org/abs/1708.05930
1.引言
裝箱問題是一類非常經典且重要的優(yōu)化問題，常被應用于物流系統(tǒng)和生產系統(tǒng)中。裝箱問題有很多變型問題，其中最重要且最難求解的是三維裝箱問題，在此問題中，需要將若干個不同大小的長方體物品放入箱子中，物品之間不能重疊且不能傾斜，箱子的尺寸和成本已知，優(yōu)化目標為最小化箱子的使用數(shù)量，即最小化總成本。裝箱問題一直是學術界非常流行的研究方向之一。除此之外，裝箱問題在實際中也有很多應用。有效的裝箱算法往往意味著計算時間、裝箱成本的大量節(jié)省和資源使用效率的大幅提升。
在某些實際業(yè)務場景中，我們發(fā)現(xiàn)裝箱時并不是使用固定尺寸的箱子（例如在跨境電商業(yè)務中，大部分是使用柔性的塑料材料，而不是箱子來包裝貨物），而且由于裝箱的成本大部分都由裝箱材料成本構成，而裝箱材料成本又主要取決于材料的表面積。所以在本研究中，我們提出了一類新型的裝箱問題。與傳統(tǒng)三維裝箱問題不同的是，本問題的優(yōu)化目標為確定一個能夠容納所有物品的箱子，并最小化此箱子的表面積。
由于尋找裝箱問題的最優(yōu)解非常難，所以相關研究者們提出了不同的近似算法和啟發(fā)式算法來求解此類問題。但是啟發(fā)式算法往往有著較強的問題依賴性，一類啟發(fā)式算法可能只適用于求解某種或某些業(yè)務場景中的裝箱問題。近些年來，人工智能技術，尤其是深度強化學習(Deep reinforcement learning, DRL)技術有著非?？焖俚陌l(fā)展，并且在某些問題上取得了令人矚目的成果。而且深度強化學習技術已經被發(fā)現(xiàn)在求解組合優(yōu)化問題方面具有較大的潛力，所以本研究使用了一種基于深度強化學習的方法來求解新型三維裝箱問題。本文基于大量實際業(yè)務數(shù)據(jù)訓練了深度強化學習模型，并驗證了模型的效果。
2.相關研究介紹
2.1 三維裝箱問題相關研究
裝箱問題是一類非常經典和流行的優(yōu)化問題。自從其在20世紀70年代被提出以來，大量研究者對此類問題進行了研究并獲得了許多有價值的成果。[Coffman et al., 1980]證明了二維裝箱問題是NP-hard問題，所以作為二維裝箱問題的一般化問題，三維裝箱問題也是NP-hard問題。由于此原因，很多之前的研究都集中于近似算法和啟發(fā)式算法。[Scheithauer, 1991]首先提出了針對三維裝箱問題的近似算法并分析了其近似比。
此外，研究者們還提出了很多不同類型的啟發(fā)式算法，例如禁忌搜索([Lodi et al.,2002], [Crainic et al., 2009]), 引導式局部搜索 ([Faroe et al., 2003]), 基于極點的啟發(fā)式算法 ([Crainic et al., 2008])，混合遺傳算法([Kang et al.,2012])等。在精確解算法方面，[Chen et al., 1995]考慮了一種有多種尺寸箱子的三維裝箱問題，并建立一個混合整數(shù)規(guī)劃模型來求解最優(yōu)解。[Martello et al.,2000]提出了一種分支定界算法來求解三維裝箱問題，并通過數(shù)值實驗表明90個物品以內的問題都可以在合理的時間內獲得最優(yōu)解。
另外，還有一些從實際業(yè)務中提出的裝箱問題的變型問題，例如[Kang and Park, 2003]提出了一種可變尺寸的裝箱問題，[Khanafer et al.,2010], [Gendreau et al., 2004]研究了一種考慮物品沖突的裝箱問題，[Clautiaux et al.,2014]對一種考慮易碎物品的裝箱問題進行了研究。
另一類裝箱問題—條帶裝箱問題(Strippacking problem)與本文提出的新問題比較接近。在一般的條帶裝箱問題中，若干個長方體物品需要被逐個放入一個給定的條帶中，條帶的長度和寬度是已知且固定的，長度為無窮大（在二維條帶裝箱問題中，條帶的寬度固定，但是長度為無窮大），優(yōu)化目標為最小化使用的條帶的高度。此類問題在鋼鐵工業(yè)和紡織工業(yè)中有很多應用，研究者們也提出了不同類型的求解算法，例如精確解算法([Martello et al., 2003]，[Kenmochi et al., 2009])，近似解算法([Steinberg, 1997])，啟發(fā)式算法([Bortfeldt and Mack, 2007], [Bortfeldt, 2006], [Hopper andTurton, 2001])等。
2.2 DRL方法在組合優(yōu)化問題中的應用研究
雖然機器學習和組合優(yōu)化問題已經分別被研究了數(shù)十年，但是關于機器學習方法在求解組合優(yōu)化問題方面的研究卻比較少。其中的一個研究方向是使用強化學習的思想來設計超啟發(fā)式算法。[Burke et al., 2013]在一篇關于超啟發(fā)式算法的綜述論文中對于一些基于學習機制的超啟發(fā)式算法進行了討論。[Nareyek, 2003]使用了一種基于非平穩(wěn)強化學習的方法來更新啟發(fā)式算法被選擇的概率。除此之外，強化學習思想在超啟發(fā)式算法中的應用研究還包括二元指數(shù)補償([Remde et al.,2009])、禁忌搜索([Burke et al.,2003])和選擇函數(shù)等([Cowling et al., 2000])。
近些年來，序列到序列模型(sequence-to-sequence)的一系列研究突破激發(fā)了研究者們對于神經組合優(yōu)化(neural combinatorial optimization)方向的興趣。其中注意機制(attention mechanism)對于加強神經網絡模型在機器翻譯([Bahdanau et al.,2014])和算法學習([Graves et al.,2014])方面的效果中扮演了重要決策。 [Vinyals et al., 2015]提出了一種帶有特殊注意機制的網絡模型—Pointer Net，并使用有監(jiān)督學習的方法來通過此模型求解旅行商問題(Travelling Salesman Problem)。[Bello et al., 2016]提出了一種基于強化學習思想的神經組合優(yōu)化(neural combinatorial optimization)框架，并使用此種框架求解了旅行商問題和背包問題(Knapsack Problem)。因為此種框架的有效性和普適性，本研究在求解新型裝箱問題中主要使用了此種框架和方法。
3.針對三維裝箱問題的DRL方法
3.1 問題定義
在經典的三維裝箱問題中，需要將若干個物品放入固定尺寸的箱子中，并最小化箱子的使用數(shù)量。與經典問題不同的是，本文提出的新型裝箱問題的目標在于設計能夠容納一個訂單中所有物品的箱子，并使箱子的表面積最小。在一些實際業(yè)務場景中，例如跨境電商中，包裝物品時使用的是柔性的塑料材料，而且由于包裝材料的成本與其表面積直接正相關，所以最小化箱子的表面積即意味著最小化包裝成本。
本文提出的新型裝箱問題的數(shù)學表達形式如下所示。給定一系列物品的集合，每個物品i都有各自的長(li)、寬(wi)和高(hi)。優(yōu)化目標為尋找一個表面積最小且能夠容納所有物品的箱子。我們規(guī)定(xi, yi,zi)表示每一個物品的左下后(left-bottom-back)角的坐標，而且(0, 0, 0)表示箱子的左下后角的坐標。決策變量的符號及其含義如表1所示。基于以上問題描述和符號定義，新問題的數(shù)學表達形式為：
3.2 DRL方法
在本部分中，我們將介紹用于求解新型三維裝箱問題的DRL方法。在求解三維裝箱問題時，決策變量主要分為三類：
（1） 物品放入箱子的順序；
（2） 物品在箱子中的擺放位置；
（3） 物品在箱子的擺放朝向。
我們首先設計了一種啟發(fā)式算法來求解此類新型三維裝箱問題。此種算法的基本思想為：在放入一個物品時，遍歷所有可用的空余空間和物品朝向，并選擇能夠最小化表面積的組合。然后再遍歷所有物品，確定一個能夠最小化浪費空間體積（least waste space）的物品。算法的詳細步驟請見附錄。在本文中，我們使用DRL方法來優(yōu)化物品的放入順序，在確定了物品的放入順序之后，選擇物品的擺放位置和朝向時使用和以上啟發(fā)式算法相同的方法。所以本研究的重點在于使用DRL方法來優(yōu)化物品的放入順序。在未來的研究中，我們將會把物品的放入順序、擺放位置和朝向統(tǒng)一納入深度強化學習方法框架中。
3.2.1 網絡結構
本研究主要使用了[Vinyals et al.,2015]和[Bello et al.,2016]提出的神經網絡結構。在Vinyals和Bello等人的研究中提出了一種名為Pointer Net (Ptr-Net)的神經網絡來求解組合優(yōu)化問題。例如，在求解旅行商問題時，二維平面中每個點的坐標被輸入到網絡模型中，經過計算之后，模型的輸出為每個點被訪問的順序。這種網絡結構與[Sutskever et al.,2014]提出的序列到序列模型非常相似，但是有兩點不同：第一，在序列到序列模型中，每一步的預測目標的種類是固定的，但是在Ptr-Net中是可變的；第二，在序列到序列模型中，在解碼階段通過注意機制將編碼階段的隱層單元組合成為一個上下文向量信息，而在Ptr-Net中，通過注意機制來選擇（指向）輸入序列中的一個來作為輸出。
本研究中使用的神經網絡模型的結構如圖1所示。網絡的輸入為需要裝箱的物品的長寬高數(shù)據(jù)，輸出為物品裝箱的順序。網絡中包含了兩個RNN模型：編碼網絡和解碼網絡。在編碼網絡的每一步中，首先對物品的長寬高數(shù)據(jù)進行嵌入表達（embedded），然后再輸入到LSTM單元中，并獲得對應的輸出。在編碼階段的最后一步，將LSTM單元的狀態(tài)和輸出傳遞到解碼網絡。在解碼網絡的每一步中，在編碼網絡的輸出中選擇一個作為下一步的輸入。如圖1所示，在解碼網絡中的第3步的輸出為4，則選擇（指向）編碼網絡的第4步的輸出，將其作為解碼網絡下一步（第4步）的輸入。此外，在每一步的預測過程中還使用了[Bello et al., 2016]提出的Glimpse機制來整合編碼階段和解碼階段的輸出信息。
圖1 神經網絡模型的結構
3.2.2 基于策略的強化學習方法
3.2.3 基準值的更新
在本研究中，我們使用了一種基于記憶重放的方法來不斷地更新基準值。首先，對于每一個樣本點si，通過啟發(fā)式算法獲取一個裝箱方案，并計算其表面積，作為b(si)的初始值。之后在每一步的訓練過程中，通過以下公式來更新基準值：
3.2.4 隨機采樣與集束搜索（Beam Search）
在模型的訓練階段，我們從模型預測的概率分布中進行隨機選取作為輸出。但是在驗證階段，我們采用貪婪策略來進行選擇，即在每一步中，我們選取概率分布中概率最大的備選項作為輸出。除此之外，我們還在驗證階段使用來集束搜索的方法來提高模型的效果，即在每一步中不是選擇對應概率最高的備選項，而是選擇概率最高的前k個備選項作為輸出。
通過以上描述，模型的整個訓練步驟總結為：
4.數(shù)值實驗
為了驗證模型的效果，我們基于大量實際業(yè)務數(shù)據(jù)完成了數(shù)值實驗。根據(jù)實驗過程中每個訂單中物品數(shù)量的不同（8，10和12），實驗分為了三個部分，但是每次實驗過程中的超參數(shù)均相同。在每次實驗中，我們采用了15萬條訓練樣本和15萬條測試樣本。在實驗過程中，每批訓練的樣本量為128，LSTM的隱層單元的數(shù)量為128，Adam的初始學習速率為0.001，并且每5000步以0.96的比例衰減。網絡模型的參數(shù)的初始值均從[-0.08, 0.08]中隨機選取。為了防止梯度爆炸現(xiàn)象的出現(xiàn)，我們在訓練過程中使用L2正則方法對梯度進行修剪。在更新基準值的過程中，的取值為0.7。在每次訓練中，我們在Tesla M40 GPU上訓練100萬步，每次的訓練時間大約為12小時。在驗證階段，使用集束搜索方法時，集束搜索的寬度為3。模型主要通過TensorFlow來實現(xiàn)。
數(shù)值實驗的結果請見表2。主要評價指標為平均表面積（Average surface area, ASA）.從表中可以看出，在使用集束搜索的情況下，本文提出的基于DRL的方法在三類測試集上分別可以獲得大約4.89%, 4.88%, 5.33%的效果提升。此外，我們還通過窮舉的方法獲得了對于8個物品測試數(shù)據(jù)中5000個樣本數(shù)據(jù)的最優(yōu)物品放入順序，并計算得到了啟發(fā)式算法的結果與最優(yōu)解的平均差距為10%左右，這說明基于DRL的方法的結果已經與最優(yōu)解比較接近。
5.結論
本文提出了一類新型三維裝箱問題。不同于傳統(tǒng)的三維裝箱問題，本文提出的問題的優(yōu)化目標為最小化能夠容納所有物品的箱子的表面積。由于問題的復雜性和求解難度，此類問題非常難以獲得最優(yōu)解，而大部分啟發(fā)式算法又缺乏普適性。所以本文嘗試將Pointer Net框架和基于深度強化學習的方法應用到了對此類問題的優(yōu)化求解中。本文基于大量實際數(shù)據(jù)對網絡模型進行了訓練和驗證，數(shù)值實驗的結果表明基于深度強化學習方法獲得的結果顯著好于已有的啟發(fā)式算法。本項研究的主要貢獻包括：第一，提出了一類新型的三維裝箱問題；第二，將深度強化學習技術應用到了此類新問題的求解中。在之后的研究中將會深入探索更有效的網絡模型和訓練算法，并且會嘗試將物品的擺放位置和朝向的選擇整合到模型中。
附錄：
A： 三維裝箱問題的啟發(fā)式算法
用于求解本文的新型三維裝箱問題的啟發(fā)式算法包括最小表面積（least surface area）算法和最小浪費空間（least wastespace）算法。算法的詳細步驟如下所示：
B：關于新型三維裝箱問題為NP-hard問題的證明
引理B.1: 本文提出的新型三維裝箱問題為NP-hard問題。
證明：
來源：阿里技術
本文為云棲社區(qū)原創(chuàng)內容，未經允許不得轉載，如需轉載請發(fā)送郵件至yqeditor@list.alibaba-inc.com；如果您發(fā)現(xiàn)本社區(qū)中有涉嫌抄襲的內容，歡迎發(fā)送郵件至：yqgroup@service.aliyun.com 進行舉報，并提供相關證據(jù)，一經查實，本社區(qū)將立刻刪除涉嫌侵權內容。
