Kevin Tierney, de la University of Paderborn (Alemania). Impartirá la conferéncia: A New Lower Bound and an Iterative Deepening Braách-and-Bound Algorithm for Container Pre-Marshalling

Dia: 30 de Enero 2018,

Hora: 12:00

Lugar: Salón de Grados Facultat de Matemàtiques

A New Lower Bound and an Iterative Deepening Branch-and-Bound Algorithm for Container Pre-Marshalling

Abstract: 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..