This technical report presents new solution methods for the block relocation problem (BRP). Although most 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 branch-and-bound algorithm that outperforms the best existing exact method and provides new optimal solutions. The branch-and-bound algorithm is adapted to tackle the restricted BRP as well, again outperforming existing methods for that problem.