双深式自动化立体仓库的货位优化研究.doc

遗传算法在双深式自动化立体仓库货位分配中的应用研究 摘要：双深式自动化立体仓库在提高土地使用率的同时对货位管理和分配提出了更高的要求，本文采用两级库位编码的方式对双深式立库的货位分配进行研究，通过建立关于货架稳定性和出库效率两个方面的多目标优化数学模型，遗传算法求解和MATLAB仿真分析，结果表明，该货位分配优化策略可以很大程度上提高双深式自动化立体仓库的效益。关键词：双深式；自动化立体仓库；货位优化；多目标优化；遗传算法中图分类号：TP39 文献标志码：AApplication of genetic algorithm in double deep shelf automated storage and retrieval system goods lacation distribution Abstract：The double deep shelf automated storage and retrieval system(AS/RS) in improving land utilization at the same time puts forward higher requirements on goods management and distribution, this paper uses two levels location coding way for double deep shelf AS/RS to study the distribution of goods, through establishing the multi-objective optimization mathematical model in two aspects of the shelf stability and outbound efficiency,genetic algorithm solution and MATLAB simulation analysis, the results show that this goods distribution optimization strategy can be largely improve the efficiency of the double deep shelf automated storage and retrieval system.Key words：double deep shelf;automated storage and retrieval system (AS/RS);slotting optimization;multiobjec-tive optimization;genetic algorithm(GA)0 引言随着土地资源的日益紧缺和成本的增大，传统的自动化立体仓库已经不能满足物流产业的效益最大化。为了克服和突破当下物流产业的这种“瓶劲”状态，有学者提出了双深式自动化立体仓库1-2。但由于这种立库最大的特点是一个堆垛机对应四排货架（每侧各两排货架），这无疑减少了巷道和堆垛机的数量，但同时也增加了货位管理的复杂程度。因此，如何更好地实现货位优化成为了提高双深式自动化立体仓库整体出库效率、改善物流产业的关键所在。货位优化是在特定的货物存储方式下，有效掌握货物和货位的变化情况，按照货物的周转率、质量和相关性等方面对货位进行实时分配。双深式自动化立体仓库的双排货架增加了临时周转单元，在进行出入库和倒库操作时可以起到很好的货物暂存作用，有效提高了货物优化的效率。1 货位配置优化问题数学模型双深式自动化立体仓库和传统的自动化立体仓库在货位优化时需要实现的目标都是一样的，都要满足货架的重心最低以提高货架稳定性、出入库时间最短以提高出库效率等目标。本文将货架稳定性和出库效率作为具体的优化目标，但这两个目标之间本身又是相互矛盾的，一个目标的实现总是以牺牲一个目标为代价，这就需要建立一个多目标优化的数学模型3-6。2.1 问题描述与基本假设本文以某物流公司的双深式自动化立体仓库为研究对象，将涉及的具体问题和参数描述如下：共有n组双排货架，将靠近巷道的一排货架规定为内侧，而远离巷道的一排货架则规定为外侧。则内侧货架可编码为2n-1，外侧货架编码可为2n，如图1所示。所示每排货架有p列q层，将靠近出库台位置双排货架的内侧排为第1排，靠近出库台位置的列记为第1列，将最底层定义为第1层。则第x排y列z层货位的坐标记为（x,y,x）（x=1,2,.,2n;y=1,2,.,p;z=1,2,.,q）。图1 双深式自动化立体仓库结构图Fig.1 The structure of the double shelf automated storage and retrieval system同时采用固定货位分配策略，也就是每个货位只能放同一种货物，不能放多种货物。另外假设立库内（x,y,z）货位处的货物出库频率为fxyz，货物质量为mxyz，货位单元格的长宽高相等均为L。为了便于计算，不考虑出库货物耗费的时间，只研究拣选所耗费的时间。2.2 目标函数及约束条件 （1）货架稳定性分析要想使货架的稳定性足够好，就必须遵循上轻下重的原则，保证货架上货物的整体重心足够低。假设将质量为mxyz的货物放在货位(x,y,z)上，为了使货物的总重心最低，从而保证货架的稳定，就要使货位(x,y,z)所在的层数z和货物质量mxyz的乘积最小，因此有满足货架稳定性最好的目标函数S如下：（1）（2）出库效率分析提高双深式自动化立体仓库的整体出库效率的本质就是缩短出库货物所用的时间，但由于堆垛机的速度是一定的，那么减小出库货物堆垛机的行走路程才是缩短出库货物时间的关键。由于双深式自动化立体仓库的货架是双排的，因此对外侧货架上的货物进行出库操作时，需要考虑内侧的货架上是否存放有货物。如果没有货物时就直接进行出库操作，如果放置有货物时需要进行周转操作。在将内侧货架上的货物取出之前，先要将外侧货架上的货物转移到临时周转单元。假设某货位的坐标为（x,y,z），出库台的坐标为（0,0,0），vy和vz分别代表堆垛机在水平方向和垂直方向的运行速度，而vx则代表将货物从货架出口送到出库台的运输机的速度。由此可以得出将货位（x,y,z）处的货物送至出库台实际所耗费的时间为：（2）其中，flag代表周转标识。当flag=0时，表示内侧货架上没有货物，不需要进行货物周转操作；当flag=1时，表示内侧货架上放有货物，需要进行货物周转操作。表示需要临时周转操作时堆垛机与取货货位点（x,y,z）对应的内侧货位点单程运行时间。实现货位优化，实际就是要减小出库频率高的货物的出库时间，使其实际耗费时间最少，因此满足出库效率最高目标的目标函数E如下：(3)式中表示不大于的最大整数，而表示取两者之间的较大值。（3）约束条件根据本文假设的仓库模型，共有n组双排货架，即2n排货架，每排货架有货位p列q层，x、y、z分别表示货架的排、列、层。因此，可以得到货位优化问题的空间约束条件为：其中，x、y、z均为正整数2.3 建立多目标数学模型在满足货位空间约束条件的同时，使货物出库的耗费时间最少、货物的总重心最低，建立了货物优化的两个目标函数，这些目标函数需要同时得到优化，因此得到本文双深式立库货位分配的基本数学模型。(4)s.t.且x,y,z均为正整数3 求解货位分配优化问题的遗传算法本文采用遗传算法来研究双深式立库的货位优化问题，结合随机权重系数法，对各个子群体分别用不同的权重系数在不同方向上搜索得到最优解7-9。3.1 随机权重系数法假设多目标问题有k个目标函数，并且需要得到它们的最小值，给每个目标函数fi(x)(i=1,2,.,k)赋予相应的代表其重要程度的权重wi(i=1,2,.,k)，那么该多目标优化问题可以表示为： (5)其中，,i=1,2,.,k且均为有3.2 适应度函数确定于算子设计（1） 适应度函数 遗传算法中的适应度主要用来评价个体的优劣程度，适应度越大个体越好，适应度越小个体越差。对个体进行选择时主要根据适应度的大小，适应度大的个体良好基因更容易进入下一代，使得个体的优良特性得以遗传。而遗传算法要求适应度函数值必须是非负数，并且最大值。本文货位分配优化的目标函数是非负数，且是最小值。为了构建本文的适应度函数，取目标函数的倒数作为适应度函数，为了防止数据溢出，在目标函数的基础上加1。经过这种转换就得到了对应的适应度函数如下：(6)（2） 选择算子设计确定每个个体的选择概率psel，是选择出理想的R/2对父本进行交叉和变异操作，产生新个体的第一步。结合他们的权重值wi，由式（5）得到相应的适应度，进而就可以得到选择概率如下： （7）其中，M代表种群规模，fmin代表当前种群中最小适应度值。（3） 交叉算子设计本文设计的交叉算子为二进制交叉算子，为了保留性能更优的个体，不是所有的父代都参加交叉操作，而是以pc的概率进行交叉的，剩下的直接进入下一代。由父代个体和交叉产生子代个体和的过程如下：首先随机选择一个数，计算出的值，即：父代产生子代的交叉运算如下：（4） 变异算子设计本文变异算子采用多项式变异算子，父代个体以pv的概率进行变异，产生性能更优的子代个体。父代个体变异产生子代个体的具体操作如下：首先随机选择一个数，计算出的值，即：父代个体变异产生自带个体的计算如下：3.3 遗传算法的实现流程编码：本文采用整数排列编码方式对染色体进行编码，基因位置表示固定货位上的货物编号，每段基因表示要存储货物的货位坐标(排、列、层)。（1） 采用随机方法产生规模为M=40的初始种群；（2） 评价当前每个个体的适应度，选取Me个非受支配解，放入暂定集合；（3） 按照式（5）确定权重值，按照式（7）确定选择算子，依次选择出（M-Me）对父代个体；（4） 将步骤(3)选取的(M-Me)对父代个体进行交叉操作后得到(M-Me)个新个体，并对它们进行变异操作；（5） 将新得到的(M-Me)个解与暂定集合中的Me个非受支配解放到一起，进行局部搜索得到M个新解作为新种群；（6） 若遗传次数达到规定上限100，终止运算，否则转到步骤(2)。4 实验仿真及结果分析本文选取某物流公司的双深式自动化立体仓库进行货位分配优化问题的研究，利用MATLAB进行优化仿真10-12，规定基本参数如下：表1 优化仿真的基本参数Table.1 The basic parameters of optimization and simulation优化参数取值优化参数取值X方向移动速度vx1m/s货架的层数6Y方向移动速度vy1m/s遗传算法迭代次数100Z方向移动速度vz0.5m/s初始种群个体M40货架单位长度L1m交叉概率pc0.7货架的排数8变异概率pv0.1货架的列数20在基本参数确定以后，结合货物信息的和双深式自动化立体仓库的货位信息，进行了大量的数据运算和试验仿真，得到了目标函数值随迭代次数在解和种群均值两个方面的结果追踪如图2所示。图2 解和种群均值追踪结果Fig.2 The tracking results of solution and population mean value同时，将货物信息和货位信息分别带入两个目标函数中，求出货位优化前后目标函数的值，并对比如下表：表2 优化前后目标函数值对比Table.2 The comparison of the objective function value before and after optimization目标函数优化前优化后降低值降低率（%）S2.89621.31571.580554.57150749E60.5333.1227.4145.28333058从表2中可以看出，经过货位分配优化之后，本文所要优化的货架稳定性和货物出库效率都得到很大的改善，两个目标的降低率分别为：54.57%、45.28%。5 结论本文采用遗传算法完成了对多目标优化问题的研究，借助MATLAB软件工具，以某物流公司双深式自动化立体仓库为研究对象，对其货位分配问题进行了优化求解和仿真分析，有效改进了当前的货位分配。对文中建立的模型试验仿真结果表明，经过货位分配优化之后，货架的稳定性和出库有效率得到了很大的改善，这大大降低了双深式立库运营过程中的成本以及货架的后期维护费用，从根本上解决了物流产业成本高昂的现状，同时也为管理人员做出科学合理的决策提供了强有力的理论支撑。参考文献1 黄杨波,刘万军,刘卉.双伸位堆垛机系统调度的优化设计J.计算机工程,2010,36(1): 260-2642 赫隆誉.双伸位堆垛机的设计J. 物流技术与应用, 2007, 12(1):98-99.3 李梅娟,陈雪波. Pareto遗传算法在货位配置中的应用研究J.控制工程, 2006, 13(2): 138-141.4 田国会, 张攀, 尹建芹, 等. 基于混合遗传算法的固定货架拣选优化问题研究J. 机械工程学报, 2004, 40(2): 141-144.5 吴婷.基于遗传算法的仓储系统多目标货位优 化的研究D.武汉:武汉理工大学, 2011.6 别文群,李拥军.遗传算法在立体仓库货位优化分配中的研究J.计算机工程与应用,2009,45(29):211-219.7 Lins Isis Didier, Droguett Enrique Lpez. Redu -ndancy allocationproblems considering syste -ms with imperfect