  The unrestricted block relocation problem is an important optimization
problem encountered at terminals, where containers are stored in stacks. It
consists in determining the minimum number of container moves so as to empty
the considered bay following a certain retrieval sequence. A container move can
be either the retrieval of a container or the relocation of a certain container
on top of a stack to another stack. The latter types of moves are necessary so
as to provide access to containers which are currently not on top of a stack.
They might also be useful to prepare future removals. In this paper, we propose
the first local search type improvement heuristic for the block relocation
problem. It relies on a clever definition of the state space which is explored
by means of a dynamic programming algorithm so as to identify the locally
optimal sequence of moves of a given container. Our results on large benchmark
instance reveal unexpectedly high improvement potentials (up to 50%) compared
to results obtained by state-of-the-art constructive heuristics.
