New insights on the block relocation problem

- New algorithms are developed for the unrestricted block relocation problem (BRP).
- New larger instances are introduced and new fast methods are developed, that scale well and outperform all existing methods.
- A new lower bound for the BRP is proposed.
- An extensive experimental study assesses the performance of each introduced algorithm.
- Highlight of the revision: following a comment from the reviewer, we now use a non-parametric statistical technique to highlight significant differences in performances among heuristics and partially rank the heuristics.

This article presents new methods for the block relocation problem (BRP). Although much of the existing work focuses on the restricted BRP, we tackle the unrestricted BRP, which yields more opportunities for optimisation. Our contributions include fast heuristics able to tackle very large instances within seconds, fast metaheuristics that provide very competitive performance on benchmark data sets, as well as a new lower bound that generalises existing ones. We embed it in a branch-and-bound algorithm, then assess the influence of various factors on the efficiency of branch-and-bound algorithms for the BRP.