包材推荐中的算法应用｜得物技术
目录
一、业务背景
二、算法架构
1. 规则
2. 算法
三、算法原理
1. 装箱
2. 装袋
四、衍生应用
1. 切箱
2. 合包
3. 箱型设计
4. 包装方案推荐
五、作者结语
一、业务背景
任何一家电商的商品出库场景中，都涉及到打包——即把订单中的商品用包材进行包裹，常见的打包方式有装袋和装箱。
仓库打包作业主要决策两点：
包材类型：一般根据商品种类判断，比如衣服使用塑料袋、日用品使用纸箱等，具体由人工录入规则维护在系统中，针对订单输出对应可用包材类型；
包材型号：具体取决于装箱还是装袋，要求使用的纸箱的体积最小或者袋子的面积最小，并且能装下订单中的所有商品。在实操中，系统通常通过拆箱逻辑应对订单中商品较多以至最大型号都装不下的情形。
针对第二点，人工决策不仅效率低而且容易造成浪费，主要是包材型号较多，而且是折叠状态。作业人员肉眼难以甄别能装下所有商品且体积最小的型号，最保险的做法是选择较大的纸箱。这样会造成浪费包材，增加履约成本。此外空间利用率不高将导致商品在运输中容易破损，引发客诉甚至退换货。
在这样背景下，需要一套包材推荐算法来解决上述包材浪费和空间利用率不高的问题。
二、算法架构
在详细进入算法细节之前，先大致了解下架构流程，具体如下图所示。
规则
如上图所示，包材推荐决策过程中首先需要经过两道业务规则，需要人工手动维护到系统中：
根据约束条件过滤筛选可用的包材类型及范围：商品入库上架时即需 要维护相关信息，至少要限定使用的包材类型（比如纸箱还是塑料袋）；
查询商品是否指定使用包材：满足一些有特殊包装要求的商品，遵循 非必要不维护原则。
算法
算法同样分为两步：
查询是否存在统计规则：由于商品或者包材基础尺寸均存在不准确的 可能性，严格根据尺寸匹配算法推荐的包材规格亦存在偏差；若某种商品 其包材推荐准确率较低，可实操中使用某种规格占比较高且超过一定阈值 （比如 80%）的情况，可认为对于该商品此种规格是最优选择并形成规则 记录下来，下一次同样商品再来请求时可直接使用规则；
根据尺寸匹配算法推荐：可分为装箱和装袋算法，后者其实可通过变 形转化为前者（算法详情请见下一章节）。主要流程如下图所示——把纸 箱按体积从小到大排序，返回第一个能装下商品的箱型即可，这样一来就 简化成一个装箱判定问题。
三、算法原理
装箱
装箱问题在运筹学中是一个经典并且非常重要的组合优化问题。所谓组合优化，是指在离散的、有限的数学结构上，寻找一个满足给定条件，并使其目标函数值达到最大或最小的解。一般来说,组合优化问题通常带有大量的局部极值点，往往是不可微的、不连续的、多维的、有约束条件的、高度非线性的 NP 完全问题。
三维装箱问题亦是 NP-hard 问题，而包材推荐就是此问题的一个典型应用，其本质就是如何合理的放置商品以达到装下的目的。
包材推荐场景中装箱算法具体逻辑可根据商品种类和数量分为以下三种：1.单品单件：将包材和商品尺寸均按照降序排序得到 (L,W,H) 和 (l,w,h) ，若满足则判定可以装下。
2.单品多件：遍历各种堆叠方式，对于每种堆叠方式找到最小凸包（即能把所有商品包住的立方体），再把这个凸包当成单品单件去做判定是否装下。
假设有 N 件商品，其尺寸为(l,w,h)，堆叠方式可表达为，即在三个维度上商品件数。
算法逻辑描述如下：
多品多件：此种场景较为复杂，求解方法可分为精确解和启发式。
精确解：
如图所示，将商品顶点坐标、长宽高放置方向、相互位置关系作为变量，运用整数规划建模调用求解器求解，只要以下约束方程组有可行解即判定可装下。
（1），（2），（3）和（4）一起用来确保放置商品时，不会存在不同商品位置重叠的情况。 （5），（6）和（7）确保商品不会被放置到包材外面。（8），（9）和（10）用来定义商品放置方式下的长宽高（不同的放置方式对应不一样的长宽高）。
（11）确保每个商品只有一个放置方式。（12）定义 0-1 变量表示商品间前后、左右、上下的空间关系。（13）定义 0-1 变量表示商品放置方式。
由于该类问题的复杂性，整数规划瓶颈在于当商品件数超过一定数量（比如 8）时求解难度和时间将大幅增加，无法在规定时间内获得精确解。
启发式：相对精确解，启发式牺牲精度换取速度，可快速求解。常见的三维装箱启发式算法有：
切割空间我们将商品放在箱子的一个角上，这样我们就可以得到[a,b,c]三个最大剩余空间，组成一个最大 剩余空间组，如下图：
上图是只放入一个商品的情况，如果放入一个新的商品，则最大剩余空间组就需要更新。
在该算法中，对于一个即将放入某一个最大剩余空间的商品来说，就会有 若干种放置方式。为了找到最优的放置方式，可以使用树搜索。
将一开始的空箱状态 S 定义为根节点，每一个节点表示一种放置状态。在 每个节点上使用某种放置方式 rank 评价函数，选择最优的前 m 个放置方 式，作为下一层的子节点。如此迭代直到迭代到第 d 层（d 是预先设定的 深度）。例如在 d=2,m=3 时，得到的树如下图所示：当迭代到 d 层时，对于每一个叶节点继续向下迭代，采用最优的放置方式直到将箱子装满。再选取其中装载率最优的完全解所对应的叶节点，作为下一次迭代的根节点。
Largest Area Fit First 首先放置覆盖箱子水平面积最大的商品，以它的高度成为水平高度。接着能够填满剩余高度的商品优先放置。随后的商品堆放在同一层的剩余空间中，体积最大的商品优先。如果商品高度低于水平高度，算法也会尝试在那里放置一些。
暴力搜索该算法没有选择最佳排列顺序或放置方向的逻辑，而是遍历所有排列、方向的可能性。由于其复杂性是指数级的，因此在合理的时间内可以包装的商品可行数量有限。
其他常用启发式：遗传、模拟退火等，不再赘述。
装袋
袋子是软的，可变形，没有固定尺寸。近似的做法是把袋子看成两层薄膜，长宽为(L,W)（厚度为 0）。然后把它捏成长方体，尺寸记作 (l,w,h) ，如下图所示：
图片源于网络
其中阴影部分代表上层，白色部分代表下层。只要长宽高满足如下条件：
再适当地枚举 (l,w,h) ，即把装袋问题近似地转化成固定尺寸的装箱问题。
四、衍生应用
切箱
对于商品数量多的大订单/包裹，即使是最大的包材也有可能装不下，于是就有切箱算法需求——即基于包材推荐将原订单/包裹分割成若干个订单/包裹并且分别匹配最优包材。
合包
对于同用户同地址的不同订单/包裹，在某些合适场景下（比如跨境集运、同库操作）可能进行合包，以减少包裹数从而降低物流成本。此时通常需要通过包材推荐算法判断是否能够合包。
箱型设计
今年的订单结构改变了，箱型怎么做调整才能适应新的订单结构？新来了一个大商家，原来的箱子还能用吗，是否需要新增箱子来匹配新商家的需求？大促要来了，现有的箱子能否匹配大促的需求？每个地区买的物品不同，是否需要针对不同的区域来设计更优的箱型？每年的 SKU 种类数不断变多，是否需要多增箱型来适应不断变多的 SKU 组合?
包材推荐是基于现有包材基础上推荐合适箱型， 而针对上述问题的解法是直接设计优化箱型尺寸，从源头直接减少浪费、节省成本。箱型设计需要基于数以亿计订单的尺寸，运用运筹优化算法重新设计一系列合适的箱型尺寸，最大化空间利用率或最小化包材表面积，其求解难度远高于包材推荐。目前得物供应链平台已初步成功打造一款箱型设计算法工具，在多个类目数据测试中已验证其效果。
包装方案推荐
推荐出库打包时除了要使用合适包材，有时还需要根据商品特点决定使用何种包装方案。比如易碎品、易燃品、高价品等可能都对应使用不同的填充物、包装方式。通常包装方案都需要人工进行手动输入维护，耗时费力。可以通过多模态算法基于商品文字描述、图片等信息自动识别归类是哪一种商品，并对应推荐使用预先设置好的哪一种包装方案。
五、作者结语
本文侧重介绍包材推荐中运筹优化算法实现的具体方法以及可以发挥的作用，旨在让大家了解其数学原理和业务价值。当然，算法在包材推荐中其实只是其中一个方面，非常依赖基础数据准确性，需要结合规则维护、报表建设、归因分析等各种手段一起提高推荐一致率，最终达到降本增效的目标。包材推荐算法在电商、物流领域已普遍应用，无论是在得物还是一些友商业务中均获得落地价值。由于得物目前商品结构大多数为单品单件，合单/合包比例也很低，因此算法应用还处于相对起步阶段，覆盖范围还不高，发挥作用还不明显。然而我们相信随着得物平台的全面发展，包材推荐对算法的需求会越来越强烈，供应链平台算法团队也期待能与业产研各方一起共同打造具有得物特色的包材推荐算法应用落地体系。
引用：
《仓储知识库 | 包材推荐装箱算法：贪婪前向树算法》https://www.163.com/dy/article/ICC2J41L0530UFIR.html
《苏宁智能包装解决方案：小包裹背后的大智慧》https://www.infoq.cn/article/suning-packaging-solutions
《包材推荐系统的设计与实践》https://blog.csdn.net/qx3501332/article/details/117283804
*文 / Lagrange
本文属得物技术原创，更多精彩文章请看：得物技术
未经得物技术许可严禁转载，否则依法追究法律责任！
版权声明: 本文为 InfoQ 作者【得物技术】的原创文章。
原文链接:【http://xie.infoq.cn/article/42cebd80d89cede61ee209eee】。文章转载请联系作者。
得物APP技术部 2019-11-13 加入
关注微信公众号「得物技术」
评论