Novel Realistic Approaches for Container Premarshalling

Abstract

[ES] En las últimas décadas, el rápido crecimiento del transporte de mercancía contenerizada ha planteado grandes retos a la eficiencia portuaria. La optimización de operaciones se ha vuelto crucial para minimizar los costes de puertos y navieras y reducir el impacto medioambiental.

La organización y gestión del patio del puerto son esenciales para garantizar la eficiencia del puerto, ya que se utiliza para almacenar contenedores y conecta todas las zonas y actividades portuarias. Este entorno dinámico exige estrategias efectivas para colocar y retirar contenedores. Al estar apilados, retirar un contenedor puede requerir mover otros que estén encima a otras pilas, lo que ralentiza la retirada. Estos movimientos se pueden evitar ordenando los contenedores de antemano en un proceso conocido como premarshalling.

El problema clásico de optimización asociado al premarshalling, que trata de encontrar el mínimo número de recolocaciones necesarias para ordenar los contenedores, se basa en varias asunciones poco realistas. Esta tesis pretende facilitar la aplicación práctica del premarshalling reformulando algunas de estas asunciones.

Los contenedores del patio se organizan en grupos llamados bahías, y el problema de premarshalling se centra en organizar una bahía de contenedores cada vez. La formulación clásica solo permite recolocaciones dentro de la bahía que se está ordenando, pero esta no es una limitación real en la práctica. Proponemos una nueva versión del problema en la que los contenedores se pueden mover a una bahía adyacente para facilitar el proceso de ordenación.

Otro aspecto poco realista de la formulación clásica es su objetivo. En literatura previa se muestra que minimizar el tiempo empleado por la grúa durante el premarshalling conduce a soluciones más eficientes que minimizar el número de recolocaciones. Esta tesis va más allá de la incorporación de tiempos de grúa y asume la disponibilidad limitada de la grúa. Mientras que la formulación original no proporciona una solución cuando el tiempo necesario para completar el premarshalling excede la disponibilidad de la grúa, definimos una nueva formulación que proporciona un premarshalling completo cuando el tiempo lo permite y parcial cuando no. Definir buenas ordenaciones parciales es un reto, así que exploramos tres estrategias alternativas.

El estudio de estas variantes del problema requería un método de resolución simple que pudiera adaptarse fácilmente a diversas asunciones y proporcionar soluciones óptimas para la validación del problema. Para cumplir con tales requerimientos, proponemos un método de resolución que combina el uso de un solver de programación por restricciones con algoritmos sencillos y fáciles de implementar. La programación por restricciones ha recibido muy poca atención en la literatura de premarshalling, a pesar de haber demostrado un buen rendimiento resolviendo problemas combinatorios en diversos campos. Esta tesis revela la eficacia de esta técnica para el problema de premarshalling al proporcionar modelos de programación por restricciones que superan a los métodos de programación matemática de vanguardia.

En líneas generales, esta tesis pretende acercar la formulación matemática del problema de premarshalling a su aplicación en el mundo real. Para ello, aborda tanto aspectos teóricos como técnicos. Desde el punto de vista teórico, introduce nuevas variantes del problema que suponen un notable avance hacia una formulación más realista. Desde el punto de vista técnico, presenta modelos de programación por restricciones que demuestran la eficacia de esta técnica sobre el problema de premarshalling.

[CA] En les últimes dècades, el ràpid creixement del transport de mercaderia conteneritzada ha plantejat grans reptes a l'eficiència portuària. L'optimització d'operacions s'ha tornat crucial per a minimitzar els costos de ports i navilieres i reduir l'impacte mediambiental.

L'organització i gestió del pati del port són essencials per a garantir l'eficiència del port, ja que s'utilitza per a emmagatzemar contenidors i connecta totes les zones i activitats portuàries. Aquest entorn dinàmic exigeix estratègies efectives per a col·locar i retirar contenidors. En estar apilats, retirar un contenidor pot requerir moure uns altres que estiguen damunt a altres piles, la qual cosa alenteix la retirada. Aquests moviments es poden evitar ordenant els contenidors per endavant, un procés conegut com premarshalling.

El problema clàssic d'optimització associat al premarshalling, que tracta de trobar el mínim nombre de recol·locacions necessàries per a ordenar els contenidors, es basa en diverses assumpcions poc realistes. Aquesta tesi pretén facilitar l'aplicació pràctica del premarshalling reformulant algunes d'aquestes assumpcions.

Els contenidors del pati s'organitzen en grups anomenats badies, i el problema de premarshalling se centra en organitzar una badia de contenidors cada vegada. La formulació clàssica només permet recol·locacions dins de la badia que s'està ordenant, però aquesta no és una limitació real en la pràctica. Proposem una nova versió del problema en la qual els contenidors es poden moure a una badia adjacent per a facilitar el procés d'ordenació.

Un altre aspecte poc realista de la formulació clàssica és el seu objectiu. En literatura prèvia es mostra que minimitzar el temps emprat per la grua durant el premarshalling condueix a solucions més eficients que minimitzar el nombre de recol·locacions. Aquesta tesi va més enllà de la incorporació de temps de grua i assumeix la disponibilitat limitada de la grua. Mentres que la formulació original no proporciona una solució quan el temps necessari per a completar el premarshalling excedeix la disponibilitat de la grua, definim una nova formulació que proporciona un premarshalling complet quan el temps ho permet i parcial quan no. Definir bones ordenacions parcials és un repte, així que explorem tres estratègies alternatives.

L'estudi d'aquestes variants del problema requeria un mètode de resolució simple que poguera adaptar-se fàcilment a diverses assumpcions i proporcionar solucions òptimes per a la validació del problema. Per a complir amb tals requeriments, proposem un mètode de resolució que combina l'ús d'un solver de programació per restriccions amb algorismes senzills i fàcils d'implementar. La programació per restriccions ha rebut molt poca atenció en la literatura de premarshalling, malgrat haver demostrat un bon rendiment resolent problemes combinatoris en diversos camps. Aquesta tesi revela l'eficàcia d'aquesta tècnica per al problema de premarshalling en proporcionar models de programació per restriccions que superen als mètodes de programació matemàtica d'avantguarda.

En línies generals, aquesta tesi pretén acostar la formulació matemàtica del problema de premarshalling a la seua aplicació en el món real. Per a això, aborda tant aspectes teòrics com tècnics. Des del punt de vista teòric, introdueix noves variants del problema que suposen un notable avanç cap a una formulació més realista. Des del punt de vista tècnic, presenta models de programació per restriccions que demostren l'eficàcia d'aquesta tècnica sobre el problema de premarshalling.

[EN] In recent decades, the rapid growth of containerized freight has posed significant challenges to port efficiency. Optimizing operations has become crucial for minimizing costs for ports and shipping companies and reducing environmental impact.

The organization and management of the port yard are essential to ensure port efficiency, as it is used for container storage and connects all port areas and activities. This dynamic environment demands effective strategies for placing and retrieving containers. Since containers are stacked, retrieving one may require moving containers above it to other stacks, which slows down the retrieval. These movements can be avoided by arranging the containers beforehand through a process known as container premarshalling.

The classical optimization problem associated with premarshalling, which aims to find the minimum number of relocations necessary to arrange the containers, relies on several unrealistic assumptions. This thesis aims to facilitate the practical application of premarshalling by reformulating some of these assumptions.

Containers in the yard are organized into groups called bays, and the premarshalling problem focuses on arranging one bay of containers at a time. The classical formulation only allows relocations within the bay being arranged, but this is not a real limitation in practice. We propose a novel version of the problem where containers can be moved to an adjacent bay to facilitate the arrangement process.

Another unrealistic aspect of the classical formulation is its objective. Previous literature shows that minimizing the total crane time during premarshalling leads to more efficient solutions than minimizing the number of relocations. This thesis goes beyond incorporating crane times and acknowledges limited crane availability. While the original formulation fails to provide a solution when the required time for completing the arrangement exceeds crane availability, we define a novel formulation that yields a complete premarshalling when time allows and a partial arrangement when it does not. Defining good-quality partial arrangements is challenging, and we explore three alternative strategies.

Studying these problem variants required a simple solution method that could be easily adapted to varying assumptions and provide optimal solutions for problem validation. To meet these requirements, we propose a solution method that combines the use of a constraint programming solver with simple algorithms that are easy to implement. Constraint programming has received very little attention in the premarshalling literature despite showing strong performance in solving combinatorial problems in various fields. This thesis reveals the effectiveness of this technique for the premarshalling problem by providing constraint programming models that outperform the state-of-the-art mathematical programming approaches.

Overall, this thesis aims to bridge the gap between the mathematical formulation of the premarshalling problem and real-world application. To achieve this, it addresses both theoretical and technical aspects. On the theoretical side, it introduces several novel variants of the problem that represent significant progress toward a more realistic formulation. On the technical side, it presents constraint programming solution methods that demonstrate the efficiency of this technique in addressing the premarshalling problem.