Simulation Platform of AGV System Scheduling Algorithms in Uncertain Environment

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

Abstract

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

CLC Number:

TP391.9

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

Figures/Tables 17

Fig. 1

Table 1

Fig. 2

Fig. 3

Fig. 4

Fig. 5

Table 2

Fig. 6

Fig. 7

Fig. 8

Fig. 9

Fig. 10

Fig. 11

Fig. 12

Fig. 13

Fig. 14

Fig. 15

References 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]	Tianzheng Wang, Jian Tang, Heng Xia, Junfei Qiao. Hardware-in-the-loop Simulation Platform of Loop Control for Municipal Solid Waste Incineration Process [J]. Journal of System Simulation, 2023, 35(2): 241-253.
[2]	Baiyuan Ding, Fuling Mu, Yunpeng Li, Zhongkuan Chen, Chengyu Liu. Design of System Combat Simulation Platform for Complex Electromagnetic Environment [J]. Journal of System Simulation, 2023, 35(2): 330-338.
[3]	Mindong Liu, Longjun Wu, Mingchao Tang, Mei Meng. Research on Information Flow Integrated M&S Method for Project Type Manufacturing Process [J]. Journal of System Simulation, 2022, 34(3): 555-563.
[4]	Xu Peng, Feng Guoqi, Dai Xuewu, Cui Dongliang, Wei Qilong, Li Baoxu, Li Jianming. Small-data Driven Modeling and Simulation of High-speed Train Running Time Under Limited Speeds [J]. Journal of System Simulation, 2021, 33(8): 1892-1904.
[5]	Huang Xiaodong, Xie Kongshu, Li Ni, Yan Xuefeng, Zhao Yali. Research and Application of Simulation Support Platform for System-of-Systems Combat [J]. Journal of System Simulation, 2021, 33(8): 1914-1926.
[6]	Chen Yuzhou, Li Yuan, Wang Qinglin, Zhang Qing, Zhang Jinyuan. Visual Simulation Platform for Visible Light Reconnaissance Load of Unmanned Aerial Vehicle [J]. Journal of System Simulation, 2021, 33(4): 910-917.
[7]	Hu Yang, Liu Wenying, Zhu Liping, Li Xiao, Wang Weizhou. Simulation Platform for Source-load Control of Active Power Based on Modular Architecture [J]. Journal of System Simulation, 2021, 33(3): 669-678.
[8]	Tong Jiahui, Liu Jin, Zhang Jinyuan, Zhang Yongxiang. Research on Real-time Simulation Platform Architecture Based on Multi-core Scheduling [J]. Journal of System Simulation, 2019, 31(8): 1495-1504.
[9]	Fu Xiuwen, Yang Yongsheng. Simulation Platform for Invulnerability of Industrial Wireless Sensor Networks [J]. Journal of System Simulation, 2019, 31(7): 1342-1350.
[10]	Yu Ying, Liang Weidong, Zhu Xiujuan, Wang Jianlin, Wang Ling. Design of Combat Simulation and Visualization System of Hypersonic Vehicle [J]. Journal of System Simulation, 2019, 31(12): 2584-2590.
[11]	Zu Xianghuan, Yang Chuanlei, Wang Yinyan. Research on Assessment and Decision Making Simulation Platform for Performance of Diesel Engine Mixed with Water [J]. Journal of System Simulation, 2017, 29(3): 559-564.
[12]	Liu zhen, Xu Dehui, Zhu Kaiwei, Sun Huilong. Research on Simulation Platform Based on Behavior Heterogeneity for Agriculture Biomass Energy [J]. Journal of System Simulation, 2017, 29(10): 2397-2406.
[13]	Chen Gong, Xu Lei, Su Zhiyong. 3D Real-time Visualization and Simulation Platform for Collaborative Path Planning of UA [J]. Journal of System Simulation, 2016, 28(9): 1996-2001.
[14]	Long Hao, Song Shujie. Study of Setting up Simulation Platform of Self-adaptive Flight Control System with Self-repair Function [J]. Journal of System Simulation, 2015, 27(11): 2791-2796.
[15]	Yang Wenbo, Song Yinhao, Zhao Xin. Development of A Virtual Reality System for Space Planning Simulation [J]. Journal of System Simulation, 2015, 27(10): 2575-2581.