有向无环图建模的自动导引车任务调度优化

doi:10.3785/j.issn.1008-973X.2025.08.015

浙江大学学报(工学版)

2025, Vol. 59

Issue (8): 1680-1688 DOI: 10.3785/j.issn.1008-973X.2025.08.015

计算机技术、控制工程、通信技术

有向无环图建模的自动导引车任务调度优化

胡毅1,2,3(

),崔梦笙1,2,张曦阳1,2,3,赵彦庆1,2

1. 中国科学院沈阳计算技术研究所，辽宁沈阳 110168
2. 中国科学院大学计算机科学与技术学院，北京 100049
3. 沈阳中科数控技术股份有限公司，辽宁沈阳 110168

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

全文: PDF(798 KB) HTML

摘要：

针对生产线和仓库之间单载自动导引车（AGV）任务调度的行驶距离优化问题，考虑多种任务选择策略，提出基于二进制粒子群优化的嵌套算法框架（BPSO嵌套框架），求解优化调度方案. 针对固定任务选择策略下的优化调度方案求解，考虑任务执行顺序约束和任务节点信息随环境变化，以最小化AGV行驶总距离为目标，建立基于有向无环图建模的动态旅行商问题（DAGDTSP）模型，提出改进遗传算法（IGA）求解模型. 实验结果表明，针对AGV任务调度方案的优化，利用IGA算法，能够有效地求解固定任务选择策略下的优化调度方案. BPSO嵌套框架能够提升求解质量，所求解的优化调度方案能够在一定程度上适应任务变化. DAGDTSP模型在不同环境参数设置的测试问题上具备准确性.

关键词： 任务调度; 行驶总距离; 有向无环图; 遗传算法; 粒子群优化算法

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.

Key words: task scheduling total travel distance directed acyclic graph genetic algorithm particle swarm optimization algorithm

收稿日期: 2024-07-02 出版日期: 2025-07-28

TP 278

基金资助: 国家产业基础再造和制造业高质量发展专项资助项目（2022-232-223-01）.

作者简介: 胡毅（1982—），男，研究员，博导，从事智能化数控技术、数字化车间智能管控技术的研究. orcid.org/ 0009-0000-1879-4396. E-mail：huyi@sict.ac.cn

	服务
	把本文推荐给朋友
	加入引用管理器
	E-mail Alert
	作者相关文章
	胡毅
	崔梦笙
	张曦阳
	赵彦庆

引用本文:

胡毅,崔梦笙,张曦阳,赵彦庆. 有向无环图建模的自动导引车任务调度优化[J]. 浙江大学学报(工学版), 2025, 59(8): 1680-1688.

Yi HU,Mengsheng CUI,Xiyang ZHANG,Yanqing ZHAO. Task scheduling optimization for automated guided vehicle based on directed acyclic graph modeling. Journal of ZheJiang University (Engineering Science), 2025, 59(8): 1680-1688.

链接本文:

https://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2025.08.015 或 https://www.zjujournals.com/eng/CN/Y2025/V59/I8/1680

图 1 仓库拓扑图和业务区域的划分

图 2 BPSO嵌套框架的程序执行流程

表 1 基准任务选择策略下IGA与其他7种算法的求解结果

表 2 IGA及其变体（IGA-NS/NC/NM）的求解结果

表 3 BPSO嵌套框架的求解结果

表 4 4种求解策略的优化效果分析

表 5 任务变化后测试问题的优化效果

表 6 不同环境参数下的测试问题优化效果

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

[1]	邢国华,陆勇健,苗鹏勇,陈思锦. 基于改进遗传算法的临时转播塔结构优化设计方法[J]. 浙江大学学报(工学版), 2025, 59(3): 469-479.
[2]	朱云辰,程明骏,郑昕文,岑沛立,郗祥硕,黄杉,华晨,黄海. 基于优化第三代非支配排序遗传算法的城市应急设施模糊选址[J]. 浙江大学学报(工学版), 2024, 58(9): 1832-1843.
[3]	薛雅丽,李寒雁,欧阳权,崔闪,洪君. 战场环境下遗传黏菌算法的多机协同任务分配[J]. 浙江大学学报(工学版), 2024, 58(8): 1748-1756.
[4]	赵杰,刘锋,夏灵,范一峰. 基于遗传算法-序列二次规划的磁共振被动匀场优化方法[J]. 浙江大学学报(工学版), 2024, 58(6): 1305-1314.
[5]	李立峰,侯坤,邹德强,彭浩,李凌霄. 中等跨径钢板组合梁截面布置优化[J]. 浙江大学学报(工学版), 2024, 58(3): 510-517.
[6]	陈丽芳,杨火根,陈智超,杨杰. B样条技术与遗传算法融合的全局路径规划[J]. 浙江大学学报(工学版), 2024, 58(12): 2520-2530.
[7]	吴越安,杜昌平,杨睿,俞佳浩,方天睿,郑耀. 基于改进遗传算法的倾转旋翼无人机区域覆盖路径规划[J]. 浙江大学学报(工学版), 2024, 58(10): 2031-2039.
[8]	郑好,曹弋,王珊. 考虑站点换乘的地铁多车站接运公交线路优化[J]. 浙江大学学报(工学版), 2024, 58(10): 2162-2170.
[9]	刘鹏,路庆昌,秦汉,崔欣. 道路网络多阶段抗灾能力优化模型构建与应用[J]. 浙江大学学报(工学版), 2024, 58(1): 96-108.
[10]	汤雪扬,蔡小培,王伟华,常文浩,王启好. 基于粒子概率神经网络算法的钢轨波磨识别[J]. 浙江大学学报(工学版), 2023, 57(9): 1766-1774.
[11]	李煌,葛红娟,马莹,王永帅. 基于超平面NSGA-II的双输入双降压逆变器系统参数优化设计[J]. 浙江大学学报(工学版), 2023, 57(3): 606-615.
[12]	许丽丽,詹燕,鲁建厦,郎一丁. 四向穿梭车仓储系统复合作业调度优化[J]. 浙江大学学报(工学版), 2023, 57(11): 2188-2199.
[13]	查浩,费少华,傅云,吕震,朱伟东. 基于EtherCAT总线的六维力传感器在线解耦技术[J]. 浙江大学学报(工学版), 2023, 57(10): 2042-2050.
[14]	赵永胜,李瑞祥,牛娜娜,赵志勇. 数字孪生驱动的机身形状控制方法[J]. 浙江大学学报(工学版), 2022, 56(7): 1457-1463.
[15]	孙宝凤,张新康,李根道,刘娇娇. 第II类机器人混流装配线的平衡与排序联合决策[J]. 浙江大学学报(工学版), 2022, 56(6): 1097-1106.

Viewed

Full text

Abstract

Cited

Shared

Discussed