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

摘要： 集装箱码头的自动化与智能化是港口物流发展新趋势,其中箱区自动化与智能化是其中的重点。自动化集装箱码头纵向大箱区布局模式使其翻箱问题成为制约码头效率提升的一个重要因素。针对自动化码头大箱区的贝内装船翻箱问题,提出基于规则集快速求解方法,并基于该方法构建相应的分支定界算法和定向搜索算法,同时分析了3种算法的时间复杂度。分支定界算法可求得该问题理论最优解,定向搜索算法能在短时内获得接近理论最优解。算例分析表明,基于规则集定向搜索算法和分支定界算法在小规模算例中都能高效求解该问题。在大规模算例中,基于规则集定向搜索算法仍然具有很高计算效率,同时优化结果接近理论最优解。通过与现有文献的数据对比分析,表明本文提出的基于规则集定向搜索算法在求解集装箱装船翻箱问题时具有更好的优化效果和更高的计算效率。

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