关键词: 集装箱码头, 堆场作业优化, 动态加权A星算法, 预翻箱问题, 翻箱位

Abstract: The increasing container throughput and the trend of larger size of container ships make container terminals face great challenges, forcing them to optimize the operation of their logistics system, constantly improve the efficiency of terminal operations and reduce operational costs. During the extraction of target containers, the wrong stacking of containers caused by cranes and ship delays will cause frequent marshalling operations in the storage yard, and further lead to port delays. Therefore, the study of container pre-marshalling plays an important role in improving the efficiency of terminal operation. The goal of the pre-marshalling operation is to eliminate all the wrong stacking containers in the bay as far as possible and reduce the total number of marshalling container by determining the optimal sequence that meets the constraints of the operation rules. Therefore, according to the requirements of practical application scenarios of container terminals, a dynamic weighted A^* algorithm is proposed and developed to solve an optimization model of thepre-marshalling problem considering the double-space rule. This process aims to identify the best sequence of container movements. The designed dynamic weighted A^* algorithm can effectively improve the ability to jump out of the local optimal solution in the optimization process. Based on the pre-marshalling operation of container loading process,the bay layout is abstracted into the state node of the A^* algorithm. The total cost function is calculated by the number of mis-overlay and the depth of iteration. The constructed dynamic weighting heuristic function controls the relocation according to the specific iteration situation. The dynamic weighting factor is introduced to control the direction of iteration, the lower bound weighted factor is introduced to dynamically adjust the lower bound of branches in each iteration, and a novel search branch rule is proposed to select the effective branch to search. Among them, the tie rule provides effective search direction for iteration; The branch rule ensures the efficiency of the algorithm by deleting the repetitive branch nodes and the branch nodes with high expected iterations. In order to ensure the orderly operation in the bay, the double-space rule stipulates that the container cannot be placed in the bayside position at the end of the iteration, and the first left rule is given priority to ensure the safe operation of the storage yard. The experiment is carried out through the example of Shanghai port and existing literature. The effectiveness and stability of the dynamic weighted A^* algorithm are verified by examples of the bay layout, operation process and mis-overlay container as the main data features. The results show that the design of dynamic weighted heuristic function could effectively improve the ability to jump out of optimal local solution. This method can effectively reduce the total number of relocations and improve the efficiency of pre-marshalling operations. When the number of stacks is higher than the height, the dynamic weighted A^* algorithm can improve the average performance by 20.3 %. The dynamic weighted A^* algorithm has better stability, which ensures that a large number of optimal solutions can be obtained in scenarios with different bay sizes. The proposed first branch rule and first left rule can select the optimal iterative branch for searching. The performance of the algorithm using the first branch rule is improved by 12.1%, while the performance of the algorithm without the first left rule is reduced by 3.7%. The performance of the dynamic weighted A^* algorithm considering the double-space rule is not significantly reduced, and a large number of optimal solutions can be obtained under the premise of guaranteeing the performance of the algorithm. The research results can be applied to pre-marshalling problem of container terminals with different operation technology and different bay layout. Furthermore, it can provide decision support for yard operation optimization.

Key words: container terminal, yard operation optimization, dynamic weighted A^* algorithm, the pre-marshalling problem, double-space