Heuristic Algorithms for Real Crane Scheduling Problems in Container Yards

• Autores: Hongtao Wang
• Directores de la Tesis: Rubén Ruiz García (dir. tes.) , María Fulgencia Villa Juliá (dir. tes.) , Eva Vallada Regalado (dir. tes.)
• Lectura: En la Universitat Politècnica de València ( España ) en 2025
• Idioma: inglés
• Tribunal Calificador de la Tesis: Javier Alcaraz Soria (presid.) , Vicent Giner Bosch (secret.) , Anna Martínez Gavara (voc.)
• Enlaces
  • Tesis en acceso abierto en: RiuNet
• Resumen

  • 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.