A multi-strategy integrated heuristic algorithm for the container relocation problem in automated container terminal yards

As the operational scale of automated container terminals continues to expand, the impact of the container relocation problem on operational efficiency and cost has be-come increasingly significant. To address the issues of excessive relocations and low operational efficiency during container retrieval within a bay, a container relocation optimization model for the yard is developed. On this basis, a bay-oriented heuristic algorithm is proposed by incorporating practical operational rules and operational experience. The algorithm prioritizes empty stacks, non-blocking stacks, and stacks with the minimum number of blocking containers. It further integrates the nearest-placement rule and safety height constraints to achieve efficient and rational relocation decisions for blocking containers. Numerical experiments with different problem scales are conducted to validate the effectiveness of the proposed method. The results show that, in small-scale instances, the proposed algorithm effectively reduces the number of relocations. In large-scale instances, its advantage becomes more pronounced as the problem size increases. Compared with the traditional nearest-placement rule, the proposed algorithm consistently achieves superior performance across different scales: the number of relocations is reduced by up to 15, the relocation rate decreases by an average of 56%, and the operational cost is reduced by approximately 35.85% on average.