BT

如何利用碎片时间提升技术认知与能力? 点击获取答案

苏宁智能包装解决方案:小包裹背后的大智慧

| 作者 叶梦贤 关注 0 他的粉丝 , 杨宇刚 关注 0 他的粉丝 发布于 2017年12月15日. 估计阅读时间: 13 分钟 | CNUTCon 了解国内外一线大厂50+智能运维最新实践案例。

近年来,我国快递行业随着互联网和电子商务的发展而成长起来,其发展势头迅猛,国家邮政局统计数据显示,2016年全国快递业务量达312.8亿件,同比增长51.7%,中国快递业已经连续六年每年增长超过50%,中国已成全球第一快递大国。随着快递量的持续增长,快递在给我们每个人生活带来很大便利的同时,也带来了快递企业包装成本的上升和严重的快递包裹材料浪费污染问题,2016年全国快递共消耗编织袋约32亿条、塑料袋约68亿个、37亿个包装箱以及3.3亿卷胶带。包装过度,大材小用,回收使用率低造成了包装成本的上升、用户体验的降低和资源的极大浪费,包装耗材的低碳化、环保化亟待加强。

苏宁物流研发大数据团队,利用历史数据分析和大数据算法技术,推出“智能包装解决方案”,结合客户订单信息、商品主数据,包装耗材数据等相关数据进行大数据算法模型优化,自动为顾客商品确认包装材料类型、包装应用、确定装箱顺序和装箱位置,实现包装的智能化应用。通过智能包装解决方案在仓库包装的应用,每年可为苏宁物流节约包装成本近千万。同时,通过新包装材料(可回收利用“漂流箱”)的推广使用,促进了包装减量化和循环利用,不仅仅节约包装成本,提升用户体验,更重要的是能够保护环境和节约资源。每个漂流箱循环使用2000次,大约可节约1棵10年树龄的树木。漂流箱在全国范围投放,每年节省下来的快递盒可绕地球一圈。

苏宁智能包装解决方案技术

合单与拆包

合单与拆包可以理解为两个“相反”的操作,简而言之,合单是将同一时间窗口内的相同收货地址的订单合并化零为整,拆包则是再将一个订单根据业务逻辑拆成多个包裹进行派送。两个操作的目的都是为了提高客户收货体验。

为了保证合单的效率,我们只考虑同一个时间窗口内产生的订单进行合并而不是对全天的订单进行合并。在同一时间窗口内,每个订单将会与其他订单做匹配,如果发现多个订单共用一个收货地址,系统将自动将这些订单合并到一起,化零为整。由于商品有不同的属性以及包装材料大小的限制,同一订单需要拆分成多个包裹进行打包。例如,客户在大促时买了大量厕所清洁产品和食品两类商品,如果将两类商品混合打包到一个包裹中,将大大降低客户体验,因此我们将两类商品分开,分别打包到不同的包裹中进行派送。同时,如果两个包裹装不下客户的所有商品,那我们再将商品分装到多个包裹中。

完成合单与拆包并确定包装材料的数量与种类后,下一步系统将会调用包装推荐算法推荐合适大小的包装材料。

包装推荐

装箱问题在物流与生产系统中是一个经典并且非常重要的优化问题。系统通过包装推荐功能找到合适大小的包装材料推荐给业务操作人员来包装客户的商品,而包装推荐就是装箱问题的一个典型应用,其本质就是如何合理的放置商品以达到包装箱的装填率最大化。2维装箱问题已被证明是个NP-hard(Coffman et al., 1980)问题,NP是指非确定性多项式(non-deterministic polynomial,缩写NP)。所谓的非确定性是指,可用一定数量的运算去解决多项式时间内可解决的问题。NP-hard问题通俗来说是其解的正确性能够被“很容易检查”的问题,这里“很容易检查”指的是存在一个多项式检查算法。相应的,若NP中所有问题到某一个问题是图灵可归约的,则该问题为NP困难问题。同理可得,3维装箱问题也是个NP-hard问题。

3维装箱数学模型

约束条件(1),(2),(3)和(4)一起用来确保放置商品时,不会存在不同商品位置重叠的情况。约束条件(5),(6)和(7)确保商品不会被放置到包装材料外面。对于同个商品,不同的放置方式,将会有不一样的长、宽、高。,约束条件(8),(9)和(10)用来重定义商品i长、宽、高。在本段开头,我们已经假设所有商品为规则的长方体,而一个长方体商品一共有三个不同的面,每个面为底有两种摆法,所以一个商品一共有6种不同的放置方式。6种放置方式如下图所示。

6种放置方式

由模型可见该问题为一个混合整数非线性规划问题,由于该类问题的复杂性,其不可能在合理时间内获得精确解。简而言之,该问题很难在合理的时间内被求解出来,不能满足我们业务实时计算反馈推荐的需求,因此我们开发了自己的包装推荐算法去寻找较好的可行解。

包装推荐算法

对于装箱问题,直接影响到装填率的因素有两个,分别是商品装箱顺序和商品装箱位置。针对这两个因素,我们分别使用了不同的优化算法进行求解。首先,我们使用了遗传算法对商品装箱顺序进行优化计算,然后我们使用了3维装箱算法对商品装箱位置进行优化计算。

整体流程

整个包装推荐算法流程如下图所示。我们首先将包装箱按最长边降序排列,筛选出符合最长边和体积要求的包装材料。

包装推荐算法流程图

然后我们初始化商品装箱序列,并使用遗传算法对商品装箱序列进行调整。在评估当前顺序的适应度时,我们调用3D装箱算法对商品进行放置,若装箱算法依照当前装箱顺序能将所有商品打包进包装材料,则停止计算。否则,继续遗传算法对装箱顺序进行调整,再评估新顺序的适应度。在往同一个包裹放置多于一件商品的情况下,由于只依靠最长边与体积无法确定商品是否都能装下,因此我们需要用遍历的方式把所有的包材依照上面的逻辑全部计算一遍,然后找出装填率最高的一种包材。

前面我们大致介绍了下包装推荐算法的整体计算流程,接下来我们将深入到细节,给大家详细介绍下算法每个模块的实现逻辑。

装箱顺序优化

在打包多件商品的情况下,通过改变商品的装箱顺序能获得不同的装箱效果。如下图所示先放置小件商品和先放置大件商品会得到不同的装箱结果。

装箱顺序对比图

遗传算法具有很好的全局寻优能力,因此我们选择了该算法去优化装箱顺序。遗传算法(Genetic Algorithm)是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法。我们使用了实数编码方式生成代表装箱顺序的基因种群。然后在进化的过程中,我们对选中的父代基因进行交叉(Crossover)与变异(Mutation)操作。如下图所示,基因的交叉就是对选中的两条基因进行元素交换以生成新的子代。交叉的方式有很多种,在此我们罗列出比较常用的几种方式。

基因交叉示例图

交叉操作主要是使种群内的信息能够进行局部交换获得新的子代,而变异操作是为了使种群内能够加入新的随机信息。由于这个随机的新信息有可能是有利于向最优解收敛的有益信息,也有可能是使搜索偏离最优解的误导信息,因此我们需要慎重地使用变异操作。我们使用了概率值来控制变异操作,当达到一定概率时,变异操作才会被激活从而获取新的随机信息。相对于交叉操作,变异操作是针对于单条基因进行变换操作。变异的方式也有很多,下图中展示了最常用的几种变异方式。

基因变异示例图

完成交叉与变异操作后,我们需要对新获得的基因组进行评估。我们依据新获得的基因即装箱顺序,调用3维装箱算法去尝试装箱。

装箱位置优化

除了装箱顺序外,在打包商品时,商品的放置位置也直接影响到最终的装箱效果。装箱位置包含了商品在包装箱内的放置位置与放置方式两个子问题。下面两个对比图分别展现了商品不同放置位置与不同放置方式最终对装箱结果的影响。

不同放置位置与不同放置方式对比图

在已知装箱顺序后,3维装箱算法决定如何寻找合适的商品放置位置与放置方式。每次放置一个商品时,我们会尝试6种不同的商品放置方式,看哪种能在箱子里放得下。每放置一个商品到一个长方形空间里时,我们称未被商品占去位置的空闲空间为残存空间(residual space)。算法对残存空间进行切割,保留能留下最大残存空间的切割方式。因为留下的残存空间越大,那之后更有可能装下剩下的商品。算法将贪婪得采用6种商品放置方式当中能生成最大残存空间的放置方式,以保证剩下的商品能顺利装箱。

切割方案对比图

上图为两种不同的切割方式对比图。灰色区域为前一个商品放置位置,A、B、A’和B’为两种不同切割方式所产生的不同的残存空间,由于A’的面积大于B,所以我们倾向保留切割方案B。

在放置商品的过程中,完整的空间被不断得切割成更小的残存空间,当剩余的商品在所有的残存空间里放不下时,算法就考虑调整一些残存空间以获得更合适的空间来放置商品。调整的方式可以千变万化,但是计算时间有限,因此我们人为缩小了搜索空间:只有两个在同一水平面并共享一个顶点和一条边的残存空间算法才尝试调整。算法从所有的残存空间里挑出满足条件的两个残存空间尝试进行调整,即在同一水平面并且共享一个顶点及一条边。如下图所示,调整前的残存空间分别为A和B,两个空间共享一个顶点及一条边。算法将会尝试将残存空间进行调整,生成新的残存空间A’ 和B’来尝试装箱。若新产生的残存空间可以放置一个商品,那我们保留该调整方案,否则我们尝试调整其余残存空间。通过对残存空间的调整,我们更有效的利用了包装箱的空间。

残存空间调整前后对比图

如上图所示调整前,残存空间A’ 和B’共享边(a, b)和顶点b并在同一水平面上。经过调整后我们获得新的空间A和B,其中B能装入之前A’和B’无法装入的狭长型商品。

Spark并行计算

苏宁全国拥有47个仓库,每天有大量包裹需要实时推荐包材,单机版的算法并不能满足业务要求。因此我们使用Spark Streaming 实现算法并行化。如下图所示,上游系统实时将批次数据写入Kafka。Spark Streaming 从Kafka不同分区实时获取数据生成RDD存放在内存中,然后根据包裹号对内存里的RDD进行拆分,分发到不同的Executor (执行器)。在各个单独的Executor中,调用实时推荐包材算法对分配到的相应数据进行计算。完成计算后,每个Executor将计算结果即推荐结果写入Kafka不同分区中。下游系统再从Kafka中实时取走推荐结果。

算法并行执行架构图

苏宁智能包装解决方案已经在苏宁仓库运行,通过统一包装耗材标准,将包装耗材种类从30种缩减到14种,在提高包装效率的基础上包装填充率总体提高59%。同时,可循环的塑料箱—“漂流箱”已经在北京、上海、广州、南京、深圳、杭州、武汉、成都八大城市上线投入10000余个,长约0.3米,宽0.2米的“漂流箱”,用它代替普通纸箱装载消费者购买的产品,由快递员进行“最后一公里”投递。用户可以在苏宁自提点、社区代收点自提快递,取出商品后将“漂流箱”放回自提点回收。此外,用户还可以选择送货上门,当面拆箱验货签收后,将漂流箱交由快递员带回作循环使用。为了增强用户体验,这些漂流箱还特意设计了牢固的“封箱扣”,保证商品安全,保障用户隐私。苏宁智能包装解决方案的推行,每年可节约1000万元的包装成本,同时,“漂流箱”及各种隐私包装的应用,保障客户的购物隐私,增强了客户的购物体验。

作者介绍

叶梦贤,运筹学与定量物流硕士研究生,苏宁物流研发中心算法工程师,主要负责物流优化,运筹学、优化算法在苏宁物流的应用。曾任埃森哲资深分析师,负责与物流相关算法设计与开发。专注于物流优化,运筹学,优化算法研究与应用,希望借助运筹学、优化算法,把握技术变革,助推智慧零售。

评价本文

专业度
风格

您好,朋友!

您需要 注册一个InfoQ账号 或者 才能进行评论。在您完成注册后还需要进行一些设置。

获得来自InfoQ的更多体验。

告诉我们您的想法

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我

看不到图 by Wang Tony

看不到图

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我

1 讨论

登陆InfoQ,与你最关心的话题互动。


找回密码....

Follow

关注你最喜爱的话题和作者

快速浏览网站内你所感兴趣话题的精选内容。

Like

内容自由定制

选择想要阅读的主题和喜爱的作者定制自己的新闻源。

Notifications

获取更新

设置通知机制以获取内容更新对您而言是否重要

BT