Embedded Files
[Description]
[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]
[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]
[Download]
Branch-and-bound algorithms
restricted block relocation problem
distinct (unique) priorities
v1.01 [TT16] [source code]
v1.11 [TM18] [source code]
v1.3 [TV22] [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]
[JT23] [source code] (Bo Jin's GitHub page)
IP-based algorithm
restricted block relocation problem
distinct (unique) priorities
v1.0 [TV22] [source code] (April 9, 2021)
[Benchmark instances]
[Benchmark instances]
Instances with distinct priorities by Zhu et al. [ZQLZ12] (downloadable from Wenbin Zhu's page)
CV instances with distinct prioritiies by Caserta and Voß [CV09]
Instances with duplicate (group) priorities generated from those by Zhu et al. [TT16]
[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]
[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]
[Demo]
Block Relocation Puzzle (external link)
Restricted Block Relocation Puzzle (external link)
Page updated
Google Sites
Report abuse