在服装制造业中，碎片化生产的现象在生产实际中越来越多地出现。某服装制造企业为了扩充产品种类、款式以适应丰富多变的市场需求，采用多种类、小批量的生产方式。多种类小规模生产在适应市场的同时也带来各种问题。企业生产实际中多采用立体仓库以提高库存占地利用率，但是多种类小规模的生产方式会产生更多种类的库存。与此同时，新制造的产品与旧库存混合堆放，导致商品订单到来时立体仓库的分拣过程过于繁琐，耗费人力物力，增加企业生产成本。

对于立体仓库的应用，国内外相关研究主要集中于货位的优化和调度任务以及路径的分配[1]。Lee等[2]采用启发式算法求解方形立体仓库的出库入库最优拣选路径问题。Kim等[3,4]采用聚类算法结合排序算法应用于立体仓库的作业拣选问题以优化最短拣选路径。常发亮等[5,6]应用离散大系统的分级递阶控制原理解决仓库作业任务分配以及调度问题。卫三军等[7]采用结合遗传算法与模拟退火算法的遗传退火算法求解堆垛机最优作业路径问题。目前对于立体仓库的建模多集中于货位优化和调度路径优化问题，对于面向小批量多种类制造方式的立体仓库分拣的相关问题还少有学者研究。

针对企业实际生产中遇到的小批量多种类制造方式分拣过程繁琐的问题，本文提出有针对性的立体仓库分拣问题建模，并将改进的遗传算法应用于企业数据中，证明遗传算法对于此类立体仓库库存分拣问题有较好的适应性，最后通过某服装制造企业的订单数据实验验证了算法的有效性。

在实际生产场景中，立体仓库可能存在一个货箱中存放多种货物，或同一种货物被存放在不同的货箱中的情况，如图1所示。

图1 货箱装货情况  下载原图

在收到分拣订单后，算法决定符合订单要求的取货方式，需要满足拣取货箱数M最小。

订单分拣问题首先要保证订单上的所有货物需求得到满足，故有约束条件，对于订单上的任意第q种货物，均满足：

∑Ni=1i=1Νxqi≥Lq(q=1,2,3,…,Q) (1)

其中，N表示分拣结果中的货箱数；xqi表示货物q在第i个箱子中的存货数；Lq为订单对第q种货物的需求数；Q为订单货物种类总数。

本问题的优化目标为使得分拣过程最简单，也即达到订单目标时取出的货箱数N最小，故目标函数定义为：

minN=card(A1∪A2∪…∪An) (2)

其中，card表示集合中元素的个数；n表示订单中不同货品的种类数；An表示分拣结果中第n种货物所在的货箱集合。

相对于传统立体仓库优化问题，本文结合企业生产实际，针对立体仓库分拣过程的优化问题建立数学模型。与传统模型相比，本文提出的立体仓库分拣模型结构更加简单，对企业实际问题的针对性更强。

本文提出的数学模型是一个典型的0-1整数规划模型。针对0-1规划问题，进化算法在并行性、随机性、非线性问题的搜索能力方面体现出优于其他算法的特点[8]。其中遗传算法在0-1规划问题方面有一种先天的优越性，因为0-1规划中的问题变量非常有利于遗传算法编码，故在0-1整数规划问题的应用中，遗传算法通常有较好的结果[9]。故本文采用遗传算法求解针对小批量多种类制造模式下立体仓库的分拣优化问题。

经典遗传算法通常采用二进制编码，经过选择、交叉、变异后得到子代基因。

首先进行选择计算，经典遗传算法通常采用轮盘赌方法，基于适应度比例确定选择的策略，每个个体i被选中的概率：

pi=fi∑Nj=1fi (3)pi=fi∑j=1Νfi(3)

其中：

fi=kFi (4)fi=kFi(4)

式中，k为比例系数；Fi为个体适应度值，由于本文采用的优化策略是减小适应度，故带比例的适应度fi取比例系数k与个体适应度Fi的比值； N为种群中个体的数目。

经典遗传算法的第m个染色体am和第n个染色体an在第k位交叉的过程如下：

{amk_new=amk(1−b)+ankbank_new=ank(1−b)+amkb (5){amk_new=amk(1-b)+ankbank_new=ank(1-b)+amkb(5)

其中，b是[0,1]之间的随机数。

经典遗传算法中选取的第i个体的第j位基因进行变异的操作方法如下：

aij={aij+(aij−amax)*f(g),r≥0.5aij+(amin−aij)*f(g),r<0.5 (6)aij={aij+(aij-amax)*f(g),r≥0.5aij+(amin-aij)*f(g),r<0.5(6)

其中：

f(g)=d1−g/Gmax (7)f(g)=d1-g/Gmax(7)

式中，d为一个随机比例系数；r为[0,1]之间的随机数；g为当前迭代次数；Gmax是最大进化次数；amax和amin分别为基因aij的上下界。

经典遗传算法在基因选择时采用的轮盘赌方法是基于概率确定子代的，此方法的缺点是可能会存在统计误差导致无法保证结果稳定收敛至最优解，故引入精英主义原则。精英主义原则也被称为保存最优原则，Eiben[10]用马尔可夫链理论证明采用精英主义原则的遗传算法可以弥补传统选择算子可能导致的统计误差，保证得到全局最优解。

精英主义原则在产生子代种群时，除了通过选择算子生成的子代种群外，还要求另外按精英比率保留适应度值最低的几个最优个体，选择过程如图2所示。

图2 精英主义原则  下载原图

图2中假设亲代种群P1到P10按适应度值从低到高的顺序排列。根据精英主义原则，在产生子代种群C1到C10时，先按一定比例将亲代种群最优个体直接复制到子代中，如图2中C1、C2。再采用轮盘赌方法产生其余个体，如图2中C3～C10。

分拣订单中每个货箱分为“取到”和“未取到”两种状态，故采用二进制编码。如图3所示，在分拣结果中，每个货箱对应基因的一位，编码“1”表示“本次分拣取到此货箱”,编码“0”表示“本次分拣未取到此货箱”。

图3 基因编码示意图  下载原图

在分拣问题中首先要保证分拣任务的完成情况。本文对于个体适应度函数分情况讨论，分拣结果未满足订单要求时，个体适应度函数直接取个体基因位数即货箱的总数；分拣结果满足订单要求时，个体适应度函数的值取个体基因编码为“1”的位的个数，即分拣结果中取出的货箱数。

步骤1:初始化种群；

步骤2:计算适应度值；

步骤3:轮盘赌算子配合精英主义原则生成子代；

步骤4:交叉操作；

步骤5:变异操作；

步骤6:判断是否满足迭代终止条件，若满足执行下一步，否则返回步骤2;

步骤7:输出迭代结果。

整体流程图如图4所示。

本次实验采用多个不同规模的订单数据，针对每个订单，由改进的遗传算法给出最优分拣方案。实验数据如下：采用某企业的生产库存数据，共有379个货箱，库存商品有523种，库存商品个数总计5617个，设置4个不同规模的订单，每组数据中包含货箱库存量数据和一个需求订单数据。库存量数据包括货箱编号、每个货箱中的商品编号以及每种商品的库存量。需求订单数据包括所需商品的编号以及数量。4组数据的规模设置如表1所示。

图4 遗传算法流程图  下载原图

表1 订单优化数据设置 导出到EXCEL

为了得到比较理想的结果，遗传算法的具体参数设置如下：种群数为100、交叉率为0.7、变异率为0.1、精英主义原则保留比率为0.05、最大迭代次数为2000次。对于本算法，采用Java语言编程进行实验，每次实验得到分拣结果中包括需要取出的货箱和货箱中取出的每种商品数量。由于遗传算法存在随机性，每组数据进行20次实验，表2记录了每次分拣结果中的货箱数。

表2 实验结果货箱数记录 导出到EXCEL

经统计，四组订单数据中商品分别分布于217、260、295、334个货箱中，为了更直观地体现算法的分拣能力，本文提出分拣比率的评价方法，分拣比率R的计算方式如下：

R=card(A1∪A2∪A3∪⋯∪An)card(B1∪B2∪B3∪⋯∪Bn) (8)R=card(A1∪A2∪A3∪⋯∪An)card(B1∪B2∪B3∪⋯∪Bn)(8)

其中，card表示集合中元素的个数；An表示分拣结果中第n种货物所在的货箱集合；Bn表示第n种货物所分布的货箱集合。根据表2实验结果记录，得到分拣比率如图5所示。

图5 分拣比率  下载原图

由分拣比率的计算方法易知，分拣结果中的货箱数占总货箱数的比例越低，即分拣比率的数值越低，则可以认为算法对于此订单的分拣效果越好。从图5可以看出，对于本次实验数据的第一组订单，分拣结果的分拣比率在15%左右，第二组在19%左右，第三组在21%左右，第四组在25%左右。说明针对本次实验的数据集在各种规模的订单下均有较好的分拣效果，订单商品种类较少时效果更好。

本文对立体仓库分拣问题进行分析建模，并采用改进的遗传算法应用于该问题，同时提出“分拣比率”的评价方式对分拣结果进行分析。由于遗传算法的优化过程存在随机性，实验过程中记录了多次结果，实验结果显示，算法可以达到较理想的分拣结果且多次实验分拣结果较为稳定。算法对不同规模数据集的分拣结果有一定区别，总体而言对较小规模的订单分拣结果更优。针对遗传算法存在的统计误差，算法采用引入精英主义原则保留最优个体的方法解决。本文利用遗传算法给企业多种类小批量生产中遇到的立体仓库出库分拣问题提出一种可能的解决方案，为类似的仓库分拣问题提供了理论依据。