计算机工程与应用 ›› 2023, Vol. 59 ›› Issue (14): 275-284.DOI: 10.3778/j.issn.1002-8331.2204-0097

• 工程与应用 • 上一篇    下一篇

动态优先级策略下快递分拨中心多AGV路径规划

田帅辉,樊略   

  1. 重庆邮电大学 现代邮政学院,重庆 400065
  • 出版日期:2023-07-15 发布日期:2023-07-15

Multi-AGV Path Planning for Express Distribution Center Under Dynamic Priority Strategy

TIAN Shuaihui, FAN Lue   

  1. School of Modern Posts, Chongqing University of Posts and Telecommunications, Chongqing 400065, China
  • Online:2023-07-15 Published:2023-07-15

摘要: 目前快递分拨中心逐渐应用自动引导车(automated guided vehicle,AGV)进行包裹分拣作业,多AGV路径规划和路径冲突是制约分拨中心多AGV系统运行效率的关键问题。为解决上述问题,提出一种先静态后动态的两阶段路径规划方法。在静态路径规划阶段,引入转向惩罚机制对A*算法进行改进,为单个AGV进行静态路径规划,避免出现无意义转向,得到较优初始路径;在动态路径规划阶段,确定快递分拨中心中AGV常见的冲突类型并制定相应的避碰策略,设计动态优先级策略,将AGV剩余电量、是否负载并结合包裹时效性等因素作为指标对AGV发生冲突时的实时优先级进行量化,以此作为AGV等待或进行路径再规划的依据,在每辆AGV生成初始路径之后找到AGV之间的冲突节点,根据动态优先级策略及避碰规则实现多AGV动态无碰撞路径规划。案例分析结果表明,使用动态优先级策略能够有效解决多AGV路径冲突问题,且可以降低总任务完成时间和为避免冲突而额外增加的时间。

关键词: 自动引导车, 路径规划, 改进A*算法, 碰撞类型, 动态优先级

Abstract: At present, automated guided vehicle(AGV) is gradually applied to parcel sorting in the delivery distribution center. Path planning and path collision are key problems restricting the operation efficiency of multi-AGV system in delivery distribution centers. To solve the problem of appeal, this paper proposes a two-stage path planning method. At the stage of static path planning, it improves A* algorithm considering turn penalty to carry out static path planning for a single AGV and obtains a better initial routing without unmeaning turn. At the stage of dynamic path planning, common collision types of AGV system in the express distribution center are firstly determined and corresponding collision avoidance strategies are formulated. Then, dynamic priority strategy quantifies the real-time priority of AGVs when collisions occur by taking AGV’s remaining electricity, load and package timeliness as indicators is designed as the basis for AGVs to wait or replan paths. Dynamic collision-free path planning for multiple AGVs is realized according to dynamic priority strategy and collision avoidance rules, after each AGV’s initial route is generated and collision nodes between AGVs are found. The case analysis results show that the dynamic priority strategy can solve the problem of multiple AGV path conflicts and reduce the total task completion time and the additional time added to avoid conflicts.

Key words: automated guided vehicle(AGV), path planning, improved A* algorithm, collision type, dynamic priority