柔性生产线立体库垛机路径优化研究
2020-3-3 来源： 成都农业科技机电分院 .四川日机密封件 作者：吴佳 王方
摘要：随着柔性制造系统的不断发展，在其制造生产线上配备自动化立体仓库可以减少生产线上物料的搬运时间，进而提高整条生产线的生产效率。自动化立体仓库作为柔性生产线的重要环节，其自身的工作效率将直接影响到整条柔性生产线的工作效率，故优化自动化立体仓库垛机的路径成为一个研究热点。针对某类具备“缓冲层”的自动化立体仓库，基于缓冲策略，提出了改进的遗传算法来优化垛机路径。“缓冲层”起到过渡作用，减少柔性生产线上加工中心的待工时间。通过VS程序仿真，验证了该算法的可行性，实现了立体仓库中垛机的运动路径优化。
关键词：自动化立体仓库；缓冲策略；遗传算法；路径优化
0 引 言
自动化立体仓库是现代物流以及机械自动化程度较高的企业所配备的大型系统，其运行效率的高低直接影响到企业效益的高低。而衡量立体仓库运行效率高低的一项重要指标是巷道中垛机的运动路径的长短。如何优化垛机的运动路径成为了热门研究对象。
目前国内外大多自动化立体仓库是由高度对称的立体货架构成，对于这类传统立体仓库的货位优化研究也是比较成熟的。Dranzen等[1]应用遗传算法解决了基于类存储系统的AS/RS中的排序问题，进而提高了生产效率。Robert等[2]采取WES（Warehouse Execution System）连接了WCS （Warehouse Control System ） 和 WMS（WarehouseManagement System），使WES不仅仅起到桥梁的作用，还优化了AS/RS中垛机运行时间。曾强等[3]针对自动化立体仓库有货位载重约束的货位分配问题，提出了一种多目标———出库时间最短、货架稳定性最高的优化方法。钟科艾等[4]以某卷烟厂的立体仓库为研究对象，依据产品周转率、产品相关性和货架稳定性来确立具体的优化目标。魏林等[5]通过分类分区的方法实现了整体出入库效率的提高和各个巷道作业时间的平衡。
一般的立体仓库有多排货架，相邻货架间由垛机运输物料，而垛机的出入口一般放置在货架的一端或者两端。如果立体仓库够高，将按层增加垛机的出入口，以便提高立体仓库的出入库效率。但是现实生产应用中，有一些立体仓库的构造相对特殊，它们跟生产线联系紧密，特别设置了“缓冲层”以增加立体仓库与生产线的衔接出入口，使得立体仓库不再仅仅是由两端出入口来与生产线连接，如图1所示
图 1 柔性生产线与立体仓库示意图
1.垛机 2．立体仓库 3．缓冲层 4．加工中心5．机器人导轨 6．机器人
为提 高 生产线的生产效率，就必须提高与之联系紧密的立体仓库的出入库效率。目前对这类特殊化构造的立体仓库的研究很少，而现有一些特殊化的立体仓库基本按照传统先进先出的原则简单地运转，不仅效率低，而且对于整个生产过程来讲，可能导致生产线上加工中心（或员工）待工时间过长，造成资源浪费，成本浪费。
1、 问题描述
1.1 工作流程分析
这类特殊化构造的立体仓库与柔性生产线联系紧密，整个柔性生产线的简单流程图如图2所示。
图2 柔性生产线与立体库之间流程的简单示意图
根据加工中心的工作状态 ，来决定立体仓库垛机的运动 。 加工中心快完成其当前的工序操作时 ，该加工中心的工作状态就被 置为 “ 加工 中 心上料”，立体仓库垛机接收该信号后，会判断是哪个加工中心发出的信号，然后再在立体仓库中找出最近的物料并将它搬运至缓冲层。生产线上的机器人再将物料搬送至加工中心。如此循环，直至该生产任务完成后，关闭柔性生产线。
由此可见，生产任务的大小、加工中心个数及其工作效率、缓冲层货位的利用均对立体仓库垛机的运动路径产生一定影响。
1.2 过程建模及优化策略
1.2.1 假定条件
1）从某时刻开始，立体仓库及生产线上的所有设备均处于可用状态；2）立体仓库不存在物料缺货情况，物料加工完成后不回库；3） 生产线上加工中心可对任意物料进行加工，而且各个加工中心的工作效率相同。
1.2.2 计算符号
1） 当前生产任务清单里包含物料总数M个（种群大小）；2）Mm（i,j,k）表示物料m在货位（i,j,k）上，i为货架序号，j为层序号，k为列序号，I,J,K分别为各序号最大值；3）Vx表示垛机水平速度；Vy表示垛机垂直速度；Vz表示垛机伸缩速度；单个货位长度为Lo，高度为Ho。这些属于立体仓库的物理构造，其数值都是已知数；4）D（p,q）表示垛机位于第p层的第q列。
图3 立体仓库二维平面图
图4 物料货位平面图
图5 物料搬运方向图
1.3 模型建立
简单以二维平面图来分析立体仓库的运动路径。立体仓库的二维平面图如图3所示，图中最底层表示“缓冲层”货位，缓冲层之上为立体仓库摆放物料的货位。假定某次生产任务中物料在如图4所示货位平面图中，其中斜线方框表示该货位有物料，其余方框表示该货位没有物料；图5为物料搬运方向图，图中箭头表示货位上的物料搬运方向。某物料Mm（i,j,k）经立体仓库垛机搬运至缓冲层Dm（p,q）的时间记为Tm，即单次搬运时间，等于物料所在货位与缓冲层目标货位之间的水平与垂直运动时间的最大值，
2 、算法选用及改进
2.1 算法选用
由简记的目标函数可以看出，为优化目标函数，尽量使得总运行时间最小，其实质是最小化|p-j|与|q-k|的值，即优化垛机的运动路径。剥离出运动路径中的M系列值与D系列的值，不难发现M系列的值类似TSP问题中的城市，D系列的值看作是两“城市”间必须经过的某个“加油站”，故此类立体仓库的垛机路径优化问题属于NP-hard问题。
由于NP-hard问题的大量实例不能用精确算法求解，即便用目前的高级计算机来穷举精确算法的结果，也非常耗时，故只能用有效的近似算法求解。而遗传算法只需要影响搜索方向的目标函数和相应的适应度函数，就能在搜索域内找出近优解。
2.2 算法改进策略
传统的遗传算法（Genetic Algorithms, GA）通过“交叉→变异→新种群→选择”来进行。通常情况下，传统的遗传算法只是被看作单个染色体，而且染色体上的遗传基因采用相同的遗传算子。
根据基因遗传学，显性基因在父代的等位基因完成交叉后，受其影响的表现型必然是显性的表现型，如人类血型A/B型为显性，O型为隐性。本文创新性地提出在单染色体的多段基因上，将显性基因与隐性基因加以区别。将总路径中D系列的值作为显性基因，M系列的值作为隐性基因，那么“显性基因”在经过交叉遗传时不至于因为相同的遗传算子而导致早熟（陷入局部最优的困境），“隐性基因”在逐代优化后就趋于稳定。经过N代遗传后，子代始终具备“显性基因”的表现型以及将这种“显性基因”遗传给下一代的能力。
2.2.1 普通基因的交叉算子与显性基因的交叉算子
普通基因的交叉算子：在父代染色体上的普通基因段通过简单的等位基因交叉互换原则，形成子代染色体上的普通基因段。例如将D系列的值按照从右到左（或从左到右）的顺序作为普通基因的交叉算子。显性基因的交叉算子：在父代染色体上的显性基因段经过重排列等处理，选出该段基因中最优的基因表达式，遗传给子代，其显性基因段在整个染色体上的位置段不变，这样在子代中就会有更加优质的个体。例如将D系列的值优化顺序作为显性基因的交叉算子。
2.2.2 普通基因的变异算子与显性基因的变异算子
普通基因的变异算子：遗传中的基因变异是以某种概率发生的，假定普通遗传基因发生变异的可能性为pm。普通基因的变异算子为在整个染色体上的位置出现个别基因段对调现象。
显性基因的变异算子：类似普通基因的变异算子，只是这种变异发生在显性基因段。在整个染色体上表现为显性基因段的个别基因对调现象。
2.2.3 形成新的种群
父代染色体经过交叉和变异后，会形成新的完整染色体。而新的染色体会更适应实际工程中的目标优化函数，经过N代遗传后，子代染色体基因顺序趋于某一确定的顺序，这个最终稳定的染色体就是前面目标优化函数的最优解或近优解。
2.2.4 选择
根据适应度来选择优劣的个体。适应度的表达式可以根据优化目标中的约束条件来自定义，如果违背了约束条件则其适应度就为0，该个体即被淘汰。如果能很好地满足优化目标的条件，则适应度高，子代个体也就越优质。
适应度函数：
2.3 改进后的遗传算法步骤
Step 1: 按照生产订单生成任务种群，迭代次数自定义；Step 2: 按照种群规模，随机生成种群的染色体集；Step 3: 进入迭代循环；Step 4: 在每代中计算各个体的适应度值，当适应度值高于平均值的时候，就评为优秀个体，有进行遗传子代的资格；Step 5: 进行交叉、变异、选择；Step 6：是否满足终止条件。
3 、模拟仿真结果对比
3.1 实例描述
根据假定条件和符号的定义，参考立体仓库垛机的物理属性，设定“计算符号”这节第三点的各符号值，通过VS程序模拟传统遗传算法（Traditional GA）和改进后的遗传算法（Improved GA），算出固定种群100个、随机种群100个、随机种群200个、随机种群300个、随机种群400个经过这两种遗传算法优化后，立体仓库垛机的总运行时间。
3.2 普通遗传结果与改进后的遗传算法结果
其三维柱状图如图6所示。
图6 三维树状图
3.3 对比说明
表1 各种群10次优化前后结果的平均值
固定初始化种群，就好像是某次生产任务里包含立体仓库中M个物料，即种群大小为M，在立体仓库货位是固定的。普通遗传算法优化后立体仓库中垛机的运动路径为:（1,2）（0,1）（1,3）（0,2）...（1,58）（0,34）（2,1）（0,35）...（2,49）（0,59）（2,51）（0,1）...（7,58）（0,41）。改进的遗传算法优化后立体仓库中垛机的运动路径为 :（1,2）（0,2）（1,3）（0,3）...（1,58）（0,58）（2,1）（0,1）...（2,49）（0,59）（2,51）（0,51）...（7,58）（0,58）。经过“显性基因”的持续优化后，其运动路径大为减少，垛机的效率大幅提高，从而整条柔性生产线的生产效率也得到提高。随着种群大小增加，改进的遗传算法的优化效果更加明显。
4、 结 语
本文考虑到该类特殊化构造的立体仓库的特点，创新性地提出了基于缓冲策略的“显性基因”持续优化并遗传给子代的遗传算法，经过N代遗传后，“显性基因”将突出目标函数“带出”局部最优的困境。改进后的遗传算法重点解决了立体仓库垛机的路径优化问题，并通过与普通遗传算法对比，验证了该算法对垛机的路径优化有显著的改善效果。立体仓库及整条柔性生产线的工作效率均得到大幅度的提高。
结合本文研究结果，下一步的研究工作：1）如果柔性生产线上的物料均在立体仓库中周转，即加工中心加工完物料后，物料放回立体仓库中，那么在该类特殊化构造的立体仓库中的“缓冲层”需要预留出回库的货位；2）加入“创新基因”，在求解工程问题上，通过训练学习过程，让机器人等智能设备具备自定义的“创新能力”———发现求解过程中出现的特殊解、异常解等，并能智能规避、解决这些问题。
投稿箱：
如果您有机床行业、企业相关新闻稿件发表，或进行资讯合作，欢迎联系本网编辑部， 邮箱：skjcsc@vip.sina.com
如果您有机床行业、企业相关新闻稿件发表，或进行资讯合作，欢迎联系本网编辑部， 邮箱：skjcsc@vip.sina.com
更多相关信息
