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
Download
- 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