The block (container) pre-marshalling problem is to sort blocks (containers) stacked in tiers for future retrieval with a minimum number of relocations.
[TK18] S. Tanaka, K. Tierney. Solving real-world sized container pre-marshalling problem with an iterative deepening branch-and-bound algorithm. European Journal of Operational Research 264(1), pp. 165-180, 2018. DOI: 10.1016/j.ejor.2017.05.046
A branch-and-bound algorithm for the container pre-marshalling problem
pmp-1.0 [source code]
pmp-1.01 [source code]
pmp-1.02 [source code]
[Notes]
There is a bug in pmp-1.0. The right stacks from the second empty stack are not scanned as a destination stack of a move.
According to [JY21], the code has been further modified. The current version is 1.02.
[JY21] B. Jin and M. Yu. Note on the dominance rules in the exact algorithm for the container pre-marshalling problem by Tanaka & Tierney (2018). European Journal of Operational Research 293(2), pp. 802-807, 2021. DOI: 10.1016/j.ejor.2020.12.041
BF instances by Bortfeldt and Forster [BF12]
[BF.zip]
EMM instances by Expósito-Izquierdo et al. [EMM12]
[EMM_regenerated.zip] (regenerated by Tierney et al. [TPV17])
BZ instances by van Brink and van der Zwaan [BZ14]
[BZ_regenerated.zip] (regenerated by us [TK18])
ZJY instances by Zhang et al. [ZJY15]
[ZJY_original.zip] (original)
[ZJY_converted.zip] (reformatted for our program)
[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.
[BF12] A. Bortfeldt, F. Forster. A tree search procedure for the container pre-marshalling problem. European Journal of Operational Research 217(3), pp. 531-540, 2012.
[EMM12] C. Expósito-Izquierdo, B. Melián-Batista, M. Moreno-Vega. Pre-marshalling problem: Heuristic solution method and instances generator. Expert Systems with Applications 39(9), pp. 8337–8349, 2012.
[TPV17] K. Tierney, D. Pacino, S. Voß. Solving the pre-marshalling problem to optimality with A* and IDA*. Flexible Services and Manufacturing Journal 29(2), pp. 223-259, 2017.
[BZ14] M. van Brink, R. van der Zwaan. A branch and price procedure for the container premarshalling problem. Lecture Notes in Computer Science 8737, pp.798-809, 2014.
[ZJY15] R. Zhang, Z. Jiang, W. Yun. Stack pre-marshalling problem: A heuristic-guided branch-and-bound algorithm. International Journal of Industrial Engineering: Theory, Applications and Practice 22(5), 509–523, 2015.
Pre-Marshalling Puzzle (external link)