Skip to Main content Skip to Navigation
Journal articles

A branch and price approach for the container relocation problem

Abstract : 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.
Document type :
Journal articles
Complete list of metadata
Contributor : Dominique Feillet Connect in order to contact the contributor
Submitted on : Monday, December 8, 2014 - 2:24:50 PM
Last modification on : Wednesday, March 2, 2022 - 3:09:39 AM

Links full text



Elisabeth Zehendner, Dominique Feillet. A branch and price approach for the container relocation problem. International Journal of Production Research, Taylor & Francis, 2014, 52 (24), pp.7159-7176. ⟨10.1080/00207543.2014.965358⟩. ⟨emse-01092223⟩



Record views