路网资源分配下自动化码头水平运输调度与路径规划

doi:10.13229/j.cnki.jdxbgxb.20230467

摘要/Abstract

摘要：

为提高自动化集装箱码头水平运输的效率，减少自动导引车（AGV）在水平运输过程中的冲突，本文建立了以最小化最大完工时间为目标的多AGV的水平运输调度与路径规划模型，提出了一种路网资源动态分配策略，并设计了由文化遗传算法（CGA）与基于时间窗的Dijkstra算法所构成的一个双层算法对模型进行求解。上层算法即CGA用以优化AGV的调度，下层算法即基于时间窗的Dijkstra算法用以无冲突的路径规划，有效地减少了自动化码头水平运输的最大完工时间，降低了冲突的可能性。通过比较基于路网资源动态分配策略的控制方法、速度控制方法和任务优先级控制方法，验证了该方法在解决自动化集装箱码头水平运输调度与路径规划的有效性。

关键词: 自动化集装箱码头, 水平运输调度, 路径规划, 文化遗传算法, 基于时间窗的Dijkstra算法

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

朱瑾,黄琦. 路网资源分配下自动化码头水平运输调度与路径规划[J]. 吉林大学学报(工学版), 2024, 54(8): 2245-2255.

Jin ZHU,Qi HUANG. Automated terminal horizontal transportation scheduling and route planning under network resource allocation[J]. Journal of Jilin University(Engineering and Technology Edition), 2024, 54(8): 2245-2255.

图/表 12

图 1

图 2

图 3

表1

图4

图5

表2

图6

图7

图8

图9

表3

参考文献 30

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.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

集装箱数量	AGV 数量	运行时间/s	CGA	PSOGA	GA	集装箱数量	AGV 数量	运行时间/s	CGA	PSOGA	GA
20	4	28.46	625	625	625	160	12	272.61	1 935	1 947	2 048
30	4	43.11	916	924	930	200	20	460.42	1 662	1 727	1 773
40	4	61.56	1 242	1 250	1 303	250	20	777.47	2 591	2 605	2 785
30	5	44.85	739	752	757	250	25	792.38	2 082	2 095	2 125
40	5	64.07	1 024	1 032	1 050	300	25	911.72	2 416	2 440	2 441
50	5	80.32	1 231	1 262	1 278	300	30	1 072.32	2 211	2 224	2 255
100	10	196.68	1 432	1 586	1 481	350	30	1 215.59	2 585	2 600	2 612
120	10	184.69	1 617	1 623	1 660	350	40	1 841.08	2 820	2 824	2 833
140	10	216.92	1 843	1 887	1 934	400	40	1 998.17	2 867	2 907	2 927
120	12	211.37	1 405	1 423	1 573	500	30	1 910.14	3 471	3 523	3 617
140	12	229.73	1 590	1 695	1 775	2 000	40	53 217.44	13 980	14 060	14 175

控制方式	AGV数量
控制方式	20	25	30	40
路网资源动态分配策略	0.018 6	0.019 9	0.021 5	0.032 3
速度控制方式	0.020 1	0.022 4	0.026 7	0.041 2
任务优先级控制方式	0.022 2	0.025 1	0.034 8	0.052 8

多种控制方式下使用不同算法	AGV数量
多种控制方式下使用不同算法	20	25	30	40
［A1］	0.018 6	0.019 9	0.021 5	0.032 3
［B1］	0.019 0	0.020 3	0.022 6	0.033 8
［C1］	0.018 9	0.020 4	0.022 7	0.034 4
［A2］	0.020 1	0.022 4	0.026 7	0.041 2
［B2］	0.020 3	0.023 1	0.027 2	0.045 1
［C2］	0.020 5	0.022 9	0.028 1	0.045 7
［A3］	0.022 2	0.025 1	0.034 8	0.052 8
［B3］	0.022 8	0.025 8	0.036 2	0.058 4
［C3］	0.022 6	0.026 1	0.036 9	0.059 6

[1]	孙帅帅,冯春晓,张良. 基于离散采样的多模态四足机器人路径规划[J]. 吉林大学学报(工学版), 2024, 54(4): 1120-1128.
[2]	孙宝凤,刘娇娇,姚天姿,任欣欣. 考虑能量消耗的纯电动物流车柔性时间窗路径规划问题[J]. 吉林大学学报(工学版), 2023, 53(4): 1047-1059.
[3]	吴振宇,刘小飞,王义普. 基于DKRRT^*-APF算法的无人系统轨迹规划[J]. 吉林大学学报(工学版), 2023, 53(3): 781-791.
[4]	孙宝凤,姚天姿,陈雨琦. 考虑时变交通拥堵的纯电动物流车路径规划模型[J]. 吉林大学学报(工学版), 2023, 53(2): 468-479.
[5]	杨帆,翟志强,汪圆圆,朱忠祥,杜岳峰,毛恩荣. 基于虚拟现实的拖拉机变速箱装配系统设计[J]. 吉林大学学报(工学版), 2023, 53(10): 3038-3044.
[6]	姜斌祥,姜彤彤,王永雷. 基于文化遗传算法的毒品检验区块链共识算法优化[J]. 吉林大学学报(工学版), 2022, 52(3): 684-692.
[7]	张必达,闫强,张琳,张海瑞. 基于实时交通信息的电动汽车充换电路径规划方法[J]. 吉林大学学报(工学版), 2022, 52(10): 2333-2342.
[8]	张家旭,王晨,赵健,卜纯研. 面向狭小平行泊车位的路径规划与跟踪控制[J]. 吉林大学学报(工学版), 2021, 51(5): 1879-1886.
[9]	张家旭,王欣志,赵健,施正堂. 汽车高速换道避让路径规划及离散滑模跟踪控制[J]. 吉林大学学报(工学版), 2021, 51(3): 1081-1090.
[10]	韩小健,赵伟强,陈立军,郑宏宇,刘阳,宗长富. 基于区域采样随机树的客车局部路径规划算法[J]. 吉林大学学报(工学版), 2019, 49(5): 1428-1440.
[11]	钱立军, 胡伟龙, 刘庆, 吴冰. 多段式自动泊车路径规划及其关键技术[J]. 吉林大学学报(工学版), 2016, 46(3): 785-791.
[12]	周炳海, 周琪. 防潜在死锁的整体式自动物料搬运系统调度方法[J]. 吉林大学学报(工学版), 2016, 46(2): 595-601.
[13]	康冰, 王曦辉, 刘富. 基于改进蚁群算法的搜索机器人路径规划[J]. 吉林大学学报(工学版), 2014, 44(4): 1062-1068.
[14]	刘厚德,梁斌,徐文福,穆清涛,余江华. 自旋目标运动预测及自主捕获路径规划方法[J]. 吉林大学学报(工学版), 2014, 44(3): 757-764.
[15]	刘罡,刘玉斌,赵杰,朱磊. 基于可视切线图的新型煤矿救援机器人路径规划[J]. 吉林大学学报(工学版), 2011, 41(4): 1107-1112.