Integrated Optimization of Bunker–Cargo Trade-Offs in Tramp Ship Routing and Scheduling

This paper studies an integrated planning problem in tramp shipping operations, with a particular focus on the bunker–cargo trade-off in maritime logistics. In practice, bunker load and cargo capacity are mutually restrictive: carrying more bunker reduces available payload, while cargo load affects fuel consumption and subsequent bunker demand, jointly shaping operating profitability. To capture this interdependency and overcome the limitations of fragmented decision-making, we jointly optimize cargo selection, vessel scheduling, routing, and bunkering decisions. The problem is formulated as a profit-maximizing mixed-integer linear programming (MILP) model. To solve large-scale instances efficiently, we adopt Dantzig–Wolfe decomposition and develop a column generation algorithm. For the pricing subproblem, we design a customized dynamic programming-based labeling algorithm for the resource-constrained shortest path problem, enhanced by dominance rules and acceleration strategies. Computational experiments show that the proposed approach outperforms alternative algorithms in both solution quality and computational efficiency, especially for large-scale problems. Ablation experiments further quantify the value of key components, including fuel discretization and deterministic acceleration strategies. Scenario analyses under different fuel prices, freight rates, bunkering policies, and fleet structures illustrate how integrated optimization can balance bunker–cargo trade-offs and provide practical decision support for tramp shipping operators.