The stacking problem is a hard combinatorial optimization problem with high practical interest in, e.g. steel storage or container port operations. In this problem, a set of items is stored in a warehouse for a period of time, using a crane to pile them in stacks. Since entrance and exit of items occurs in arbitrary order, items may have to be relocated in order to reach and deliver other items below them. The objective of the problem is to find sequences of movements having the minimum number of movements.

We propose two heuristic methods to solve the problem, and study the scalability of an exact approach. The two heuristic approaches are a multiple simulation algorithm using semi-greedy construction heuristics, and a stochastic best-first tree search algorithm. The two methods are compared in a set of challenging instances, confirming the effectiveness of the proposed tree search approach.