Path-Relinking Heuristics for the Offshore Wind Farm Cable Routing Problem
DOI:
https://doi.org/10.5753/jbcs.2026.7304Keywords:
Offshore Wind Farm Cable Routing, Metaheuristics, Path-Relinking, Graph-Based OptimizationAbstract
{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.
Downloads
References
Alencar, M. S., Göçmen, T., and Cutululis, N. A. (2026). Flexible cable routing framework for wind farm collection system optimization. European Journal of Operational Research, 329(3):1037-1051. DOI: 10.1016/j.ejor.2025.07.069.
Amorosi, L., Fischetti, M., Paradiso, R., and Roberti, R. (2024). Optimization models for the installation planning of offshore wind farms. European Journal of Operational Research, 315(3):1182-1196. DOI: 10.1016/j.ejor.2024.01.011.
Bauer, J. and Lysgaard, J. (2015). The offshore wind farm array cable layout problem: a planar open vehicle routing problem. Journal of the Operational Research Society, 66(3):360-368. DOI: 10.1057/jors.2013.188.
Butterwick, T., Kheiri, A., Lulli, G., Gromicho, J., and Kreeft, J. (2023). Application of selection hyper-heuristics to the simultaneous optimisation of turbines and cabling within an offshore windfarm. Renewable Energy, 208:1-16. DOI: 10.1016/j.renene.2023.03.075.
Cazzaro, D., Fischetti, M., and Fischetti, M. (2020). Heuristic algorithms for the wind farm cable routing problem. Applied Energy, 278:115617. DOI: doi.org/10.1016/j.apenergy.2020.115617.
Cazzaro, D., Koza, D. F., and Pisinger, D. (2023). Combined layout and cable optimization of offshore wind farms. European Journal of Operational Research, 311(1):301-315. DOI: 10.1016/j.ejor.2023.04.046.
Cazzaro, D. and Pisinger, D. (2022). Balanced cable routing for offshore wind farms with obstacles. Networks: An International Journal, 80(4):386-406. DOI: 10.1002/net.22100.
Cerveira, A., de Sousa, A., Pires, E. S., and Baptista, J. (2016). Optimal cable design of wind farms: The infrastructure and losses cost minimization case. IEEE Transactions on Power Systems, 31(6):4319-4329. DOI: 10.1109/TPWRS.2016.2521700.
Conover, W. J. (1999). Practical nonparametric statistics, volume 350. John Wiley & Sons. DOI: 10.2307/1402479.
El Jaadi, M., Haidi, T., and Belfqih, A. (2024). Advancements in wind farm layout optimization: a comprehensive review of artificial intelligence approaches. TELKOMNIKA (Telecommunication Computing Electronics and Control), 22(3):763-772. DOI: 10.12928/telkomnika.v22i3.25609.
Fernandes, I. F., Goldbarg, E. F., Maia, S. M., and Goldbarg, M. C. (2021). Multi- and many-objective path-relinking: A taxonomy and decomposition approach. Computers & Operations Research, 133:105370. DOI: 10.1016/j.cor.2021.105370.
Fernandes, I. F. d. C. (2022). Hybridizing metaheuristics for multi- and many-objective problems in a multi-agent architecture. PhD thesis, Universidade Federal do Rio Grande do Norte. Available at:[link].
Fischetti, M. and Fischetti, M. (2022). Integrated layout and cable routing in wind farm optimal design. Management Science, 69(4):2147-2164. DOI: 10.1287/mnsc.2022.4470.
Fischetti, M. and Pisinger, D. (2018a). Mixed integer linear programming for new trends in wind farm cable routing. Electronic Notes in Discrete Mathematics, 64:115-124. DOI: 10.1016/j.endm.2018.01.013.
Fischetti, M. and Pisinger, D. (2018b). Optimizing wind farm cable routing considering power losses. European Journal of Operational Research, 270(3):917-930. DOI: 10.1016/j.ejor.2017.07.061.
Fischetti, M. and Pisinger, D. (2019). Mathematical optimization and algorithms for offshore wind farm design: An overview. Business & Information Systems Engineering, 61(4):469-485. DOI: 10.1007/s12599-018-0538-0.
Global Wind Energy Council (GWEC) (2025). Global Wind Report 2025. Available at:[link].
Glover, F. (1997). Tabu search and adaptive memory programming—advances, applications and challenges. Interfaces in Computer Science and Operations Research: Advances in Metaheuristics, Optimization, and Stochastic Modeling Technologies, pages 1-75. DOI: 10.1007/978-1-4615-4102-8_1.
He, J., Ge, M., Žarković, S. D., Li, Z., and Hilber, P. (2024). A novel integrated optimization method of micrositing and cable routing for offshore wind farms. Energy, 306:132443. DOI: 10.1016/j.energy.2024.132443.
Hou, P., Hu, W., and Chen, Z. (2016). Optimisation for offshore wind farm cable connection layout using adaptive particle swarm optimisation minimum spanning tree method. IET Renewable Power Generation, 10(5):694-702. DOI: 10.1049/iet-rpg.2015.0340.
Hou, P., Zhu, J., Ma, K., Yang, G., Hu, W., and Chen, Z. (2019). A review of offshore wind farm layout optimization and electrical system design methods. Journal of Modern Power Systems and Clean Energy, 7(5):975-986. DOI: 10.1007/s40565-019-0550-5.
Jin, R., Hou, P., Yang, G., Qi, Y., Chen, C., and Chen, Z. (2019). Cable routing optimization for offshore wind power plants via wind scenarios considering power loss cost model. Applied Energy, 254:113719. DOI: 10.1016/j.apenergy.2019.113719.
Klein, A. and Haugland, D. (2019). Obstacle-aware optimization of offshore wind farm cable layouts. Annals of Operations Research, 272(1):373-388. DOI: 10.1007/s10479-017-2581-5.
Laguna, M., Martí, R., Martínez-Gavara, A., Pérez-Peló, S., and Resende, M. G. (2025). Greedy randomized adaptive search procedures with path relinking. an analytical review of designs and implementations. European Journal of Operational Research, 327(3):717-734. DOI: 10.1016/j.ejor.2025.02.022.
López-Ibánez, M., Dubois-Lacoste, J., Cáceres, L. P., Birattari, M., and Stützle, T. (2016). The irace package: Iterated racing for automatic algorithm configuration. Operations Research Perspectives, 3:43-58. DOI: 10.1016/j.orp.2016.09.002.
Machado, M. O., Fernandes, I. F. C., Maia, S. M. D. M., and Goldbarg, E. F. G. (2024). A hybrid multi-agent metaheuristic for the offshore wind farm cable routing problem. Expert Systems with Applications, page 124668. DOI: 10.1016/j.eswa.2024.124668.
Pérez-Rúa, J.-A. and Cutululis, N. A. (2019). Electrical cable optimization in offshore wind farms—a review. IEEE Access, 7:85796-85811. DOI: 10.1109/ACCESS.2019.2925873.
Pérez-Rúa, J.-A. and Cutululis, N. A. (2022). A framework for simultaneous design of wind turbines and cable layout in offshore wind. Wind Energy Science, 7(2):925-942. DOI: 10.5194/wes-7-925-2022.
Pérez-Rúa, J.-A., Stolpe, M., and Cutululis, N. A. (2019). Integrated global optimization model for electrical cables in offshore wind farms. IEEE Transactions on Sustainable Energy, 11(3):1965-1974. DOI: 10.1109/TSTE.2019.2948118.
Pillai, A. C., Chick, J., Johanning, L., Khorasanchi, M., and De Laleu, V. (2015). Offshore wind farm electrical cable layout optimization. Engineering Optimization, 47(12):1689-1708. DOI: 10.1080/0305215X.2014.992892.
Resendel, M. G. and Ribeiro, C. C. (2005). GRASP with path-relinking: Recent advances and applications. Metaheuristics: progress as real problem solvers, pages 29-63. DOI: doi.org/10.1007/0-387-25383-1_2.
Ribeiro, C. C. and Resende, M. G. C. (2012). Path-relinking intensification methods for stochastic local search algorithms. Journal of heuristics, 18:193-214. DOI: 10.1007/s10732-011-9167-1.
Rizk-Allah, R. M., Snášel, V., Deng, X., Song, D., and Hassanien, A. E. (2024). Topological optimization of offshore wind farm cable routing system based on an improved equilibrium optimization algorithm. Ocean Engineering, 313:119539. DOI: 10.1016/j.oceaneng.2024.119539.
Sathler, K., Yeter, B., Gouveia, A., and Kolios, A. (2025). Effects of neighbouring offshore wind farms on techno-economic metrics: A case study of a brazilian offshore wind project. Ocean Engineering, 339:122189. DOI: doi.org/10.1016/j.oceaneng.2025.122189.
Simões, M., Bahiense, L., and Figueiredo, C. (2023). Hyper-heuristics with Path Relinking applied to the Generalised Time-Dependent ATSP in air travel. Procedia Computer Science, 223:35-42. DOI: 10.1016/j.procs.2023.08.211.
Song, D., Shen, G., Huang, C., Huang, Q., Yang, J., Dong, M., Joo, Y. H., and Duić, N. (2024). Review on the application of artificial intelligence methods in the control and design of offshore wind power systems. Journal of marine science and engineering, 12(3):424. DOI: 10.3390/jmse12030424.
Taillard, É. D., Waelti, P., and Zuber, J. (2008). Few statistical tests for proportions comparison. European Journal of Operational Research, 185(3):1336-1350. DOI: 10.1016/j.ejor.2006.03.070.
Tao, S., Xu, Q., Feijóo, A., and Zheng, G. (2020). Joint optimization of wind turbine micrositing and cabling in an offshore wind farm. IEEE Transactions on Smart Grid, 12(1):834-844. DOI: 10.1109/TSG.2020.3022378.
Wędzik, A., Siewierski, T., and Szypowski, M. (2016). A new method for simultaneous optimizing of wind farm’s network layout and cable cross-sections by milp optimization. Applied Energy, 182:525-538. DOI: 10.1016/j.apenergy.2016.08.094.
Yang, B., Liu, B., Zhou, H., Wang, J., Yao, W., Wu, S., Shu, H., and Ren, Y. (2022). A critical survey of technologies of large offshore wind farm integration: Summary, advances, and perspectives. Protection and Control of Modern Power Systems, 7(1):17. DOI: 10.1186/s41601-022-00239-w.
Zhang, D., Liu, Z., Liang, Y., Li, C., Zhang, J., and Hu, G. (2024). Bilevel optimization of non-uniform offshore wind farm layout and cable routing for the refined LCOE using an enhanced PSO. Ocean Engineering, 299:117244. DOI: 10.1016/j.oceaneng.2024.117244.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2026 Murilo O. Machado, Islame F. C. Fernandes, Silvia M. D. M. Maia
This work is licensed under a Creative Commons Attribution 4.0 International License.
