A three-stage heuristic for optimizing container relocations in maritime container terminals

The Container Relocation Problem (CRP) is one of the most important optimization problems in maritime container terminals. The objective is to minimize the number of relocation operations for retrieving containers in a sequence. If the container to be retrieved next is not at the top of a stack, unproductive relocations have to be carried out. Due to the large number of containers handled by busy terminals, a slight reduction in relocation rates can result in significant savings in operating costs. Most of the existing heuristics make relocation decisions for the blocking containers one by one, based on simple indicators. In this article, we propose a Three-Stage Heuristic (3SH) that extends the decision horizon to multiple containers to achieve a higher-quality solution. Computational experiments are conducted on 3 sets of benchmark instances, and the results show that the proposed heuristic outperforms the state-of-the-art heuristics documented in the research literature.