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.
Keywords: Maritime transportation, offshore logistics, routing and scheduling, large neighbourhood
search heuristic.