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 theminimum 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 isknown as the stochastic container relocation problem. In this case, the containers are partitioned into batches. The retrievalorder among the batches is known, while that of the containers of the same batch is uncertain and becomes available onlywhen the last container of the previous batch is retrieved. The solution approaches proposed so far in the literature presenta common pitfall concerning the complexity of the produced solutions, whose size can grow exponentially with the numberof blocks. Here we present a new ad hoc heuristic approach for the problem that applies a suitable reduction of the solutionspace. Computational experiments on a set of instances taken from the literature are performed. The proposed methodology isable to solve instances that was not possible to solve before. This makes the procedure very appealing also for being appliedin practice. Statistics showing how the performances are affected by the size of the instances are also presented.