Improving the Performance of Relocation Rules for the Container Relocation Problem with the Rollout Algorithm

Container relocation problems represent a significant challenge in maritime ports and terminals. To address this challenge, there is a growing demand for innovative and efficient solution methods. While exact and metaheuristic methods often yield superior results, they require a substantial time to reach good solutions. On the other hand, relocation rules (RRs) represent simple yet efficient constructive heuristics. Nevertheless, RRs suffer from two main issues, they are difficult to design for different problem variants and their performance is quite limited. To tackle the first issue, genetic programming is commonly used to automatically generate RRs. However, regarding the second issue, there is no single approach by which their performance can be improved. In this study, we investigate the application of the rollout algorithm in combination with manually and automatically generated RRs to improve their performance. The idea of using the rollout algorithm is to balance between an exhaustive and heuristic search, where RRs are used to determine the most appropriate decision in each step of the rollout algorithm. The results demonstrate that with the use of the rollout algorithm it is possible to significantly improve the performance of RRs, albeit with increased execution time. Nevertheless, even in this case, the method can still solve all the considered problems within seconds, underscoring its effectiveness.