包材推荐中的算法应用

蓝球爱好者

目录一、业务背景二、算法架构? ? 1. 规则????2. 算法三、算法原理? ? 1. 装箱????2. 装袋四、衍生应用????1. 切箱????2. 合包????3. 箱型设计????4. 包装方案推荐五、作者结语一业务背景任何一家电商的商品出库场景中，都涉及到打包——即把订单中的商品用包材进行包裹，常见的打包方式有装袋和装箱。仓库打包作业主要决策两点：包材类型：一般根据商品种类判断，比如衣服使用塑料袋、日用品使用纸箱等，具体由人工录入规则维护在系统中，针对订单输出对应可用包材类型；包材型号：具体取决于装箱还是装袋，要求使用的纸箱的体积最小或者袋子的面积最小，并且能装下订单中的所有商品。在实操中，系统通常通过拆箱逻辑应对订单中商品较多以至最大型号都装不下的情形。针对第二点，人工决策不仅效率低而且容易造成浪费，主要是包材型号较多，而且是折叠状态。作业人员肉眼难以甄别能装下所有商品且体积最小的型号，最保险的做法是选择较大的纸箱。这样会造成浪费包材，增加履约成本。此外空间利用率不高将导致商品在运输中容易破损，引发客诉甚至退换货。在这样背景下，需要一套包材推荐算法来解决上述包材浪费和空间利用率不高的问题。二算法架构在详细进入算法细节之前，先大致了解下架构流程，具体如下图所示。规则如上图所示，包材推荐决策过程中首先需要经过两道业务规则，需要人工手动维护到系统中：根据约束条件过滤筛选可用的包材类型及范围：商品入库上架时即需要维护相关信息，至少要限定使用的包材类型（比如纸箱还是塑料袋）；查询商品是否指定使用包材：满足一些有特殊包装要求的商品，遵循非必要不维护原则。算法算法同样分为两步：查询是否存在统计规则：由于商品或者包材基础尺寸均存在不准确的可能性，严格根据尺寸匹配算法推荐的包材规格亦存在偏差；若某种商品其包材推荐准确率较低，可实操中使用某种规格占比较高且超过一定阈值（比如 80%）的情况，可认为对于该商品此种规格是最优选择并形成规则记录下来，下一次同样商品再来请求时可直接使用规则；根据尺寸匹配算法推荐：可分为装箱和装袋算法，后者其实可通过变形转化为前者（算法详情请见下一章节）。主要流程如下图所示——把纸箱按体积从小到大排序，返回第一个能装下商品的箱型即可，这样一来就简化成一个装箱判定问题。三算法原理装箱装箱问题在运筹学中是一个经典并且非常重要的组合优化问题。所谓组合优化，是指在离散的、有限的数学结构上，寻找一个满足给定条件，并使其目标函数值达到最大或最小的解。一般来说,组合优化问题通常带有大量的局部极值点，往往是不可微的、不连续的、多维的、有约束条件的、高度非线性的NP完全问题。三维装箱问题亦是 NP-hard 问题，而包材推荐就是此问题的一个典型应用，其本质就是如何合理的放置商品以达到装下的目的。包材推荐场景中装箱算法具体逻辑可根据商品种类和数量分为以下三种：1. 单品单件：将包材和商品尺寸均按照降序排序得到?(L,W,H)?和?(l,w,h)?，若满足则判定可以装下。2. 单品多件：遍历各种堆叠方式，对于每种堆叠方式找到最小凸包（即能把所有商品包住的立方体），再把这个凸包当成单品单件去做判定是否装下。假设有N件商品，其尺寸为(l,w,h)，堆叠方式可表达为，即在三个维度上商品件数。算法逻辑描述如下：