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.