Block (Container) Pre-marshalling Problem

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

• CV instances by Caserta and Voß [CV09]

  • (external link)

• BF instances by Bortfeldt and Forster [BF12]

  • [BF.zip]

• EMM instances by Expósito-Izquierdo et al. [EMM12]

  • (regenerated by Expósito-Izquierdo et al., external link)

  • [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)