Análisis del Block Relocation Problem

Abstract

[ES] El Block Relocation Problem es un problema de gran interés en la logística actual. Este problema consiste en minimizar el número de recolocaciones necesarias para extraer un conjunto de bloques apilados en un orden determinado donde solo se pueden reubicar los bloques de mayor altura. Una de las principales aplicaciones aparece en las terminales portuarias. Aquí, los bloques son los contenedores que están apilados en los bloques. Optimizar la extracción supone un gran ahorro en el tiempo de grúa de patio y por tanto en eficiencia para la terminal. En este TFM se estudiará el Block Relocation Problem desde varios puntos de vista. Primero se tratará de encontrar el mejor modelo para la resolución de manera exacta en la bibliografía actual y se intentará mejorar. Después, veremos las limitaciones que presentan estos modelos a la hora de resolver casos reales y se propondrá como alternativa una heurística. Aquí se procederá de manera similar. Comenzando por comparar las mejores heurísticas propuestas en la actualidad e intentar mejorarlas.

[EN] The Block Relocation Problem is a problem of great interest in current logistics. This problem consists of minimizing the number of relocations required to extract a set of blocks stacked in a certain order where only the taller blocks can be relocated. One of the main applications appears in port terminals. Here, the blocks are the containers that are stacked in the blocks. Optimizing extraction means a great saving in yard crane time and therefore in efficiency for the terminal. In this TFM the Block Relocation Problem will be studied from various points of view. First we will try to find the best model for the exact resolution in the current bibliography and we will try to improve. Later, we will see the limitations that these models present when solving real cases and a heuristic will be proposed as an alternative. Here we will proceed in a similar way. Starting by comparing the best heuristics currently proposed and trying to improve them.