|
|
|
| Task scheduling optimization for automated guided vehicle based on directed acyclic graph modeling |
Yi HU1,2,3( ),Mengsheng CUI1,2,Xiyang ZHANG1,2,3,Yanqing ZHAO1,2 |
1. Shenyang Institute of Computing Technology, Chinese Academy of Sciences, Shenyang 110168, China
2. School of Computer Science and Technology, University of Chinese Academy of Sciences, Beijing 100049, China
3. Shenyang CASNC Technology Limited Company, Shenyang 110168, China |
|
|
|
Abstract A nested algorithm framework based on the binary particle swarm optimization (BPSO nested framework) was proposed considering multiple task selection strategies to solve the optimal scheduling solution aiming at the issue of optimizing the travel distance for task scheduling of a single-load automated guided vehicle (AGV) between the production line and the warehouse. A dynamic traveling salesman problem model based on directed acyclic graph modeling (DAGDTSP), with the aim of minimizing the total travel distance, was established by considering the task execution sequence constraints and the dynamic changes in task node information in response to environmental variations in order to address the optimal scheduling solution under the fixed task selection strategy. An improved genetic algorithm (IGA) was proposed to solve the model. The experimental results demonstrate that optimal scheduling solutions under the fixed task selection strategy can be effectively solved for AGV task scheduling by employing the IGA algorithm. The BPSO nested framework can improve solution quality, and the optimal scheduling solutions can adapt to task changes to some extent. The DAGDTSP model achieves accuracy on test problems with different environmental parameter settings.
|
|
Received: 02 July 2024
Published: 28 July 2025
|
|
|
| Fund: 国家产业基础再造和制造业高质量发展专项资助项目（2022-232-223-01）. |
有向无环图建模的自动导引车任务调度优化
针对生产线和仓库之间单载自动导引车（AGV）任务调度的行驶距离优化问题，考虑多种任务选择策略，提出基于二进制粒子群优化的嵌套算法框架（BPSO嵌套框架），求解优化调度方案. 针对固定任务选择策略下的优化调度方案求解，考虑任务执行顺序约束和任务节点信息随环境变化，以最小化AGV行驶总距离为目标，建立基于有向无环图建模的动态旅行商问题（DAGDTSP）模型，提出改进遗传算法（IGA）求解模型. 实验结果表明，针对AGV任务调度方案的优化，利用IGA算法，能够有效地求解固定任务选择策略下的优化调度方案. BPSO嵌套框架能够提升求解质量，所求解的优化调度方案能够在一定程度上适应任务变化. DAGDTSP模型在不同环境参数设置的测试问题上具备准确性.
关键词：
任务调度,
行驶总距离,
有向无环图,
遗传算法,
粒子群优化算法
|
|
| [1] |
牛昊一, 吴维敏, 章庭棋, 等 自适应樽海鞘群算法求解考虑运输时间的柔性作业车间调度[J]. 浙江大学学报: 工学版, 2023, 57 (7): 1267- 1277
NIU Haoyi, WU Weimin, ZHANG Tingqi, et al Adaptive salp swarm algorithm for solving flexible job shop scheduling problem with transportation time[J]. Journal of Zhejiang University: Engineering Science, 2023, 57 (7): 1267- 1277
|
|
|
| [2] |
WU Y, ZHU X, FEI J, et al A novel joint optimization method of multi-agent task offloading and resource scheduling for mobile inspection service in smart factory[J]. IEEE Transactions on Vehicular Technology, 2024, 73 (6): 8563- 8575
doi: 10.1109/TVT.2024.3361492
|
|
|
| [3] |
ZHANG Z, WU L, ZHANG W, et al Energy-efficient path planning for a single-load automated guided vehicle in a manufacturing workshop[J]. Computers and Industrial Engineering, 2021, 158: 107397
doi: 10.1016/j.cie.2021.107397
|
|
|
| [4] |
LI Y, HUANG H Efficient task planning for heterogeneous AGVs in warehouses[J]. IEEE Transactions on Intelligent Transportation Systems, 2024, 25 (8): 10005- 10019
doi: 10.1109/TITS.2024.3356514
|
|
|
| [5] |
XIE L, LI H, LUTTMANN L Formulating and solving integrated order batching and routing in multi-depot AGV-assisted mixed-shelves warehouses[J]. European Journal of Operational Research, 2023, 307 (2): 713- 730
doi: 10.1016/j.ejor.2022.08.047
|
|
|
| [6] |
李昆鹏, 刘腾博, 李文莉 改进自适应遗传算法求解“货到人”拣选系统订单分批问题[J]. 机械工程学报, 2023, 59 (4): 308- 317
LI Kunpeng, LIU Tengbo, LI Wenli Improved adaptive genetic algorithm for order batching of “part-to-picker” picking system[J]. Journal of Mechanical Engineering, 2023, 59 (4): 308- 317
doi: 10.3901/JME.2023.04.308
|
|
|
| [7] |
范厚明, 郭振峰, 岳丽君, 等 考虑能耗节约的集装箱码头双小车岸桥与AGV联合配置及调度优化[J]. 自动化学报, 2021, 47 (10): 2412- 2426
FAN Houming, GUO Zhenfeng, YUE Lijun, et al Joint configuration and scheduling optimization of dual-trolley quay crane and AGV for container terminal with considering energy saving[J]. Acta Automatica Sinica, 2021, 47 (10): 2412- 2426
|
|
|
| [8] |
王无印, 黄子钊, 庄子龙, 等 基于深度强化学习的自动化码头堆场场桥调度方法[J]. 机械工程学报, 2024, 60 (6): 44- 57
WANG Wuyin, HUANG Zizhao, ZHUANG Zilong, et al Yard crane scheduling method based on deep reinforcement learning for the automated container terminal[J]. Journal of Mechanical Engineering, 2024, 60 (6): 44- 57
|
|
|
| [9] |
YUE L, FAN H Dynamic scheduling and path planning of automated guided vehicles in automatic container terminal[J]. IEEE/CAA Journal of Automatica Sinica, 2022, 9 (11): 2005- 2019
doi: 10.1109/JAS.2022.105950
|
|
|
| [10] |
SUN P Z H, YOU J, QIU S, et al AGV-based vehicle transportation in automated container terminals: a survey[J]. IEEE Transactions on Intelligent Transportation Systems, 2023, 24 (1): 341- 356
doi: 10.1109/TITS.2022.3215776
|
|
|
| [11] |
WANG Y, LIU X, LENG J, et al Study on scheduling and path planning problems of multi-AGVs based on a heuristic algorithm in intelligent manufacturing workshop[J]. Advances in Production Engineering & Management, 2022, 17 (4): 505- 513
|
|
|
| [12] |
ZACHARIA P T, XIDIAS E K AGV routing and motion planning in a flexible manufacturing system using a fuzzy-based genetic algorithm[J]. The International Journal of Advanced Manufacturing Technology, 2020, 109 (7): 1801- 1813
|
|
|
| [13] |
DE RYCK M, VERSTEYHE M, SHARIATMADAR K Resource management in decentralized industrial automated guided vehicle systems[J]. Journal of Manufacturing Systems, 2020, 54: 204- 214
doi: 10.1016/j.jmsy.2019.11.003
|
|
|
| [14] |
高文文, 胡志华 考虑任务偏序关系的AGV路径优化[J]. 大连海事大学学报, 2019, 45 (4): 45- 54
GAO Wenwen, HU Zhihua AGV routing optimization considering task partial order relation[J]. Journal of Dalian Maritime University, 2019, 45 (4): 45- 54
|
|
|
| [15] |
祁璇, 周通, 王村松, 等 基于改进近端策略优化算法的AGV路径规划与任务调度[J]. 计算机集成制造系统, 2025, 31 (3): 955- 964
QI Xuan, ZHOU Tong, WANG Cunsong, et al AGV path planning and task scheduling based on improved proximal policy optimization algorithm[J]. Computer Integrated Manufacturing Systems, 2025, 31 (3): 955- 964
|
|
|
| [16] |
SLOWIK A, KWASNICKA H Evolutionary algorithms and their applications to engineering problems[J]. Neural Computing and Applications, 2020, 32 (16): 12363- 12379
doi: 10.1007/s00521-020-04832-8
|
|
|
| [17] |
NAYAK J, SWAPNAREKHA H, NAIK B, et al 25 years of particle swarm optimization: flourishing voyage of two decades[J]. Archives of Computational Methods in Engineering, 2022, 30 (3): 1663- 1725
|
|
|
| [18] |
TANG J, LIU G, PAN Q A review on representative swarm intelligence algorithms for solving optimization problems: applications and trends[J]. IEEE/CAA Journal of Automatica Sinica, 2021, 8 (10): 1627- 1643
doi: 10.1109/JAS.2021.1004129
|
|
|
| [19] |
NADIMI-SHAHRAKI M H, ZAMANI H, ASGHARI VARZANEH Z, et al A systematic review of the whale optimization algorithm: theoretical foundation, improvements, and hybridizations[J]. Archives of Computational Methods in Engineering, 2023, 30 (7): 4113- 4159
doi: 10.1007/s11831-023-09928-7
|
|
|
| [20] |
WEI L, ZHANG Z, ZHANG D, et al A simulated annealing algorithm for the capacitated vehicle routing problem with two-dimensional loading constraints[J]. European Journal of Operational Research, 2018, 265 (3): 843- 859
doi: 10.1016/j.ejor.2017.08.035
|
|
|
| [21] |
李国明, 李军华 基于混合禁忌搜索算法的随机车辆路径问题[J]. 控制与决策, 2021, 36 (9): 2161- 2169
LI Guoming, LI Junhua Stochastic vehicle routing problem based on hybrid tabu search algorithm[J]. Control and Decision, 2021, 36 (9): 2161- 2169
|
|
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
| |
Shared |
|
|
|
|
| |
Discussed |
|
|
|
|
