The periodic supply vessel planning problem with flexible departure times and coupled vessels

In upstream offshore petroleum logistics, periodic supply vessel planning plays an important role since it ensures the replenishment of offshore installations on a regular basis with all the necessary equipment and materials from an onshore base. The problem involves the determination of the fleet composition and of the vessel schedules over a given time horizon. We present an extended version of this problem involving flexible departures from the base and the possibility of coupling vessels by swapping their schedules. We propose a voyage-based model that can be solved exactly for small- and medium-size instances. For the solution of larger instances, we have developed an adaptive large neighborhood heuristic, which yields optimal or near-optimal solutions relatively fast on small- and medium- size instances. Its performance on larger instances is significantly better than that of alternative algorithms previously developed for the same problem.