Logic-Based Benders Decomposition for Unmanned Electric Tugboat Scheduling Considering Battery-Swapping Operations

As the electrification reform accelerates in ports worldwide, the application of electric tugboats is becoming more widely applied, posing a challenge in the balance between working arrangement and energy replenishment, especially when the shore energy replenishment facilities are limited. Aligning with the emerging trends of port electrification, unmanned operations, and intelligentization, this paper investigates unmanned electric tugboat scheduling considering battery-swapping operations that combine the assignment of tasks to the working periods of tugboats, the allocation of battery-swapping operations to the shore battery-swapping stations, and the sequencing of operations at each station. The problem is formulated into a mixed-integer linear programming to minimize the total completion time of the battery-swapping operations. A logic-based Benders decomposition method is proposed that decomposes the problem into a master problem and a subproblem. The master problem relaxes the sequencing constraints and solves the assignment of tasks to tugboats and the allocation of battery-swapping operations to stations. The SP, based on the solution to the master problem, determines the sequencing of battery-swapping operations at each station. Considering the interdependence of swapping operations of each tugboat that might be allocated to different stations, a dispatching heuristic is designed to efficiently obtain high-quality sequences for the stations. Numerical experiments are conducted based on 80 randomly-generated instances with up to 100 tasks, ten tugboats, and six battery-swapping stations. The results demonstrate that LBBD is capable of solving all 80 instances, whereas the commercial solver CPLEX fails to solve those with 80 or more tasks. Moreover, the average computational time of CPLEX on the instances it can solve is 241.32 s, nearly 32 times that of LBBD (7.57 s). This clearly indicates that LBBD significantly outperforms CPLEX in terms of both computational capacity and efficiency. Further analyses show that the increase in the number of tugboats will significantly shorten the makespan and make ETSBS easier to solve, while the increase in the number of battery-swapping stations makes the problem more challenging with longer computational time.