A branch-and-price approach for optimizing all-electric ship scheduling in waterborne transport

All-electric ships (AESs) have emerged as a promising solution for decarbonizing the waterborne transport sector. However, their limited sailing range compared to conventional fuel-powered ships presents a significant operational challenge, which necessitates the integration of energy refueling decisions into the scheduling process. Therefore, this study investigates the joint optimization problem of cargo transport and energy refueling for AESs in inland waterways. First, we establish an inland waterway shipping network for the main waterway and its tributaries. Based on this network, we formalize our problem into a pickup and delivery problem with on-site refueling and develop a mixed-integer linear programming model that jointly optimizes cargo transport, involving both pickup and delivery, and a flexible on-site energy refueling policy, aiming to minimize the total operational cost. To address instances of practical scale, we develop a specialized branch-and-price framework. The efficiency of this exact method is driven by several tailored acceleration strategies, including a state-reduction-based construction heuristic, a graph-reduction-based heuristic-then-exact pricing strategy, and a multi-state labeling algorithm with two customized dominance rules. Computational results validate that our algorithm achieves superior performance in both solution quality and efficiency compared to the solver. Finally, our comprehensive sensitivity analysis yields valuable managerial insights by assessing the influence of key parameters, such as network density and planning horizon, on operational costs and ship scheduling metrics.