A branch and price approach for the container relocation problem

The objective of the container relocation problem is to retrieve a set of containers from the bay (a part of the yard) of a container terminal in a given order with a minimum number of parasite movements. Up to now, only few exact solution approaches exist for this problem. They are only able to solve small and medium sized instances since the number of variables increases exponentially with the number of containers and the bay size. To overcome this problem, we introduce the first column generation approach for this problem and embed it into a branch and price procedure. We also introduce a new upper bound on the number of relocations based on the values of dual variables. Computational results show that our column generation approach provides a tight gap and solves small and medium instances with a small subset of columns within few iterations. But, the time spent on solving the subproblem prevents solving larger instances. Finding a way to reduce the time spent on the subproblem constitutes the next step of this work.