仓储是物流系统的一个重要组成部分。据估算,储存和物料搬运成本占物流总成本的26%,因此加强仓储管理,提高仓储运作效率,降低仓储运作成本是降低物流成本的重要途径。汽车配件仓储是一种特殊的仓储类别,配件库汽配货物具有种类繁多、出入库频率差异较大、需求时间与需求数量具有随机性等特点。汽车配件仓储作为汽车行业售后物流的一个重要环节,在整个供应链中也扮演了非常重要的角色[1] 。

货位优化是仓库布局研究的一个主要分支,随着现代计算机技术以及控制技术的不断发展,生产企业和物流仓储企业仓库管理呈现出控制最优化、运行智能化的发展趋势,对仓库的货位优化已成为物流技术发展的一个重要标志[2] 。国外对仓储货位优化研究相对较早。Hesket[3] 研究了货物存储所需要的存储空间以及货物的订单数量对仓储效率的影响。Goetschalckx等[4] 证明了N类货物分配下最低COI值的货物存储在最适宜的货位,订单拣选和存储时间得到了优化。Graves等[5] 分析了货物组合成更少的类别时,高周转率的货物可能会占据不理想的货位。Rosenwein[6] 提出了货位布局的分级存储策略。Larson等[7] 在Rosenwein研究基础上,使用启发式算法对分级存储策略进行探讨。Sooksaksun等[8] 基于分类存储策略对巷道的数量、长度、产品的分类存储建立数学模型,模型以最小化平均行走距离为目标。Zhan等[9] 研究了带邻接约束的多层次仓库布局问题,建立了描述同类产品的临近放置的整数规划模型,并采用禁忌搜索算法求解。

在国内,对货位优化研究方面,文献[10] 和[11]为本文在算法方面的探究提供了算法的支持,认为遗传算法在解决货位优化NP-难问题方面具有有效性。谭泽波[12] 以货物的位置、货物的质量和存取次数为变量建立货位优化模型,文章对货物的相关性等因素缺乏考虑。董溪哲等[13] 提出了以物品周转率为标准的货位优化模型。王建[14] 以货物出入库效率、货架稳定性以及货品存放的相关性为目标建立了多目标的优化模型,采用权重系数法将多目标问题转化为单目标问题,但没有对不同量纲的目标函数做标准化处理。吴璟等[15] 重点讨论了影响拣货效率的因素,根据这些因素引入拣货成本系数,在路径、周转率等关键指标基础上建立线性规划的货位模型。郑凌莺[16] 在解决货物相关性即产品族的问题方面,综合考虑货物的周转率、重量和类聚现象的三个主次目标,建立货位优化的多目标模型。马永杰等[17] 基于随机存储策略对自动化仓库的库区和货位分配以及堆垛机行驶时间进行优化,在约束条件中考虑到堆垛机容量和速度。马婷[18] 提出基于最小时间算法的货位优化方法,建立自动化立体仓库三维立体模型,实现了对烟草仓库货位的优化。

应当看到的是,上述研究成果大多仅局限于理论探索层面,由于每个仓储企业的业务范围、服务对象的差异,特别是在仓库的规模、物料的规格、包装、形状、市场销售等诸多方面存在的差异性,需要我们在实际生产过程中加强具体的实用性研究。因此本文主要考虑汽配件仓储特点,基于汽配件入库频率等因素建立仓储货位优化模型,以实现汽配件仓储货位优化,满足生产对汽配件的配送要求。

汽车配件库的仓储管理货物品类相对较多,对于高架立体仓储区在存储策略选择方面适宜采用分类管理策略,把不同的货物进行归类处理,以方便管理(见图1)。

图1 货物归类示意图Fig.1 Goods classification diagram  下载原图

在实际优化中本着为取而存的思想,首先将货物分为若干大类,每大类货物又包含若干小类货物,对各大类货物的平均在库量(按每大类货物月均在库的托盘数量计算)进行统计。下面给出大类的平均在库量的统计公式,见式(1)。

式中:P为大类的货物平均在库量;p为小类货物的平均在库量。

接着在统计数据的基础上对未来一个周期的各大类货物平均在库量进行预测,根据预测结果确定该类货物需要分配的货架排数。对大类货物出入库频率(按每大类货物每月的平均出入库量计算)进行预测。

然后按照大类的平均出入库频率高低顺序依次分配靠近出库口的某排货架(如图2所示)。设有n大类的货物,它们的平均出入库频率的预测值为Fi(i=1,2..n),若Fx的值最大,且x类货物需要两排货架,则分配第1排、第2排货架给x类货物,然后按照这个方法再分配相应排数的货架给其他类货物,直到所有类货物都分配完毕。

考虑到本文货位分配的依据是平均出入库频率,因此会存在某个时间段内某排货架的货物在库量超出该排货架的容量,所以分配完货架还应考虑建立适量的机动货架来存放超出部分的货物。

图2 立体仓货架库示意图Fig.2 Stereoscopic warehouse shelves library  下载原图

最后对每排货架进行细致到货格的货位优化,每排货架的结构示意图如图3所示。

图3 货架单排结构示意图Fig.3 Shelves with single structure diagram  下载原图

为了更加清楚描述本文的优化思路,本文以流程图方式表示如图4。

为了将研究问题简化,本文单排货架货位优化模型建立在以下假设基础上:

1)仓库每个巷道均有一台堆垛机;

2)堆垛机的行走的水平速度和垂直速度均为匀速;

3)每个货格的规格是一样的,即货格的长度和高度是固定的;

4)每一类货物的出库频率都能得到满意的预测结果。

图4 货位优化思路流程图Fig.4 Flow chart of slotting optimization idea  下载原图

x={1,2,…a}为某排货架的第x列;

y={1,2,…b}为表示某排货架的第y层;

wxy为放在第x列、第y层的货物的重量;

rxy为放在第x列、第y层的货物的出库频率预测值;

txy为第x列、第y层货格的货物到达出库口所需时间;

l为货格的长度;

h为货格的高度;

Vi为堆垛机行走的平均水平速度;

Vj为堆垛机行走的平均垂直速度;

单排货架上货物的优化最主要目的是提升订单的响应速度,这里衡量响应速度的指数当中最直接的就是时间,使出入库频繁高的货物放置在靠近巷道口处是节约出库时间的良好策略,依据上面的思想,建立第一目标函数如式(2)。

其中rxy可以由预测方法得到。

单排货架上货物的优化的同时应注意保持货架的稳定性,要遵循“上轻下重”的优化原则,该目标可以转化为所有货物的整体重心高度最低。依据以上思想,建立第二目标函数如式(4)。

因为对单排货位优化时,考虑所有的货位都有货物,而且某排货物分配的货物的种类和数量都已知,因此对于给定的某排货架 为常量,同时h也是常量,式(4)可以简化成式(5)。

综合以上可得出单排货位优化的多目标规划的模型如下:

x,y为整数

多目标优化(multiple objective program,简记为MOP)问题由FY Edgeworth最先提出,V Pareto对其进行了完整的定义。在求解多目标问题时候,各个目标函数存在着相互冲突,很难求到满足所有目标函数的最优解,只在非劣解的基础上不断寻找满意解,即帕累托(Pareto)最优解。

多目标优化问题可以描述如下:

对于 ,使得fi(Xp)≤fi(Xq)(i=1,2…n),则称Xp为该问题的帕累托最优解。

本文采用乘除法,通过目标函数的相乘使所得函数具有明确的含义,这样就把多目标函数转化成单目标函数,这个单目标函数中包含了多目标优化的意图,并利用遗传算法进行求解。

遗传算法(Genetic Algorithm,GA)最早是由Holland教授在20世纪70年代提出并发展起来的智能优化算法,具有更好的全局寻优的能力。遗传算法对种群的每个个体进行搜索,算法通过有效的设计可以跳出局部最优的“陷阱”,有利于得到全局最优解,并且全局最优的获得往往不依赖于初始解。而传统优化算法的寻优能力往往比较依赖于初始解,且不易得到全局最优。

本文建立的目标函数有两个,一个关注出入库的效率,另一个关注货架的稳定性。为了便于模型的求解,这里利用乘除法把两个目标转化成单个目标。则原目标函数就变成了:

本文对单排货架上的货物采用真值编码,编码串的长度为a*b位,即编码串的长度是单排货架的层数与列数的乘积,也就是单排货架上的所有货物数。如c1c2…cn…ca*b,代表1到a*b之间所有的整数的一个排列组合,cn表示第cn个货物放在第x列第y层的货架上(其中x的取值为a整除n的商加1,y的取值为b整除n的余数)。

1到a*b之间所有的整数的一种排列组合组成了一个完整的个体的染色体,随机产生M个染色体即可组成初始种群,一般种群的规模在20~100之间。

适应度函数又叫评价函数,在遗传算法中适应度值高的个体遗传到下一代的概率比较大,本文的模型是求解最小值,因此需要在目标函数和适应度函数之间做出变换。由于两个目标函数的最小值均为非负,因此可以将目标函数的倒数作为适应度函数,目标函数值越大的解对应的适应度函数值就越小,这样的解被“优胜”的可能性也就会越小。

本文选择轮盘赌的策略对父代个体进行选择,复制到下一代。每个个体就好比轮盘上的一个扇形,扇形的角度与个体的适应度值成正比例关系,适应度越高的个体对应的扇形越大,被选中的概率也越大,图5为轮盘赌的示意图。因此在轮盘赌的策略下,第i个个体被选中的概率p(i)与其适应度值Fs(i)的大小成正比,见式(10)。

那么个体被选中次数的期望为n·p(i)。

图5 轮盘赌示意图Fig.5 Roulette schematic  下载原图

在交叉运算前先将种群中的M个体以随机的方式组成[M/2]对配对,交叉操作就是在这些配对的父代中进行的。本文在交叉策略方面选取单点交叉,在个体的编码串随机设置一个点,对该点以后的部分染色体进行相互交换,对于长度为N位的编码串个体,则交叉点的位置有N-1种可能。单点交叉的示意图如图6。

图6 单点交叉示意图Fig.6 A single point of cross schematic diagram  下载原图

本文在编码中采用的是整数编码,为了使变异后的个体染色体仍然能表示可行解,在变异操作中选取个体染色体的指定位置上的基因进行对调(见图7),从而既通过变异产生新个体又能保持染色体基因组的完备性。

图7 变异运算示意图Fig.7 Mutation operation schematic diagram  下载原图

这里采用迭代次数达到预设的代数来判断算法是否终止。

Step1:初始化,设置控制参数和终止条件;

Step2:Gen N:=0,随机产生初始种群Pop(0);

Step3:计算初始种群个体的适应度值和目标函数值;

Step4:按照轮盘赌选择策略,从Pop(Gen N)种群中选择出Pop(Gen N+1)种群;

Step5:对Pop(Gen N+1)种群进行交叉、变异运算,Gen N:=Gen N+1;

Step6:判断算法是否满足终止条件,满足则停止,不满足则转Step3,继续迭代;

Step7:输出最优解。

先根据指数平滑预测方法,对仓库的货物进行预测。假定已得到库内某排货架上的16种货物(共计200托盘的量)的属性,具体如表1所示。

把以上货物按照上表中的顺序,以托盘为单位编号1~200,然后将1~200号货物随机排列作为一个初始解见下表2,表中的单元格表示该排货架某个货位对应的货物,如第二列第三层的货格对应的是第133号货物。该初始解对应的目标函数为9.216 8*108。

假设货格的长度和高度均为1米,堆垛机的垂直和水平行走速度均为1 m/s,取种群规模NIND=100,代沟GGAP=0.7,交叉概率Pc=0.7,变异概率Pm=0.1,迭代次数为4 000代,可以得到优化后的解如表3,该优化后的解对应的目标函数值为4.684 9*108。

表1 某排架内货物的属性Table 1 Properties in the cargo bay  下载原图

表1 某排架内货物的属性Table 1 Properties in the cargo bay

表2 货位优化前的随机初始解Table 2 Random initial solution before slotting optimization  下载原图

表2 货位优化前的随机初始解Table 2 Random initial solution before slotting optimization

表3 货位优化后的解Table 3 Solution after slotting optimization  下载原图

表3 货位优化后的解Table 3 Solution after slotting optimization

由表1和表3可以看出优化后的货位较大程度上保留了货物的相关性,即属性类似的货物临近放置。

图8为算法的优化过程。

图8 算法优化的过程Fig.8 Algorithm optimization process  下载原图

由图8算法的优化过程可以看出,算法在1500代时已经较好的收敛,整个优化时间为164.25s,优化后解的目标函数值降至原随机解的目标函数的50.83%。也就是说本文建立的货位优化模型,在保持货架的稳定性即货物的摆放遵循“上轻下重”的优化原则的同时,最大限度地把出入库频繁的货物放置在靠近巷道口处,这将极大地提升订单的响应速度。

1)本文建立了基于出库时间和货物重心最低的货位优化的双目标优化模型,并利用乘除法将双目标函数转化为单目标函数,并设计了求解此模型的遗传算法。

2)通过遗传算法求解,优化后的目标函数值降至原随机解的目标函数值的50.83%,说明了遗传算法在解决此类问题时的有效性,为企业节约仓储成本,提高作业效率奠定了基础。