PDF (1.2 MB)
Collect
Submit Manuscript
Open Access

An Effective Optimization Method for Integrated Scheduling of Multiple Automated Guided Vehicle Problems

School of Computer Science, Liaocheng University, Liaocheng 252000, China
Industrial Engineering Department, Baskent University, Ankara 06000, Türkiye
Show Author Information

Abstract

Automated Guided Vehicle (AGV) scheduling problem is an emerging research topic in the recent literature. This paper studies an integrated scheduling problem comprising task assignment and path planning for AGVs. To reduce the transportation cost of AGVs, this work also proposes an optimization method consisting of the total running distance, total delay time, and machine loss cost of AGVs. A mathematical model is formulated for the problem at hand, along with an improved Discrete Invasive Weed Optimization algorithm (DIWO). In the proposed DIWO algorithm, an insertion-based local search operator is developed to improve the local search ability of the algorithm. A staggered time departure heuristic is also proposed to reduce the number of AGV collisions in path planning. Comprehensive experiments are conducted, and 100 instances from actual factories have proven the effectiveness of the optimization method.

References

[1]

M. De Ryck, M. Versteyhe, and F. Debrouwere, Automated guided vehicle systems, state-of-the-art control algorithms and techniques, J. Manuf. Syst., vol. 54, pp. 152–173, 2020.

[2]

S. Riazi, K. Bengtsson, and B. Lennartson, Energy optimization of large-scale AGV systems, IEEE Trans. Automat. Sci. Eng., vol. 18, no. 2, pp. 638–649, 2021.

[3]

W. Q. Zou, Q. K. Pan, T. Meng, L. Gao, and Y. L. Wang, An effective discrete artificial bee colony algorithm for multi-AGVs dispatching problem in a matrix manufacturing workshop, Expert Syst. Appl., vol. 161, p. 113675, 2020.

[4]

W. Q. Zou, Q. K. Pan, and L. Wang, An effective multi-objective evolutionary algorithm for solving the AGV scheduling problem with pickup and delivery, Knowl. Based Syst., vol. 218, p. 106881, 2021.

[5]

W. Q. Zou, Q. K. Pan, and M. F. Tasgetiren, An effective iterated greedy algorithm for solving a multi-compartment AGV scheduling problem in a matrix manufacturing workshop, Appl. Soft Comput., vol. 99, p. 106945, 2020.

[6]

H. Hu, X. Chen, T. Wang, and Y. Zhang, A three-stage decomposition method for the joint vehicle dispatching and storage allocation problem in automated container terminals, Comput. Ind. Eng., vol. 129, pp. 90–101, 2019.

[7]

J. Luo and Y. Wu, Scheduling of container-handling equipment during the loading process at an automated container terminal, Comput. Ind. Eng., vol. 149, p. 106848, 2020.

[8]

G. Fragapane, R. de Koster, F. Sgarbossa, and J. O. Strandhagen, Planning and control of autonomous mobile robots for intralogistics: Literature review and research agenda, Eur. J. Oper. Res., vol. 294, no. 2, pp. 405–426, 2021.

[9]

Q. K. Pan, L. Gao, and L. Wang, An effective cooperative co-evolutionary algorithm for distributed flowshop group scheduling problems, IEEE Trans. Cybern., vol. 52, no. 7, pp. 5999–6012, 2022.

[10]

X. L. Jing, Q. K. Pan, L. Gao, and L. Wang, An effective iterated greedy algorithm for a robust distributed permutation flowshop problem with carryover sequence-dependent setup time, IEEE Trans. Syst. Man. Cybern. Syst., vol. 52, no. 9, pp. 5783–5794, 2022.

[11]

F. Wang, Y. Li, and J. Chen, Bi-level programming model for post-disaster emergency supplies scheduling with time windows and its algorithm, Int. J. Autom. Control, vol. 16, no. 1, pp. 45–63, 2022.

[12]

E. Jiang, L. Wang, and J. Wang, Decomposition-based multi-objective optimization for energy-aware distributed hybrid flow shop scheduling with multiprocessor tasks, Tsinghua Science and Technology, vol. 26, no. 5, pp. 646–663, 2021.

[13]

L. Meng, K. Gao, Y. Ren, B. Zhang, H. Sang, and C. Zhang, Novel MILP and CP models for distributed hybrid flowshop scheduling problem with sequence-dependent setup times, Swarm Evol. Comput., vol. 71, p. 101058, 2022.

[14]

A. Mohammad, O. Saleh, and R. A. Abdeen, Occurrences algorithm for string searching based on brute-force algorithm, J. Comput. Sci., vol. 2, no. 1, pp. 82–85, 2006.

[15]

O. Karasakal, L. Kandiller, and N. E. Özdemirel, A branch and bound algorithm for sector allocation of a naval task group, Nav. Res. Logist., vol. 58, no. 7, pp. 655–669, 2011.

[16]

W. C. Yeh, An efficient branch-and-bound algorithm for the two-machine bicriteria flowshop scheduling problem, J. Manuf. Syst., vol. 20, no. 2, pp. 113–123, 2002.

[17]

H. Zhang, J. Xie, J. Ge, J. Shi, and Z. Zhang, Hybrid particle swarm optimization algorithm based on entropy theory for solving DAR scheduling problem, Tsinghua Science and Technology, vol. 24, no. 3, pp. 282–290, 2019.

[18]

X. Wang, L. Wang, S. Wang, J. Pan, H. Ren, and J. Zheng, Recommending-and-grabbing: A crowdsourcing-based order allocation pattern for on-demand food delivery, IEEE Trans. Intell. Transp. Syst., vol. 24, no. 1, pp. 838–853, 2023.

[19]

F. Ming, W. Gong, L. Wang and L. Gao, Balancing convergence and diversity in objective and decision spaces for multimodal multi-objective optimization, IEEE Trans. Emerg. Top. Comput. Intell., vol. 7, no. 2, pp. 474–486, 2023.

[20]

X. Wang, Y. Dai, L. Wang, and Z. Jia, Transient analysis and scheduling of bernoulli serial lines with multi-type products and finite buffers, IEEE Trans. Automat. Sci. Eng., vol. 20, no. 4, pp. 2367–2382, 2023.

[21]

X. Wu, X. Xiao, and Q. Cui, Multi-objective flexible flow shop batch scheduling problem with renewable energy, Int. J. Autom. Control, vol. 14, nos. 5&6, pp. 519–553, 2020.

[22]

F. Zhao, S. Di, and L. Wang, A hyperheuristic with Q-learning for the multiobjective energy-efficient distributed blocking flow shop scheduling problem, IEEE Trans. Cybern., vol. 53, no. 5, pp. 3337–3350, 2023.

[23]

M. Tan, Z. Zhang, Y. Ren, I. Richard, and Y. Zhang, Multi-agent system for electric vehicle charging scheduling in parking lots, Complex Syst. Model. Simul., vol. 3, no. 2, pp. 129–142, 2023.

[24]

Z. Li, H. Sang, Q. Pan, K. Gao, Y. Han, and J. Li, Dynamic AGV scheduling model with special cases in matrix production workshop, IEEE Trans. Ind. Inf., vol. 19, no. 6, pp. 7762–7770, 2023.

[25]

X. He, Q. K. Pan, L. Gao, L. Wang, and P. N. Suganthan, A greedy cooperative co-evolutionary algorithm with problem-specific knowledge for multiobjective flowshop group scheduling problems, IEEE Transactions on Evolutionary Computation, vol. 27, no. 3, pp. 430–444, 2023.

[26]

Z. Shu, A. Song, G. Wu, and W. Pedrycz, Variable reduction strategy integrated variable neighborhood search and NSGA-II hybrid algorithm for emergency material scheduling, Complex Syst. Model. Simul., vol. 3, no. 2, pp. 83–101, 2023.

[27]
X. Zhang, H. Sang, Z. Li, B. Zhang, and L. Meng, An efficient discrete artificial bee colony algorithm with dynamic calculation method for solving the AGV scheduling problem of delivery and pickup, Complex Intell. Syst.
[28]

Y. Fu, Y. Hou, Z. Wang, X. Wu, K. Gao, and L. Wang, Distributed scheduling problems in intelligent manufacturing systems, Tsinghua Science and Technology, vol. 26, no. 5, pp. 625–645, 2021.

[29]
M. X. Tian, H. Y. Sang, W. Q. Zou, Y. T. Wang, M. P. Miao, and L. L. Meng, Joint scheduling of AGVs and parallel machines in an automated electrode foil production factory, Expert Systems with Applications, http://doi.org/10.1016/jeswa.2023.122197, 2024.
[30]

S. Nesmachnow, An overview of metaheuristics: Accurate and efficient methods for optimisation, Int. J. Metaheuristics, vol. 3, no. 4, pp. 320–347, 2014.

[31]

R. Choe, J. Kim, and K. R. Ryu, Online preference learning for adaptive dispatching of AGVs in an automated container terminal, Appl. Soft Comput., vol. 38, pp. 647–660, 2016.

[32]

J. Luo and Y. Wu, Modelling of dual-cycle strategy for container storage and vehicle scheduling problems at automated container terminals, Transp. Res. E Logist. Transp. Rev., vol. 79, pp. 49–64, 2015.

[33]

J. Luo, Y. Wu, and A. B. Mendes, Modelling of integrated vehicle scheduling and container storage problems in unloading process at an automated container terminal, Comput. Ind. Eng., vol. 94, pp. 32–44, 2016.

[34]

N. Wu and M. Zhou, Shortest routing of bidirectional automated guided vehicles avoiding deadlock and blocking, IEEE/ASME Trans. Mechatron., vol. 12, no. 1, pp. 63–72, 2007.

[35]

M. Saidi-Mehrabad, S. Dehnavi-Arani, F. Evazabadian, and V. Mahmoodian, An ant colony algorithm (ACA) for solving the new integrated model of job shop scheduling and conflict-free routing of AGVs, Comput. Ind. Eng., vol. 86, pp. 2–13, 2015.

[36]

Y. Yang, M. Zhong, Y. Dessouky, and O. Postolache, An integrated scheduling method for AGV routing in automated container terminals, Comput. Ind. Eng., vol. 126, pp. 482–493, 2018.

[37]

J. Euchi and A. Sadok, Hybrid genetic-sweep algorithm to solve the vehicle routing problem with drones, Phys. Commun., vol. 44, p. 101236, 2021.

[38]

G. Li, B. Zeng, W. Liao, X. Li, and L. Gao, A new AGV scheduling algorithm based on harmony search for material transfer in a real-world manufacturing system, Adv. Mech. Eng., vol. 10, no. 3, pp. 1–13, 2018.

[39]

S. C. Srivastava, A. K. Choudhary, S. Kumar, and M. K. Tiwari, Development of an intelligent agent-based AGV controller for a flexible manufacturing system, Int. J. Adv. Manuf. Technol., vol. 36, no. 7, pp. 780–797, 2008.

[40]
D. K. Liu and A. K. Kulatunga, Simultaneous planning and scheduling for multi-autonomous vehicles, in Evolutionary Scheduling, K. P. Dahal, K. C. Tan, and P. I. Cowling, eds. Berlin, Germany: Springer, 2007, pp. 437–464.
[41]

A. Derhab, M. Belaoued, I. Mohiuddin, F. Kurniawan, and M. K. Khan, Histogram-based intrusion detection and filtering framework for secure and safe in-vehicle networks, IEEE Trans. Intell. Transp. Syst., vol. 23, no. 3, pp. 2366–2379, 2022.

[42]
Y. Kang, D. A. De Lima, and A. C. Victorino, An approach of human driving behavior correction based on dynamic window approach, in Proc. 2014 IEEE Intelligent Vehicles Symposium, Dearborn, MI, USA, 2014, pp. 304−309.
[43]
J. van den Berg, S. J. Guy, M. Lin, and D. Manocha, Reciprocal n-body collision avoidance, in Proc. 14th International Symposium ISRR on Robotics Research, Berlin, Germany, 2011, pp. 3−19.
[44]

Z. K. Li, H. Y. Sang, X. J. Zhang, W. Q. Zou, B. Zhang, and L. L. Meng, An effective discrete invasive weed optimization algorithm for multi-AGVs dispatching problem with specific cases in matrix manufacturing workshop, Comput. Ind. Eng., vol. 174, p. 108755, 2022.

[45]

W. Y. Szeto, Y. Wu, and S. C. Ho, An artificial bee colony algorithm for the capacitated vehicle routing problem, Eur. J. Oper. Res., vol. 215, no. 1, pp. 126–135, 2011.

[46]

J. P. Huang, Q. K. Pan, L. Gao, and L. Wang, An effective iterated greedy algorithm for PCBs grouping problem to minimize setup times, Appl. Soft Comput., vol. 112, p. 107830, 2021.

Tsinghua Science and Technology
Pages 1355-1367
Cite this article:
Sang H, Li Z, Tasgetiren MF. An Effective Optimization Method for Integrated Scheduling of Multiple Automated Guided Vehicle Problems. Tsinghua Science and Technology, 2024, 29(5): 1355-1367. https://doi.org/10.26599/TST.2023.9010087
Metrics & Citations  
Article History
Copyright
Rights and Permissions
Return