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聚类算法使机器人搬运货架次数得到有效减少，提升了拣选效率，降低了拣选成本。