Solving real-world sized container pre-marshalling problems with an iterative deepening branch-and-bound algorithm

- A new exact algorithm for the container pre-marshalling problem that solves real-world sized problems.
- Tightened lower bound procedure improving on the bound from Bortfeldt and Forster.
- An effective heuristic procedure for completing a partial pre-marshalling solution.
- Optimal solutions for 161 previously unsolved pre-marshalling instances.

Container terminals around the world regularly re-sort the containers they store according to their retrieval times in a process called pre-marshalling, thus ensuring containers are efficiently transferred through the terminal. State-of-the-art algorithms struggle to find optimal solutions for real-world sized pre-marshalling problems. To this end, we introduce an improved exact algorithm using an iterative deepening branch and bound search, including a novel lower bound computation, a new branching heuristic, new dominance rule and a new greedy partial solution completion heuristic. Our approach finds optimal solutions for 161 more instances than the state-of-the-art algorithm on two well known, difficult pre-marshalling datasets, and solves all instances in three other datasets in just several seconds. Furthermore, we find optimal solutions for a majority of real-world sized instances, and feasible solutions with very low relaxation gaps on those instances where no optimal could be found.