Block (Container) Relocation Problem

[Description]

The block (container) relocation problem is to find an optimal sequence of crane operations to retrieve blocks (containers) according to their given priorities.

[Papers]

[TT16] S. Tanaka and K. Takii. A faster branch-and-bound algorithm for the block relocation problem. IEEE Transactions on Automation Science and Engineering 13(1), pp. 181-190, 2016. DOI: 10.1109/TASE.2015.2434417

[TM18] S. Tanaka and F. Mizuno. An exact algorithm for the unrestricted block relocation problem. Computers & Operations Research, vol. 95, pp. 12-31, 2018. DOI: 10.1016/j.cor.2018.02.019

[TV22] S. Tanaka and S. Voß. An exact approach to the restricted block relocation problem based on a new integer programming formulation. European Journal of Operational Research. vol. 296, no. 2, pp. 485-503, 2022. DOI: 10.1016/j.ejor.2021.03.062

[JT23] B. Jin and S. Tanaka. An exact algorithm for the unrestricted container relocation problem with new lower bounds and dominance rules. European Journal of Operational Research, vol. 304, no. 2, pp. 494-514, 2023. DOI: 10.1016/j.ejor.2022.04.006

[Download]

Branch-and-bound algorithms
- restricted block relocation problem
  - distinct (unique) priorities
    - v1.01 [TT16] [source code]
    - v1.11 [TM18] [source code]
    - v1.3 [TV21] [source code] (Nov 17, 2022)
  - duplicate (group) priorities
    - v1.02 [TT16] [source code]
- unrestricted block relocation problem

distinct (unique) priorities
- v1.01 [TM18] [source code]

IP-based algorithm
- restricted block relocation problem
  - distinct (unique) priorities
    - v1.0 [TV21] [source code] (April 9, 2021)

[Benchmark instances]

Instances with distinct priorities by Zhu et al. [ZQLZ12] ~~(downloadable from~~ ~~Wenbin Zhu's page~~)
- [Zhu_dataset.zip]
CV instances with distinct prioritiies by Caserta and Voß [CV09]
- (external link)
Instances with duplicate (group) priorities generated from those by Zhu et al. [TT16]
- [dup_dataset.zip]

[ZQLZ12] W. Zhu, H. Qin, A. Lim, H. Zhang. Iterative deepening A* algorithms for the container relocation problem. IEEE Transactions on Automation Science Engineering 9(4), pp. 710-722, 2012.

[CV09] M. Caserta, S. Voß. A corridor method-based algorithm for the pre-marshalling problem. Lecture Notes in Computer Science 5484, pp. 788--797, 2009.

[Data file format]

[number of stacks] [number of blocks]

[number of blocks in stack 1] [priority of block (1, 1)] [priority of block (1, 2)] ...

[number of blocks in stack 2] [priority of block (2, 1)] [priority of block (2, 2)] ...

...

[Demo]

Block Relocation Puzzle (external link)

Restricted Block Relocation Puzzle (external link)