業務背景
網易嚴選是一家自營電商，每天有數以萬計的訂單需要揀貨、打包和出庫。打包的過程就是把訂單中的商品用包材進行包裹，常見的打包方式有纏膜、裝袋和裝箱。袋子和箱子有不同的種類和型号，比如袋子有共擠膜袋、鍍鋁膜袋、塑膠袋等。
倉庫作業勞工需要對商品按訂單進行打包。具體來說，主要決策兩件事：
第一，根據訂單的商品選擇正确的包材類型。比如服裝毛巾等柔軟的商品适合用袋子；易碎品、液體和貴重物品适合用紙箱；有些商品自身的包裝結實耐磨，可以選擇纏膜或者裸發。如果适用的包材類型有沖突，則選擇優先級最高的包材。
第二，如果是裝箱（或裝袋），需要決定箱型。我們要求紙箱的體積最小（袋子的面積最小），并且能裝下訂單中的所有商品。在實際情況中，如果訂單中商品過多，系統會預先把大訂單拆成多個子訂單。
人工決策不僅效率低而且容易造成浪費。原因有兩點：
第一，商品種類太多，人記不住正确的包材清單，隻能憑經驗判斷。勞工害怕出錯，最保險的方法是一律使用紙箱，于是一些本來應該纏膜或裝袋的訂單，結果用紙箱打包。
第二，紙箱型号有三十多種，而且是折疊狀态（如下圖所示）。勞工難以判斷哪個紙箱是體積最小且能裝下整個訂單的商品。最保險的做法是選擇較大的紙箱。
這樣的結果是浪費包材，增加履約成本。此外，紙箱的空間使用率不高，導緻商品在運輸中容易破損，引發客戶投訴甚至是退換貨。
在這樣的背景下，我們需要一套包材推薦系統來解決上述包材浪費和空間使用率不高的問題。
系統功能
系統的核心功能是實作訂單的包材推薦，即給定訂單中的商品清單，輸出對應的包材型号。考慮到不同商品适用不同的包材類型，不同倉庫有不同的包材清單，我們把這些業務限制稱為限制條件。
為了滿足多變的業務情況，包材推薦系統需要支援多種包材類型、限制條件和業務目标。
包材類型
包材類型需要考慮優先級，包材按優先級向下相容。比如袋子的優先級低于箱子，那麼可以用袋子裝的商品也可以用箱子，反之則不行。同一個訂單中的商品适用的包材類型可能不同，系統會選擇優先級最高的包材。
目前支援的包材類型如下所示。
| 包材類型 | 說明 | 優先級 |
|---|---|---|
| 裸發 | 不使用任何包材 | |
| 纏膜 | 防塵和防潮的作用 | 1 |
| 塑膠袋 | 裝衣服等柔軟的不易損壞的商品 | 2 |
| 共擠膜袋 | 裝柔軟且需要保護的商品 | 3 |
| 鍍鋁膜袋 | 功能與共擠膜袋一樣（看起來更高端） | 4 |
| T型箱 | T型紙闆, 折疊友善, 能緊貼商品的高進行包裝 | 5 |
| 普通紙箱 | 裝普通的商品 | 6 |
| 自制箱型 | 沒有任何可行的包材時傳回的虛拟包材類型 | 7 |
限制條件
在實際業務中，限制條件多樣而且多變，是以系統中維護的限制條件需要可插拔。
考慮如下限制條件（取交集）。
| 限制條件 | 說明 |
|---|---|
| 商品限制 | 根據商品屬性過濾得到可用的包材類型 |
| 類目限制 | 根據商品類目過濾得到可用的包材類型 |
| 包材限制 | 根據包材屬性判斷是否可用，例如最大可裝商品件數、最大可裝商品價值、最大承重 |
| 管道限制 | 根據銷售管道過濾得到可用的包材類型 |
| 承運商限制 | 根據承運商過濾得到可用的包材類型 |
| 倉庫限制 | 根據倉庫過濾得到可用的包材類型 |
| 運輸距離 | 根據長途和短途區分可用的包材類型 |
業務目标
業務目标是降低包材成本和提高包材的體積使用率。在計算最優包材的時候，可以選擇成本優先，也可以選擇體積使用率優先，或者是兩者的權重。
系統架構
包材推薦系統的整體架構如下圖所示。
其中最核心的子產品是裝箱算法和裝袋算法（紅色部分）。黃色部分主要是算法相關的工程，主要用規則實作。灰色部分主要是前端展示和底層資料。
算法架構
包材推薦算法的架構如下圖所示。
輸入商品清單，輸出包材類型和型号。算法的基本流程如下。
第一步：輸入包材清單，包材選擇器通過基礎資料子產品獲得商品、包材、承運商、倉庫等基礎資料。
第二步：包材選擇器根據限制條件得到訂單對應的可用包材類型和型号清單。
第三步：算法選擇器根據包材類型選擇對應的算法進行求解。例如，包材類型是袋子，那麼選擇裝袋算法。
第四步：輸出算法的計算結果（包材類型和型号）。
裝箱算法
裝箱算法是包材推薦系統的核心算法。下面我們簡單介紹一下裝箱算法需要解決的問題。
裝箱
把商品近似地看成長方體，然後測量商品的長寬高。
箱型選擇問題
給定 m m m個紙箱，它們的長寬高為 ( L i , W i , H i ) (L_i, W_i, H_i) (Li,Wi,Hi)， i = 1 , 2 , … , m i=1, 2, \ldots, m i=1,2,…,m；給定 n n n個物品，它們的長寬高分别為 ( l j , w j , h j ) (l_j, w_j, h_j) (lj,wj,hj)， j = 1 , 2 , … , n j=1, 2, \ldots, n j=1,2,…,n。傳回一個體積最小的紙箱，使得它能裝下 n n n個商品。如果不存在這樣的紙箱，則傳回空。
注意：允許物品90度旋轉（下文不再重複解釋）。
可以把紙箱按體積從小到大排序，傳回第一個能裝下所有商品的箱型即可。這樣一來，上面的問題可以簡化成一個判定問題。
三維裝箱判定問題
給定一個紙箱，它的長寬高為 ( L , W , H ) (L, W, H) (L,W,H)；給定 n n n個物品，它們的長寬高分别為 ( l j , w j , h j ) (l_j, w_j, h_j) (lj,wj,hj)， j = 1 , 2 , … , n j=1, 2, \ldots, n j=1,2,…,n。判斷所有物品是否能裝入紙箱。
裝袋
袋子在幾何上是一個三維流形，通俗地講，袋子是軟的。它可以捏成奇奇怪怪的形狀，精确地模組化和求解顯得非常困難。我們的做法是先把袋子看成“兩層”的矩形薄膜，長寬為 ( L , W ) (L, W) (L,W)， L ≥ W L\geq W L≥W（厚度為0）。
然後把它捏成長方體，長寬高記作 ( l , w , h ) (l,w,h) (l,w,h)，如下圖所示。
其中陰影部分代表上層的“膜”，白色部分代表下層的“膜”。長寬高滿足如下條件：
l + h ≤ L w + h ≤ W \begin{aligned} & l+h \leq L \\ & w + h \leq W \end{aligned} l+h≤Lw+h≤W
這樣一來，通過規則适當地枚舉 l , w , h l,w,h l,w,h的可能性，我們把裝袋問題近似地轉化成上面的裝箱問題。
柔性商品
我們一般假設普通物品不可折疊。但在實際情況中，很多物品是柔性的，例如服裝。這不僅會增加模組化和求解的難度，還讓測量更複雜。
假設柔性物品有 k k k 種尺寸， ( l 1 , w 1 , h 1 ) , … , ( l k , w k , h k ) (l_1,w_1,h_1), \ldots, (l_k, w_k, h_k) (l1,w1,h1),…,(lk,wk,hk)，且所有尺寸對應的體積相同，即 l i w i h i = l j w j h j l_i w_i h_i = l_j w_j h_j liwihi=ljwjhj， ∀ i ≠ j \forall i\neq j ∀i=j 。這樣一來，普通物品可以看成隻有一種尺寸的柔性物品。
在實際的測量中，我們可以要求測量人員按照2-3種折疊方式，測量物品的長寬高。通過這種方式，我們把柔性物品的裝箱問題轉化成了普通物品的裝箱問題。
裝箱算法結果需要滿足真陽性：算法說能裝下就能裝下；算法說裝不下，可以允許出錯。在裝箱問題的算法設計中，我們同時考慮了多個精确算法和啟發式算法，由于篇幅有限，這裡不介紹具體的裝箱算法。
效果評估
效果評估主要分為兩個方面：一個是業務效果，另一個是算法效果。最重要的當然是業務效果，算法效果的評估是為了改進算法，進而更好地提升業務效果。
業務效果
如前文所述，業務關心兩個業務名額：包材成本和空間使用率。由于測量存在誤差，還需要追蹤基礎資料和算法的異常。我們通過對比”推薦的“和”實際使用的“包材型号來分析問題。
推大用小：算法推薦的箱型比實際箱型大。說明人工經驗比算法結果好，對成本節省有利。從另一個方面也說明算法可能有優化的空間。
推小用大：算法推薦的箱型比實際箱型小。說明資料測量有問題或者人工操作不規範。這種情況下需要重點檢查資料的準确性以及加強對操作人員的教育訓練。
推用一緻：算法推薦的箱型與實際箱型一緻。基礎資料越準确，人工操作越規範，算法效果越好，于是推用一緻的占比就越高。
算法效果
算法效果主要從兩個方面衡量：一個是計算效率，我們要求單個請求的響應時間不超過1秒；另一個是計算效果，可以用準确率來衡量，比如計算1萬個三維裝箱判定問題的執行個體，然後評估正确回答的占比。
計算效果的衡量其實并不簡單。原因在于三維裝箱判定問題的計算複雜性是 NP-hard，這意味着它不存在多項式時間的精确算法（在 N P ≠ P NP\neq P NP=P 的假設下）。
通俗地說，如果想要準确求解，那麼随着物品數量的增加，計算需要的時間呈指數增長。例如，當物品的數量增加到十多個，計算時間可能是分鐘、小時甚至是天的級别。
既然不知道裝箱問題的正确答案，那麼如何測試效果？
需要用一些方法構造三維裝箱問題的執行個體，保證構造的執行個體符合預設的答案。可以考慮四種方法：
第一，根據箱型的可用空間進行随機切分，進而保證切分出的物體始終能裝入該箱型；
第二，随機生成三維物品和擺放位置，保證物品擺放的長寬高不超過箱子的長寬高；
第三，随機生成三維物品，然後用精确算法進行求解（适用于物品數量較少的情況）。
第四，用真實的訂單資料進行測試。雖然有測量誤差和物品形狀的幹擾，但可以用來橫向比較算法之間的差異。
總結
包材推薦系統主要解決的是人工選材導緻的包材浪費和空間使用率不高的問題。站在企業的角度，包材推薦系統不僅節省了物流成本，還提升了打包效率；站在使用者的角度，空間使用率的提升減少了投訴；站在社會的角度，該系統增加了裸發、纏膜和塑膠袋的包裹量，進而減少了紙箱的浪費。
包材推薦不隻是一個算法問題。除此以外，它還要考慮資料品質、業務限制和工程實作。在工程端，需要要保證服務的高可用，是以還要保障系統的性能和穩定，實時監控它的運作狀态。