业务背景
网易严选是一家自营电商，每天有数以万计的订单需要拣货、打包和出库。打包的过程就是把订单中的商品用包材进行包裹，常见的打包方式有缠膜、装袋和装箱。袋子和箱子有不同的种类和型号，比如袋子有共挤膜袋、镀铝膜袋、塑料袋等。
仓库作业工人需要对商品按订单进行打包。具体来说，主要决策两件事：
第一，根据订单的商品选择正确的包材类型。比如服装毛巾等柔软的商品适合用袋子；易碎品、液体和贵重物品适合用纸箱；有些商品自身的包装结实耐磨，可以选择缠膜或者裸发。如果适用的包材类型有冲突，则选择优先级最高的包材。
第二，如果是装箱（或装袋），需要决定箱型。我们要求纸箱的体积最小（袋子的面积最小），并且能装下订单中的所有商品。在实际情况中，如果订单中商品过多，系统会预先把大订单拆成多个子订单。
人工决策不仅效率低而且容易造成浪费。原因有两点：
第一，商品种类太多，人记不住正确的包材列表，只能凭经验判断。工人害怕出错，最保险的方法是一律使用纸箱，于是一些本来应该缠膜或装袋的订单，结果用纸箱打包。
第二，纸箱型号有三十多种，而且是折叠状态（如下图所示）。工人难以判断哪个纸箱是体积最小且能装下整个订单的商品。最保险的做法是选择较大的纸箱。
这样的结果是浪费包材，增加履约成本。此外，纸箱的空间利用率不高，导致商品在运输中容易破损，引发客户投诉甚至是退换货。
在这样的背景下，我们需要一套包材推荐系统来解决上述包材浪费和空间利用率不高的问题。
系统功能
系统的核心功能是实现订单的包材推荐，即给定订单中的商品列表，输出对应的包材型号。考虑到不同商品适用不同的包材类型，不同仓库有不同的包材列表，我们把这些业务限制称为约束条件。
为了满足多变的业务情况，包材推荐系统需要支持多种包材类型、约束条件和业务目标。
包材类型
包材类型需要考虑优先级，包材按优先级向下兼容。比如袋子的优先级低于箱子，那么可以用袋子装的商品也可以用箱子，反之则不行。同一个订单中的商品适用的包材类型可能不同，系统会选择优先级最高的包材。
当前支持的包材类型如下所示。
| 包材类型 | 说明 | 优先级 |
|---|---|---|
| 裸发 | 不使用任何包材 | |
| 缠膜 | 防尘和防潮的作用 | 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 的假设下）。
通俗地说，如果想要准确求解，那么随着物品数量的增加，计算需要的时间呈指数增长。例如，当物品的数量增加到十多个，计算时间可能是分钟、小时甚至是天的级别。
既然不知道装箱问题的正确答案，那么如何测试效果？
需要用一些方法构造三维装箱问题的实例，保证构造的实例符合预设的答案。可以考虑四种方法：
第一，根据箱型的可用空间进行随机切分，从而保证切分出的物体始终能装入该箱型；
第二，随机生成三维物品和摆放位置，保证物品摆放的长宽高不超过箱子的长宽高；
第三，随机生成三维物品，然后用精确算法进行求解（适用于物品数量较少的情况）。
第四，用真实的订单数据进行测试。虽然有测量误差和物品形状的干扰，但可以用来横向比较算法之间的差异。
总结
包材推荐系统主要解决的是人工选材导致的包材浪费和空间利用率不高的问题。站在企业的角度，包材推荐系统不仅节省了物流成本，还提升了打包效率；站在用户的角度，空间利用率的提升减少了投诉；站在社会的角度，该系统增加了裸发、缠膜和塑料袋的包裹量，从而减少了纸箱的浪费。
包材推荐不只是一个算法问题。除此以外，它还要考虑数据质量、业务限制和工程实现。在工程端，需要要保证服务的高可用，因此还要保障系统的性能和稳定，实时监控它的运行状态。