Page 151 - 《软件学报》2020年第9期

2772 Journal of Software 软件学报 Vol.31, No.9, September 2020

决多层仓库库位布局问题.蠕虫类似于群体智能算法,使用连接图的方式来表现,通过迭代、限界来搜寻最优解.
在 Arnaout 等人描绘的特定仓储算例中,与基本遗传算法相比,基于蠕虫算法的仓储布局算法计算时间较短.
基于对上述国内外研究现状的分析,可以看出,库位优化问题是一个 NP 难问题,目标函数较多,目前解决方
法主要是来自于自启发算法的各类变种算法,这也是解决 NP 难问题的常规方式.但是,多数方法的优化思路都
集中在根据物品和货架的关系来进行货位优化,忽略了出货路径对货位摆放优化的影响.
1.2 自动导引车路径规划研究现状
AGV(automated guided vehicle,自动导引车)是智能仓储的重要组成部分,在仓储系统中,主要扮演智能物流
搬运的角色,配合任务分配和调度系统实现物品的智能配送、周转、出入库等操作 [12] .现阶段,针对 AGV 的优
化算法主要分为两个方面:一方面是对路径进行优化,另一方面是针对 AGV 的任务调度进行优化.虽然侧重点
不同,但其目标都在于提高 AGV 的使用效率.
Zhang 等人 [13] 在 A*算法的基础上加入 AGV 转弯次数影响因素,通过减少 AGV 的转弯次数,降低 AGV 转
弯的时间消耗,有效地提高了 AGV 的使用效率.但算法忽略了 AGV 的冲突问题.姜康等人 [14] 研究了改进的遗传
算法,在基因片段里,以三元为一组,整个任务序列为全部任务.对此基因段进行交叉、变异,通过适应度函数进行
筛选.由于该算法每次都会计算全部的任务序列,频繁的新任务添加会大大增加此算法的计算次数.同时,该方
法也忽略了小车的碰撞以及充电对调度带来的影响.张素云等人 [15] 在解决 AGV 冲突方面展开研究,提出了通
过加减速控制 AGV 的碰撞避免方法.该方法先预估哪些节点会产生碰撞,在该节点部分使用加减速控制,以此
来避免冲撞.在实际运行中,该算法需进一步考虑 AGV 承重、重心高低等因素对加减速幅度的影响.
Bilge 等人 [16] 使用时间窗法解决行驶冲突,对所有 AGV 的行动进行预估,可以预知所有车辆在不同时段所
占用的不同路段,以此避免 AGV 车辆的碰撞.Mousavi 等人 [17] 采用混合遗传算法和粒子群算法优化多目标 AGV
调度.该算法在初期选用粒子群算法,在粒子进行移动后,更新粒子位置找到最佳粒子位置,再使用遗传算法对
粒子的位置进行再优化,而后再回到粒子群算法中进行下一次粒子移动计算,直到收敛.此算法在收敛速度方面
与遗传算法相近,最终结果优于单独使用遗传算法或粒子群算法.其缺点在于混合算法计算耗时较长.
*
上述国内外研究现状为本文的研究提供了很多值得借鉴的思路,比如遗传算法中的编码方式、A 算法中关
于 AGV 转弯会影响效率的提示、时间窗法通过静态规划路径来避免冲突等.同时,分析当前国内外的研究现状
不难发现:现有 AGV 的优化算法中,对冲突问题的时间代价没有充分考虑.更重要的是,缺少将货架优化和路径
规划联系起来进行统一优化的方法.这种忽略货架和路径的内在联系、两者分开优化、仅将两部分各自的最优
解的串行组合的方式,很难找到一个全局最优解.
1.3 协同进化算法研究现状

协同进化算法框架的形成较早,是 Hillis 从自然界捕食、竞争以及共生关系得到启发,于 1990 年将这种协
同的思想引入到进化算法中 [18] .Potter 将协同进化算法进行了进一步的研究,提出了合作式协同进化算法 [19] .此
算法主要提出了一个算法框架,将完整的系统根据一定规则分为子系统,以“分而治之”的思想对子系统分别求
解,将求解结果与其他子系统互动,达到协同进化的目的.
目前,协同算法在国内主要运用于空间布置,如 Wang 等人 [20] 、Huo 等人 [21] 在卫星舱的布局问题上使用协
同进化的思想,配合相对应的算法,较好地解决了空间布局问题.Wang 等人在协同进化的基础上加入散射搜索
法,更加贴合卫星舱的特点.而 Huo 等人则通过使用协同进化遗传算法,取得较好的布局优化结果.梁静等人 [22]
则通过协同进化的思想,提出使用粒子群算法来解决高维度问题.
比起具体的解决方案,协同进化更多的是一种解决问题的思想.上述的研究者在此思想上,结合适合的算法
用来解决不同种类的问题,都取得一定成果.因此,结合智能仓储的特点,我们研究团队尝试将该思想引入仓储
领域,运用协同进化的思想来对货架优化和路径规划进行集成研究 [23] .
综合分析上述国内外研究现状,可以看出:关于货架优化和 AGV 路径规划的相关解决方案和算法的独立研
究都有重大进展,而对两问题的集成研究极少.大多数在进行货架优化时根本不考虑路径问题,忽略路径对最终