1 引言

“货到人”拣选系统在现代化的电商物流自动货仓中的运用日益广泛，其拣选效率较人工仓更具优势，但恒久经营发明，其拣选本钱也更高。凭据相关视察发明，影响拣选本钱的主要因素就是机械人的有效事情率，即搬运货架行走时间与机械人总运行时间的比值。所以，如何通过优化订单拣选顺序来减少机械人的排队期待时间，提升其有效事情率，成了“货到人”拣选系统提升拣选效率亟待解决的问题。

目前，与电商物流仓储拣选作业有关的研究主要集中于拣货路径优化和订单分派方面。于浩洋 (2019) 接纳遗传算法求解人工拣货方法的电子商务配送中心的拣选路径优化问题，结果证实路径优化后能有效地减少实际行走路径[1]。胡金昌 (2016) 研究了基于革新K-Means算法的“货到人”拣选系统中多层穿梭车分拣系统的订单分派战略，得出聚类比不聚类订单分派战略平均能减少料箱收支库次数40%以上的结论[2]。王迪 (2018) 系统地将订单分批、批次分派和排序与拣选路径联合起来剖析，并建立混淆整数计划模型求解[3]。吴颖颖等 (2016) 针对“货到人”拣选系统的订单排序优化问题，以订单耦合因子为模型参数，提出革新的K-Means聚类算法对拣选系统订单排序进行优化，结果标明订单排序优化后拣选效率提高15.9%[4]。建立订单排序优化模型时多以订单处理时间为目标函数，张贻弓等 (2008) 以总拣选时间最短为目标函数，应用最大最小蚁群算法求解模型[5]。

通过文献综述可知，对电商物流仓储拣选作业的研究已有较为全面的理论和要领探索，但大都研究仅限于对“人到货”模式下订单拣选路径及订单分批进行优化，少数针对“货到人”模式下拣选优化也是以总路径最短或总拣选时间最短为目标函数，这两个目标更多强调的是整体最优对实际事情的指导意义有限。本文基于“货到人”拣选系统，将机械人搬运货架次数最少作为目标函数，以节约算法的思想盘算订单之间的耦合度，凭据耦合度接纳K-Means聚类算法对订单排序进行优化，减少机械人无效事情时间，具体指导实际事情，进一步提升拣选效率。

2 问题描述与模型构建

2.1 K-Means聚类算法特点

K-Means聚类是一种动态聚类的算法，它是给出一个初始的聚类结果，即把所有数据分成K类，然后通过一定的要领，完善优化此聚类结果，不绝迭代，最后得出一个最优结果[6]。它具有快速、简单，对大数据集聚类有较高的效率并且具有可伸缩性，且时间庞漂后近于线性，适合挖掘大规模数据集等优点。

电子商务物流的订单具有较强的动态波动性，而关于这种有大宗变体的多簇聚类问题，K-Means聚类算法具有较好的适应性。

2.2 问题描述

在电商物流仓储拣选历程中，由于系统给同时进行拣选作业的波次安排的货架拣选序次缺乏合理性，所以当泛起多个拣选站台某一时刻均需要某一个货架进行拣选作业时，后拣选该货架的拣选站台会爆发大宗期待时间，这是造成拣选效率低下，拣选本钱过高的重要原因。凭据文献调研发明，在对订单进行合理分批之后能有效减少货架的搬运次数。因此，需制定更为合理的货架拣选序次，来优化机械人的排队序次，最终提高系统的拣选效率，降低拣选本钱。

2.3 模型假设与参数界说

2.3.1 模型假设

实际生产中保存多种庞大因素影响优化效果，为包管模型的可行性和正确性，做出以下假设: (1) 一种商品对应一个货架的一个储位; (2) 一个订单至少包括一个品项; (3) 同一订单不允许支解; (4) 搬运历程中不保存梗塞情况; (5) 搬运历程中机械人电量富足; (6) 机械人运行速度一致; (7) 不考虑缺货和紧急插单等情况。

2.3.2 参数界说

为了更简便地描述订单排序历程，对相关参数界说及符号说明体现如下。

N:订单品项所包括的总货架数，N=1, 2, 3，…，n;

P:订单分批获得的总批次数，P=1, 2, 3，…，p, q;

t:拣选站台序数，t=1, 2, 3，…s;

K:拣选序次，K=1, 2, 3…，k;

γαks:波次α被分派至第s个拣选站台且拣选序次为k, a=1, 2, 3…, q;

γpks:每个波次被分派至一个拣选站台，且在该拣选站台有唯一的拣选序次。

2.4 模型构建

假设系统中每个拣选站台最多触发5个移动货架的拣选任务，当一个货架正在拣选时，其余的货架依次排队期待拣选，期待拣选的货架数量称为缓存容量。本文凭据波次单的耦合度来进行划分波次单，将耦合度大的波次分派在同一个拣选站台，将波次单的排队顺序转化为货架搬运次数的问题，把相似度高的波次安排在相邻的拣选序次上，以货架搬运次数来量化波次单的排队优化水平，即以节约货架搬运次数最多为目标函数建立数学模型。

当第p个波次和第q个波次的耦合因子较大，两者安排于拣选缓存区上的共需货箱较多。如果将p、q分派至一个拣选站台且拣选序次先后排列，即先拣选波次p，拣选完成后立即拣选波次q。则当两者有共需的货架时，完成波次p的拣选任务后，共需货架进入缓存区期待波次q的拣货，可制止重复收支拆零区，有效减少机械人进出拆零区次数，提高移动货架准时抵达率，减少机械人的搬运时间和搬运距离。

目标函数

约束条件

其中:目标函数 (1) 体现所有波次拣选完节约的货架搬运次数最大，约束条件 (2) 体现波次α是否被分派至第s个拣选站台以及拣选序次是否为k。如果是，取值为1，否取值为0; (3) 体现每个波次被分派至一个拣选站台，且在该拣选站台有唯一的拣选序次; (4) 体现每个拣选序次仅包括一个波次。

3 基于节约算法的革新K-Means聚类

3.1 节约算法

节约算法的提出是为了解决运输问题，凭据客户的地舆位置以及客户和客户之间的距离，通过将两个或两个以上的客户合并同时配送，来盘算节约的运输里程，从而找出节约里程最多的客户合并方法[6]。在安排波次单的拣选顺序时可以运用节约算法的思想，凭据差别订单需要搬运的配合货架数，盘算两两拣选波次的耦合度对波次单进行开端排序。

3.2 革新K-Means聚类算法

将按耦合度排序获得的波次单运用K-Means聚类算法求解波次单拣选顺序，算法办法如下:

(1) 盘算两两波次单的耦合度，并按耦合度巨细降序排序，Np1≥Np2≥Np3≥Np4≥…≥Np (P-1) 。

(2) 为每个拣选站台随机设置初始波次单作为聚类中心点。

(3) 搜索拣选站台S中拣选顺序为k的波次p，并比较其他未被分派的波次q之间的耦合度Npq的巨细，选择Npq最大的波次q，将其分派至p波次之后拣选。

(4) 不绝重复办法 (3) ，直至所有订单分派完毕。

4 仿真验证

4.1 实验历程

在MATLAB中随机生成拣选站台和波次单来进行仿真验证，每个拣选站台的缓存容量都为4。通过不绝变换波次单的数量，来盘算机械人搬运货架的次数。

图1 排序拣选温顺序拣选仿真结果  

对波次单排序优化前后的收支库次数进行比照剖析。划分以两种情况进行剖析: (1) 波次单顺序拣选; (2) 波次单排序优化。随着波次单数量不绝增加，两种情况下三组数据的移动货架搬运次数如图1所示。随着波次单数量的增加三组数据接纳波次单排序优化后，移动货架的搬运次数均有效减少。

4.2 优化效果比照

划分以拣选18、30、42个波次单为例，作为数据一、数据二、数据三，在MATLAB中进行仿真，获得最终需要的移动货架搬运次数如表1所示。

表1 移动货架搬运次数比照表  

三组数据在波次单排序优化后移动货架搬运次数优化水平与按顺序拣选相比划分优化了20.8%、23.4%、25.8%。由于数据是系统随机生成，拣选每个波次单所需的移动货架可能漫衍较广，导致差别波次单之间的耦合度较实际数据而言更小。所以实际生产中其优化水平随波次单数量的增加会更明显。

4.3 结果剖析

通过上述仿真验证结果，对分批的订单凭据革新K-Means聚类算法进行订单拣选排序后，能够有效减少机械人搬运货架次数，与不进行排序优化相比，搬运货架次数减少了20%-30%，同时减少机械人无效事情时间，抵达了提升拣选效率，降低拣选本钱的目的。

5 结论

综上，通过把波次单的排队顺序转化为货架搬运次数的问题，以货架搬运次数最少为目标函数，利用节约算法的思想对K-Means聚类算法进行革新后，应用于电商物流仓储拣选作业的订单分批波次单拣选排序优化，建立数学模型并求解，凭据仿真结果，验证了运用革新k-means聚类算法使机械人搬运货架次数获得有效减少，提升了拣选效率，降低了拣选本钱。