A Matheuristic Algorithm for an Offshore Multi-period Location Routing Problem

Abstract

With the recent increase in energy production generated by offshore wind farms, regular maintenance is important for wind farm owners to ensure that they remain operational. Currently, maintenance tasks are performed by service vessels driven by fossil fuels and the work they perform may take several days to complete. To minimise the environmental impact of ship operations, emission-free vessel operations are possible by connecting vessels to the power grid. To achieve this, it is important to strategically determine the locations for charging infrastructure. This thesis presents a location routing problem with a multi-period planning horizon to consider the routes of electric vessels while determining the locations of potential charging stations to offer strategic insights to wind farm owners. As a solution method, a matheuristic algorithm is proposed. The routing of vessels is determined with an adaptive large neighbourhood search (ALNS) metaheuristic which is passed to an integer program (IP) to find the optimal placement of charging stations based on the vessel routing variables. The algorithm is tested on newly generated instances and performs well for both small and large instance sizes. Furthermore, the matheuristic is compared to an exact approach to validate its performance. These findings indicate that the proposed approach is effective and offers wind farms owners a tool to strategically site the infrastructure of charging units.