A Time-Dependent Vessel Routing Problem with Speed Optimization

We study an operational planning problem arising in the offshore oil and gas industry, in which we determine routes, as well as sailing speeds along these routes, for a set of platform supply vessels (PSVs) servicing a given set of delivery and pickup orders such that costs are minimized. The sailing costs, mainly induced by fuel consumption for the PSVs, heavily depend on the chosen sailing speeds. Furthermore, the fuel consumption and the feasible speed ranges for the PSVs are largely affected by weather conditions that may vary over time, resulting in a weather- or Time-Dependent Vessel Routing Problem with Speed Optimization (TDVRP-SO). Optional decisions include the postponement of certain orders and the chartering of spot vessels, both associated with additional costs. We present a time-discrete mixed integer programming (MIP) model for the TDVRP-SO. To overcome the challenges of solving large-scale instances of the TDVRP-SO with a commercial MIP solver, we propose an Adaptive Large Neighborhood Search (ALNS) heuristic extended with a local search and a set partitioning model. The ALNS heuristic also includes solving the sub-problem of determining the optimal sailing speeds along each PSV route. Computational tests on instances based on a real planning case from the Norwegian continental shelf show that the ALNS heuristic efficiently provides high-quality solutions. It is also demonstrated that, in contrast to current planning practice, accounting for speed optimization and weather conditions significantly improves the solutions