Optimal scheduling of vessels passing a waterway bottleneck

We develop a novel schedule optimization model for vessels passing a waterway bottleneck. From the system-optimal perspective, the model aims to minimize the total vessel bunker cost and delay penalties at destinations by incorporating the nonlinear relationship between bunker consumption and sailing speed into its calculations. The nonlinear model is linearized via two commonly used approximation techniques. The first one linearizes the bunker consumption function using a piecewise linear lower bound, while the second does so by discretizing the time. Numerical case studies are conducted for a real-world waterway bottleneck, the Three Gorges Dam Lock. Results reveal how the optimal cost components, vessel schedules, and delays are affected by key operating parameters, including the fuel prices, delay penalty rates, and the tightness of sailing time windows. Comparison against two simpler benchmark scheduling strategies (one with no vessel coordination and the other adopting a naïve coordination) manifests the sizeable benefit of optimal vessel scheduling. This paper presents the first investigation into the system-optimal scheduling strategy for vessels navigating a shared bottleneck, considering bunker costs, schedule delay penalties, and varying sailing speeds. The results highlight the significant potential of system-optimal scheduling and potential coordination strategies that enable approximation of the system-optimal solution. Additionally, our numerical experiments uncover the limitations of the outer-approximation method, while demonstrating that the discrete-time approach surpasses it in terms of both solution quality and computational efficiency.