基于遗传算法的立体仓库货位动态分配优化

张晓兰，蒋丽娜，于洪涛

(哈尔滨商业大学，计算机与信息工程学院，哈尔滨150028)

随着计算机技术、现代通信技术和自动控制技术的迅猛发展，仓储管理水平也已经向着信息化、自动化、智能化方向发展[1].而在仓储管理中货位的分配及优化问题一直是一个非常棘手的问题.高效的货位动态分配优化算法将提升各企业在仓储管理方面的竞争实力.实时分配的优化货位对降低仓库中货品搬运的成本，提高仓库的空间利用率及货品出入库的效率具有非常重要的现实意义.

货位的分配及优化问题是一个多目标的优化问题.遗传算法具有鲁棒性好，全局搜索能力强的特点，它是解决多目标优化问题强有力的工具[2].本文采用基于遗传算法的权重系数变换法对货位动态分配优化问题进行研究.

1 立体仓库货位动态分配优化问题

1.1 问题的提出

在对企业仓储管理实际情况的调研中发现，一些仓库的货位分配策略不尽合理，管理人员仅凭直观经验进行药品货位分配，缺乏先进的科学依据，不利于货品的快速出/入库;且货品存放随意，库存面积利用率不高，库存周转效率较低，严重影响了企业的生产组织和经济效益.经研究发现，同一货品存放在仓库中的不同货位，所消耗的能量是不同的，例如货品放在离出/入库工作台近的货位比离出/入库工作台远的货位要节省出/入库时间，同时也节约了能量消耗，降低运行成本，放存在高货位比存放在低货位消耗的能量要多[3].因此，对立体仓库的货位进行动态分配优化，可以很好地解决上述问题.

1.2 货位分配策略的选择

1.2.1 常用的货位分配策略

常用的货位分配策略有:1)定位存储:每一种货品都依据其周转率安排固定的货位，货品之间不能互用货位，其优点是管理方便，缩短出入库运行距离，缺点是降低库区空间的平均使用效率.2)随机存储:每一种货品的货位随机指派，而且可以经常改变，其优点是可以共享货位，提高货位使用效率，缺点是出入库管理和盘点困难.3)分类存储:所有的货品按照其特性进行分类，然后采用固定货位存储固定种类的货品，其优点是有利于畅销品的存放，缺点是库区储位必须设计为货品的最大在库量，降低了使用效率.4)分类随机存储:每一种货品有固定的存放区域，但在存放区域内货位的分配是随机的，其优点是提高货位使用效率，缺点是出入库管理和盘点困难.5)共享存储:不同的货品的货位不但可以随机指派，而且货品之间可以共享货位空间，其优点是节省空间和搬运时间，缺点是管理非常复杂.

1.2.2 货位存储策略的选择

采用RFID对货品的各种相关信息进行记录，使仓库管理系统具备了可实时查询和定位货品的功能，克服了出入库管理和盘点困难的缺点，因此采用随机存储的货位分配策略.

1.3 多目标优化问题

1.3.1 优化模型的建立

假设立体仓库有K排I层J列，货架的宽度与货架间的距离之和为H、货位的宽度为L，并且离出/入库工作台最近的列记为第1列、最近的排记为第1排.处于第x列y排z层的货位记为(x，y，z)(x=1，2，……J;y=1，2……K;z=1，2，……I).货位上货品的质量为Mxyz.

1)根据“就近存取”的原则，将货品放在离库门最近的地方.则货位分配优化模型可以描述为:

2)考虑货架的承重能力，将货品质量Mxyz较小的货品尽可能地存放在货架的高处.则货位优化模型可以描述为:

3)考虑货架的稳定性，取货时应该尽可能的先从高处取货.此优化模型可以描述为:

将其转化为求最小值问题:

1.3.2 优化模型的约束条件

当有货品要进行存储时，要保证所分配的货位为空，即:P(x，y，z)=0式中:P(x，y，z)代表货位(x，y，z)是否为空的标志位.

2 遗传算法求解约束多目标的货位动态分配优化问题

从建立的优化模型可以看出储位优化是一个多目标优化问题.多目标优化问题的各目标函数之间往往相互冲突，通常不存在对所有目标都是最优的解，只存在一组均衡解，即所谓的Pareto最优解，难以得出一个满足所有目标函数的最优解[4].针对这种情况本文采用基于遗传算法的权重系数变换法求解此多目标优化问题，即给每个目标优化函数f(i)(i=1，2，……n)赋予权重系数Wi(i=1，2，……n)，则多目标优化问题就转化为单目标优化问题，即可以利用单目标优化的遗传算法求解多目标优化问题[4].因此优化模型可以转化为:

对于不同的公司，他们注重的优化点不同，有的公司注重货位出入库的效率，有的注重货架的承重能力，而有的注重货架的稳定性问题，因而采取权重系数变换法可以给用户更多的选择余地，可以根据自己的实际情况进行权重系数的设置，这样更有利于实际问题的解决，提高工作效益，达到事半功倍的效果.针对本文的实例情况，该制药企业对出入库的效率更加的重视一些，因此采用2∶1∶1的比例分配权重系数.

其遗传算法求解步骤

1)获取立体仓库的当前库存状态信息(空货位位置、各货位上货品重量等).

2)确定种群数目Pop、最大遗传代数Gmax、编码长度、代沟GGAP、交叉概率Pc、变异概率Pm等参数.

3)采用二进制编码方法对货位进行编码，并增加货位标志位P(x，y，z)(其值为0时代表该货位为空)，随机生成初始种群.

4)适应度函数的确定.由目标函数可得适应的函数为

其中:Cmax为f(x，y，z)的最大值估计.

5)分别计算每个个体的适应度值，对于违反约束条件的个体进行惩罚.即对个体的适应度调整:

其中:Fit(f(x，y，z))为原始适应度;Fit(f(x，y，z))为调整后的新适应度;P(x，y，z)为惩罚函数.

6)根据适应度和代沟GGAP从种群中选择优良个体.

7)完成种群的重组，按照交叉概率Pc进行交叉、按照变异概率Pm进行变异，形成新的种群.

8)算法终止条件.当遗传代数达到最大遗传代数Gmax，结束算法，并输出最优解.

9)更新库存信息.

应用上述算法以某制药企业药品仓库为例进行仿真实验，该仓库共有10排立体货架，每排货架包括4层25列共1 000个货位.实验中，取货架的宽度与货架间的距离之和H=1、货为的宽度L=0.8、种群规模N=100、交叉概率Pc=0.8，变异概率Pm=0.1，最大迭代次数为100.实验结果验证了算法的有效性.

3 结语

基于遗传算法的立体仓库货位动态分配优化的算法，以存取路径距离及货架承重能力和稳定性为优化目标.通过权重系数变换法较好的解决了多目标之间相互冲突的问题，并加入惩罚函数，淘汰不满足约束条件的解.仿真实验结果表明该算法能够提高货位分配效率，降低货位管理成本.

[1]蔡增玉，甘 勇，金保华，等.基于RFID的物流管理系统设计[J].郑州轻工业学院学报:自然科学版，2009，24(6):23－28.

[2]邹晖华，胡吉全，杨艳芳.自动化立体仓库货位分配策略优化研究[J].湖北工业大学学报，2008，23(3):43－45.

[3]QUW J，XU F，LIU ZH，etal.Regional Higher Education Resource Allocation Pareto Equilibrium Analysis[C]//International Conference on Intellectual Technology in Industrial Practice，Chang Sha，China，2010(1):354－348.

[4]李敏强，林 丹，李书全，等.遗传算法的基本理论与应用[M].北京:科学出版社，2004.