Efficient scheduling and routing of vessels are crucial in the oil and gas industries. In this paper, we consider a periodic supply vessel planning problem in which the weekly demands at multiple offshore facilities are satisfied with a fleet of heterogeneous vessels. Preemptive service at the base, variable service at facilities, and split delivery are allowed. The objective is to find the optimal fleet composition and weekly trips for vessels that minimize the total travel and fixed costs. The scheduling challenge is modelled by arc-flow, path-flow, and set-partitioning formulations. For the first time in the literature on periodic supply vessel planning problem, we propose a branch-and-price algorithm. 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.