基于对上述国内外研究现状的分析,可以看出,库位优化问题是一个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调度.该算法在初期选用粒子群算法,在粒子进行移动后,更新粒子位置找到最佳粒子位置,再使用遗传算法对粒子的位置进行再优化,而后再回到粒子群算法中进行下一次粒子移动计算,直到收敛.此算法在收敛速度方面与遗传算法相近,最终结果优于单独使用遗传算法或粒子群算法.其缺点在于混合算法计算耗时较长.

上述国内外研究现状为本文的研究提供了很多值得借鉴的思路,比如遗传算法中的编码方式,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调度不堵塞,从整体上提高仓库出货效率.