Yard Crane Scheduling Method Based on Deep Reinforcement Learning for the Automated Container Terminal

doi:10.3901/JME.2024.06.044

Abstract

Abstract: As the core working machinery of automated terminal yard, the dispatching of yard crane is the key to improve the efficiency of container operation. In order to minimize the waiting time of AGVs and external container trucks, a mathematical programming model for the yard crane scheduling problem is established considering complex spatio-temporal coupling characteristics and high dynamic, and a novel deep reinforcement learning method is proposed to solve the problem. The algorithm describes the yard environment close to reality through the agent definition, and improves the ability of extracting hidden state patterns through pointer network, attention mechanism and A-C architecture in the interaction design between the agent and the environment. Experiments are carried out on examples of different scales based on the actual data of Yangshan Phase IV Automated Terminal. The results show that the proposed algorithm can provide an approximately optimal crane scheduling scheme in a relatively short time, and the performance of it is about 17% better compared with state-of-art heuristic rule algorithms. Therefore, the proposed scheduling method is effective and superior, and it can provide dynamic decision support for yard operation in practice.

Key words: automated container terminal, yard, yard crane scheduling, deep reinforcement learning

CLC Number:

U691

WANG Wuyin, HUANG Zizhao, ZHUANG Zilong, FANG Huaijin, QIN Wei. Yard Crane Scheduling Method Based on Deep Reinforcement Learning for the Automated Container Terminal[J]. Journal of Mechanical Engineering, 2024, 60(6): 44-57.

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

URL: http://www.cjmenet.com.cn/EN/10.3901/JME.2024.06.044

http://www.cjmenet.com.cn/EN/Y2024/V60/I6/44

References

[1] 黄子钊，庄子龙，滕浩，等. 自动化码头出口箱箱位分配优化超启发式算法[J]. 计算机集成制造系统，2022，28(8)：2619-2632. HUANG Zizhao，ZHUANG Zilong，TENG Hao，et al. Optimization of outbound container space assignment in automated container terminals based on hyper-heuristic[J]. Computer Integrated Manufacturing Systems，2022，28(8)：2619-2632.
[2] BOYSEN N，BRISKORN D，MEISEL F. A generalized classification scheme for crane scheduling with interference[J]. European journal of operational research， 2017，258(1)：343-357.
[3] NOSSACK J，BRISKORN D，PESCH E. Container dispatching and conflict-free yard crane routing in an automated container terminal[J]. Transportation Science， 2018，52(5)：1059-1076.
[4] EILKEN A. A Decomposition-based approach to the scheduling of identical automated yard cranes at container terminals[J]. Journal of Scheduling，2019，22(5)：1-25.
[5] KRESS D，DORNSEIFER J，JAEHN F. An exact solution approach for scheduling cooperative gantry cranes[J]. European Journal of Operational Research，2019，273(1)：82-101.
[6] CORDEAU J F, LEGATO P, MAZZA R M, et al. Simulation-based optimization for housekeeping in a container transshipment terminal[J]. Computers & Operations Research, 2015, 53：81-95.
[7] GHAREHGOZLI A H，VERNOOIJ F G，ZAERPOUR N. A simulation study of the performance of twin automated stacking cranes at a seaport container terminal[J]. European Journal of Operational Research，2017，261(1)：108-128.
[8] JAEHN F，KRESS D. Scheduling cooperative gantry cranes with seaside and landside jobs[J]. Discrete Applied Mathematics，2018，242：53-68.
[9] EHLEITER A，JAEHN F. Scheduling crossover cranes at container terminals during seaside peak times[J]. Journal of Heuristics，2018，24(6)：899-932.
[10] GHAREHGOZLI A H，LAPORTE G，YU Y，et al. Scheduling twin yard cranes in a container block[J]. Transportation Science，2015，49(3)：686-705.
[11] HU Z H，SHEU J B，LUO J X. Sequencing twin automated stacking cranes in a block at automated container terminal[J]. Transportation Research Part C： Emerging Technologies，2016，69：208-227.
[12] LU H，WANG S. A Study on multi-ASC scheduling method of automated container terminals based on graph theory[J]. Computers & Industrial Engineering，2019，129：404-416.
[13] ZHENG F，MAN X，CHU F，et al. Two yard crane scheduling with dynamic processing time and interference[J]. IEEE Transactions on Intelligent Transportation Systems，2018，19(12)：3775-3784.
[14] HAN X，WANG Q，HUANG J. Scheduling cooperative twin automated stacking cranes in automated container terminals[J]. Computers & Industrial Engineering，2019，128：553-558.
[15] HE J，TAN C，ZHANG Y. Yard crane scheduling problem in a container terminal considering risk caused by uncertainty[J]. Advanced Engineering Informatics，2019，39：14-24.
[16] ZHENG F，MAN X，CHU F，et al. A two-stage stochastic programming for single yard crane scheduling with uncertain release times of retrieval tasks[J]. International Journal of Production Research，2019，57(13)：4132-4147.
[17] SUTTON R S，BARTO A G. Reinforcement learning： An introduction[M]. Cambridge：MIT Press，2018.
[18] LIN X，BELING P A，COGILL R，et al. Multiagent inverse reinforcement learning for two-person zero-sum games[J]. IEEE Transactions on Computational Intelligence and AI in Games，2017，10(1)：56-68.
[19] NAZARI M，OROOJLOOY A，SNYDER L V，et al. Reinforcement learning for solving the vehicle routing problem[C]// Advances in Neural Information Processing Systems 31. Montréal：Neural Information Processing Systems，2018：9861-9871.
[20] HWANG I，JANG Y J. Q(λ) learning-based dynamic route guidance algorithm for overhead hoist transport systems in semiconductor fabs[J]. International Journal of Production Research，2020，58(4)：1199-1221.
[21] 刘朝阳，穆朝絮，孙长银. 深度强化学习算法与应用研究现状综述[J]. 智能科学与技术学报，2020，2(4)：314-326. LIU Zhaoyang，MU Chaoxu，SUN Changyin. An overview on algorithms and applications of deep reinforcement learning[J]. Chinese Journal of Intelligent Science and Technology，2020，2(4)：314-326.
[22] 肖鹏飞，张超勇，孟磊磊，等. 基于深度强化学习的非置换流水车间调度问题[J]. 计算机集成制造系统，2021，27(1)：192-205. XIAO Pengfei，ZHANG Chaoyong，MENG Leilei，et al. Non-permutation flow shop scheduling problem based on deep reinforcement learning[J]. Computer Integrated Manufacturing Systems，2021，27(1)：192-205.
[23] VINYALS O，FORTUNATO M，JAITLY N. Pointer networks[C]//Advances in Neural Information Processing Systems 28：International Conference on Neural Information Processing Systems，2015：1-8.
[24] 范华丽，熊禾根，蒋国璋，等. 动态车间作业调度问题中调度规则算法研究综述[J]. 计算机应用研究，2016，33(3)：648-653. FAN Huali，XIONG Hegen，JIANG Guozhang，et al. A review of scheduling rule algorithms in dynamic job shop scheduling problem[J]. Computer Application Research， 2016，33(3)：648-653.
[25] LIU Wenqian，ZHU Xiaoning，WANG Li，et al. Optimization approach for yard crane scheduling problem with uncertain parameters in container terminals[J]. Journal of Advanced Transportation，2021(3)：1-15.
[26] EHLEITER A，JAEHN F. Scheduling crossover cranes at container terminals during seaside peak times[J]. J. Heuristics，2018，24：899-932.