## Block Relocation Problem

### Definition

Let S be a system (yard) defined by w stacks of capacity (in terms of available slots/tiers) h and let {1,...,n} be a set of n blocks located in the slots of the w stacks. A reshuffle operation (or simply a reshuffle ) is a movement of a block from a stack to another, while a retrieval is a movement of a block from a stack to the outside of the system. The stacks can store blocks according to a last-in / first-out policy. When a block has to be moved in one of the stacks, it has to be allocated in the first slot available from the bottom to the top. In a stack only the topmost block is accessible and when a block has to be retrieved all the blocks above it have to be reshuffled. A block is a blocking one if it is located in an upper slot and in the same stack of a block with an higher retrieval priority.

The Block Relocation Problem (BRP) consists in deciding where to reallocate every block that is moved by a reshuffle operation, in order to minimize the total number of reshuffles needed to retrieve all the blocks to the retrieval order (1,...,n).

Figure 1 gives an example of the BRP with a system defined by w = 3 stacks, h = 3 available slots for each stack, and n = 6 blocks. Starting from the initial yard, where blocks 5 and 6 are blocking, the sequence of movements of an optimal solution is reported. At each step, the next block to be moved with a reshuffle or a retrieval operation is highlighted in gray. The minimum number of reshuffled required is equal to 3: one reshuffle of block 6 to retrieve block 1, one reshuffle of block 5 to retrieve block 2, and one reshuffle of block 6 to retrieve block 4.

### Code of the algoritms

The code of the Branch and Cut method and the Bounded Beam Search heuristic can be downloaded here (Gurobi optimization software is required).

### Benchmark Instances

All the instances are available in the following format:

w h n

k1   m11  m12  ...  m1k1

k2   m21  m22  ...  m2k2

k w   m w 1  m w 2  ...  m w k w

hello

w : number of stacks

h : number of slots for each stack

n : number of blocks

k i : number of blocks in stack i

m sj : priority order of item located in slot j of stack s

hello

- GROUP 1  (w = 6, h∈[2;5], n∈[3;21])

[1] Y. Wan, J. Liu, and P-C. Tsai. The assignment of storage locations to containers for a container stack. Naval Research Logistics, 56(8):699–713, 2009.

- GROUP 2  (w∈[3;12], h∈[3;12], n∈[7;133])

[2] K. C. Wu and C. J. Ting. A beam search algorithm for minimizing reshuffle operations at container yards. International Conference on Logistics and Maritime Systems, 2010.

- GROUP 3  (w∈[16;160], h∈[6;8], n∈[70;720])

[3] Y. Lee and Y. L. Lee. A heuristic for retrieving containers from a yard. Computers & Operations Research, 47:1139–1147, 2010.

- GROUP 4  (w∈[3;100], h∈[5;102], n∈[9;10000])

[4] M. Caserta, S. Voß, and M. Sniedovich. Applying the corridor method to a blocks relocation problem. OR Spectrum, 33(4):915–929, 2011.

- GROUP 5  (w∈[3;7], h∈[4;7], n∈[6;36])

[5] T. Unluyurt and C. Aydin. Improved rehandling strategies for the container retrieval process. Journal of Advanced Transportation, 46(4):378–393, 2012.

- GROUP 6  (w∈[6;10], h∈[3;7], n∈[15;69])

[6] W. Zhu, H. Qin, A. Lim, and H. Zhang. Iterative deepening A* algorithms for the container relocation problem. IEEE Transactions on Automation Science and Engineering, 9:710–722, 2012.

- LBRI  (w∈[50;1000], h∈[4;10], n∈[196;9999])

### The Bounded Beam Search heuristic algorithm for the restricted Block Relocation Problem

Computational results of the Bounded Beam Search algorithm on each benchmark instances are available here

### The Branch and Cut exact algorithm for the restricted Block Relocation Problem

Computational results of the Branch and Cut algorithm on the sets GROUP 4 and GROUP 6 are available in .pdf fomat or in .csv