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