Dynamic path planning method considering load balancing of road network for AGV sorting system
Article Text (Baidu Translation)
-
摘要: 为解决大规模自动化分拣系统中自动导引车(AGV)的路径规划和路网拥堵问题，考虑路网负载均衡性和利用率，提出了一种基于滑动时间窗的任务级全局规划与动作级局部调整相结合的路径规划框架；设计考虑了转弯次数的多终点A*(A*-Ⅰ)算法，以规划进入系统的AGV的全局路径；基于滑动时间窗框架更新系统内运行中的AGV位置信息，帮助其进行动作选择以避免路径冲突；通过每隔一定周期计算路网各路段的平均通行速度，更新路网各区域的路阻因子矩阵，在A*-Ⅰ算法基础上设计了考虑路阻因子的A*-Ⅱ算法，用于调整AGV的局部路径；通过结合A*-Ⅰ和A*-Ⅱ算法，实现自动化分拣系统中多AGV的无冲突路径规划，并提高了分拣系统路网均衡性和利用率；基于元胞自动机方法，确定了系统内AGV运行和状态更新规则，构建了一种大规模AGV分拣系统仿真框架。研究结果表明：所提出的路径规划方法相较于传统的全局路径规划方法，路网高负载节点负载量占比下降17%，整体路网负载标准差下降6.7%，有效提高单位时段的商品分拣数量；路阻因子权重和路网状态更新周期是影响系统作业效率的主要因素，当路阻因子权重大于4、路网状态更新周期取5个时间步时系统分拣效率最佳。所提方法能够有效缓解大规模AGV分拣系统的路网拥堵，提升系统吞吐量与运行稳定性，可为智能仓储与自动化分拣场景下的实时路径调度提供可行技术方案。Abstract: To solve the path planning and road network congestion problems of automated guided vehicles (AGVs) in large-scale automatic sorting systems, by considering the load balancing and utilization rate of the road network, a path planning framework based on a sliding time window that integrated task-level global planning and action-level local adjustment was proposed. A multi-endpoint A* (A*-Ⅰ) algorithm considering the number of turns was designed to plan the global paths of AGVs entering the system. Based on the sliding time window framework, the position information of running AGVs in the system was updated to help them select actions to avoid path conflicts. By calculating the average passing speed of each road section in the road network every certain period, the road resistance factor matrix of each region in the road network was updated, and an A*-Ⅱ algorithm considering the road resistance factor was designed based on the A*-Ⅰ algorithm to adjust the local paths of AGVs. By combining the A*-Ⅰ and A*-Ⅱ algorithms, the conflict-free path planning of multiple AGVs in the automatic sorting system was realized, and the road network balancing and utilization rate of the sorting system were improved. Based on the cellular automata method, the operation and status update rules of AGVs in the system were determined, and a simulation framework for a large-scale AGV sorting system was constructed. Research results indicate that compared with the traditional global path planning method, the proposed path planning method reduces the load ratio of high-load nodes in the road network by 17% and the standard deviation of the overall road network load by 6.7%, effectively increasing the sorting quantity of goods per unit time. The road resistance factor weight and the road network status update cycle are the main factors affecting the system operation efficiency, and the system sorting efficiency is the best when road resistance factor weight is greater than 4, and road network status update cycle takes five time steps. The proposed method can effectively alleviate the road network congestion of large-scale AGV sorting systems, improve the system throughput and operation stability, and provide a feasible technical scheme for real-time path scheduling in intelligent warehousing and automatic sorting scenarios.
-
表 1 栅格属性编码
Table 1. Grid attribute coding
属性 编码 取货口 3 出口 2 投递口 4 预留区 5 路段 0 负载AGV占用 -1 空载AGV占用 1 
下载: 导出CSV
表 2 路径冲突试验参数
Table 2. Path conflict experimental parameters
AGV编号 开始运行的时间步 入口坐标 投递位置坐标 出口坐标 1 1 (0, 3) (11, 11) (27, 12) 2 3 (27, 22) (14, 11) (27, 9) 3 4 (27, 22) (3, 22) (0, 22)
下载: 导出CSV
表 3 死锁参数
Table 3. Deadlock parameter
AGV编号 当前坐标 投递位置坐标 出口坐标 1 (5, 3) (6, 3) (0, 1) 2 (6, 3) (9, 3) (27, 3) 3 (7, 3) (7, 5) (0, 7) 4 (5, 4) (5, 2) (0, 1) 5 (6, 4) (2, 2) (0, 1) 6 (7, 4) (3, 4) (0, 4) 7 (8, 4) (3, 4) (0, 4) 8 (9, 4) (6, 4) (0, 4) 9 (8, 3) (3, 4) (0, 4) 10 (7, 2) (5, 6) (0, 4)
下载: 导出CSV
表 4 故障试验参数
Table 4. Fault test parameters
AGV编号 当前坐标 投递位置坐标 故障点 出口坐标 1 (0, 0) (9, 12) (14, 12) (27, 12) 2 (27, 13) (14, 11) (27, 9) 3 (27, 10) (9, 10) (0, 10)
下载: 导出CSV
表 5 测试案例仿真参数
Table 5. Actual case simulation parameters
案例编号 AGV数量/veh 任务数量 LR/% LSD/veh SCT/时间步 A* STW-RRP* STW-RRP A* STW-RRP* STW-RRP A* STW-RRP* STW-RRP S1 50 500 7.80 6.13 5.33 13.63 10.56 10.66 489 389 364 S2 60 700 8.72 6.46 5.62 17.70 15.98 10.85 516 406 379 S3 70 900 9.26 7.20 4.72 21.63 17.32 13.26 546 409 383 M1 80 1 300 9.80 7.58 3.48 24.50 19.65 15.84 570 446 417 M2 90 1 400 16.42 7.72 1.84 27.64 23.92 19.80 450 427 M3 100 1 500 16.81 7.96 1.82 27.49 24.27 20.13 453 430 L1 120 1 800 17.51 8.03 1.53 27.35 26.73 21.36 448 424 L3 140 2 000 18.37 8.24 1.24 28.46 27.40 21.58 461 431
下载: 导出CSV
表 6 实际案例仿真参数
Table 6. Actual case simulation parameters
参数 值 系统容量/veh 130 路阻因子权重γ 3 任务数量/件 2 000 路网状态更新周期δ/时间步 5 死锁检测频率π/时间步 5
下载: 导出CSV
表 7 实际案例仿真结果
Table 7. Simulation results of actual cases
算法 LR/% LSD/veh SRL/m STS/时间步 SCT/时间步 A* 18.16 28.60 17 860 15 698 STW-RRP* 7.84 27.63 50 805 37 251 447 STW-RRP 1.14 21.97 51 009 37 346 421
下载: 导出CSV
-
[1] FRAGAPANE G, DE KOSTER R, SGARBOSSA F, et al. Planning and control of autonomous mobile robots for intralogistics: Literature review and research agenda[J]. European Journal of Operational Research, 2021, 294(2): 405-426. doi: 10.1016/j.ejor.2021.01.019 [2] 李昆鹏, 韩雪芳. 智能仓库中多AGV在线任务指派与全局路径规划问题研究[J]. 中国管理科学, 2025, 33(3): 264-276.LI Kun-peng, HAN Xue-fang. Research on online task assignment and global path planning problem of multi-AGV in intelligent warehouses[J]. Chinese Journal of Management Science, 2025, 33(3): 264-276. [3] CAO Y, YANG A, LIU Y, et al. AGV dispatching and bidirectional conflict-free routing problem in automated container terminal[J]. Computers & Industrial Engineering, 2023, 184: 109611. [4] ZHONG M S, YANG Y S, DESSOUKY Y, et al. Multi-AGV scheduling for conflict-free path planning in automated container terminals[J]. Computers & Industrial Engineering, 2020, 142: 106371. [5] 周琛淏, 焦俊玲, 车阿大. 自动化码头AGV无死锁在线路径规划算法[J]. 管理科学学报, 2026, 29(4): 104-117.ZHOU Chen-hao, JIAO Jun-lin, CHE A-da. Deadlock-free online path planning algorithm for AGVs in automated terminals[J]. Journal of Management Sciences in China, 2026, 29(4), 104-117. [6] 黄岩松, 姚锡凡, 景轩, 等. 基于深度Q网络的多起点多终点AGV路径规划[J]. 计算机集成制造系统, 2023, 29(8): 2550-2562.HUANG Yan-song, YAO Xi-fan, JING Xuan, et al. DQN-based AGV path planning for situations with multi-starts and multi-targets[J]. Computer Integrated Manufacturing Systems, 2023, 29(8): 2550-2562. [7] LUO L, ZHAO N, ZHU Y, et al. A* guiding DQN algorithm for automated guided vehicle pathfinding problem of robotic mobile fulfillment systems[J]. Computers & Industrial Engineering, 2023, 178: 109112. [8] WANG K, LIANG W, SHI H G, et al. Driving line-based two-stage path planning in the AGV sorting system[J]. Robotics and Autonomous Systems, 2023, 169: 104505. doi: 10.1016/j.robot.2023.104505 [9] LI S Q, FAN L B, JIA S. A hierarchical solution framework for dynamic and conflict-free AGV scheduling in an automated container terminal[J]. Transportation Research Part C: Emerging Technologies, 2024, 165: 104724. doi: 10.1016/j.trc.2024.104724 [10] 余娜娜, 李铁克, 张文新, 等. 自动分拣仓库中多载量AGV调度与路径规划算法[J]. 计算机集成制造系统, 2024, 30(4): 1458-1471.YU Na-na, LI Tie-ke, ZHANG Wen-xin, et al. Multi-load AGVs scheduling and routing algorithm in automatic sorting warehouse[J]. Computer Integrated Manufacturing Systems, 2024, 30(4): 1458-1471. [11] YANG G P, LI M Y, GAO Q. Multi-automated guided vehicles conflict-free path planning for packaging workshop based on grid time windows[J]. Applied Sciences, 2024, 14(8): 3341. doi: 10.3390/app14083341 [12] 付建林, 张恒志, 张剑, 等. 自动导引车调度优化研究综述[J]. 系统仿真学报, 2020, 32(9): 1664-1675.FU Jian-lin, ZHANG Heng-zhi, ZHANG Jian, et al. Review on AGV scheduling optimization[J]. Journal of System Simulation, 2020, 32(9): 1664-1675. [13] 温惠英, 元昱青, 林译峰. 考虑道路负载均衡的码头多AGV无冲突路径规划[J]. 华南理工大学学报(自然科学版), 2023, 51(10): 1-10.WEN Hui-ying, YUAN Yu-qing, LIN Yi-feng. Conflict-free path planning for multi-AGVs in automated terminals considering road load balancing[J]. Journal of South China University of Technology (Natural Science Edition), 2023, 51(10): 1-10. [14] 袁洋, 叶峰, 赖乙宗, 等. 结合负载均衡与A*算法的多AGV路径规划[J]. 计算机工程与应用, 2020, 56(5): 251-256.YUAN Yang, YE Feng, LAI Yi-zong, et al. Multi-AGV path planning combined with load balancing and A* algorithm[J]. Computer Engineering and Applications, 2020, 56(5): 251-256. [15] 张丹露, 孙小勇, 傅顺, 等. 智能仓库中的多机器人协同路径规划方法[J]. 计算机集成制造系统, 2018, 24(2): 410-418.ZHANG Dan-lu, SUN Xiao-yong, FU Shun, et al. Cooperative path planning in multi-robots for intelligent warehouse[J]. Computer Integrated Manufacturing Systems, 2018, 24(2): 410-418. [16] FRANSEN K J C, VAN EEKELEN J A W M, POGROMSKY A, et al. A dynamic path planning approach for dense, large, grid-based automated guided vehicle systems[J]. Computers & Operations Research, 2020, 123: 105046. [17] FRANSEN K, VAN EEKELEN J. Efficient path planning for automated guided vehicles using A* (astar) algorithm incorporating turning costs in search heuristic[J]. International Journal of Production Research, 2023, 61(3): 707-725. doi: 10.1080/00207543.2021.2015806 [18] SI M, LIU M F, CAO X G, et al. A two-stage robust optimization method for multi-AGV path planning under uncertain disturbances[J]. Control and Decision, 2026. [19] 孙毛毛, 匡兵. 基于时间窗的AGV动态避碰路径规划方法[J]. 计算机应用研究, 2022, 39(1): 54-58.SUN Mao-mao, KUANG Bing. Path planning method for AGV dynamic collision avoidance based on time window[J]. Application Research of Computers, 2022, 39(1): 54-58. [20] LIAN Y D, XIE W, ZHANG L W. A probabilistic time-constrained based heuristic path planning algorithm in warehouse multi-AGV systems[J]. IFAC-PapersOnLine, 2020, 53(2): 2538-2543. doi: 10.1016/j.ifacol.2020.12.293 [21] 官祥锦, 陈娟, 张为民. 基于改进A*算法的多AGV路径规划研究[J]. 航空制造技术, 2023, 66(5): 76-85, 90.GUAN Xiang-jin, CHEN Juan, ZHANG Wei-min. Research on multi-AGV path planning based on improved A* Algorithm[J]. Aeronautical Manufacturing Technology, 2023, 66(5): 76-85, 90. [22] 刘春, 彭太平. 大规模AGV的改进时间窗路径规划[J]. 计算机应用研究, 2023, 40(1): 52-56.LIU Chun, PENG Tai-ping. Improved time window path planning for large-scale AGV[J]. Application Research of Computers, 2023, 40(1): 52-56. [23] 赵红星, 王钰捷, 聂江龙, 等. 元胞推演多步决策的交叉口深度强化学习信号连续控制[J]. 交通运输工程学报, 2025, 25(4): 296-310. doi: 10.19818/j.cnki.1671-1637.2025.04.021 ZHAO Hong-xing, WANG Yu-jie, NIE Jiang-long, et al. Deep reinforcement learning signal continuous control of intersection based on cellular deduction multi-step decision mechanism[J]. Journal of Traffic and Transportation Engineering, 2025, 25(4): 296-310. doi: 10.19818/j.cnki.1671-1637.2025.04.021 [24] 黄玮, 胡洋. 考虑交叉口渠化区排队特征的元胞传输模型[J]. 交通运输工程学报, 2023, 23(2): 212-224. doi: 10.19818/j.cnki.1671-1637.2023.02.015HUANG Wei, HU Yang. Cell transmission model considering queuing characteristics of channelized zone at intersections[J]. Journal of Traffic and Transportation Engineering, 2023, 23(2): 212-224. doi: 10.19818/j.cnki.1671-1637.2023.02.015 -
图(15) / 表(7)
计量
- 文章访问数: 8
- HTML全文浏览量: 11
- PDF下载量: 2
- 被引次数: 0
