基于欧氏距离聚合算法模型的仓库配货行走路径研究

赵坚密 周旭 江骏风 颜嘉梁

上海聚水潭网络科技有限公司 上海 200040

引言

新零售时代，仓库往往会面临大量的SKU和订单，在消费者对物流时效性和服务要求越来越高的趋势下，配送任务随之变得繁重而艰巨。配货是客户提交订单后，配货员尽可能在最短的时间内完成对订单上商品的分拣、配货过程，或是仓库按照商品配送计划高效、准确地将货品从对应货架库位拣取出来，按照规定的方式对货品配货、分装、等待送货的作业，它是仓库中最费时费力的环节，配货效率的高低可以直接影响客户满意度，传统依赖人海战术、人脑记忆的作业形式已难以满足仓库高效配货的需求。在仓库所有作业流程中，订单分拣配货越来越受到企业的关注。

1 基于欧式距离的聚合算法模型

为解决配货难题，越来越多的商家仓库寻求突破，例如通过拣货车配货、聚合最早被拣货的商品货位、限定订单拣货通道等方式进行订单配货，此类方式在一定程度上缓解了配货难题，但随之也带来拣货工作量大、工作死板低效、拣货通道拥堵等问题。由于仓库所用货架大都相对固定，因此在研究如何提高仓库配货工作效率的问题上，应考虑对拣货路径进行优化——缩短完成所有订单所需的行走距离[1]。基于欧式距离聚合分析算法模型把批次路径聚合寻优的复杂问题转化为一个对二维空间点进行聚类的简单问题，将在拣货路径上相似度较高的订单聚合到同一批次，让完成批次所需行走的路径贴近批次中任意订单所需的路径，从而缩短完成所有订单所需的行走路长，提高仓库配货工作效率。

1.1 算法原理

欧氏距离是常用的一种距离计算方法，源自欧氏空间中两点间的距离公式，即两点之间直线距离，例如把A点和B点用一条直线连接，直线段的长度就是A点到B点的欧式距离，目前已广泛用于工程学中的定位分析、数据挖掘领域的聚类分类、自然语言处理中的文本距离算法等各种应用场景。

映射到仓库订单分拣配货作业中，鉴于大多数仓库所用的货架相对固定，考虑当订单路径聚合程度足够好的时候，完成某一订单所需行走的路长与该订单经过的货架数是成正比的。同时，由于订单聚合足够好，完成该订单所在批次时，途径通道都会有拣货操作，而不能进行通道或区域的跳跃或抄捷径[2]。因此，可以在以货架行走index为标尺的一维坐标系中，如下定位一个订单。

图1 订单A、B、C一维坐标系

图2 订单A、B、C二维坐标系

例如，设定A、B、C3个订单最先拣货的商品所在货架分别为最后拣货的商品所在货架分别为从一维、二维坐标系中可以看出，距离相近的订单B和订单C就非常适合聚合在一个拣货批次，拣货人员可对订单B、订单C安排同批次拣货。

1.2 算法模型

优化拣货路径即让配货员完成批次所需行走的拣货路径贴近批次中任意订单所需的路径，缩短完成所有订单所需的行走路长[3]。基于此，本文提出建立基于欧式距离的订单聚合算法模型，通过算法演算从众多待拣货位中选择n个点，一旦n个点确定之后，拣货路径便固定下来且唯一，以实现将拣货路径上相似度较高的订单聚合到同一拣货批次，使配货员完成所有订单拣货、配货行走的距离最短。

1.2.1 前提条件。基于欧式距离的订单聚合算法模型来解决仓库拣货路径优化问题，需要设置一定的前提条件[4]：①每个订单包括至少1种商品，至多N个商品（N为仓库中的货架库位总数，每个库位只能存放1种商品），商品坐标明确；②每位配货员负责一批订单货品的拣货、配货；③配货员在仓库内拉着拣货车的行走距离可计算。

1.2.2 模型建立。定义O表示订单集合，分别表示第1，2…n个订单。

该距离越小的越适合聚合，该距离越大的越不适合聚合。

1.2.3 执行过程。

（1）选择种子订单。对订单集合O首先按照的距离升序排序，距离相同的再按照升序排序，若距离依旧有相同的再按照付款时间先后排序，选择排序后且库存充足的第一个订单作为种子订单（距离越小表示这个订单要走的货架越接近，尽量把这样的订单作为种子订单去聚合其他订单）。

（2）计算相似度。计算其余所有订单与种子订单的欧式距离，由小到大排序，选择固定框数且库存充足的订单组成一个批次。

（3）完成所有订单组批。重复步骤1、2直至所有订单组批完成，实现对于同一批次的订单，拣货人员在途经通道都会有拣货操作，而不进行通道或区域的跳跃或抄捷径。

1.3 算法实现流程[5]

①通过系统（例如借助聚水潭的天机智仓软件）或手动录入的模式，绑定每个库位的行走index，该数据准备好之后，便可开始从系统获取订单进行处理；②对订单进行初步的筛选和归类。剔除库存无法满足商品需求的订单（当前无法完成配货，可等补货到位后再配），然后根据订单体积进行归类，以便被分配到符合大小的拣货车。一般订单会被分为2-4类，不同类订单被分配到不同订单池，可装载不同拣货车。只有相同订单池的底单才可聚合，不同订单池的订单不能聚合，否则会出现拣货车装载不下或装载过少的情况。③根据订单商品内容确定订单在二维坐标系中的坐标（X,Y）：每个订单的起始货架index值为X ，终止货架index值为Y。④根据坐标距离和库存，将订单聚合到批次：距离接近的订单应被聚合到同一批次，库存不足的订单应被剔除出订单池。⑤为防止出现通道拥挤的情况，可在生成批次前对聚合完毕的批次按一定规则进行排序。⑥输出订单批次到系统，有序安排配货。

2 预期效果分析

2.1 改善仓库现场状态

基于欧式距离的聚合算法模型优化订单拣货路径后，分拣人员能够在指定拣货通道或区域按照一定的操作标准（同一拣货批次订单统一拣货）有序进行拣货。同时通过体积归类、库存校验、批次排序等措施，有效解决订单体积大小不同、库位库存缺货、通道拥堵等问题，从而确保仓库分拣配货作业有条不紊地进行。

2.2 提升配货作业效率

最新的仓储调查报告显示订单分拣是提高仓库生产效率最优先考虑的运营活动，对订单分拣行走路径优化后，拣货效率平均可提升25%以上，折算成时间能节省2个人的日工作时间，分拣配货成本、配货错误率、配货员工作强度明显降低。同时，仓库配货作业效率的提升对提升仓储货物出库速度、缩短订单配送时限、优化客户服务等方面具有重要意义。

2.3 推动数字仓储建设

信息时代，该模型涉及的仓储基础数据资源的采集离不开信息技术的支撑，传统人工方式数据采集的低效率、成本高、易出错等弊端的显现，一定程度上也倒逼各类智能化系统和设备在仓储管理中的普及应用，对数字仓储建设乃至引领数字商务发展具有很大推动作用。

3 结束语

本文以一般仓库为研究对象，提出基于欧氏距离订单聚合算法的仓库拣货路径优化方法，根据订单明细商品所对应库位的拣货顺序对订单进行数据抽象和定义，并以此订单定义为基础将拣货路径长度问题转化为一个二维空间中点与点距离问题的技术特征，把批次路径聚合寻优的复杂问题转化为一个对二维空间点进行聚类的简单问题，从而达到快速算得优化结果的技术效果，以此求取仓库配货作业中拣货员最优行走路径。