Electric tugboat scheduling with charging considerations at container terminals

In response to the evolving landscape of container terminals, characterized by the growing prevalence of electrified ports and the ensuing challenges in electric tugboat operations, this research addresses the intricate tugboat scheduling problem with a particular focus on integrating charging operations. The overall port efficiency is aimed to be enhanced, congestion alleviated and service quality elevated. Realistic constraints such as berthing time windows, limited heterogeneous tugboat availability and battery capacity limits are considered. To address these challenges, a mixed-integer linear programming model is proposed, and two algorithms are developed: a matheuristic method and an adaptive large neighbourhood search (ALNS) algorithm. The matheuristic method is the primary approach in the authors' solution, as it reduces the number of decision variables by fixing the task execution sequence, which decreases problem complexity and allows for the efficient generation of feasible solutions. While the heuristic method forms the foundation of the optimization, recent research has demonstrated that ALNS is effective in solving complex scheduling problems. Therefore, a tailored ALNS algorithm is developed specifically for this problem. The ALNS framework's adaptive mechanism, which dynamically adjusts the selection of operators based on their performance during the search process, ensures a more robust exploration of the solution space. Computational experiments on randomly generated instances reveal that, in terms of algorithm and model performance, the matheuristic method outperforms ALNS, which, in turn, outperforms CPLEX $ <^>{\circledR } $ (R). However, for large-scale instances where the matheuristic fails to find a feasible solution, ALNS remains effective and continues to yield strong results, even in highly complex scenarios.