不确定情景下AGV系统调度算法的仿真平台

doi:10.16182/j.issn1004731x.joss.22-1214

摘要/Abstract

摘要：

不确定情境下的完整自动引导车(automated guided vehicle，AGV)系统调度算法，除了要包含常见的任务指派策略和路径规划算法之外，还需要包含冲突应对策略。由于存在随机性，这样的调度算法难以从理论上分析其特性，相关研究也较少。基于离散事件仿真技术，设计并开发了一个AGV系统仿真平台，可以灵活地设置调度问题，并选择调度算法中的任务指派策略、路径规划算法和路径冲突应对策略进行仿真。该平台具有可视化的界面，可以直观地观察AGV的运行状态和调度算法的表现，也可以输出最终的仿真实验统计数据。实验表明：该平台可以准确有效地对不确定情景下的调度算法进行评估与比较。

关键词: AGV(automated guided vehicle)系统调度, 不确定情景, 路径冲突, 离散事件仿真, 仿真平台

Abstract:

As a complete automated guided vehicle(AGV) system scheduling algorithm, it must include conflict-handling strategy, together with common dispatching strategy and routing algorithm. However, due to the uncertainty, characteristics of such scheduling algorithm are difficult to be analyzed theoretically, and the relevant study is lacking. AnAGV system simulation platform based on the discrete-event simulation technique is designed and developed, which can flexibly set the scheduling problem, choose the dispatching strategy, routing algorithm, and conflict-handling strategy for the scheduling algorithm, to run the simulation. The platform has a visual interface, from which the running status of AGVs and the performance of the scheduling algorithm can be intuitively observed, and it can also output statistical data of the simulation experiment. Experiment results show that the simulation platform can accurately and effectively evaluate and compare the scheduling algorithms in uncertain environment.

Key words: automated guided vehicle(AGV) system scheduling, uncertain environment, route conflict, discrete-event simulation, simulation platform

中图分类号:

TP391.9

石志浩,沈海辉 . 不确定情景下AGV系统调度算法的仿真平台[J]. 系统仿真学报, 2024, 36(2): 385-404.

Shi Zhihao,Shen Haihui . Simulation Platform of AGV System Scheduling Algorithms in Uncertain Environment[J]. Journal of System Simulation, 2024, 36(2): 385-404.

图/表 17

图1

表1

图2

图3

图4

图5

表2

图6

图7

图8

图9

图10

图11

图12

图13

图14

图15

参考文献 34

1	佚名. 中华人民共和国国家标准-物流术语[J]. 交通建设与管理, 2007(10): 106-120.
2	Oyekanlu E A, Smith A C, Thomas W P, et al. A Review of Recent Advances in Automated Guided Vehicle Technologies: Integration Challenges and Research Areas for 5G-based Smart Manufacturing Applications[J]. IEEE Access, 2020, 8: 202312-202353.
3	Schneier M, Bostelman R. Literature Review of Mobile Robots for Manufacturing[M]. Gaithersburg: U.S. Deptartment of Commerce, National Institute of Standards and Technology, 2015.
4	Iwasa M, Toda Y, Saputra A A, et al. Path Planning of the Autonomous Mobile Robot by Using Real-time Rolling Risk Estimation with Fuzzy Inference[C]//2017 IEEE Symposium Series on Computational Intelligence (SSCI). Piscataway, NJ, USA: IEEE, 2017: 1-6.
5	Anon. Automated Guided Vehicle Market Size, Share & Trends Analysis Report By Vehicle Type, By Navigation Technology, ApplicationBy, By End-use Industry, ComponentBy, By Battery Type, RegionBy, and ForecastsSegment, 2021-2028[EB/OL]. [2022-03-16]. .
6	现代物流. 运用数字孪生让AGV迸发仓储活力[EB/OL]. (2021-12-13) [2022-04-13]. .
7	苏州艾吉威机器人有限公司.智慧物流管理系统[EB/OL]. [2022-04-13]. .
8	Anon. FUJI Taps Digital Twin for Simulation in Smart Factories \| AEI[EB/OL]. (2021-07-06) [2022-04-13]. .
9	Staff M M H. KION Group Starts Research Project ARIBIC Focused on Digital Twins of Warehouses[EB/OL]. (2021-08-04) [2022-04-13]. .
10	Mäntysaari J. Time Window Based Vehicle Routing System[D]. [S.l.]: Tampere University, 2017.
11	M S Dias Luís, A C Vieira António, Pereira G A B, et al. Discrete Simulation Software Ranking-A Top List of the Worldwide Most Popular and Used Tools[C]//2016 Winter Simulation Conference (WSC). Piscataway, NJ, USA: IEEE, 2016: 1060-1071.
12	熊俊涛, 李中行, 林国茂, 等. 基于交互式控制的AGV实时仿真系统研究[J]. 系统仿真学报, 2021, 33(3): 657-668.
	Xiong Juntao, Li Zhongxing, Lin Guomao, et al. Research on AGV Simulation System Based on Interactive Control[J]. Journal of System Simulation, 2021, 33(3): 657-668.
13	Robinson S. Simulation: The Practice of Model Development and Use[M]. New York: Palgrave Macmillan, 2014.
14	René (M) B M de Koster, Le-Anh T, J Robert van der Meer. Testing and Classifying Vehicle Dispatching Rules in Three Real-world Settings[J]. Journal of Operations Management, 2004, 22(4): 369-386.
15	Vis I F A. Survey of Research in the Design and Control of Automated Guided Vehicle Systems[J]. European Journal of Operational Research, 2006, 170(3): 677-709.
16	Bartholdi J J III, Platzman L K. Decentralized Control of Automated Guided Vehicles on a Simple Loop[J]. IIE Transactions, 1989, 21(1): 76-81.
17	Egbelu P J, Tanchoco J M A. Characterization of Automatic Guided Vehicle Dispatching Rules[J]. International Journal of Production Research, 1984, 22(3): 359-374.
18	Qiu Ling, Hsu W J, Huang S Y, et al. Scheduling and Routing Algorithms for AGVs: A Survey[J]. International Journal of Production Research, 2002, 40(3): 745-760.
19	Möhring Rolf H, Köhler Ekkehard, Gawrilow E, et al. Conflict-free Real-time AGV Routing[C]//Operations research proceedings 2004. Berlin, Heidelberg: Springer Berlin Heidelberg, 2005: 18-24.
20	Broadbent A J. Free Ranging AGV Systems: Promises, Problems and Pathways[C]//Proceedings of the 2nd International Conference on Automated Materials Handling. [S.l.]: [s.n.], 1985: 221-237.
21	Dijkstra E W. A Note on Two Problems in Connexion with Graphs[J]. Numerische Mathematik, 1959, 1(1): 269-271.
22	Huang J, Palekar U S, Kapoor S G. A Labeling Algorithm for the Navigation of Automated Guided Vehicles[J]. Journal of Engineering for Industry, 1993, 115(3): 315-321.
23	Hart P E, Nilsson N J, Raphael B. A Formal Basis for the Heuristic Determination of Minimum Cost Paths[J]. IEEE Transactions on Systems Science and Cybernetics, 1968, 4(2): 100-107.
24	Taghaboni-Dutta F, Tanchoco J M A. Comparison of Dynamic Routeing Techniques for Automated Guided Vehicle System[J]. International Journal of Production Research, 1995, 33(10): 2653-2669.
25	Sun X C, Tchernev N. Impact of Empty Vehicle Flow on Optimal Flow Path Design for Unidirectional AGV Systems[J]. International Journal of Production Research, 1996, 34(10): 2827-2852.
26	Malmborg C J. A Model for the Design of Zone Control Automated Guided Vehicle Systems[J]. International Journal of Production Research, 1990, 28(10): 1741-1758.
27	付建林, 张恒志, 张剑, 等. 自动导引车调度优化研究综述[J]. 系统仿真学报, 2020, 32(9): 1664-1675.
	Fu Jianlin, Zhang Hengzhi, Zhang Jian, et al. Review on AGV Scheduling Optimization[J]. Journal of System Simulation, 2020, 32(9): 1664-1675.
28	Nishi T, Morinaka S, Konishi M. A Distributed Routing Method for AGVs Under Motion Delay Disturbance[J]. Robotics and Computer-Integrated Manufacturing, 2007, 23(5): 517-532.
29	珍珍. 618发力!京东“亚洲一号”对外开放,真如外界传的那样壮观[EB/OL]. (2019-06-07) [2022-03-27]. .
30	Xiang Xi, Liu Changchun, Miao Lixin. Storage Assignment and Order Batching Problem in Kiva Mobile Fulfilment System[J]. Engineering Optimization, 2018, 50(11): 1941-1962.
31	Hong L J, Nelson B L. A Brief Introduction to Optimization Via Simulation[C]//Proceedings of the 2009 Winter Simulation Conference (WSC). Piscataway, NJ, USA: IEEE, 2009: 75-85.
32	Fu M C. Handbook of Simulation Optimization[M]. New York: Springer New York, 2015.
33	Shen Haihui, Hong L J, Zhang Xiaowei. Ranking and Selection with Covariates for Personalized Decision Making[J]. INFORMS Journal on Computing, 2021, 33(4): 1500-1519.
34	Xiong Shifeng. Personalized Optimization and Its Implementation in Computer Experiments[J]. IISE Transactions, 2020, 52(5): 528-536.

调度算法组成	调度算法种类
任务指派策略	NVF+NMF、NVF+EMF、 LIVF+NMF、LIVF+EMF
路径规划算法	TWA、ASA
冲突应对策略	CSS、CAS、MS

离散事件类型		优先顺序
障碍事件	障碍出现	1
障碍事件	障碍消失	2
AGV活动事件	路径开始	3
	路径结束
	位置改变
重调度事件		4

[1]	王向前, 郭璞昊, 孟祥瑞. 采选充一体化煤炭生产物流系统仿真及优化[J]. 系统仿真学报, 2023, 35(5): 907-919.
[2]	王天峥, 汤健, 夏恒, 乔俊飞. 城市固废焚烧过程的回路控制半实物仿真平台[J]. 系统仿真学报, 2023, 35(2): 241-253.
[3]	丁柏圆, 穆富岭, 李云鹏, 陈忠宽, 刘承禹. 面向复杂电磁环境的体系作战仿真平台设计[J]. 系统仿真学报, 2023, 35(2): 330-338.
[4]	付建林, 丁国富, 张剑, 江海凡, 郭沛佩. 基于响应面和NSGA-II的AGV系统多目标优化配置[J]. 系统仿真学报, 2022, 34(5): 994-1002.
[5]	刘闽东, 吴龙军, 汤明超, 孟梅. 项目型制造过程信息流集成建模仿真研究[J]. 系统仿真学报, 2022, 34(3): 555-563.
[6]	赵梓安, 周泓, 雷颖健. 基于改进狼群算法与仿真的单元调度优化[J]. 系统仿真学报, 2022, 34(2): 201-211.
[7]	尹长青, 谭天然, 王建民. 车载人因协同仿真系统研究及实现[J]. 系统仿真学报, 2022, 34(1): 134-144.
[8]	徐鹏, 冯国奇, 代学武, 崔东亮, 魏七龙, 李宝旭, 李建明. 高铁限速运行时分的小数据驱动建模与仿真[J]. 系统仿真学报, 2021, 33(8): 1892-1904.
[9]	黄晓冬, 谢孔树, 李妮, 燕雪峰, 赵亚丽. 面向体系对抗的仿真支撑平台研究及应用[J]. 系统仿真学报, 2021, 33(8): 1914-1926.
[10]	陈瑜洲, 李原, 王庆林, 张卿, 张津源. 无人机可见光侦察载荷视景仿真平台[J]. 系统仿真学报, 2021, 33(4): 910-917.
[11]	胡阳, 刘文颖, 朱丽萍, 李潇, 王维洲. 基于模块化架构的荷源日前有功控制仿真平台[J]. 系统仿真学报, 2021, 33(3): 669-678.
[12]	佟佳慧, 刘金, 张津源, 张永祥. 基于多核调度的实时仿真平台架构研究[J]. 系统仿真学报, 2019, 31(8): 1495-1504.
[13]	符修文, 杨勇生. 一种工业无线传感器网络抗毁性仿真平台[J]. 系统仿真学报, 2019, 31(7): 1342-1350.
[14]	于盈, 梁伟栋, 朱秀娟, 王建林, 王玲. 临近空间飞行器作战对抗仿真与推演系统设计[J]. 系统仿真学报, 2019, 31(12): 2584-2590.
[15]	于绍政, 孙冬石, 陈靖, 李勇超. 自动化集装箱码头机械配置仿真优化研究[J]. 系统仿真学报, 2019, 31(12): 2750-2757.