基于遗传算法的密集型自动化立体仓库货位分配优化研究
2019-10-18徐伟华沈文喆巫仁亮张婷
徐伟华 沈文喆 巫仁亮 张婷
摘要：密集型自动化立体仓库是由在货架轨道上行走的穿梭板与堆垛机配合作业。而影响其系统效率的主要因素是堆垛机要搬运穿梭板。文章研究了仓库中货物订单的最优货位分配与出入库作业次序。在研究基础上建立数学模型，运用遗传算法以及MATLAB软件对模型求解并得出数据。用FLEXSIM仿真软件建立某企业仓库1：1实体模型，先得出优化前数据，然后对模型优化得出优化后数据。将优化前数据与求解数据和优化后数据进行对比，发现堆垛机搬运穿梭板的次数减少了30%，运行效率提高了10.4%，且求解数据和优化后数据结果误差较小。
关键词：密集型自动化立体仓库;货位分配;遗传算法
中图分类号：F406.5文献标识码：A
0引言
随着时代的发展，企业开始逐渐认识到了自动化立体仓库所带来的竞争优势。在现如今由穿梭板式货架、穿梭板、堆垛机以及输送装置组成的密集型存储系统，在一定投资范围内使得立体仓库存储空间增加，提高自动化立体仓库的存储密度。国内外对自动化立体仓库货位分配的研究文献自1993年开始，2001年，S.Hsieh提出一种基于BOM的自动化立体仓库货位分配方法，强调将货物先分类，再存储的策略，并结合算例验证了该方法的有效性。2006年，Byung等为仓库的货位依据周转率的高低设定了分区，高周转率库区在出入库站台附近，低周转率库区距离出入库站台较远。2007年，朱从民、王卫青等详述了自动穿梭板的设计及其自动穿梭板的工作方式，为穿梭板应用在自动化立体仓库中奠定了基础。2011年，Kov6cs A提出了一种MIP模型，用于寻找基于分类的存储货位分配策略，它可以最小化订单周期时间，平均采购工作量或者2个标准的线性组合。2014年，Chuang等首先通过网站统计数据与关联规则挖掘研究了产品类别间的相对强度，然后按类分配。2017年，杨骁等通过分析穿梭式自动化立体仓库系统的各个设备的特点及其调度作业特点，提出穿梭式自动化立体仓库的出入库调度策略，通过对穿梭板和堆垛机的调度运行时间的分析对所提出的策略进行合理验证，通过数据的支撑证明所提出的策略的優化性。国内外学者对密集型自动化立体仓库的研究多集中在货位分配方法上，对于货位分配优化问题研究相对较少。
本文以某企业“堆垛机加穿梭板”式密集型立体仓库为基础进行研究，该仓库具体布局图如图1所示：
以优化货位分配为目标，建立数学模型，减少堆垛机搬运穿梭板次数。
1模型建立
1.1问题描述。密集型自动化立体仓库货架由n个货架区组成，密集型货架最外侧均为单排货架区，用来存储零散的货物托盘，中间由任意组S排单排货架紧密排列在一起组成P组密集型货架组。密集型自动化立体仓库中各个货位尺寸相同，承载的货物托盘以及各个穿梭板大小相同;堆垛机在水平方向做匀速运动，竖直方向做初速度为0的加速运动，穿梭板在货架轨道上做匀加速直线往复运动，堆垛机和穿梭板作业的速度、加速度已知;在该密集型自动化立体仓库中货位的位置、存储的物料种类、频率以及穿梭板所在的位置均是已知的;密集型货架的每一个密集货格列中，存储的货物种类是一样的。
1.2符号说明（见表1）：
1.3模型分析。在单排货架区O，n上的货物托盘的分配作业中，不需要堆垛机搬运穿梭板;在密集型货架区1，2，…，n-l中，需要堆垛机搬运穿梭板，将某一时刻的某种类出入库的任务订单个数M以密集型货格列的货位数s进行分解，即M=nis+cini，进行如下工况分析：
工况一：当Mi=1时，此时出入库第i种货物托盘的台数数量较少，可以选择货架系统的单排货架，或者密集型货架组中存储该类货物托盘的近巷道的密集型货位;上述两种情况是基于不用堆垛机搬运穿梭板的情况下进行的货位分配，搬运穿梭板的次数为O;
工况二：当Mi>s时，将Mi以密集型货架组的货格列中的总货位数s为单元进行分解，即M=nis+Ci;其中：（1）ni≥1：这种情况下的出入库作业的货位分配，以密集型货架组的货格列为全空或者全实为出入库作业的货位研究对象，建立货位分配模型时将该种类的全空或者全实货物托盘简化成第i种类有ni个货物托盘进行出入库作业，将密集型货格列简化成单排货架的形式，第i种货物托盘的出入库货位分配的托盘个数为密集型货格列货位总数的整数部分，即选定某一密集型货格列存储该种类货物托盘，堆垛机从站台至该货位需要搬运s次，由此对该种货物托盘的频次和存储该种类的密集型货格列的位置与堆垛机搬运托盘次数的乘积之和求最小。
（2）1i
1.4建立模型。根据上述分析建立密集型自动化立体仓库的货位分配模型目标函数：
其中：约束条件式（2）、式（3）表示根据第i种货物托盘的数量考虑货位分配的各个货位域;式（4）、式（5）、式（6）表示堆垛机的运行时间、速度与距离之间的关系;式（7）表示目标函数中的各个货位的时间的取值;式（8）表示第i种类的货物托盘的个数与密集型货格列货位数之间的关系，是第i种类的货物托盘数分解成密集型货格列货位数的整数倍部分和剩余的小于密集型货格列货位数的部分;式（9）表示第i种货物托盘除密集型货格列整数倍外的余数部分取值范围;式（10）表示第i种类的货物托盘的余数部分存储在某密集型货格列中的个数;式（11）表示当第i种货物托盘存储进某货位，当该部分的货物托盘的数量等于1时，表示不需要搬运穿梭板，取值为O，当该部分的货物托盘的数量大于1，小于密集型货格列货位数s时，需要搬运穿梭板，取值为1。
2遗传算法与仿真实例验证
运用遗传算法求解，取种群规模为250，选择算例货架区中的货位作为本研究的初始解，选取变异概率为Pm=0.05，交叉概率取Pn=0.8。当连续Ⅳ代子代种群的最优个体适应度都小于等于父代最优个体的适应度时可以终止运算。当组中结果趋于平缓，迭代可能达到算法设定的迭代次数而停止，也可能迭代到第n次时，所得到的结果与第n-1代的结果相差较小时，即△F=（Fn-Fn-1）/Fn，当△F=0.5时，此时也可认定迭代停止，终止运算。
利用MATLAB软件对密集型自动化立体仓库的货位优化模型进行遗传算法求解，将预先设定好的参数（见表2）代入目标函数。
随着迭代次数的增加，适应度值在减小，当迭代次数达到230次，适应度函数的值基本趋于稳定，取迭代到232次时的最优适应度值为57.12min，完成订单搬运穿梭板的次数为7次。数据计算统计结果如表3所示：
以某卷烟厂密集型自动化立体仓库的货物托盘的存取为例，该密集型自动化立体仓库同本文研究的密集型自动化立体库货架结构相一致，抽取80条出入库货物托盘的订单任务。
根据卷烟厂密集型自动化立体仓库的实体模型，使用Flexsim仿真软件建立1：1的实体模型，并按照该卷烟厂密集型自动化立体仓库的出入库作业流程进行实体连接。按照密集型自動化立体仓库的运作流程，对实体参数进行设置，通过Flexsim的dbopen（）函数连接编程数据库，通过dbsqlquery（）函数编写执行sql语句，以数据库中的货位信息表和出入库作业表作为输入进行仿真。对模型进行调试运行后，基于目前该厂在密集型自动化立体仓库的出入库作业中使用的随机货位分配策略对80条出入库作业任务进行仿真模拟运行。在对数据进行总结的时候，取不同时间段作业的平均值，选择适中的一组仿真统计输出数据。依据仿真数据对该卷烟厂密集型自动化立体仓库的堆垛机搬运穿梭板的次数以及货物托盘的出入库过程中堆垛机搬运货物托盘的出入库时间等进行计算统计如表4所示：
将本文优化后的货位分配方案输入仿真模型，运行后输出仿真结果。在对数据进行总结的时候，取不同时间段作业的平均值，选择适中的一组仿真统计输出数据。依据仿真数据对密集型自动化立体仓库的堆垛机搬运穿梭板的次数以及货物托盘的出入库过程中堆垛机搬运货物托盘的出入库时间等进行计算统计如表5所示：
将得到的仿真结果与该卷烟厂原始作业的仿真结果进行对比如表6所示：
3结论
与通过遗传算法计算出的堆垛机作业时间相比较，仿真得到的结果偏大，两者误差约为0.77%，误差较小。该卷烟厂采取的货位分配策略与本文提出的货位分配策略相比较，烟厂目前采用的货位分配策略中堆垛机搬运穿梭板的次数要较后者多，搬运穿梭板次数减少了30%。本文提出的密集型自动化立体仓库货位分配优化研究中，相较于该厂现有作业策略，堆垛机搬运穿梭板次数减少了，堆垛机搬运作业的总时间减少，堆垛机搬运货物托盘出入库的效率提高了10.4%。
