自动化码头同时考虑握手区容量和位置的双ASC调度

doi:10.3778/j.issn.1002-8331.2305-0477

摘要/Abstract

摘要： 为了提高自动堆垛起重机（ASC）在自动化集装箱码头（ACT）存取箱同步模式下的调度效率，对不可跨越式双ASC在同一箱区的调度进行了研究，考虑了堆场海侧和陆侧存箱、取箱任务的混合堆放，同时考虑握手区容量和位置约束，建立了以最小化最大ASC完工时间为目标的双ASC调度混合整数规划（MIP）模型。以作业任务顺序为编码设计了排列编码的混沌离散粒子群优化算法（CDPSO），通过设计的混沌因子序列提高了算法收敛速度。通过改变不同的握手区位置和容量设计了三组实验，实验结果表明，最优的握手区位置和容量有助于降低双ASC的最大完工时间、冲突时间，同时，不同的算法对比实验表明所设计的算法可以有效求解双ASC调度混合整数规划模型，相较于其他算法，得到的最优解具有更优的双ASC的空载时间和最大完工时间。

关键词: 自动化集装箱码头（ACT）, 自动堆垛起重机（ASC）, 混沌离散粒子群优化算法（CDPSO）, 双ASC调度

Abstract: In order to improve the scheduling efficiency of automatic stacking crane (ASC) in the synchronous mode of container storage and retrieval at automated container terminal (ACT), the scheduling of uncrossable twin ASC in the same block is investigated, with the objective of minimizing the maximum ASC completion time, a twin ASC scheduling mixed integer programming (MIP) model is established, which considers both the constraints of the capacity and location of the handshake area, and the mixed stacking of storage and retrieval tasks on the seaside and landside of the yard. The chaotic discrete particle swarm optimization (CDPSO) algorithm with permutation coding is designed with the sequence of operational tasks as the coding, and the convergence speed of the algorithm is improved by the designed sequence of chaotic factors. Three sets of experiments are designed by changing different handshake area location and capacity, and the experimental results show that the optimal handshake area location and capacity help to reduce the maximum completion time and conflict time of twin ASC, and meanwhile, the comparison experiments of different algorithms show that the designed algorithm can effectively solve the twin ASC scheduling MIP model, and the optimal solution obtained has better no-load time and maximum completion time of twin ASC compared with other algorithms.

Key words: automated container terminal (ACT), automated stacking crane (ASC), chaotic discrete particle swarm optimization (CDPSO), twin ASC scheduling

马飞扬, 朱瑾. 自动化码头同时考虑握手区容量和位置的双ASC调度[J]. 计算机工程与应用, 204, 60(17): 302-311.

MA Feiyang, ZHU Jin. Twin ASC Scheduling Considering Capacity and Location of Handshake Area in Automated Terminal[J]. Computer Engineering and Applications, 204, 60(17): 302-311.

参考文献

[1] 常祎妹, 朱晓宁, 王力. 集装箱码头集成调度研究综述[J]. 交通运输工程学报, 2019, 19(1): 136-146.
CHANG Y M, ZHU X N, WANG L. Review on integrated scheduling of container terminals[J]. Journal of Traffic and Transportation Engineering, 2019, 19(1): 136-146.
[2] 李柏鹤, 蒋祖华, 陶宁蓉, 等. 基于混合优化算法的船舶分段堆场间调度研究[J]. 哈尔滨工程大学学报, 2018, 39(12): 2025-2032.
LI B H, JIANG Z H , TAO N R , et al. Research on dispatch of blocks between stockyards based on hybrid optimization algorithm[J]. Journal of Harbin Engineering University, 2018, 39(12): 2025-2032.
[3] VIS I F A, CARLO H J. Sequencing two cooperating automated stacking cranes in a container terminal[J]. Transportation Science, 2010, 44(2): 169-182.
[4] HE J, HUANG Y, YAN W. Yard crane scheduling in a container terminal for the trade-off between efficiency and energy consumption[J]. Advanced Engineering Informatics, 2015, 29(1): 59-75.
[5] HE J, CHANG D, MI W, et al. A hybrid parallel genetic algorithm for yard crane scheduling[J]. Transportation Research Part E: Logistics and Transportation Review, 2010, 46(1): 136-155.
[6] SHA M, ZHANG T, LAN Y, et al. Scheduling optimization of yard cranes with minimal energy consumption at container terminals[J]. Computers & Industrial Engineering, 2017, 113: 704-713.
[7] KOVALYOV M Y, PESCH E, RYZHIKOV A. A note on scheduling container storage operations of two non‐passing stacking cranes[J]. Networks, 2018, 71(3): 271-280.
[8] FAN H, PENG W, MA M, et al. Storage space allocation and twin automated stacking cranes scheduling in automated container terminals[J]. IEEE Transactions on Intelligent Transportation Systems, 2021, 23(9): 14336-14348.
[9] 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.
[10] HE J, XIAO X, YU H, et al. Dynamic yard allocation for automated container terminal[J]. Annals of Operations Research, 2022: 1-22.
[11] GUO X, HUANG S Y, HSU W J, et al. Dynamic yard crane dispatching in container terminals with predicted vehicle arrival information[J]. Advanced Engineering Informatics, 2011, 25(3): 472-484.
[12] LI W, WU Y, PETERING M E H, et al. Discrete time model and algorithms for container yard crane scheduling[J]. European Journal of Operational Research, 2009, 198(1): 165-172.
[13] 周亚民, 杨勇生, 仲美稣, 等. 自动化码头堆场穿越式双ASC调度[J]. 计算机工程与应用, 2021, 57(2): 251-256.
ZHOU Y M, YANG Y S, ZHONG M S, et al. Scheduling of crossing double ASC in yard of automated terminals[J]. Computer Engineering and Applications, 2021, 57(2): 251-256.
[14] 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.
[15] NG W C. Crane scheduling in container yards with inter-crane interference[J]. European Journal of Operational Research, 2005, 164(1): 64-78.
[16] 魏晨, 胡志华, 高超锋, 等. 自动化集装箱码头堆场内双起重机调度模型与算法[J]. 大连海事大学学报, 2015, 41(4): 75-80.
WEI C, HU Z H, GAO C f, et al. Scheduling model and algorithm of twin synchronized stacking cranes in stack yard of automated container terminal[J]. Journal of Dalian Maritime University, 2015, 41(4): 75-80.
[17] 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.
[18] HU Z H, TIAN X D, YIN Y Q, et al. Positioning a handshake bay for twin stacking cranes in an automated container terminal yard block[J]. Journal of Advanced Transportation, 2022, 2022: 1-17.
[19] CARLO H J, MARTíNEZ-ACEVEDO F L. Priority rules for twin automated stacking cranes that collaborate[J]. Computers & Industrial Engineering, 2015, 89: 23-33.
[20] 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.
[21] DORNDORF U, SCHNEIDER F. Scheduling automated triple cross-over stacking cranes in a container yard[J]. OR Spectrum, 2010, 32(3): 617-632.
[22] HAN X L, WANG Q, HUANG J W. Scheduling cooperative twin automated stacking cranes in automated container terminals[J]. Computers & Industrial Engineering, 2019, 128: 553-558.
[23] 程聪聪, 梁承姬, 李晔. 自动化集装箱港口考虑AGV伴侣的AGV调度优化问题研究[J]. 计算机应用研究, 2019, 36(8): 2349-2354.
CHENG C C, LIANG C J, LI Y. Study on AGV scheduling with considering AGV partner in automated container ports[J]. Application Research of Computers, 2019, 36(8): 2349-2354.
[24] KUMAR M M, OMKAR S N. Optimization of yard crane scheduling using particle swarm optimization with genetic algorithm operators(PSOGAO)[J]. Journal of Scientific & Industrial Research, 2008, 67(5): 335-339.
[25] WANG S, ZHENG K, ZHENG J, et al. An improved discrete particle swarm optimization for tugboat scheduling problem in container terminal[C]//Proceedings of the 2010 3rd International Conference on Information Management, Innovation Management and Industrial Engineering, 2010: 593-596.
[26] LUO J, WU Y. Scheduling of container-handling equipment during the loading process at an automated container terminal[J]. Computers & Industrial Engineering, 2020, 149: 106848.