Path-Relinking Heuristics for the Offshore Wind Farm Cable Routing Problem

Abstract

An important task in offshore wind farm design is connecting previously installed turbines to a substation in a way that minimizes the total cost of submarine cables. The Offshore Wind Farm Cable Routing Problem (WFCRP), an NP-hard graph-based optimization problem, has modeled this task. Despite recent advances, existing approaches primarily rely on localized search strategies and do not fully exploit the structural information in high-quality solutions. This paper introduces six hybrid path-relinking heuristics for the WFCRP, representing the first systematic application of path-relinking strategies to this problem. The proposed algorithms combine a constructive sweep heuristic, elite-solution path-relinking trajectories, and stochastic local search. An extensive experimental evaluation on 200 real-world instances with up to 120 turbines shows that the proposed methods significantly improve solution quality for small and medium-sized instances, outperforming state-of-the-art methods such as Variable Neighborhood Search and a Multi-agent Hybrid Metaheuristic.