Heuristic Algorithms for Real Crane Scheduling Problems in Container Yards

[ES] El transporte de contenedores es un factor clave en el comercio moderno, representando el segmento de más rápido crecimiento en el transporte marítimo, lo que ejerce una inmensa presión sobre los terminales portuarios, especialmente en las grúas de patio. Esta tesis aborda un problema realista de programación de grúas de patio (YCSP) que incluye asignaciones dinámicas de puntos de entrada/salida (I/O) durante el proceso de optimización. Los puntos I/O actúan como buffers entre los modos de transporte dentro de la terminal, y su disponibilidad afecta la eficiencia en los procesos de almacenamiento y extracción. El problema es altamente realista pero complejo de resolver, lo que limita la eficiencia de carga en el terminal. Para mejorar la eficiencia de carga, esta tesis primero introduce una heurística simple, denominada Regla de Tiempo de Finalización Simulado (SETR), que secuencia contenedores y asigna puntos I/O. SETR supera las heurísticas basadas en reglas existentes, aunque sigue enfrentando desafíos en instancias más grandes. Además, recurrimos a una serie de metaheurísticas, incluidos los Procedimientos de Greedy Randomized Adaptive Search Procedure (GRASP) y el Iterated Greedy (IG). Se proponen dos enfoques GRASP junto con mejoras en las fases de construcción de soluciones y búsqueda local, específicamente adaptadas a este YCSP. Para una mejora adicional, se diseñan tres métodos IG con una intensificación de nuevos operadores IG de destrucción, reconstrucción y búsqueda local. Todos los métodos GRASP e IG propuestos se calibraron y evaluaron cuidadosamente a través de experimentos computacionales exhaustivos. Los resultados indican que ambos métodos GRASP pueden resolver de manera efectiva y eficiente instancias grandes con mejoras significativas en comparación con los enfoques más avanzados. Los métodos IG propuestos incluso superan a todos los algoritmos GRASP, donde pequeños cambios en las características del algoritmo tienen un impacto profundo en el rendimiento final. En resumen, esta tesis se centra en mejorar la eficiencia operativa de las grúas de patio al considerar operaciones de carga realistas durante la programación de grúas, lo que acerca el estudio científico a la práctica en el mundo real. Diseñamos, calibramos y evaluamos heurísticas y metaheurísticas efectivas para optimizar las operaciones de entrega, con un enfoque práctico en las asignaciones dinámicas de los puntos I/O. Esto no solo mejora la eficiencia de los terminales portuarios, sino que también promueve un futuro más verde y sostenible.

[CA] El transport de contenidors és un factor clau en el comerç modern, representant un dels segments de més ràpid creixement en el transport marítim, la qual cosa exerceix una gran pressió sobre els terminals portuaris, especialment en les grues de pati. Aquesta tesi aborda un problema realista de programació de grues de pati (YCSP) que inclou assignacions dinàmiques dels punts d'entrada/ixida (I/O) durant el procés d'optimització. Els punts d'I/O actuen com a búfers entre els modes de transport dins de la terminal, i la seua disponibilitat afecta l'eficiència dels processos d'emmagatzematge i extracció. El problema és molt realista, però complex de resoldre, la qual cosa limita l'eficiència de la càrrega en el terminal. Per a millorar l'eficiència de la càrrega, aquesta tesi primer introdueix una heurística senzilla, denominada Regla de Temps de Finalització Simulat (SETR), que seqüencia contenidors i assigna punts d'I/O. SETR supera les heurístiques basades en regles existents, encara que s'enfronta a desafiaments en instàncies més grans. A més, es proposa una sèrie de metaheurístiques, incloent-hi Procediments de Greedy Randomized Adaptive Search Procedure (GRASP) i Iterated Greedy (IG). Es proposen dues aproximacions GRASP juntament amb millores en les fases de construcció de solucions i de cerca local, específicament adaptades per a aquest YCSP. Per a una millora addicional, es dissenyen tres mètodes IG amb una intensificació de nous operadors IG de destrucció, reconstrucció i cerca local. Tots els mètodes GRASP i IG proposats són calibrats i avaluats acuradament mitjançant experiments computacionals exhaustius. Els resultats indiquen que ambdós mètodes GRASP poden resoldre de manera efectiva i eficient instàncies grans, amb millores significatives respecte als enfocaments més avançats. Els mètodes IG proposats superen fins i tot a tots els algoritmes GRASP, on xicotets canvis en les característiques dels algoritmes tenen un impacte profund en el rendiment final. En resum, aquesta tesi se centra en millorar l'eficiència operativa de les grues de pati tenint en compte operacions de càrrega realistes durant la programació de grues, la qual cosa acosta l'estudi científic a la pràctica del món real. Hem dissenyat, calibrat i avaluat heurístiques i metaheurístiques efectives per a optimitzar les operacions de lliurament, amb un enfocament pràctic en les assignacions dinàmiques dels punts I/O. Això no només millora l'eficiència dels terminals portuaris, sinó que també promou un futur més verd i sostenible.

[EN] Containerized transport is a major factor in modern trade leading the fastest-growing segment of maritime transport, which exerts immense pressure on port terminals, particularly on yard cranes. This thesis addresses a realistic yard crane scheduling problem (YCSP) that includes dynamic assignments of input/output (I/O) points during the optimization process. I/O points serve as buffers between transportation modes within the terminal, and their availability affects efficiencies in storing and retrieval processes. The problem is highly realistic yet complex to solve, which constricts the loading efficiency in the terminal. To improve the loading efficiency, the thesis first introduces a simple heuristic, referred to as the Simulated Ending Time Rule (SETR), which sequences containers and assigns I/O points. SETR outperforms existing rule-based heuristics, while it still encounters challenges in larger instances. Furthermore, we turn to a series of metaheuristics including Greedy Randomized Adaptive Search Procedures (GRASP) and Iterated Greedy (IG). Two GRASP approaches are proposed along with improvements to the solution construction and local search phases that are specifically tailored for this YCSP. For further improvement, three IG methods are designed with novel IG operators of destruction, reconstruction, and local search. All the proposed GRASP and IG methods are carefully calibrated and evaluated throughout comprehensive computational experiments. The results indicate that both the GRASP and IG methods can effectively and efficiently solve large instances with significant improvements against the state-of-the-art approaches. The proposed IG methods even outperform all GRASP algorithms, where small changes in algorithm features have a profound impact on the final performance. In summary, this thesis focuses on improving the operational efficiency of the yard crane by considering realistic loading operations during the crane scheduling, which brings the scientific study closer to real-world practice. We design, calibrate, and evaluate effective heuristics and metaheuristics to optimize delivery operations, with a practical focus on dynamic I/O assignments. This not only improves the efficiency of terminal ports but also promotes a greener and more sustainable future.