A Large Neighbourhood Search Heuristic for a Periodic Supply Vessel Planning Problem Arising in Offshore Oil and Gas Operations

The periodic supply vessel planning problem arises in supply operations performed by a heterogeneous fleet of vessels operating from an onshore base to offshore installations. These vessels must supply the installations on a periodic basis. Given a planning horizon, the problem consists of determining the fleet composition as well as the vessel schedules. This paper proposes a large neighbourhood search heuristic capable of solving large instances of the problem. On small instances for which an optimal solution is known, the heuristic consistently finds optimal or near-optimal solutions. It can also solve larger instances which are intractable by an exact algorithm.