Branch-and-price for clash-free periodic supply vessel planning problem with split delivery and variable service time

This paper considers a periodic supply vessel planning problem in which the weekly demands at multiple offshore facilities are satisfied with a fleet of heterogeneous vessels. The objective is to find the optimal fleet composition and weekly trips for ships that minimize the total travel and fixed costs. The scheduling challenge is modelled by arc-flow, path-flow, and set-partitioning formulations. The proposed branch-and-price algorithm is used for the first time in the literature on planning problems. Simulation results for the North West Shelf project in Australia show that the proposed approach can generate high-quality solutions to large, industrial-scale problem instances. The techniques and applications can be transferred to maintenance planning and scheduling.