一种基于数据驱动的解决包装和装载问题的方法
2019年03月21日 由 z朝闻 发表
23167
0
物流领域的一个重要问题是包装和装载问题,即如何将材料或货物装入箱子或集装箱。而如何在实际复杂场景中找到低成本、高效率的解决方案一直是一个难题。华为诺亚方舟实验室企业智能团队采用基于数据驱动(历史数据、人工仿真数据等)的启发式、元启发式算法,帮助解决华为供应链中的包装和装载问题。通过在线部署,取得了良好的效果,每年可节省几万美元。
自动包装
物料包装是指在一定的包装条件下,为给定的物料分配合适的包装盒。下图为华为的三级包装流程:
在实际情况中,主要困难有:
1)有很多种材料。2018年发货的材料有xx万多种,其中大部分没有准确的重量和尺寸信息。
2)有很多种箱子。2018年使用的箱子超过x千种,常用的箱子约有xxx种。
3)在不同的子场景中,包装约束并不统一,非常复杂且非结构化。
因此,传统的三维装箱算法很难在华为实现自动装箱。为此,设计了一种基于Spark的数据驱动算法,通过多级多粒度模糊匹配自动挖掘包装结构。算法框架如下:
输入材料给定后,根据包装优先级,首先对粗粒度(订单级)进行模糊匹配,检查历史上是否存在相同或相似配置的订单。如果满足包装要求,则直接输出最终的包装配置,否则将进入下一级模糊匹配。
其次,对中粒级(大盒级)进行模糊匹配,检查历史上是否存在配置相关的大盒。经过组合校正,如果满足装箱要求,则直接输出最终装箱结果,否则进入下一阶段的模糊匹配。
最后,进行细粒度(小盒级)模糊匹配,匹配过程与中粒度匹配相同。
在上述三层匹配中,利用材料的预估体积/重量和可替换信息,输出满足包装要求的最终包装构型。
下图为华为欧洲供应中心托盘(即大盒子)上的包装材料场景:
该算法已申请专利并部署在华为全球供应中心。
自动加载
装货是指将多个拣货平台的货物(纸箱、木箱、托盘、木轴等,即自动包装的输出)分送至相应的货柜车。第一个目标是最小化集装箱卡车的数量,第二个目标是最小化车辆路径的长度,以及在集装箱卡车中放置货物需要满足装载限制。
在实际情况中,主要困难有:
1)采摘平台较多,货物形状大小不一,数量较多。平均每个订单的提货平台数量为x(甚至是xx),货物种类为xx,货物数量为xxx。
2)车辆路径约束和立体装箱约束比较复杂,包含大量强制约束或推荐约束。
3)时间限制较短,一般订单需要在xx秒内完成计算。
因此,我们设计了一种基于贝叶斯估计和数据驱动的进化算法,该算法简单有效地解决了这一复杂的联合优化问题,并且几乎可以输出最优解。如下图所示,首先将整个问题分解为三个子问题:车辆路径问题、分送路径问题和立体装箱问题。
其次,设计了一个三层进化算法来解决这三个子问题。最外层解决车辆路径问题,输出候选车辆路径解集。中间层解决分拣配送路径问题,根据最外层的输出,输出一组货物分拣方案。最内层解决了立体装箱问题,根据外层两层的输出,输出一套立体装箱方案。
然后利用评价函数对上述三层算法的联合解集输出进行评价,确定哪些需要保留,哪些需要丢弃。迭代继续进行,直到收敛或满足停止条件。
最后,该算法输出到目前为止找到的最优解。
上述算法发表于KDD 2018(Link),并已申请专利。