Computer Engineering and Applications ›› 2020, Vol. 56 ›› Issue (5): 251-256.DOI: 10.3778/j.issn.1002-8331.1910-0293

Previous Articles     Next Articles

Multi-AGV Path Planning Combined with Load Balancing and A* Algorithm

YUAN Yang, YE Feng, LAI Yizong, ZHAO Yuting   

  1. School of Mechanical and Automotive Engineering, South China University of Technology, Guangzhou 510000, China
  • Online:2020-03-01 Published:2020-03-06

结合负载均衡与A*算法的多AGV路径规划

袁洋,叶峰,赖乙宗,赵雨亭   

  1. 华南理工大学 机械与汽车工程学院,广州 510000

Abstract:

In this paper, the local congestion prevention and load balancing problems of multi-AGV running road networks in large-scale application scenarios are proposed. The path planning method using A* algorithm with improved load balancing is proposed. When calculating the operating cost of the AGV, the traditional A* algorithm is considered to consider only the evaluation function of a single running distance, and the way of running distance combined with the regional load as a new evaluation function is introduced. The area load balancing of the AGV running road network is realized under the premise of not increasing the running distance. The one-way multi-input and multi-out and two-way multi-input and multi-outlet network models are used for simulation verification. The road network scale and load factor are changed for multiple simulation experiments. The results show that the improved algorithm can effectively balance the road network load and greatly improve the AGV overall operating efficiency of the system.

Key words: load balancing, A* algorithm, multiple AGV, path planning, congestion prevention

摘要:

针对目前大规模应用场景下多AGV运行路网的局部拥塞防止和负载均衡问题,提出了使用负载均衡改进的A*算法进行路径规划的方法。在计算AGV运行代价时,摒弃了传统A*算法只考虑单一运行路程的评价函数,引入了运行路程结合区域负载作为新评价函数的方式。在几乎不增大运行路程的前提下,实现了AGV运行路网的区域负载均衡。采用了单向多入多出以及双向多入多出路网模型进行仿真验证,改变路网规模以及负载系数进行多次仿真实验,结果表明改进算法可以有效地均衡路网负载,极大提高了AGV系统整体运行效率。

关键词: 负载均衡, A*算法, 多AGV, 路径规划, 拥堵防止