自动导引车调度优化研究综述

doi:10.16182/j.issn1004731x.joss.19-0042

摘要/Abstract

摘要： 制造系统中自动导引车（Automated Guided Vehicles,AGV）调度对于提高制造系统效益和降低制造成本具有重要作用,同时AGV调度也是十分复杂的组合优化问题,将AGV调度优化问题分为3类：AGV静态调度、AGV动态调度、AGV同时调度（与其他资源联合调度）进行了概述,并对其研究方法进行了分析与总结,包括传统分析方法、建模与仿真方法、智能优化算法、混合优化方法,分析了各类方法的优缺点,指出了当前AGV调度优化研究中存在的不足,并提出了未来的研究方向和建议。

关键词: 自动导引车, 调度, 动态调度, 同时调度, 智能优化

Abstract: AGV scheduling plays an important role in improving the efficiency and reducing manufacturing cost, but it is also a very complex combinatorial optimization procedure. AGV scheduling optimization is divided into three types, AGV static scheduling, AGV dynamic scheduling and AGV simultaneous scheduling with other resources scheduling. Various methods are summarized and listed, including traditional analysis method, modeling and simulation method, intelligent optimization algorithm and hybrid optimization method, and the advantages and disadvantages of each method are also analyzed. The deficiencies of AGV scheduling research are pointed out and the research directions for future are presented.

Key words: AGV, scheduling, dynamic scheduling, simultaneous scheduling, intelligent optimization

中图分类号:

TP391.9

付建林, 张恒志, 张剑, 姜良奎. 自动导引车调度优化研究综述[J]. 系统仿真学报, 2020, 32(9): 1664-1675.

Fu Jianlin, Zhang Hengzhi, Zhang Jian, Jiang Liangkui. Review on AGV Scheduling Optimization[J]. Journal of System Simulation, 2020, 32(9): 1664-1675.

参考文献

[1] Vis I F.A Survey of research in the design and control of automated guided vehicle systems[J]. European Journal of Operational Research (S0377-2217), 2006, 170(3): 677-709.
[2] Qiu L, Hsu W J, Huang S Y, et al.Scheduling and routing algorithms for AGVs: a survey[J]. International Journal of Production Research (S0020-7543), 2002, 40(3): 745-760.
[3] Le-Anh T, De Koster M B M. A review of design and control of automated guided vehicle Systems[J]. European Journal of Operational Research (S0377-2217), 2006, 171(1): 1-23.
[4] Fazlollahtabar H, Saidi-Mehrabad M.Methodologies to Optimize Automated Guided Vehicle Scheduling and Routing Problems: A Review Study[J]. J Intell Robot Syst (S0921-0296), 2015, 77: 525-545.
[5] Miyamoto T, Inoue K.Local and random searches for dispatch and conflict free routing problem of capacitated AGV systems[J]. Computers & Industrial Engineering (S0360-8352), 2016, 91: 1-9.
[6] 马越汇, 胡志华. 不确定环境下自动化集装箱码头AGV调度与配置问题[J]. 广西大学学报(自然科学版), 2016, 41(2): 589-597.
Ma Yuehui, Hu Zhihua.The dispatching and scheduling problems of AGVs at automated container terminals under uncertainty conditions[J]. Journal of Guangxi University (Natural Science Edition), 2016, 41(2): 589-597.
[7] 霍凯歌, 胡志华. 基于遗传算法的自动化集装箱码头多载AGV调度[J]. 上海海事大学学报, 2016, 37(3): 7-33.
Huo Kaige, Hu Zhihua.Multi-load AGV scheduling in automated container terminals based on genetic algorithm[J]. Journal of Shanghai Maritime University, 2016, 37(3): 7-33.
[8] 霍凯歌, 张亚琦, 胡志华. 自动化集装箱码头多载AGV调度问题研究[J]. 大连理工大学学报, 2016, 56(3): 244-251.
Huo Kaige, Zhang Yaqi, Hu Zhihua.Research on scheduling problem of multi-load AGV at automated container terminal[J]. Journal of Dalian University of Technology, 2016, 56(3): 244-251.
[9] Meersmans P J M, Wagelmans A. Effective algorithms for integrated scheduling of handling equipment at automated container terminals[C]. ERIM Report Series Research in Management. Rotterdam,The Netherlands: Erasmus Research Institute of Management(ERIM), 2001.
[10] Bilge Ü, Ulusoy G.A time window approach to simultaneous scheduling of machines and material handling system in an FMS[J]. Operations Research (S0030-364X), 1995, 43: 1058-1070.
[11] Heger J, Thomas V.Optimal Scheduling for Automated Guided Vehicles (AGV) in Blocking Job-Shops[C]. IFIP International Conference on Advances in Production Management Systems (APMS). Hamburg, Germany: Springer, Cham, 2017: 151-158.
[12] Heger J, Voss T.Optimal Scheduling of AGVs in a Reentrant Blocking Job-shop[C]. Procedia CIRP. Amsterdam, Netherlands: Elsevier, 2018, 67(1): 41-45.
[13] Egbelu P J, Jose M A.Tanchoco Characterization of automatic guided vehicle dispatching rules[J]. International Journal of Production Research (S0020-7543), 1984, 22(3): 359-374.
[14] Jawahar N, Aravindan P, Ponnambalam S G, et al.AGV Schedule integrated with production in flexible manufacturing systems[J]. Int. J. Adv. Manuf. Technol (S0268-3768), 1998, 14: 428-440.
[15] Sabuncuoglu I.Experimental investigation of an FMS due-date scheduling problem: evaluation of machine and AGV scheduling rules[J]. The International Journal of Flexible Manufacturing Systems (S1936-6582), 1993, 5: 301-323.
[16] Namita S, Sarngadharan P V, Pal P K.AGV Scheduling for Automated Material Distribution: A Case Study[J]. Journal of Intelligent Manufacturing (S0956-5515), 2011, 22(2): 219-228.
[17] Kim B K, Oh S J.Development of dispatching rules for automate guided vehicle systems[J]. Journal of Manufacturing Systems (S0278-6125), 1998, 17(2): 137-143.
[18] 管贤平, 戴先中. 自动导引车系统避免死锁的多属性任务调度方法[J]. 中国机械工程, 2009, 20(19): 2337-2342.
Guan Xianping, Dai Xianzhong.Multi-attribute Dispatching Method with Deadlock Avoidance for AGV Systems[J]. China Mechanical Engineering, 2009, 20(19): 2337-2342.
[19] 肖海宁, 楼佩煌, 满增光, 等. 自动导引车系统实时多属性任务调度方法[J]. 计算机集成制造系统, 2012, 18(10): 2224-2230.
Xiao Haining, Lou Peihuang, Man Zengguang, et al.Real-time multi-attribute dispatching method for automatic guided vehicle system[J].Computer Integrated Manufacturing Systems, 2012, 18(10): 2224-2230.
[20] Ulusoy G, Bilge U.Simultaneous scheduling of machines and automated guided vehicles[J]. INT. J. PROD. RES.(S0020-7543), 1993, 31(12): 2857-2873.
[21] 黄一钧. 车身车间AGV物料搬运系统小车数量配置规划[J]. 工业工程与管理, 2015, 20(4): 156-162.
Huang Yijun.Planning on the Number of Vehicle Requirement for Body Shop AGV Material Handling System[J]. Industrial Engineering and Management, 2015, 20(4): 156-162.
[22] 金芳, 方凯, 王京林. 基于排队论的AGV调度研究[J].仪器仪表学报, 2004, 25(增1): 844-846.
Jin Fang, Fang Kai, Wang Jinglin.Research on AGV's Scheduling Based on Queuing Theory[J]. Chinese Journal of Scientific Instrument, 2004, 25(S1): 844-846.
[23] 桑泽磊. 基于Agent的车间AGV智能调度技术研究[D]. 南京: 南京航空航天大学, 2016.
Sang Zelei.Research on Intelligent Scheduling of AGV Based on Agent in Floor Shop[D]. Nanjing: Nanjing University of Aeronautics and Astronautics, 2016.
[24] 经建峰. 基于智能体的多AGV自主控制系统研发[D]. 南京: 南京航空航天大学, 2014.
Jing Jianfeng.Study and Development of Autonomous Control Multi-AGV System Based on Agent[D]. Nanjing: Nanjing University of Aeronautics and Astronautics, 2014.
[25] 李晓萌, 杨煜普, 许晓鸣. 基于多级决策的多智能体自动导航车调度系统[J]. 上海交通大学学报, 2002, 36(8): 1146-1149.
Li Xiaomeng, Yang Yupu, Xu Xiaoming.Multi-agent AGV Dispatching System Using Multilevel Decision Methods[J]. Journal of Shanghai Jiaotong University, 2002, 36(8): 1146-1149.
[26] Cenk S, Melek D, Rizvan E, et al.A multi-agent based approach to dynamic scheduling with flexible processing capabilities[J]. J Intell Manuf (S0956-5515), 2017, 28: 1827-1845.
[27] 任小龙. 基于Petri网的FMS调度问题研究[D]. 西安: 西安电子科技大学, 2010.
Ren Xiaolong.Study on Scheduling Flexible Manufacturing Systems Using Petri Nets[D]. Xi'an: XiDian University, 2010.
[28] 李国飞. 叉车式AGV运动控制与调度方法的研究[D]. 哈尔滨: 哈尔滨工业大学, 2015.
Li Guofei.Research on Motion control and Scheduling method of Forklift AGV[D]. Harbin: Harbin Institute of Technology, 2015.
[29] Nishi T, Tanaka Y.Petri Net Decomposition Approach for Dispatching and Conflict-Free routing of Bidirectional Automated Guided Vehicle Systems[J]. IEEE Transactions on Systems, Man and Cybernetics- Part A: Systems and Humans (S2168-2216), 2012, 42(5): 1230-1243.
[30] Giglio D, Paolucci M.Agent-based Petri net models for AGV management in manufacturing systems[C]. Proceedings of IEEE International Conference on Systems, Man, and Cybernetics. Los Alamitos, CA: IEEE Computer Society, 2001: 2457-2462.
[31] Yim D S, Linn R J.Push and pull rules for dispatching automated guided vehicles in a flexible manufacturing system[J]. International Journal of Production Research (S0020-7543), 1993, 31: 43-57.
[32] Baruwa O T, Piera M A.A coloured Petri net based hybrid heuristic search approach to simultaneous scheduling of machines and automated guided vehicles[J]. International Journal of Production Research (S0020-7543), 2016, 54(16): 4773-4792.
[33] 柯冉绚, 任亚东. 集装箱码头AGV调度优化[J]. 集美大学学报(自然科学版), 2016, 21(1): 35-41.
Ke Ranxuan, Ren Yadong.Study on Optimizing AGV Control in Container Terminals[J]. Journal of Jimei University (Natural Science), 2016, 21(1): 35-41.
[34] 李军涛, 夏琨, 木漱洋. 交叉环单向循环搬运系统调度问题的仿真优化研究[J]. 系统仿真学报, 2016, 28(7): 1561-1574.
Li Juntao, Xia Kun, Kise Hiroshi.Scheduling Problem of Unidirectional Material Handling System with Short-cut[J]. Journal of System Simulation, 2016, 28(7): 1561-1574.
[35] 杨武平. 模具智能车间公共缓存区单AGV调度策略与仿真[D]. 广州: 广东工业大学, 2016.
Yang Wuping.Intelligent die shop public buffer zone single AGV scheduling and simulation[D]. Guangzhou: Guangdong University of Technology, 2016.
[36] 韩晓龙, 樊加伟. 自动化港口AGV调度配置仿真分析[J]. 重庆交通大学学报(自然科学版), 2016, 35(5): 151-154.
Han Xiaolong, Fan Jiawei.Analysis of AGV Dispatching and Configuration Simulation of Automated Container Terminals[J], Journal of Chongqing Jiaotong University(Natural Science), 2016, 35(5): 151-154.
[37] Mousavi M, Yap H J, Musa S N, et al.Multi-objective AGV scheduling in an FMS using a hybrid of genetic algorithm and particle swarm optimization[J]. PLoS ONE (S1932-6203), 2017, 12(3): 1-24.
[38] Mousavi M, Yap H J.A fuzzy hybrid GA-PSO algorithm for multi-objective AGV scheduling in FMS[J]. Int J simul model (S1726-4529), 2017, 16(1): 58-71.
[39] Viharos A B, István N.Simulation and Scheduling of AGV Based Robotic Assembly Systems[C]. IFAC-Papers On Line. Amsterdam, Netherlands: Elsevier, 2018, 51(11): 1415-1420.
[40] 朱琳, 范秀敏. 柔性生产系统配料区多自动导航小车调度优化[J]. 计算机集成制造系统, 2012, 18(6): 1168-1175.
Zhu Lin, Fan Xiumin.Scheduling optimization for multi-AGVs in batching area of flexible production system[J]. Computer Integrated Manufacturing Systems, 2012, 18(6): 1168-1175.
[41] 刘旭. 基于AGV平台的多品种混流装配智能调度与控制技术研究[D]. 南京: 南京航空航天大学, 2015.
Liu Xu.Research on Intelligent Dispatching and Control for Mixed Mode Assembly Based on AGV Platform[D]. Nanjing: Nanjing University of Aeronautics and Astronautics, 2015.
[42] 汪先超. 多AGV系统的组合导航控制与调度方法研究[D]. 大连: 大连理工大学, 2016.
Wang Xianchao, Integrated Navigation Control and Research on Scheduling Method for Multi-AGVs system[D]. Dalian: Dalian University of Technology, 2016.
[43] Lin L, Gen M.A random key-based genetic algorithm for AGV dispatching in FMS[J]. International Journal of Manufacturing Technology and Management (S1741-5195), 2009, 16: 58-75.
[44] Ulusoy G, Bilge U.A genetic algorithm approach to the simultaneous scheduling of machines and automated guided vehicles[J]. Computers and Operations Research (S0305-0548), 1997, 24: 335-351.
[45] Reddy B S P, Rao C S P. A hybrid multi-objective GA for simultaneous scheduling of machines and AGVs in FMS[J]. Int. J. Adv. Manuf. Technol (S0268-3768), 2006, 31(5/6): 602-613
[46] Jerald J, Asokan P, Saravanan R, et al.Simultaneous scheduling of parts and automated guided vehicles in an FMS environment using adaptive genetic algorithm[J]. Int. J. Adv. Manuf. Technol (S0268-3768), 2006, 29: 584-589.
[47] Abdelmaguid T F, Nassef A O, Kamal B A, et al.A hybrid GA/heuristic approach to the simultaneous scheduling of machines and automated guided vehicles[J]. International Journal of Production Research (S0020-7543), 2004, 42: 267-281.
[48] Chaudhry I A, Mahmood S, Shami M.Simultaneous scheduling of machines and automated guided vehicles in flexible manufacturing systems using genetic algorithms[J]. Journal of South University of Technology (S2095-2899). 2011, 18(5): 1473-1486.
[49] 李岩. 柔性加工环境中机器和AGV的集成调度[J]. 中国机械工程, 2001, 12(4): 447-451.
Li Yan.Integrated Scheduling of Machines and AGVs in Flexible Manufacturing Environment[J]. China Mechanical Engineering, 2001, 12(4): 447-451.
[50] 柳赛男, 柯映林. 一种解决有AGV小车约束的车间智能调度问题的算法[J]. 中国机械工程, 2007, 18(15): 1810-1813.
Liu Sainan, Ke Yinglin.An Algorithm for Job Shop Scheduling in Dual Resource Constrained with AGV[J]. China Mechanical Engineering, 2007, 18(15): 1810-1813.
[51] 肖海宁, 楼佩煌, 严伟国, 等. 柔性作业车间中机床与自动导引车在线调度方法[J]. 农业机械学报, 2013, 44(4): 280-286
Xiao Haining, Lou Peihuang, Yan Weiguo, et al.On-line Scheduling Method for Simultaneous Scheduling of Machines and Automated Guided Vehicles in Flexible Job Shop[J]. Transactions of the Chinese Society for Agricultural Machinery, 2013, 44(4): 280-286.
[52] Yang Y S, Zhong M S, Dessouky Y, et al.An Integrated Scheduling Method for AGV Routing in Automated Container Terminals[J]. Computers & Industrial Engineering (S0360-8352), 2018, 126: 482-493.
[53] 冯辉宗, 陈勇, 刘飞, 等. 基于遗传算法的配送车辆优化调度[J]. 计算机集成制造系统, 2004, 10(增1): 81-84.
Feng Huizong, Chen Yong, Liu Fei, et al.Optimized scheduling of distribution vehicles based on genetic algorithm[J]. Computer Integrated Manufacturing Systems, 2004, 10(S1): 81-84.
[54] Jin J, Zhang X H.Multi AGV scheduling problem in automated container terminal[J]. Journal of Marine Science and Technology-Taiwan (S1023-2796), 2016, 24(1): 32-38.
[55] 魏昆. 柔性制造系统AGV动态调度模型与算法[D]. 沈阳: 沈阳大学, 2014.
Wei Kun.The Dynamic Scheduling Model and Algorithm of AGV in Flexible Manufacturing System[D]. Shenyang: Shenyang University, 2014.
[56] 焦福明. 自动化仓储系统AGV调度研究与实现[D]. 济南: 山东大学硕士论文, 2013.
Jiao Fuming.Study and Realization of AGV Scheduling in Automatic Storage & Retrieval System[D]. Jinan: Shangdong University, 2013.
[57] 边培莹, 李德信, 包宝军, 等. 粒子群算法在生产物流调度中的应用研究[J]. 计算机工程与应用, 2010, 46(17): 220-223.
Bian Peiying, Li Dexin, Bao Baojun, et al.Application research of particle swarm optimization in production logistics scheduling[J]. Computer Engineering and Applications, 2010, 46(17): 220-223.
[58] 郝一名. AGV系统作业调度策略研究[D]. 济南: 山东大学硕士学位论文, 2016.
Hao Yiming.Research of Strategy on Automated Guided Vehicle System Task Scheduling[D]. Jinan: Shandong University, 2016
[59] 罗键, 吴长庆, 李波, 等. 基于改进量子微粒群的轨道导引小车系统建模与优化[J]. 计算机集成制造系统, 2011, 17(2): 321-328.
Luo Jian, Wu Changqing, Li Bo, et al.Modeling and optimization of RGV system based on improved QPSO[J]. Computer Integrated Manufacturing Systems, 2011, 17(2): 321-328.
[60] Zhang F Q, Li J J.An Improved Particle Swarm Optimization Algorithm for Integrated Scheduling Model in AGV-Served Manufacturing Systems[J]. Journal of Advanced Manufacturing Systems (S0219-6867), 2018, 17(3): 375-390.
[61] Lin L, Liang Y, Gen M, et al.A hybrid evolutionary algorithm for FMS optimization with AGV dispatching[C]. CIE42 Proceedings. Cape Town, South Africa: SAIIE, 2012.
[62] 杨锋英, 刘会超. AGV作业调度模型及改进的DE算法研究[J]. 计算机工程与应用, 2014, 50(9): 225-230.
Yang Fengying, Liu Huichao.Research on AGV job scheduling model and improved differential evolution algorithm. Computer Engineering and Applications[J]. Computer Engineering and Applications, 2014, 50(9): 225-230.
[63] Satish K M V, Janardhana R, Rao C S P. Simultaneous scheduling of machines and vehicles in an FMS environment with alternative routing[J]. International Journal of Advanced Manufacturing Tecnology (S0268-3768), 2011, 53: 339-351.
[64] Gnanavel Babu A, Jerald J, Noorul Haq A, et al.Scheduling of machines and automated guided vehicles in FMS using differential evolution[J]. International Journal of Production Research (S0020-7543), 2010, 48(16): 4683-4699.
[65] 张磊. 轮式机器人路径规划及任务调度算法研究与设计[D]. 广州: 华南理工大学, 2016.
Zhang Lei.Research and Design in Algorithm of Path Planning and Task Scheduling for Wheeled Robot[D]. Guangzhou: South China University of Technology, 2016
[66] Saidi-Mehrabad M, Dehnavi-Arani S, Evazabadian F, et al.An Ant Colony Algorithm (ACA) for solving the new integrated model of job shop scheduling and conflict-free routing of AGVs[J]. Computers & Industrial Engineering (S0360-8352), 2015, 86: 2-13.
[67] Li G M, Bing Z, Wei L, et al.A New AGV Scheduling Algorithm Based on Harmony Search for Material Transfer in a Real-World Manufacturing System[J]. Advances in Mechanical Engineering (S1687-8140), 2018, 10(3): 1-13.
[68] Xue T F, Peng Z, Yu H B.A Reinforcement Learning Method for Multi-AGV Scheduling in Manufacturing[C]. 2018 IEEE International Conference on Industrial Technology (ICIT). Los Alamitos, CA: IEEE Computer Society, 2018: 1557-1561.
[69] Murugesan R.Optimization Algorithm for Minimizing the Earliness/Tardiness of Automated Guided Vehicles Using Artificial Immune System[J]. International Journal of Applied Engineering Research (S0973-4562), 2017, 12(22): 11913-11919.
[70] 袁颖河, 吴智铭. FMS_AGV传输系统自学习调度方法[J]. 上海交通大学学报, 1998, 32(6): 83-87.
Yuan Yinghe, Wu Zhiming.Algorithm of Self-Learning Scheduling in FMS-AGV Transportation System[J]. Journal of Shanghai Jiaotong University, 1998, 32(6): 83-87.
[71] 于璐. 基于混合遗传算法的柔性制造系统调度研究[D]. 镇江: 江苏大学, 2016.
Yu Lu.Research on Scheduling for Flexible Manufacturing System Based on Hybrid Genetic Algorithm[D]. Zhenjiang: Jiangsu University, 2016.
[72] Umar A U, Ariffin M K A. Hybrid multi-objective genetic algorithms for integrated dynamic scheduling and routing of jobs and automated-guided vehicle (AGV) in flexible manufacturing systems (FMS) environment[J]. Int J Adv Manuf Technol (S0268-3768), 2015(81): 2123-2141.
[73] Udhayakumar P, Kumanan S.Task Scheduling of AGV in FMS using Non-traditional Optimization Techniques[J]. International Journal of Simulation Modeling (S1726-4529), 2010, 9(1): 28-39.
[74] Zhang J, Ding G F, Zou Y S, et al.Review of Job Shop Scheduling Research and its New Perspectives Under Industry 4.0[J]. Journal of Intelligent Manufacturing (S0956-5515), 2017: 1-22.