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

摘要： 为改善堆场作业效率,提出考虑堆场翻箱位规则的集装箱预翻箱作业优化模型并使用动态加权A星算法进行求解,进而确定满足作业规则限制的最优移动序列。基于集装箱装船过程的预翻箱作业,将预翻箱作业过程的贝位布局抽象为A星算法的状态节点,以错误堆叠箱和翻箱迭代深度计算总成本函数,引入动态加权因子控制翻箱迭代方向,提出新颖的搜索分支规则选择有效分支进行搜索。通过上海港码头和相关文献的算例进行实验,结果表明,设计的动态加权启发式函数能够有效改善寻优过程中跳出局部最优解的能力,验证了考虑堆场运作规则-翻箱位规则的算法有效性和稳定性。研究成果能够普遍适用于作业工艺和贝位布局不同的集装箱码头预翻箱作业,能够为堆场运作优化提供决策参考。

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