A Branch-and-Price Approach to the Platform Supply Vessel Routing and Scheduling Problem with Uncertain Demand

With the expansion of offshore oil and gas exploration into deep-water regions, the efficient scheduling of Platform Supply Vessels (PSVs) is critical to offshore operations. The Platform Supply Vessel Routing and Scheduling Problem (PSVRSP) is an NP-hard combinatorial optimization problem, which is further complicated by uncertainty in offshore demand. Existing studies reveal a methodological gap: heuristic approaches cannot guarantee optimality, while exact algorithms often ignore demand uncertainty. To address this gap, this study proposes a Branch-and-Price (B&P) method for the Platform Supply Vessel Routing and Scheduling Problem with Uncertain Demand (PSVRSP-UD). A scenario-based Mixed-Integer Linear Programming (MILP) model is formulated, in which demand uncertainty is captured using Latin Hypercube Sampling (LHS) combined with Cholesky Decomposition and Sample-Based Reduction (SBR). Based on Dantzig–Wolfe Decomposition, the proposed B&P algorithm integrates NG-Route labeling and a two-level branching strategy to achieve global optimization. Computational experiments show that the B&P algorithm outperforms CPLEX in both computational efficiency and solution quality. Sensitivity analyses examine the impacts of scenario number, demand fluctuation, and weight coefficients on the results. The new results in this study can provide a practical decision-support tool for offshore logistics operations.