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

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

d
f mn . = ( + f i + f I − j + f J −i j ) + f f c (4)
v
f other 主要包括两个部分:一个是物品间相关度计算,用于物品的分类;另外一个就是货架优化算法的时间消
耗,此处 i+1<G,见公式(5):
G G
=
f other ∑∑ f , i g g + f s (5)
i= 1 j i = + 1 j
下面我们将从货品相似度算法、多 AGV 路径规划算法、货位规划和 AGV 路径规划协同优化算法这 3 部
分详细描述本文提出的货位规划与 AGV 路径规划协同优化算法的实现思路.货品相似度算法和多 AGV 路径
规划算法将为最终的货位路径协同优化算法提供支持.
2.2 货品相似度算法
本文对实际正在运维的仓储货物数据进行处理,清洗去除操作时间、货品名称等无关数据,抽取货品编号
(即货品的唯一标示)、批次(同一批次货品可理解为在同一时间内执行出入库)等数据进行数据分析,以 0 和 1
标识是该编号货品否在该批次出货,每个货品都是一个由批次数各维度组成的向量.通过余弦相似度算法计算
该向量间的相似度,获得货品相似度.具体来说,基于余弦相似度的货品相似度计算方法具体流程如图 1 所示.

计算货品 计算两两货品
开始 出货次数向量 间的相似度

抽象仓储 统计各货品 根据货架
数据信息 出货批次 容量分组

将货品和
统计关键值 结束
批次列成矩阵

Fig.1 Flowchart of proposed product similarity solving algorithm
图 1 货品相似度算法流程图

首先,根据仓储数据信息计算最大出货批次数.将货品的出货信息记录下来,形成向量表.例如,1 号货物的向
量值为[0,1,1,0,1],分别代表在 2 批次、3 批次、5 批次出货,其他货品以此类推.在此基础上累加货品出库总次数,
计算出库频率.基于余弦公式(公式(6))计算两两货物间的余弦值:
∑ n x * y
cos( , ) = i= 1 i i (6)
xy
∑ i= n 1 i 2 * ∑ n i= 1 y i 2
x
由于货品和它本身和的余弦值为 1,代表两货物最为相似.因此,我们将货物余弦值减去 1 再求其绝对值,和
1 的差值越小,证明相似度越高.以这个新的值代表两货物间的相似度,最终会获得一个货品和货品相似的上三
角矩阵.根据这个矩阵的值,即可计算出一个货品组.
2.3 路径规划算法

基于对遗传算法的改进,本文设计的基于遗传算法的多 AGV 路径规划算法,将路径长度、转弯数加入适应
度函数,即转弯次数越少,路径总长越短,该个体越优秀.同时,采用改进的静态地图法来解决多 AGV 路径冲突问
题.路径的规划是货位路径协同优化的基础,是本文的重要内容之一,主要使用遗传算法执行规划路径的操作,
其伪代码如下所示.
输入:地图信息、起点、终点;
输出:规划完成的路径点集合.
1. funcation GA_path(Map,start,end)
2. P k ←init(⋅) /*初始化种群*/
3. k←0 /*初始化遗传代数*/