关键词: 装船翻箱问题, 定向搜索算法, 分支定界算法, 自动化集装箱码头

Abstract: Automation and intellectualization is the new trend in the development of port logistics,especially for yard operation.In the Automated Container Terminal (ACT),the vertical and large size yard block makes the relocation problem to be an important factor restricting the improvement of efficiency.Aiming at the Loading Relocation Problem (LRP) in the large size Bay of ACT,a Rule Set (RS) based algorithm was proposed,based on which the corresponding Branch and Bound (B&B) algorithm and Beam Search (BS) algorithm were constructed,and the time complexity of the algorithms was analyzed.The B&B algorithm could obtain the theoretical optimal solution,and the BS algorithm could obtain the approximate theoretical optimal solution in a short time.The case study showed that the BS algorithm and the B&B algorithm could solve the problem efficiently in small-scale cases.In large-scale cases,the BS algorithm still had high computational efficiency,and the result was close to the optimal solution.The comparative analysis with the results of the existing literature showed that the BS algorithm had a better optimal effect and computational efficiency.

Key words: loading relocation problem, beam search algorithm, branch and bound algorithm, automated container terminal