基于改进遗传K-均值算法的多品种小批量订单分批方法

，

(浙江理工大学机械与自动控制学院，杭州 310018)

0 引 言

拣选作业是指仓库根据客户订单要求或配送计划，将商品从储位拣取出来并进行分类集中的作业过程[1]。简单拣选作业效率低，特别是对于多品种小批量订单，采用单个订单拣选耗时耗力，所有订单统一拣选又不切实际，所以分批拣选就显得尤为重要。分批拣选可以提升拣选效率[2]，订单分批策略有时窗分批和订单相似度分批两种[3]。时窗分批适用于短时间内订单密集达到或有明显的时间延迟惩罚机制的情况；订单相似度分批适用范围广，常用方法有种子算法、优先规则算法、智能算法[4]等。针对订单拣选的实际情况，选择合理的分批方法对提升拣选效率具有重要意义。

王旭坪等[5]针对在线订单达到时间不确定的特性，把基于完成期限的动态时窗作为分批条件来进行订单的分批优化。文坚等[6]将制造延迟思想引入配送中心的拣选作业中，提出了基于时间延迟的动态时窗分批策略。李晓杰[7]将移动货架仓库系统作为背景，验证货位分配和订单组合策略对分批拣选产生的影响。马廷伟等[8]对二进制粒子群算法进行了改进，并用改进算法求解订单分批问题。李诗珍等[9]采用聚类算法，以储位特征向量和坐标特征向量为条件进行订单分批，并用启发式算法计算拣选距离长短。胡小建等[10]考虑到主观选择聚类中心容易导致计算结果偏差，采用了基于Canopy算法的改进K-均值算法进行分批。

在上述研究中，有些从时间窗角度进行分批研究，但这些方法多应用于电子商务环境，对一般仓库分批拣选的适用性较低；还有些从订单相似度入手进行研究，只考虑了算法的部分优化，难以避免初始聚类个数和对象选择的盲目性。本文以某企业售服仓的备件订单分批拣选问题为研究对象，构建了以订单相似度最高为目标的分批优化模型。该模型先用密度和最小距离作为参数确定初始聚类中心，再用改进遗传K-均值算法获取k值，并进行聚类中心迭代以求出最优分批结果。本文通过计算拣选距离来衡量订单分批的有效性，为多品种小批量订单的分批方法提供了一种思路。

1 问题描述及模型建立

1.1 问题描述

本文研究某售后服务备件仓某一时间段内到达的多个订单的分批问题。该问题中订单的需求货物种类多但数量少，需根据特定规则将订单分成几个批次进行拣选作业，目的是在满足拣选约束的情况下，降低拣选作业的时间成本，即拣选距离，订单分批拣选流程如图1所示。订单分批拣选描述为：在某一个时间段内共有s个订单O1,O2,…，OS需要进行拣选，每一个订单中有若干种货物，每一种货物数量不定。第t张订单Ot中共有pt种货物，有qt个需要被拣选的货物，这qt个货物的总重量为wt，总体积为vt。假定仓库中每一种货物有且只有唯一一个货位，以仓库入口集货点为坐标原点，横向为X轴，纵向为Y轴建立坐标系，把每个库位的中心位置视为该库位的坐标,那么订单Ot中货物a的坐标为(xa,ya)。之后按照特定的分批规则，将s个订单进行分批处理，目标是使订单相似程度最高，总的拣选距离最短。

图1 订单分批拣选流程

考虑到实际问题的复杂性和不确定性，在对订单分批问题建立模型之前，需要对该问题进行必要的简化并设定条件，本文中对于该问题的假设如下：

a) 拣货小车的最大载重为W，最大容积为V；

b) 每张订单必须包含不少于一种的货物，且一个订单中货物的总重量wt≤W，总体积vt≤V；

c) 不考虑货物放置时产生的空隙部分而造成的容积浪费，即假设货物之间紧密放置；

d) 同一张订单中的货物不可分割，必须一次拣选完毕；

e) 不考虑缺货和插单等意外情况；

f) 拣选员在拣选前明确拣选流程和路线，不考虑因失误导致的往返情况；

g) 由于是多品种小批量的订单分批拣选，采用穿越型路径策略较为合适。

1.2 模型建立

分批拣选的目标是把客户订单分成几批，每一批订单之间的相似度较高，在考虑拣选限制的前提下使总的拣选距离最短。建立订单分批拣选优化的数学模型如下：

目标函数：

(1)

(2)

约束函数:

(3)

(4)

(5)

(6)

(7)

其中：Z表示分批后所有批次的总相似程度，是由被选中的批次中的客户订单相似程度叠加得到；K表示分批后的批次，若最终所有订单分成5批则K值取5；k为分批后的某一个批次；bk为分批后某个批次的相似程度，δk为决策变量，当第k批被选中时，δk取值为1，没被选中时取值为0；vt表示订单编号为t的订单中货物总体积，wt表示订单编号为t的订单中货物总重量，θtk为决策变量，当订单t被选中到第k批中时，θtk取值为1，反之则取值为0；Batchk表示分批之后的第k批的订单集合，即第k批中包含的所有订单信息，O表示为未分批订单的订单集合。

目标函数(1)表示订单分批后的总目标是实现订单相似度之和的最大值；式(2)表示控制变量的取值范围为{0,1}，当第k批被选中时δk为1，否则为0；式(3)表示分批后的每个批次的订单总体积不得超过拣选车的容积V的限制；式(4)表示控制变量的取值范围为{0,1},当订单t被归入到批次k时，θtk为1，否则为0；式(5)表示分批后的每个批次的订单总中联不得超过拣选车的载重W的限制；式(6)表示所有批次中的订单的并集等于未分批订单集合O本身，即所有订单必须要都被拣选到；式(7)表示所有批次中的订单的交集必须是空集，即一个订单只能属于一个批次，不能再被拆分。

2 算法设计

K-均值算法是划分聚类算法之一，它的实现简单高效，虽然因为运行效率而降低了聚类精度，和一些智能算法相比不够精确，但在实际操作中并不会有太大的误差，所以被广泛应用在实际生产中。K-均值算法一般以距离作为数据对象间相似性度量的标准，将相似程度高的对象聚合在一起代表一个聚类[11]，较适用于以坐标距离作为划分的数据集，例如仓库中的货位坐标信息。然而，K-均值算法也有其局限性，首先，该算法中的K值是人工给定或是系统随机的，因为事先不知道需要将数据集分成多少类；其次，需要人工确定初始聚类中心，再对初始划分进行优化，初始聚类中心的选择会对聚类结果产生明显影响[12]。基于上述缺点，本文提出一种改进遗传K-均值算法来求解上述模型。

2.1 综合距离密度最优的初始聚类中心

步骤1：计算订单Ot的中心点坐标，一个订单中有pt种货物，每种货物数量为na，那么该订单的中心点坐标为：

(8)

(9)

步骤2：计算两个订单之间的欧式距离，根据步骤1计算出的订单中心点坐标，计算两两中心点之间的欧氏距离d(t,i)：

(10)

步骤3：计算截断半径dj，就是计算出所有订单中心点之间的平均距离：

(11)

步骤4：计算订单Ot的密度ρt，将所有订单的中心点作为画到坐标轴上为圆心，以截断距离为半径作圆，包含在该圆内的中心点坐标的个数就是该订单的密度，圆内的中心点数量越多，密度越大，该订单就越可能成为初始聚类中心：

(12)

(13)

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

(14)

(15)

步骤6：计算密度和最小距离的乘积mt，该值越大，就说明该中心点被选为初始聚类中心的可能性越大：

mt=ρt×lt

(16)

2.2 基于K值优化的改进遗传K-均值聚类算法

相比于传统聚类算法，改进遗传算法的K不需要事先确定，而是利用遗传算法全局搜索替代穷举。步骤1：对十进制的聚类中心数K进行编码。由杨善林等[13]对K值问题的研究可以得到K的范围为大于0且小于样本个数的算数平方根，例如有100个样本订单，则0

步骤2：初始化种群。确定种群的规模s,一般s的取值范围为[30,150]；选择交叉概率se=0.5～1.0和变异概率sm=0.001～0.050。

步骤3：初始聚类，把种群中每个染色体解码成十进制，即对应的类别数K[14]。对于每个订单，根据之前初始聚类中心优化得到的mt的大小按照先后顺序选取K个数据作为类中心。将种群中的其它订单按照新的分配方式进行分配：

(17)

步骤4：适应度函数的设计，需要同时考虑组内间距最小和组间间距最大的综合最优。组内间距，即同一批中的订单中心点与聚类中心的距离和：

(18)

组间间距，即不同批次聚类中心之间的距离：

(19)

适应度函数：

(20)

步骤5：遗传操作。

a) 选择因子：对于染色体的选择，采用精英策略和轮盘赌相结合的选择方法[15]。精英策略是把群体在进化过程中迄今出现的最好个体。轮盘赌是依据个体的适应度值计算每个个体在子代中出现的概率，并按照此概率随机选择个体构成子代种群。

b) 交叉因子：交叉算子是对种群中选出的两个个体进行交叉操作。

c) 变异因子：变异是指对群体中个体串某些基因座上的基因值产生变动[16]。本例中对编码后的K值进行0与1互换的变异，使K值产生变动。

d) 生存因子：需要判断迭代之后的分批组合是否符合拣选车的载重和容积的限制，选择拣选车的载重和容积作为生存因子[17]。

2.3 拣选路径策略选择

拣选路径选择策略主要包括穿越型路径策略、中点型路径策略、往返型路径策略、组合型路径策略等[18]。不同策略的适用环境有所差别，穿越式路径策略适用于货物密度高但数量少的情况，拣货人从通道一端进入，同时拣选通道两侧货架上的物品，最后从通道另一端离开，在返回出入口之前，拣货人会走遍所有包含拣取位置的巷道。

穿越型路径策略拣选示意图如图2所示，拣选员从仓库左下角集货点出发，遇到有需求货物的货架就从一端进入，拣选货物并从另一端离开，当一整排货架都没有需求货物的时候就忽略该通道，依次进行判断和拣选，最后回到集货点，完成本次拣选，整个拣选路线不往返。

图2 穿越型路径策略拣选示意图

3 仿真实验

3.1 订单分批拣选实例描述

本文以某机械设备生产公司售后服务备件仓为例，对该仓库一段时间内的订单需求数据进行仿真实验。该仓库为一个双分区仓库，货架纵向排列，前分区共有12排单层货架，靠墙两侧为单排货架，中间为双排货架和巷道的间隔排列，每排货架有10个货位，货位简化为长宽都为1.5 m的矩形，前后分区布局相同，两个分区中间贯穿一条横向巷道，巷道宽同样为1.5 m。拣选小车的容积和载重限制分别量化为600 dm3和120 kg。拣选员在某个时间段内一共收到40个客户订单，总体积为1298 dm3，总重量为544 kg，每个订单的货物需求不完全相同且单个订单的需求货物总体积和总重量均不超过拣选小车的限制。

如表1所示，每个订单货物坐标的的中点为中心点坐标，X和Y值为中心点的横纵向位置，订单体积和重量均为该订单中所有货物的体积和重量的和。

表1 订单信息表

3.2 确定初始聚类中心

根据表1中每个订单的中心坐标，绘制相应的散点图，计算两两订单的中心点之间的欧氏距离。表2为其中10个订单中心点之间的距离表，例如订单1与订单2中心点距离为3.1 m，与订单3中心点距离为8.1 m。

表2 部分订单中心点距离 m

求得两两订单中心点之间距离后计算截断距离dj并依次选取每个中心点，以截断距离为圆心作圆，统计包含在圆内的点的个数，即为该中心点对应订单的密度。中心点密度示意图如图3所示，以中心点坐标为(6,2)的订单为例，其对应的密度为5，即以该订单的中心点为圆心，以截断距离为半径的圆包含了其它4个订单的中心点。之后计算该点到更高密度中心点的最小距离，与密度的乘积就是该点所对应的订单被选为初始聚类中心的概率。

图3 中心点密度示意图

3.3 改进遗传K-均值算法

确定改进遗传K-均值算的参数为：交叉算子为随机选择交叉点的单点交叉，交叉概率se=0.7,变异算子为单点变异，变异概率sm=0.01，获取最佳聚类数之后再配合优选的初始聚类中心进行聚类分析。

根据图4所示，结合拣选小车的容积和载重约束。当聚类数小于4时，平均每批订单的体积及重量均超过限制。当聚类数为5时适应度函数的值最大，所以选择将样本订单分成5批。确定初始聚类中心及分批数之后，进行订单分批的操作。

图4 分批数对应的适应度函数值

运用改进的聚类算法，经过7次迭代获得局部最优解如图5所示，图中共有6种不同形状的点，其中无填充色的圆表示为迭代之后的聚类中心，其余5种形状，相同形状的点表示为同一类点，即该中心点所对应的订单是归在同一批中进行拣选的。

图5 本文算法第7次迭代结果

为验证本文方法的有效性，选择K-均值算法对该订单数据进行简单分批，指定能产生较优分批结果的初始聚类中心并确定分批数为5，得到分批结果后用穿越型路径策略分别计算两种算法的总拣选距离长进行比较。表3表示两种算法对于订单分批拣选的验证结果。

表3 两种算法分批结果对比

本实验样本大小为40，结果表明，K-均值算法迭代4次取到局部最优，总的拣选路程为321.0 m，而本文算法优选了初始聚类中心并求得最优的分批数K为5，经过7次迭代取得局部最优解，分批后总的拣选路程为277.5 m，缩短了14%的拣选路程，提升效果较为显著。同时算法复杂度也有所增加，因为聚类算法的复杂度上界与样本大小、分批数和迭代次数线性相关，本文算法与传统聚类算法相比，迭代次数由4次增至7次，导致算法复杂度增加1.75倍。

4 结 论

本文针对售服仓多品种小批量订单的分批问题，以订单相似性为切入点，构建了订单分批优化模型。针对传统K-均值算法中聚类中心人为确定而影响聚类结果的缺陷，采用了初始聚类中心的优化方法，按照密度和最小距离综合最优的原则，优选了初始聚类订单；对于K值确定问题，采用了改进遗传算法，通过遗传迭代来确定K值后再进行聚类，最后用穿越型路径方法计算拣选距离长短来衡量分批结果的优劣。仿真实验结果表明，本文采用的方法迭代次数较多，不易陷入局部最优，分批效果也更好，能够显著缩短拣选距离，减轻拣选作业的工作强度，验证了该算法的有效性。

本文方法消除了函数对于初始聚类的依赖，但无法避免聚类过程中对于聚类中心生成次序的依赖性。算法采用迭代方法，当面对大规模数据量时，算法需要不断进行分类并重新调整新的聚类中心，会造成算法运行时间成倍增加，算法复杂程度增加，上述问题有待于进一步的研究。