Large Neighborhood Local-Search for Block Relocation Problems

Block relocation problems are important optimization problem encountered at terminals, where containers are stored in stacks. It consists in determining the minimum number of container moves (retrieval and relocations) so as to empty the considered bay following a certain retrieval sequence. In this paper, we propose the first local search operator for these problems, based on the exploration of a large neighborhood by dynamic programming. 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.