上述国内外研究现状为本文的研究提供了很多值得借鉴的思路,比如遗传算法中的编码方式,A*算法中关于AGV转弯会影响效率的提示,时间窗法通过静态规划路径来避免冲突等.同时,分析当前国内外的研究现状不难发现,现有AGV的优化算法中对冲突问题的时间代价没有充分考虑.更重要的是缺少将货架优化和路径规划联系起来进行统一优化的方法.这种忽略货架和路径的内在联系,两者分开优化,仅将两部分各自的最优解的串行组合的方式,很难找到一个全局最优解.
2.3 协同进化算法研究现状
协同进化算法框架的形成较早,是Hillis从自然界捕食、竞争以及共生关系得到启发,于 1990年将这种协同的思想引入到进化算法中[18].Potter 将协同进化算法进行了进一步的研究,提出了合作式协同进化算法[19].此算法主要提出了一个算法框架,将完整的系统根据一定规则分为子系统,以“分而治之”的思想对子系统分别求解,将求解结果与其他子系统互动,达到协同进化的目的.
目前,协同算法在国内主要运用于空间布置,如 Wang[20]、Huo[21]等人在卫星舱的布局问题上使用协同进化的思想,配合相对应的算法较好的解决了空间布局问题.Wang 等人在协同进化的基础上加入散射搜索法,更加贴合卫星舱的特点.而Huo等人则通过使用协同进化遗传算法,取得较好的布局优化结果.梁静等人[22]则通过以协同进化的思想,提出使用粒子群算法来解决高维度问题.
比起具体的解决方案,协同进化更多的是一种解决问题的思想.上述的研究者在以此思想上,结合适合的算法用来解决不同种类的问题,都取得一定成果.因此,结合智能仓储的特点,我们研究团队尝试将该思想引入仓储领域,运用协同进化的思想来对货架优化和路径规划进行集成研究[23].
综合分析上述国内外研究现状,可以看出,关于货架优化和AGV路径规划的相关解决方案和算法的独立研究都有重大进展,而对两问题的集成研究极少.大多数在进行货架优化时根本不考虑路径问题,但其实路径影响最终仓储出库效率.举个简单例子,最优的货架优化可能会带来出货时的AGV拥堵,给AGV路径规划带来严重问题,从而影响到仓储出库效率.针对这种现象,本文将对AGV路径和货架优化进行集成研究,使用协同优化的思想将货物、货架、路径三者结合起来,使得在进行货架优化时考虑到货物的同时也将路径纳入到影响因素中,从而提高仓储的整体效率,进一步降低仓储成本.
3 货位规划与AGV路径规划协同优化算法
现有智能仓储的主要优化方法为采用传统货架优化算法进行货位计算后,执行路径规划算法.这种优化方法容易导致一定区域内的车辆堵塞问题,大大降低了出货效率.针对这个问题,本文基于协同进化思想的启发,分析货物、货架、AGV 车路径规划的相互影响关系,提出了货架规划和路径规划协同进化算法,实现货架规划和AGV 路径规划协同优化.该协同优化算法基于经典遗传算法上进行改进,其创新点在于将货位规划和路径规划协同考虑后,构造的适应性函数能够将相似度高的货架分散放置,且高频出库货物放置在易于出货的位置上,从而实现在大量同时出库任务到来时AGV调度不堵塞,从整体上提高仓库出货效率.
具体来说,本文提出的货位规划与AGV路径协同优化算法（简称协同优化算法）旨在通过设计合理的货位摆放,为出货路径的规划提供辅助,使用自启发算法产生一个考虑货位摆放因素的优化运输方案.其详细方案如下,协同优化算法首先根据历史出货批次对零散货物进行编码处理;利用货物批次产生的编码计算“货品间”相似度,并因此对零散货物进行组合,生成货品组;每一个货品组为待入库状态,视为一个货架单元,与货位一一对应.其次,在货品组入库之前,先为每一个货位计算相应的出货路径,记录并保存货架位置对应的出货路径.基于上述计算结果,算法进入协同优化模块,即货品组放入货位的顺序是自由的,这种随机放置的方案构成协同优化过程的货位因素;而货品组不同的摆放方案会在出货任务到来时生成不同的运输路线,这种不确定的运输路线就是优化过程的路径因素;最后,利用遗传算法框架对货位因素编码生成初始种群,计算不同出库方案下适应度函数的值,在不断迭代的过程中搜寻最优方案,在确定货品组入库摆放的同时确定出库路线.综上,这种包含两方面因素的迭代寻优过程就是货位-路径协同优化.
3.1 协同优化数学模型
本文通过对智能仓储环节中各部分的关系进行耦合分析,提出了货位协同优化的数学模型.该模型与传统智能仓储优化算法的区别在于,将路径规划和货架优化归为一个整体并用数学公式表达两者间的关系.具体变量及变量约束条件描述如下,f(X)为协同优化的总目标函数,fpath为所有任务出库总时间花费,fother为除AGV车辆路径规划外算法其他部分的开销,α和β分别为影响系数,且α + β = 1.N为AGV车辆总数. ni为当前AGV车辆编号,i =1,2……N, i∈N. M为出货任务总数. mi为当前出货任务编号,i =1,2……M, i∈N.G为货品总数. gi为当前货品编号,i =1,2……G, i∈N.（i, j）表示当前坐标点位置,i, j∈N, i <= I, j <= J. S为货架总数.μ为车辆从终点返回起点的惩罚系数. 具体来说,本文协同优化的总体目标如式 3-1 表示：
其中,α和β为影响系数,α系数为“路径最短”的权重,关注算法寻找出来的路线最短,β系统为“额外开销”的权重,关注碰撞、冲突、转弯等额外时间消耗,即关注多个 AGV选择的运输路径相互之间尽可能不重合,以免发生冲突等.
当M>N时,即任务数大于车辆总数时,车辆从终点返回起点需要一定时间,见式 3-2：
当M<=N时,即车辆数大于任务数时,每个任务一辆AGV车,见式 3-3：
fm,n为某一次调度时车辆运行花费时间,其中（i, j）为目标点,fc为车辆出现堵塞后所等待的时间,详见式3-4：
fother主要包括两个部分,一个是物品间相关度计算,用于物品的分类;另外一个就是货架优化算法的时间消耗,此处i +1< G,见式 3-5：
下面我们将从货品相似度算法、多AGV路径规划算法、货位规划和AGV路径规划协同优化算法三部分详细描述本文提出的货位规划与AGV路径规划协同优化算法的实现思路.货品相似度算法和多AGV路径规划算法将为最终的货位路径协同优化算法提供支持.
3.2 货品相似度算法
本文对实际正在运维的仓储货物数据进行处理,清洗去除操作时间、货品名称等无关数据,抽取货品编号（即货品的唯一标示）、批次（同一批次货品可理解为在同一时间内执行出入库）等数据进行数据分析,以0和1标识是该编号货品否在该批次出货,每个货品都是一个由批次数各维度组成的向量.通过余弦相似度算法计算该向量间的相似度,获得货品相似度.具体来说,基于余弦相似度的货品相似度计算方法具体流程如图3-1所示.
图 3-1 货品相似度算法流程图
首先,根据仓储数据信息计算最大出货批次数.将货品的出货信息记录下来,形成向量表.例如1号货物的向量值为[0, 1, 1, 0, 1]分别代表在 2、3、5 批次出货其他货品以此类推.在此基础上累加货品出库总次数,计算出库频率.基于余弦公式（式 3-6）计算两两货物间的余弦值.由于货品和它本身和的余弦值为 1,代表两货物最为相似.因此,我们将货物余弦值减去1再求其绝对值,和1的差值越小证明相似度越高,以这个新的值代表两货物间的相似度,最终会获得一个货品和货品相似的上三角矩阵.根据这个矩阵的值,即可计算出一个货品组.
