基于规则集定向搜索算法的装船翻箱问题  

Loading relocation problem based on rule set based beam search algorithm

作　　者：杨小明[1] 周云鹏 耿志康 徐子奇[1] YANG Xiaoming;ZHOU Yunpeng;GENG Zhikang;XU Ziqi(Offshore Engineering Institute,Shanghai Maritime University,Shanghai 201306,China;College of Logistics Engineering,Shanghai Maritime University,Shanghai 201306,China)

机构地区：[1]上海海事大学离岸工程研究院,上海201306 [2]上海海事大学物流工程学院,上海201306

出　　处：《计算机集成制造系统》2023年第3期1040-1054,共15页Computer Integrated Manufacturing Systems

基　　金：上海市科学技术委员会科技创新行动计划重大专项资助项目(19511132502)。

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

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

分 类 号：TP399[自动化与计算机技术—计算机应用技术]