(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111454010.9 (22)申请日 2021.12.01 (71)申请人 合肥工业大 学智能制造技 术研究院 地址 230051 安徽省合肥市包河区花园大 道369号 (72)发明人 胡小建　杨智　袁丁　黄亚领　 (74)专利代理 机构 北京润平知识产权代理有限 公司 11283 代理人 肖冰滨　刘兵 (51)Int.Cl. G06N 3/00(2006.01) G06Q 10/04(2012.01) G06Q 10/08(2012.01) (54)发明名称 基于双混合粒子群的多AGV路径 规划问题优 化方法及系统 (57)摘要 本发明提供一种基于双混合粒子群的多AGV 路径规划问题优化方法及系统， 属于仓库物料搬 运AGV调度技术领域。 双混合粒子群算法基于粒 子群算法与A *算法混合， 并引入遗传算法的交叉 和变异。 所述方法包括： 编码自动化分拣仓库的 货位点序列产生初始的种群； 采用路径生成算法 即A*算法生 成最优路径； 根据最优路径和种群中 的每个个体计算每个个体的停车等待次数； 计算 种群的每个个体的适应度值； 对种群执行交叉和 变异操作； 判断当前是否满足终止条件； 在判断 当前未满足终止条件的情况下， 再次返回执行计 算种群的每个个体的适应度值的步骤， 直到判断 当前满足终止条件； 在判断当前满足终止条件的 情况下， 输出优化后的方案。 该方法及系统能够 提高仓库调度的效率。 权利要求书3页 说明书12页 附图8页 CN 114358233 A 2022.04.15 CN 114358233 A 1.一种基于双混合粒子群的多AGV路径规划问题优化方法， 其特征在于， 所述方法包 括： 编码自动化分拣仓库的货位 点序列以产生初始的种群； 采用预设的路径生成算法即A*算法生成最优路径； 根据所述 最优路径和所述种群中的每 个个体计算每个个体的停车等待次数； 计算所述种群的每 个个体的适应度值； 对所述种群执 行个体最优交叉操作； 对个体最优交叉操作后的所述种群执 行种群最优交叉操作； 对种群最优交叉操作后的所述种群执 行变异操作； 判断当前 是否满足 终止条件； 在判断当前未满足终止条件的情况下， 再次返回执行计算所述种群的每个个体的适应 度值的步骤， 直到判断当前满足 终止条件； 在判断当前满足 终止条件的情况 下， 输出优化后的方案 。 2.根据权利要求1所述的方法， 其特征在于， 编码自动 化分拣仓库的货位和路径以产生 初始的种群包括： 采用数字 0表示AGV小车的停靠区， 采用整数作为待搬运的货位。 3.根据权利要求1所述的方法， 其特 征在于， 所述路径生成算法包括： 确定所有 待行驶点， 其中， 所述待行驶 点包括AGV小车的起 点、 终点或货位 点； 初始化路径集合和待行驶集合， 其中， 所述路径集合包括所述起点， 所述待行驶集合包 括所有货位 点的集合中除所述 起点以外所有的所述待行驶 点； 遍历并计算所述待行驶 集合中的每 个所述待行驶 点的f值； 选择f值最小的所述待行驶 点以作为当前选择点； 将所述当前选择点加入所述路径集 合中； 判断当前选择点是否为所述终点； 在判断当前选择点不为所述终点的情况下， 判断所述待行驶集合是否包含至少一个与 当前选择点相邻的所述待行驶 点； 在判断所述待行驶集合包含至少一个与 所述当前选择点相邻的待行驶点的情况下， 将 与所述当前选择点相邻的所述待行驶 点加入所述路径集 合中； 将与所述当前选择点相邻的待行驶点作为所述当前选择点的子节点， 并根据公式(1) 至(3)计算所述子节点的f值， f(j)＝g(j)+h(j)    (1) g(j)＝g(i)+|xj‑xi|+|yj‑yi|      (2) 其中， f(j)为所述子节点的f值， g(j)为所述子节点距离所述起点的代价值， h(j)为所 述子节点到终点的预计代价值， g(i)为所述父节点距离所述起点的代价值， 所述父节点为 当前选择点， i为所述父节点的编号， u0为终点的编号， j为所述子节点的编号， x为所述待行 驶点的横坐标， y为所述待行驶 点的纵坐标， D为AGV小车每行驶单位距离的代价 值； 在判断所述待行驶集合不包含与 所述当前选择点相邻的待行驶点的情况下， 判断与 所权　利　要　求　书 1/3 页 2 CN 114358233 A 2述当前选择点相邻的待行驶 点的预计代价 值是否均小于上一轮迭代中的预计代价 值； 在判断与所述当前选择点相邻的待行驶点的预计代价值小于上一轮迭代中的预计代 价值的情况下， 将当前选择点作为与所述当前选择点相邻的待行驶点的父节点， 并根据公 式(1)至(3)更新所述父节点的f值、 所述父节点距离所述起点的代价值和所述父节点到终 点的预计代价 值； 再次返回执 行选择f值 最小的所述货位 点的步骤， 直到判断当前选择点 为所述终点； 在判断当前选择点 为所述终点的情况 下， 输出所述路径集 合为所述最优路径。 4.根据权利要求1所述的方法， 其特 征在于， 所述计算每 个个体的适应度值包括： 根据公式(4)及公式(5)计算所述 适应度值， Fitness(i)＝max(t1,t2,…,tk,…,tm)     (4) 其中， t1,t2,…,tk,…,tm分别为编号为1、 2、 …、 k、…、 m的AGV小 车的总运输时间， tk为多 个Tk的和， Tk表示编号 为k的AGV小车AGVk搬运一次货物所需要的时间， 其中， di1表示任务i的第一段曼哈顿距离， 即任 务i的起点到货架之间的曼哈顿距 离， di2 表示任务i的第二段曼哈顿距离， 即货架到拣货台之间的曼哈顿距离， di3表示任务i的第 三 段曼哈顿距离， 即拣货台到终点之间的曼哈顿距离,且di1＝|xs‑xi|+|ys‑yi|， di2＝|xi‑1|+| yi‑yp|， di3＝|1‑xe|+|yp‑ye|， xs为任务i的起点的横坐标， ys为任务i的起点的纵坐标， xi为 任务i的货架的横坐标， yi为任务i的货架的纵坐标， yp为任务i的拣货台的纵坐标， xe为任务 i的终点的横坐标， ye为任务i的终点的纵坐标， xik为用于指示任务i是否由AGV小车AGVk搬 运的指示变量， xik取值为1表示任务i由AGV小车AGVk搬运， 否则取值为0； tw表示AGV小车一 次停车等待时间。 5.根据权利要求1所述的方法， 其特 征在于， 所述个 体最优交叉操作包括： 从所述种群中随机选取一个未被选取的个体与当前种群中适应度最小的个体形成父 代个体； 随机产生两个自然数r1和r2； 交换父代的两个 个体在自然数r1和r2之间的片段； 判断交换后的两个 个体是否均存在重复的货位 点编号； 在判断交换后的两个个体存在重复的货位点编 号的情况下， 取交换片段的补集重新随 机排列到非交换片段 上； 判断所述种群中是否还 存在未被选取的个 体； 在判断所述种群中还存在未被选取的个体的情况下， 再次返回执行从所述种群中随机 选取一个未被选取的个体与当前种群中适应度最小的个体形成父代个体的步骤， 直到判断 所述种群中不存在未被选取的个 体； 在判断所述种群中不存在未被选取的个体的情况下， 输出个体最优交叉操作完成的所 述种群。 6.根据权利要求1所述的方法， 其特 征在于， 所述种群最优交叉操作包括： 从所述种群中随机选取一个未被选取的个体与历史生成的种群中适应度最小的个体权　利　要　求　书 2/3 页 3 CN 114358233 A 3