无人仓系统中订单分批策略研究

2019-08-26胡鸿

数字技术与应用 2019年5期

关键词：聚类算法订单

胡鸿

摘要：针对目前订单多品类小批量的特点，构建了基于聚类算法的解求解订单分批问题的新思路。本文介绍了无人仓系统的构成要素和订单拣选模式，分析了改进的密度峰值聚类算法，研究了基于改进的密度峰值聚类算法的订单分批问题的求解思路，并进行总结。

关键词：无人仓系统;订单;聚类算法

中图分类号：TP18 文献标识码：A 文章编号：1007-9416（2019）05-0108-02

0 引言

随着物流行业的快速发展，智能仓储、智能分批等名词渐渐进入人们的视野，物流订单能在短短一天甚至是半小时内就能完成，这样的惊人效率主要取决于智能化的设备和相关算法研究。在对订单分批的求解中有以下研究：李诗珍等[1]采用货品在仓库中位置特征向量为衡量标准进行订单分批，并用启发式算法的思想求解最短拣选距离。邵泽熠等[2]利用相似度系数最高为衡量标准进行订单的划分，并用改进的遗传算法K-means算法求解订单分批模型问题。李晓杰[3]针对移动货架仓库系统中储位分配和点分批综合进行考虑，提高拣选效率。王占磊[4]在双区型仓库环境背景中，实行多AGV并行拣选策略，详细设计了遗传算法求解订单分批的思路，有效减少了拣选距离。胡小建[5]采用基于Canopy和k-means算法对订单分批进行求解，减少主观因素带来的计算偏差。

1 无人仓系统中订单拣选模式概述

1.1 无人仓系统构成要素简介

无人仓规划系统分为仓储区、分拣区、生产加工区三部分，各个区主要由操作站台、AGV小车、货架、通道、货品等要素组成。由于本文主要研究订单分批拣选问题，所以只以拣选站台为重点介绍对象，下面对各个部分进行简单概括：

（1）操作站台。操作站台包括分拣站台、拣选站台、打包站台、充电站台等，各个站台对应着不同的工作范围。无人仓系统中拣选站主要由拣选操作人员、传送带、装载订单货物的载货架、上位机等组成，为了提高拣选效率，每个仓库中都会有多个拣选台、多台AGV小车并行工作，每个拣选台上有一个工作人员进行拣选工作。（2）货架。无人仓系统中的货架用于存储货品，每个货架基本类似于竖着的长方体，分为多层，一般每層由多个货格组成，每个货架可以放多种货品，被称为共享货架[6]。（3）AGV小车。在无人仓系统中，AGV小车一般由两部分组成：行驶模块和升举模块，行驶部分只要使用电力为动力来源，升举部分大约载重量为1000KG，可以用于旋转货架，AGV小车通过具有实时避障功能，通过陀螺仪调整角度，实时矫正AGV小车的行驶方向。

1.2 基于无人仓系统的订单拣选模式

在无人仓系统中订单拣选的业务流程为：仓库中AGV小车接收到来自客户的订单，按照订单拣货信息单的相关信息，AGV小车将货架运送至拣选台，工作人员拣选相关的货品后，AGV小车将货架运送回货架原位置。可以看出无人仓系统是基于“货到人”的拣选模式进行操作的系统，相对于传统的“人到货”的拣选模式，减少了人工成本和人工拣选时间等因素，大大提高了拣选效率。无人仓系统的订单拣选模式流程图如图1所示。

2 订单分批策略

2.1 传统的分批策略

（1）总合计量分批。当接收到的订单中的品相数目达到阈值时，则将这些订单归为一批进行拣选。比如阈值为100时，则表示无论多短或多长的时间内，订单中的品相数目达到100时则将这些订单归为一批进行拣选任务。（2）时窗分批。时窗分批（Batching with Time Window）也是设置阈值，该阈值为一个时间段，该方法适合于订单量比较集中在一个时间段或比较紧急的订单。（3）固定订单量分批。固定订单量采用先到先处理的基本原则，当接收到订单总量达到设定的阈值时，订单归为一批次进行拣货。该方法适用于客户订单比较持续，才能保证拣选作业效率。（4）智能型分批。智能型分批是近几年比较流行的分批方法，效率一般比传统的分批方法更高。该方法是将接收到的客户订单经过计算机预处理，将相似度大的订单归为一批进行拣选。采用这种分批方法能大大降低拣选路径和拣选时间，提高拣选效率和客户满意度。

2.2 基于改进密度峰值聚类算法的订单分批问题研究

2.2.1 改进密度峰值聚类算法的算法设计

CFSFDP（clustering by fast search and find of density peaks）[7]是在聚类分析算法中一种比较新的以密度为衡量标准的算法，该算法的基本原理就是数据集合的聚类中心点一般具有较大局部密度值和彼此间较大距离值，然后将剩余部分的数据集按照高密度距离最小归类，实现数据集合的最终聚类划分。本文引入万有引力定律改进该算法，由该定律启发人们，距离可以被引力F所取代，从而有一个更好的度量标准来检测粒子聚类中心和异常点，所以依据次思想改进密度峰值聚类算法，并将改进后的新算法用到订单分批中求解订单分批问题。改进后算法的参数公式如下：

参数解释如：式（1）中为数据点的局部密度值，S为数据集合，S={1，2，.......n}，为指标函数，是数据点i与j之间的欧氏距离，是人为设定的截断距离，它被定义为：，代表各数据点的平均局部密度为总数据量的，其中式（1）适用于对海量的数据集的计算，式（2）适用于对较小规模的数据集。式（3）中表示高密度最小距离，当该数据点为最高密度时，其值为离该点最远点的长度，即。式（4）为原算法的改进地方，利用该式（4）替代原算法中的式（3），即由和画决策图，然后选取决策中心。

2.2.2 改进密度峰值聚类算法求解订单分批问题的研究

步骤4：计算订单的局部密度，以订单的中心点位圆心，截断距离为半径画圆，落在园内的中心点坐标的个数就是订单的局部密度，圆内的中心点数量越多表示密度越大，该订单就越可能成为聚类中心。

步骤5：计算订单到更高密度点的最小距离。

步骤6：计算各个订单之间的密度引力。

步骤7：以局部密度为横坐标，密度引力的倒数为纵坐标，画出决策图，通过观察决策图选取两个值都同时较大的点为聚类中心;或者计算局部密度和密度引力倒数的乘积，该值越大，说明该中心点为聚类中心点概率越大。

步骤8：将其余订单按照聚类后生成的的密度引力大小进行归类。

步骤9：将分好批次的订单放入无人仓系统中进行实验验证。

以上是对该算法应用于订单分批问题的求解思路，可能不是很成熟，后续还会继续深入研究。

3 结语

本文主要介绍基于改进聚类算法的订单分批问题研究，包括密度峰值聚类算法的改进设计和应用于订单分批的求解思路。该算法相对于其他聚类算法来说比较新，目前对于该算法的研究大多集中在改进算法上，对算法实际应用研究比较少，所以本文尝试将该算法进行改进并用于实际问题的研究中，所以比较有研究潜力和研究价值。

参考文献

[1] 李诗珍，杜文宏.基于聚类分析的订单分批拣货模型及启发式算法[J].统计与决策，2008（12）：53-56.