›› 2020, Vol. 26 ›› Issue (第1): 171-180.DOI: 10.13196/j.cims.2020.01.018

Previous Articles     Next Articles

Multi-AGVs scheduling and path planning algorithm in automated sorting warehouse

  

  • Online:2020-01-31 Published:2020-01-31
  • Supported by:
    Project supported by the National Natural Science Foundation,China(No.71701016,71231001),the Humanity and Social Science Youth Foundation of Ministry of Education,China(No.17YJC630143),the Beijing Municipal Natural Science Foundation,China(No.9174038),and the Fundamental Research Funds for Central Universities,China(No.FRF-BD-17-009A,FRF-BD-16-006A).

自动化分拣仓库中多AGV调度与路径规划算法

余娜娜1,2,李铁克1,2+,王柏琳1,2,袁帅鹏1,2   

  1. 1.北京科技大学东凌经济管理学院
    2.钢铁生产制造执行系统技术教育部工程研究中心
  • 基金资助:
    国家自然科学基金资助项目(71701016,71231001);教育部人文社会科学研究青年基金项目资助(17YJC630143);北京市自然科学基金项目(9174038);中央高校基本科研业务费资助项目(FRF-BD-17-009A,FRF-BD-16-006A)。

Abstract: The automated sorting warehouses are operated by multiple AGVs simultaneously,which can quickly sort a large number of packages.How to determine the handling package sequence for AGVs and plan the conflict-free path is the key to the sorting operation.In order to improve sorting efficiency,aiming at minimizing the maximum handling completion time,firstly,the priority of the conflicting AGVs is defined and a path planning algorithm for generating a conflict-free path is proposed.Furthermore,considering the AGV scheduling and path planning comprehensively,an improved differential evolution algorithm is proposed,the algorithm generates the initial population based on the opposition-based learning,uses adaptive mutation and crossover probabilities to evolve individuals,a dynamic differential evolution strategy is designed to improve the convergence speed,the exchange neighborhood and the insertion neighborhood based on the key AGV are designed for local search.The effectiveness of the algorithm is verified by data experiments,and the key parameters are analyzed.

Key words: automated guided vehicle, automated sorting warehouse, scheduling, path planning, differential evolution algorithm

摘要: 自动化分拣仓库由多自动导引小车(AGV)同时作业,对大量包裹进行快速分拣。如何为AGV确定搬运包裹序列并规划无冲突的路径,是分拣作业的关键所在。为提高分拣效率,以最小化最大搬运完成时间为目标,定义了冲突AGV的优先级,提出一种生成无路径冲突的路径规划算法;进而,综合考虑AGV调度和路径规划,提出一种改进差分进化算法,算法采用反学习方法生成初始种群,运用自适应的变异和交叉概率进行进化操作,设计动态差分进化策略来提高收敛速度,并设计交换邻域和基于关键AGV的插入邻域进行局部搜索。通过数据实验验证了算法的有效性,并对关键问题参数进行了分析。

关键词: 自动导引小车, 自动化分拣仓库, 调度, 路径规划, 差分进化算法

CLC Number: