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

蔺一帅 等:智能仓储货位规划与 AGV 路径规划协同优化算法 2773

仓储出库效率的影响.举个简单例子:最优的货架优化可能会带来出货时的 AGV 拥堵,给 AGV 路径规划带来严
重问题,从而影响到仓储出库效率.针对这种现象,本文将对 AGV 路径和货架优化进行集成研究,使用协同优化
的思想将货物、货架、路径三者结合起来,使得在进行货架优化时,除了考虑到货物,也将路径纳入到影响因素
中,从而提高仓储的整体效率,进一步降低仓储成本.

2 货位规划与 AGV 路径规划协同优化算法

现有智能仓储的主要优化方法为采用传统货架优化算法进行货位计算后,执行路径规划算法.这种优化方
法容易导致一定区域内的车辆堵塞问题,大大降低了出货效率.针对这个问题,本文基于协同进化思想的启发,
分析货物、货架、AGV 车路径规划的相互影响关系,提出了货架规划和路径规划协同进化算法,实现货架规划
和 AGV 路径规划协同优化.该协同优化算法基于经典遗传算法上进行改进,其创新点在于将货位规划和路径规
划协同考虑后,构造的适应性函数能够将相似度高的货架分散放置,且高频出库货物放置在易于出货的位置上,
从而实现在大量同时出库任务到来时,AGV 调度不堵塞,从整体上提高仓库出货效率.
具体来说,本文提出的货位规划与 AGV 路径协同优化算法(简称协同优化算法)旨在通过设计合理的货位
摆放,为出货路径的规划提供辅助,使用自启发算法产生一个考虑货位摆放因素的优化运输方案.其详细方案如
下:协同优化算法首先根据历史出货批次对零散货物进行编码处理;利用货物批次产生的编码计算“货品间”相
似度,并因此对零散货物进行组合,生成货品组;每一个货品组为待入库状态,视为一个货架单元,与货位一一对
应.其次,在货品组入库之前,先为每一个货位计算相应的出货路径,记录并保存货架位置对应的出货路径.基于
上述计算结果,算法进入协同优化模块,即货品组放入货位的顺序是自由的,这种随机放置的方案构成协同优化
过程的货位因素;而货品组不同的摆放方案会在出货任务到来时生成不同的运输路线,这种不确定的运输路线
就是优化过程的路径因素;最后,利用遗传算法框架对货位因素编码生成初始种群,计算不同出库方案下适应度
函数的值,在不断迭代的过程中搜寻最优方案,在确定货品组入库摆放的同时确定出库路线.综上,这种包含两
方面因素的迭代寻优过程就是货位-路径协同优化.

2.1 协同优化数学模型
本文通过对智能仓储环节中各部分的关系进行耦合分析,提出了货位路径协同优化的数学模型.该模型与
传统智能仓储优化算法的区别在于:将路径规划和货架优化归为一个整体,并用数学公式表达两者间的关系.具
体变量及变量约束条件描述如下:f(x)为协同优化的总目标函数,f path 为所有任务出库总时间花费,f other 为除 AGV
车辆路径规划外算法其他部分的开销,α和β分别为影响系数,且α+β=1.n 为 AGV 车辆总数.n i 为当前 AGV 车辆
编号, i=1,2,…,n,i∈N.M 为出货任务总数.m i 为当前出货任务编号,i=1,2,…,M,i∈N.G 为货品总数.g i 为当前货品编
号, i=1,2,…,G,i∈N.(i,j)表示当前坐标点位置,i,j∈N,i≤I,j≤J.S 为货架总数.μ为车辆从终点返回起点的惩罚系数.
具体来说,本文协同优化的总体目标如公式(1)表示:
f(X)=αf path +βf other ,α+β=1 (1)
其中,α和β为影响系数:α系数为“路径最短”的权重,关注算法寻找出来的路线最短;β系数为“额外开销”的权重,
关注碰撞、冲突、转弯等额外时间消耗,即关注多个 AGV 选择的运输路径相互之间尽可能不重合,以免发生冲
突等.
当 M>N 时,即任务数大于车辆总数时,车辆从终点返回起点需要一定时间,见公式(2):
f path ∑ = N f m ,n + μ ∑ M f m ,n (2)
M = 1 M N + = 1
当 M≤N 时,即车辆数大于任务数时,每个任务一辆 AGV 车,见公式(3):
N
=
f path ∑ f m ,n (3)
M = 1
f m,n 为某次调度时,车辆运行花费的时间,其中,(i,j)为目标点,f c 为车辆出现堵塞后的等待时间,详见公式(4):