A time-dependent vessel routing problem with speed optimization

Karl Petter Ulsrud, Anders Helgeland Vandvik, Andreas Breivik Ormevik, Kjetil Fagerholt and Frank Meisel

European Journal of Operational Research, 2022, vol. 303, issue 2, 891-907

Abstract: 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.

Keywords: Transportation; Time-dependent vessel routing; Speed optimization; Pickup and delivery; Adaptive large neighborhood search heuristic (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221722002223
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:303:y:2022:i:2:p:891-907

DOI: 10.1016/j.ejor.2022.03.015

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().