The Optimization of Container Relocation in Terminal Yards: A Computational Study Using Strategy-Iterative Deepening Branch-and-Bound Algorithm

Abstract

Container relocation operations at terminal yards represent a fundamental pillar in the optimization of stowage scheduling during vessel loading, serving as a critical component of port operational efficiency. This paper focuses on the restricted container relocation problem (RCRP), in which the objective is to minimize the number of relocations for retrieving all containers from a bay under a predetermined retrieval sequence. A strategy-oriented algorithm (SOA) was proposed to address this issue, and a strategy-iterative deepening branch-and-bound algorithm (S-IDB&B) was constructed based on this algorithm. Among them, the SOA can quickly find feasible solutions to the problem, while the S-IDB&B algorithm can find the optimal solution to the problem and can also set an early stopping mechanism to obtain high-quality solutions in a shorter period of time. Comparative computational experiments demonstrate that the strategy-iterative deepening branch-and-bound algorithm finds optimal solutions for all small-scale instances within 0.01 s and achieves optimal solutions for over 80% of medium-to-large-scale instances, and it outperforms existing exact algorithms (solve larger scale instances with shorter computation time); moreover, when equipped with the early stopping mechanism, it yields higher solution quality than existing heuristic algorithms (the maximum accuracy deviation is around 20%) while maintaining comparable computation times.