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

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

通过相似度算法获取
开始
货品组相关信息

通过路径规划算法获取
货架最佳出库路径

对货架的摆放方式进行
编码并生成初始种群

结束 根据fit= *Best_path+ *Related_path
计算适应度

是否达到 使用锦标赛法
获取最佳适应值的解
是 最大遗传代数 否 选择算子

更新种群并计算适应度
保留最佳适应值的解 交叉操作
当前代数加一
1
是
解是否
对解进行修复 变异操作
否 完整

Fig.2 Flowchart of proposed shelf and AGV path coopeartive optimization algorithm
图 2 货位规划与路径规划协同优化算法流程图

货位路径协同优化的第 2 步为计算每个应摆放货架的位置.基于上文给出的路径规划算法,我们计算从该
位置单独出货时的最佳出货路径,以获得每个可能摆放货架的位置和其出库的最佳路径,即最快出库方式.在获
取并记录了各个货架位置的最佳出库路径后,开始对货架位置进行综合运算.
货位路径协同优化算法的求解算法基于遗传算法设计,首先对遗传算法进行编码.根据需要解决的问题,需
要把未入库的货架,摆放到货架位置上,需要计算的是货架如何入库的问题.在编码上,选用排列编码即可.在排
列上,选取货架位置作为空位,将未入库货架放入其中.例如,[5,4,2,3,1]意为将 5 号未入库货架放入 1 号货架位,
将 4 号未入库货架放入 2 号货架位,以此类推.完成编码的选择和实现后,即可以生成初始种群.初始种群的建立
是生成一组随机数,随机数区间在未入库货架号区间范围内.具体实现为:先获取所有未入库的货架号放入集合
A;再生成随机数,将其放入到个体的基因中记为集合 B.此时,该货架号从之前的集合 A 除去,防止再次选中.经过
不断的生成,直到取完集合 A 中所有数.在随机生成的种群中,考虑个体重合问题,使用生成新的个体来替代重合
个体,直到该种群中个体的数量满足设定的值.完成初始种群的生成后,计算该种群中个体的适应值.适应值 fit
的计算方式如公式(9)所示:
⎛ N ⎞
fit = f × ⎜ α Bestpath β × + × ∑ Relatpath i ⎟ (9)
⎝ i= 1 ⎠
其中,f 是该货架的出入库频率,此参数可以放大整体适应度,使出库频率影响到货架摆放位置;Bestpath 为当前
N
货架出库的最佳路径; ∑ Relatpath 为与所有当前货架相似度较高的货架的出库路径重合量的和,该参数可用
i
i= 1
来降低冲突发生的情况,将避免冲突考虑到货架排放中;α和β为权重系数,在满足α+β=1 的约束下,调节两个参