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: exact optimization algorithms have rarely been applied to this problem, as most prior research relies on heuristic methods that cannot guarantee optimality. To address this gap, this study proposes a novel enhanced branch-and-price (B&P) algorithm for the platform supply vessel routing and scheduling problem with uncertain demand (PSVRSP-UD). The proposed approach integrates NG-route labeling, a group-representative label mechanism, and a two-level branching strategy to efficiently obtain globally optimal solutions under demand uncertainty. 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, time window tightness, and weight coefficients on the results. The new results in this study can provide a practical decision-support tool for offshore logistics operations.