A large neighbourhood search heuristic for a periodic supply vessel planning problem arising in offshore oil and gas operations

Upstream logistics in the Norwegian oil industry includes, along with other activities, providing the offshore installations with necessary supplies. These are periodically delivered to the installations by supply vessels from onshore bases. This paper proposes a large neighbourhood heuristic for a real-world periodic supply vessel planning problem faced by StatoilHydro, the largest Norwegian offshore oil and gas operator. However, the model and the algorithm provided in the paper are of wide applicability. The problem calls for the simultaneous determination of a repetitive weekly sailing plan and of the configuration of the supply vessel fleet. Computational comparisons with an exact solution method results demonstrate the competitiveness of the heuristic.