Journal of Jilin University(Engineering and Technology Edition) ›› 2024, Vol. 54 ›› Issue (8): 2245-2255.doi: 10.13229/j.cnki.jdxbgxb.20230467

Previous Articles     Next Articles

Automated terminal horizontal transportation scheduling and route planning under network resource allocation

Jin ZHU(),Qi HUANG   

  1. Institute of Logistics Science and Engineering，Shanghai Maritime University，Shanghai 201306，China
  • Received:2023-05-11 Online:2024-08-01 Published:2024-08-30

RICH HTML

 1   

PDF (PC)

145

Abstract:

In order to improve the efficiency of horizontal transportation of automated container terminals and reduce conflicts between automated guided vehicles （AGV） in the horizontal transportation， a multi-AGV horizontal transportation scheduling and path planning model with the goal of minimizing makespan is established， a dynamic allocation strategy of road network resources is proposed， and a two-layer algorithm composed of Cultural-Genetic Algorithm and Dijkstra Algorithm based on time window is designed to solve the model. The upper layer algorithm is the Cultural-Genetic Algorithm to optimize the scheduling of AGV， and the lower algorithm is the Dijkstra Algorithm based on time window for conflict-free route planning， which effectively reduces the makespan of horizontal transportation at the automated terminal and reduces the possibility of conflict. By comparing the dynamic allocation policy control method， speed control method and task priority control method based on road network resources， the effectiveness of the proposed method in solving the problem of horizontal transportation scheduling and path planning of automated container terminals is verified.

Key words: automated container terminal, horizontal transportation scheduling, path planning, cultural-genetic algorithm, dijkstra algorithm based on time window

Fig.1

Typical layout of automation terminal"

Fig.2

Algorithm flowchart"

Fig.3

Encoding scheme"

Table 1

Comparison of maximum completion time"

集装箱

数量

AGV

数量

运行

时间/s

CGAPSOGAGA

集装箱

数量

AGV

数量

运行

时间/s

CGAPSOGAGA
20428.4662562562516012272.611 9351 9472 048
30443.1191692493020020460.421 6621 7271 773
40461.561 2421 2501 30325020777.472 5912 6052 785
30544.8573975275725025792.382 0822 0952 125
40564.071 0241 0321 05030025911.722 4162 4402 441
50580.321 2311 2621 278300301 072.322 2112 2242 255
10010196.681 4321 5861 481350301 215.592 5852 6002 612
12010184.691 6171 6231 660350401 841.082 8202 8242 833
14010216.921 8431 8871 934400401 998.172 8672 9072 927
12012211.371 4051 4231 573500301 910.143 4713 5233 617
14012229.731 5901 6951 7752 0004053 217.4413 98014 06014 175

Fig.4

Convergence graph of different examples"

Fig.5

Congestion rate based on dynamic allocation strategy of road network resources for different AGV quantities"

Table 2

Comparison of different control methods"

控制方式AGV数量
20253040
路网资源动态分配策略0.018 60.019 90.021 50.032 3
速度控制方式0.020 10.022 40.026 70.041 2
任务优先级控制方式0.022 20.025 10.034 80.052 8

Fig.6

Blockage rate of different control methods"

Fig.7

Standard deviation of blockage rate for different control methods"

Fig.8

Changes in average blockage rate corresponding to different numbers of AGVs"

Fig.9

Average congestion rate of different scheduling algorithms"

Table 3

Blockage rates of different control methods under different scheduling algorithms"

多种控制方式下使用不同算法AGV数量
20253040
［A1］0.018 60.019 90.021 50.032 3
［B1］0.019 00.020 30.022 60.033 8
［C1］0.018 90.020 40.022 70.034 4
［A2］0.020 10.022 40.026 70.041 2
［B2］0.020 30.023 10.027 20.045 1
［C2］0.020 50.022 90.028 10.045 7
［A3］0.022 20.025 10.034 80.052 8
［B3］0.022 80.025 80.036 20.058 4
［C3］0.022 60.026 10.036 90.059 6
1 Zheng Y, Xiao Y, Seo Y. A tabu search algorithm for simultaneous machine/AGV scheduling problem[J]. International Journal of Production Research, 2014, 52(19): 5748-5763.
2 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, 2017, 12(3): No.e0169817.
3 Liu Y, Ji S, Su Z, et al. Multi-objective AGV scheduling in an automatic sorting system of an unmanned (intelligent) warehouse by using two adaptive genetic algorithms and a multi-adaptive genetic algorithm[J]. PloS One, 2019, 14(12): No.e0226161.
4 Chawla V K, Chanda A K, Angra S. Multi-load AGVs scheduling by application of modified memetic particle swarm optimization algorithm[J]. Journal of the Brazilian Society of Mechanical Sciences and Engineering, 2018, 40(9): 1-13.
5 Zou W Q, Pan Q K, Meng T, et al. An effective discrete artificial bee colony algorithm for multi-AGVs dispatching problem in a matrix manufacturing workshop[J]. Expert Systems with Applications, 2020, 161: No.113675.
6 Li G, Zeng B, Liao W, 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, 2018, 10(3): No.1687814018765560.
7 Boden P, Hahne H, Rank S, et al. Dispatching of multiple load automated guided vehicles based on adaptive large neighborhood search[C]∥Operations Research Proceedings 2019, Springer, Cham, 2020: 375-380.
8 滕浩,庄子龙,黄子钊,等.自动化码头水平运输调度的改进人工蜂群算法[J].计算机集成制造系统,2023,29(7):2449-2460.
Teng Hao, Zhuang Zi-long, Huang Zi-zhao, et al. Improved artificial bee colony algorithm for automatic terminal horizontal transportation scheduling[J].Computer Integrated Manufacturing Systems,2023,29(7):2449-2460.
9 朱承元,晏楠欣,刘裕旭.基于仿真优化的临时航线动态规划[J].计算机仿真,2022,39(11):60-64,91.
Zhu Cheng-yuan, Yan Nan-xin, Liu Yu-xu. Dynamic programming of temporary routes based on simulation optimization[J]. Computer Simulation, 2022, 39(11): 60-64,91.
10 Gan Y, Ji S, Zhao Q, et al. Scheduling problems of automated guided vehicles in automated container terminals using a genetic algorithm[C] ∥ IOP Conference Series: Materials Science and Engineering, IOP Publishing, 2020, 790(1): No.012069.
11 Luo J, Wu Y. Modelling of dual-cycle strategy for container storage and vehicle scheduling problems at automated container terminals[J]. Transportation Research Part E: Logistics and Transportation Review, 2015, 79: 49-64.
12 Jin J, Zhang X H. Multi agv scheduling problem in automated container terminal[J]. Journal of Marine Science and Technology, 2016, 24(1): 5.
13 Chen X, He S, Zhang Y, et al. Yard crane and AGV scheduling in automated container terminal: a multi-robot task allocation framework[J]. Transportation Research Part C: Emerging Technologies, 2020, 114: 241-271.
14 杨勇生,冯有勇,梁承姬,等.自动化集装箱码头自动导引小车与轨道式龙门起重机的协同调度[J].上海海事大学学报,2017,38(2):1-6.
Yang Yong-sheng, Feng You-yong, Liang Cheng-ji, et al. Integrated scheduling of automated guided vehicles and rail-mounted gantry cranes at automated container terminals[J].Journal of Shanghai Maritime University,2017,38(2):1-6.
15 Yang Z, Li C, Zhao Q. Dynamic time estimation based AGV dispatching algorithm in automated container terminal[C]∥2018 37th Chinese Control Conference (CCC),IEEE, 2018: 7868-7873.
16 Hu H, Chen X, Wang T, et al. A three-stage decomposition method for the joint vehicle dispatching and storage allocation problem in automated container terminals[J]. Computers & Industrial Engineering, 2019, 129: 90-101.
17 Luo J, Wu Y. Modelling of dual-cycle strategy for container storage and vehicle scheduling problems at automated container terminals[J]. Transportation Research Part E: Logistics and Transportation Review, 2015, 79: 49-64.
18 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, 2015, 86: 2-13.
19 Xin J, Negenborn R R, Corman F, et al. Control of interacting machines in automated container terminals using a sequential planning approach for collision avoidance[J]. Transportation Research Part C: Emerging Technologies, 2015, 60: 377-396.
20 Zhong M, Yang Y, Sun S, et al. Priority-based speed control strategy for automated guided vehicle path planning in automated container terminals[J]. Transactions of the Institute of Measurement and Control, 2020, 42(16): 3079-3090.
21 Guo K, Zhu J, Shen L. An improved acceleration method based on multi-agent system for AGVs conflict-free path planning in automated terminals[J]. IEEE Access, 2020, 9: 3326-3338.
22 Hu Y, Dong L, Xu L. Multi-AGV dispatching and routing problem based on a three-stage decomposition method[J]. Mathematical Biosciences and Engineering, 2020, 17(5): 5150-5172.
23 Wang X, Shi H, Zhang C. Path planning for intelligent parking system based on improved ant colony optimization[J]. IEEE Access, 2020, 8: 65267-65273.
24 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.
25 Farooq B, Bao J, Ma Q. Flow-shop predictive modeling for multi-automated guided vehicles scheduling in smart spinning cyber–physical production systems[J]. Electronics, 2020, 9(5): 799
26 李静,朱小林.集装箱码头上多自动引导车的调度和路径规划[J].计算机集成制造系统,2022,28(5):1449-1461.
Li Jing, Zhu Xiao-lin. Scheduling and path planning of multiple automatic guided vehicles in container terminals[J].Computer Integrated Manufacturing Systems,2022,28(5):1449-1461.
27 王占中,蒋婷,张景海.基于模糊双边界网络模型的道路运输效率评价[J].吉林大学学报:工学版,2023,53(2):385-395.
Wang Zhan-zhong, Jiang Ting, Zhang Jing-hai.Evaluation of road transportation efficiency based on fuzzy double frontiers network model[J].Journal of Jilin University(Engineering and Technology Edition),2023,53(2):385-395.
28 Zhong M, Yang Y, Dessouky Y, et al. Multi-AGV scheduling for conflict-free path planning in automated container terminals[J]. Computers & Industrial Engineering, 2020, 142: No.106371.
29 郑长江,胡欢,杜牧青.考虑枢纽失效的多式联运快递网络结构设计[J].吉林大学学报:工学版,2023,53(8):2304-2311.
Zheng Chang-jiang, Hu Huan, Du Mu-qing. Design of multimodal express delivery network structure considering hub failure[J].Journal of Jilin University(Engineering and Technology Edition),2023,53(8):2304-2311.
30 Miyamoto T, Inoue K. Local and random searches for dispatch and conflict-free routing problem of capacitated AGV systems[J]. Computers & Industrial Engineering, 2016, 91: 1-9.
[1] Shuai-shuai SUN,Chun-xiao FENG,Liang ZHANG. Path planning for multimodal quadruped robots based on discrete sampling [J]. Journal of Jilin University(Engineering and Technology Edition), 2024, 54(4): 1120-1128.
[2] Hao ZHENG,Li-jun YU,Peng-peng ZHI,Zhong-lai WANG. Dynamic obstacle avoidance strategy for flapping⁃wing micro air vehicles [J]. Journal of Jilin University(Engineering and Technology Edition), 2023, 53(9): 2732-2740.
[3] Zhen-yu WU,Xiao-fei LIU,Yi-pu WANG. Trajectory planning of unmanned system based on DKRRT*⁃APF algorithm [J]. Journal of Jilin University(Engineering and Technology Edition), 2023, 53(3): 781-791.
[4] Fan YANG,Zhi-qiang ZHAI,Yuan-yuan WANG,Zhong-xiang ZHU,Yue-feng DU,En-rong MAO. Design of assembly system for tractor transmission based on virtual reality [J]. Journal of Jilin University(Engineering and Technology Edition), 2023, 53(10): 3038-3044.
[5] Jia-xu ZHANG,Chen WANG,Jian ZHAO,Chun-yan BU. Path planning and tracking control for narrow parallel parking space [J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(5): 1879-1886.
[6] Jia-xu ZHANG,Xin-zhi WANG,Jian ZHAO,Zheng-tang SHI. Path planning and discrete sliding mode tracking control for high⁃speed lane changing collision avoidance of vehicle [J]. Journal of Jilin University(Engineering and Technology Edition), 2021, 51(3): 1081-1090.
[7] Xiao-jian HAN,Wei-qiang ZHAO,Li-jun CHEN,Hong-yu ZHENG,Yang LIU,Chang-fu ZONG. Local path planning of bus based on RS-RRT algorithm [J]. Journal of Jilin University(Engineering and Technology Edition), 2019, 49(5): 1428-1440.
[8] QIAN Li-jun, HU Wei-long, LIU Qing, WU Bing. Multiple segment method for automatic parking path planning and its key technology [J]. 吉林大学学报(工学版), 2016, 46(3): 785-791.
[9] ZHOU Bing-hai, ZHOU Qi. Impending deadlock-free scheduling method for unified AMHS in semiconductor FABs [J]. 吉林大学学报(工学版), 2016, 46(2): 595-601.
[10] KANG Bing, WANG Xi-hui, LIU Fu. Path planning of searching robot based on improved ant colony algorithm [J]. 吉林大学学报(工学版), 2014, 44(4): 1062-1068.
[11] LIU Hou-de, LIANG Bin, XU Wen-fu, MU Qing-tao, YU Jiang-hua. Motion prediction and autonomous path planning for spinning target capturing [J]. 吉林大学学报(工学版), 2014, 44(3): 757-764.
[12] LIU Gang, LIU Yu-bin, ZHAO Jie, ZHU Lei. Path planning for a new mine rescue robot base on visual tangent graphs [J]. 吉林大学学报(工学版), 2011, 41(4): 1107-1112.
[13] ZHAO Yang, ZHAO Ji, ZHANG Lei, JI Li-Zhe. Robotic blade grinding based on reverse engineering [J]. 吉林大学学报(工学版), 2009, 39(05): 1176-1180.
[14] YIN Li-ming1, JIA Yang2 . Algorithm evaluation for lunar rover path-planning [J]. 吉林大学学报(工学版), 2008, 38(04): 996-1000.
[15] CHEN Mou, XIAO Jian, JIANG Chang-sheng . Three dimensional path planning of UAV with improved ant algorithm [J]. 吉林大学学报(工学版), 2008, 38(04): 991-995.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright © Journal of Jilin University(Engineering and Technology Edition), All Rights Reserved.
Tel: +86-431-85095297　Fax: +86-431-85094074　E-mail: xbgxb@jlu.edu.cn
Powered by Beijing Magtech Co. Ltd