The realization-independent reallocation heuristic for the stochastic container relocation problem

The container relocation problem is one of the most relevant problems in the logistics of containers. It consists in finding the minimum number of moves that are needed to retrieve all the containers located in a bay, according to a given retrieval order. Unfortunately, such an order may be subject to uncertainty. The variant of the problem that takes such issue into account is known as the stochastic container relocation problem. In this case, the containers are partitioned into batches. The retrieval order among the batches is known, while that of the containers of the same batch is uncertain and becomes available only when the last container of the previous batch is retrieved. The solution approaches proposed so far in the literature present a common pitfall concerning the complexity of the produced solutions, whose size can grow exponentially with the number of blocks. Here we present a new ad hoc heuristic approach for the problem that applies a suitable reduction of the solution space. Computational experiments on a set of instances taken from the literature are performed. The proposed methodology is able to solve instances that was not possible to solve before. This makes the procedure very appealing also for being applied in practice. Statistics showing how the performances are affected by the size of the instances are also presented.