摘要

智能仓储的优化一般分为货架优化和路径优化两部分.货架优化针对货物与货架两者的关系,对货物摆放位置进行优化;而路径优化主要寻找自动引导小车（Automated Guided Vehicle,AGV）的最优路径规划.目前,大多的智能仓储优化仅对这两部分进行独立研究,在实际仓储应用中只能以线性叠加的方式解决问题，在实际仓储应用中只能以线性叠加的方式解决问题,导致问题的求解易陷入局部最优中.本文通过对智能仓储环节中各部分的关系进行耦合分析，本文通过对智能仓储环节中各部分的关系进行耦合分析,提出了货位和AGV路径协同优化数学模型,将货架优化和路径规划归为一个整体;此外,提出了智能仓储协同优化框架的求解算法,包括货品相似度求解算法和改进的路径规划算法;并在以上两种算法的基础上,使用改进的遗传算法,实现了货位路径协同优化.实验结果验证了本文提出的智能仓储协同优化算法的有效性和稳定性.通过使用该算法可有效提高仓储的出货效率,降低运输成本.

1 概述

智能仓储系统是由立体货架、有轨巷道堆垛机、出入库输送系统、信息识别系统、自动控制系统、计算机监控系统、计算机管理系统等其他辅助设备组成的智能化系统.智能仓储的高度信息化、自动化使得控制优化算法成为了智能仓储的灵魂所在[1].目前,智能仓储优化算法主要集中在货架优化和AGV车路径规划这两部分,且关于这两部分的研究都是各自独立的.货架优化是针对货物与货架两者的关系,对货物摆放位置的优化,其重点关注于总体出货代价、货架稳定性等因素[2].而路径优化主要针对于自动化运载车辆的路径规划的优化,要关注的重点在于完成任务的时间开销最小、避免车辆之间发生碰撞等.然而,基于对实际仓储的运维数据分析,我们发现传统的独立的智能仓储优化策略,即研究货架优化时只专注于货架摆放最优结果,研究路径规划时只关注于算法的执行效率和优化成果,完全忽视了货架规划和路径规划两者间的耦合关系,严重影响了智能仓储的出货效率最大化[3][4][5].因此,本文提出了基于遗传算法的货位规划与AGV路径规划协同优化算法（以下简称货位路径协同优化算法）.该协同优化算法改进了经典遗传算法,其创新点在于将货位规划和路径规划协同考虑后,构造的适应性函数能够将相似度高的货架分散放置,将高频出库货物放置在易于出货的位置上,从而实现在大量同时出库任务到来时AGV调度不堵塞,从整体上提高仓库出货效率.

本文主要创新贡献如下：
（1）本文通过对智能仓储环节中各部分的关系进行耦合分析,进而提出货位和AGV路径协同优化的数学模型.该模型与传统智能仓储优化算法的区别在于,将货架优化和路径规划归为一个整体并用数学公式表达两者间的关系.
（2）提出了智能仓储协同优化的求解算法,其中包括有货品相似度求解算法,改进的路径规划算法.在以上两种算法的基础上,使用改进适应性函数的遗传算法,实现了货位路径协同优化.同时,通过实验验证了该协同优化算法在不同场景下的表现情况.

2 国内外研究现状

本文研究的智能仓储货位与路径协同优化算法相关的公开文献资料很少,大多都是以货架优化和AGV路径规划独立研究为主.本文将分别就这两类问题分析国内外研究现状以及存在的相关问题.除此之外,对本文提出的协同优化算法的协同优化思想起源以及应用实例给予简要介绍.

2.1 智能仓储货架优化研究现状

货架（货位）优化研究是智能仓储领域的重要研究方向.货架优化就是计算货物摆放位置的算法,货架优化的目标是在保证仓储环境稳定的条件下,提高仓库的出入库效率,同时,优化货架空间,使仓储放入货品的数量最大化.

在国内,由Cai J等人[6]针对仓储策略部分,提出了基于存储的出入库频率和负载平衡的绝对的主通道存储策略,与平均和最大值相关的控制政策,提升了库位使用率.Wang W 等人[7]对传统的遗传算法进行改进,研究出基于遗传算法的库位分配方法.该方法以货品位置坐标为基因,使用权重和的方式来统一多目标函数为一个函数,使其成为适应性函数.通过基因遗传运算,得出优化后的库位摆放方案.刘峰等人[8]使用模糊化这一理念,形成模糊算法,对货品的出货率,重量进行模糊化.但该优化算法每次只计算单个货品的位置摆放,对于一次性全部入库的运算会变得十分复杂.同时,模糊化方式存在使用精确度来换取计算时间的弊端.杨玮等人[9] 基于混合粒子群算法采用多色集合概念对货位进行分区,对不同对象使用相同形式的数学模型进行仿真.该算法的优点在于没有交叉变异,需要调整的参数较少.其缺点在于因缺乏动态调节,存在陷入局部最优的可能.

在国外,Tinelli 等人[10]使用多标准工具来优化智能仓储货位分配,应用层次分析法,以目标按照一定方式分成不同的标准,标准间相互组合形成不同的解,即对不同的目标函数进行求解并组合.Arnaout J P等人[11]用蠕虫优化来解决多层仓库库位布局问题.蠕虫类似于群体智能算法,使用连接图的方式来表现,通过迭代,限界来搜寻最优解.在 Arnaout J P描绘的特定仓储算例中,和基本遗传算法相比,基于蠕虫算法的仓储布局算法计算时间较短.

基于对上述国内外研究现状的分析,可以看出,库位优化问题是一个NP难问题,目标函数较多,目前解决方法主要是来自于自启发算法的各类变种算法,这也是解决NP难问题的常规方式.但是,多数方法的优化思路都集中在根据物品和货架的关系来进行货位优化,忽略了出货路径对货位摆放优化的影响.

2.2 自动导引车路径规划研究现状

AGV(Automated Guided Vehicle,自动导引车)是智能仓储的重要组成部分,在仓储系统中主要扮演智能物流搬运的角色,配合任务分配和调度系统实现物品的智能配送、周转、出入库等操作[12].现阶段针对AGV的优化算法主要分为两个方面,一方面是对路径进行优化,另一方面是针对AGV的任务调度进行优化.虽然侧重点不同,但其目标都在于提高AGV的使用效率.

在国内,Zhang B等人[13]在A*算法的基础上,加入AGV转弯次数影响因素,通过减少AGV的转弯次数,降低AGV转弯的时间消耗,有效的提高了AGV的使用效率.但算法忽略了AGV的冲突问题.姜康等人[14]研究了改进的遗传算法,在基因片段里,以三元为一组,整个任务序列为全部任务.对此基因段进行交叉、变异,通过适应度函数进行筛选.由于该算法每次都会计算全部的任务序列,频繁的新任务添加会大大增加此算法的计算次数.同时,该方法也忽略了小车的碰撞以及充电对调度带来的影响.张素云等人[15]在解决AGV冲突方面展开研究,提出了通过加减速控制AGV的碰撞避免方法.该方法先预估哪些节点会产生碰撞,在该节点部分使用加减速控制,以此来避免冲撞.在实际运行中,该算法需进一步考虑AGV承重、重心高低等因素对加减速幅度的影响.

在国外,Ümit Bilge 等人[16]使用时间窗法解决行驶冲突,对所有AGV的行动进行预估,可以预知所有车辆在不同时段所占用的不同路段,以此避免AGV车辆的碰撞.Mousavi M 等人[17]采用混合遗传算法和粒子群算法优化多目标AGV调度.该算法在初期选用粒子群算法,在粒子进行移动后,更新粒子位置找到最佳粒子位置,再使用遗传算法对粒子的位置进行再优化,而后再回到粒子群算法中进行下一次粒子移动计算,直到收敛.此算法在收敛速度方面与遗传算法相近,最终结果优于单独使用遗传算法或粒子群算法.其缺点在于混合算法计算耗时较长.