Locating Refueling Stations for Hydrogen-Powered Well-Boats: A Hybrid Arc-Flow and Path-Flow Formulation

Abstract

I henhold til utvidelsen av Paris-avtalen har Norge forpliktet seg til å redusere klimagassutslippene med 55% innen 2030, med et langsiktig mål om å oppnå en reduksjon på 90-95% innen 2050, sammenlignet med 1990-nivå. Som Norges nest største næring har havbruksnæringen et betydelig miljøavtrykk, og brønnbåtdriften står for omtrent en tredjedel av sektorens utslipp. Avkarbonisering av brønnbåtflåten er derfor kritisk for å nå Norges utslippsmål. Overgang til nullutslippsdrivstoff, som hydrogen, er en lovende løsning. Innføringen av hydrogendrift for brønnbåter hindres imidlertid av mangelen på hydrogeninfrastruktur, som for øyeblikket er ikke-eksisterende. Dette understreker det presserende behovet for strategisk planlegging i utviklingen av hydrogen-infrastruktur for å støtte oppunder havbruksnæringens bærekraftsutvkling.

Vi introduserer et Zero-Emission Well-Boat Location Routing Problem (ZEWB-LRP). Dette problemet integrerer ruting av brønnbåter med strategisk plassering av hydrogenfyllestasjoner. Objektivet er å minimere de totale kostnadene knyttet til stasjonsåpning, igangsetting av fartøy, samt totale energikostnader. I tillegg må rutingen av fartøyene sikre at oppdrettsanleggenes servicebehov blir oppfylt. Vi formulerer problemet som et hybrid bue- og nodeflyt-problem. Videre implememterer vi en algoritme for forhåndsgenerering av fartøysruter, og benytter teknikker fra dynamisk programmering for å eliminere mindre hensiktsmessige ruter på en effektiv måte.

Vi presenterer både en eksakt og en heuristisk løsningsmetode. I den eksakte metoden foreslår vi en iterativ prosedyre der begrensningene for eliminering av subturer relakseres og legges til problemet når det er nødvendig. Den heuristiske metoden følger en totrinns tilnærming der den først bestemmer hvor hydrogenfyllestasjonene skal plasseres, og deretter løser et rent rutingproblem. Begge metodene er testet på instanser fra Lofoten og Vesterålen. Resultatene viser at for de største instansene finner den heuristiske metoden tilnærmet optimale løsninger langt raskere enn den eksakte metoden. I tillegg gir heuristikken bedre både nedre og øvre grenser enn den eksakte metoden for instanser som ikke løses til optimalitet.

Vi analyserer også hvordan sesongvariasjoner i etterspørselen etter brønnbåttjenester, endringer i stasjonskostnader og varierende fartøysrekkevidde påvirker beslutningene om hvor stasjonene bør plasseres. Vi trekker frem tre hovedfunn fra analysen:

- Lokasjonsbeslutinger basert på perioder med høy etterspørsel er robuste. - Et robust sett med hydrogenfyllestasjoner sikrer stabile driftskostnader. - Åpning av ekstra stasjoner på strategisk fordelaktige steder kan redusere de totale kostnadene.

Norway has committed under the Paris Agreement to reduce greenhouse gas emissions by 55% by 2030, with a long-term goal of achieving a 90-95% reduction by 2050, compared to 1990 levels. As Norway's second-largest industry, aquaculture has a significant environmental footprint, with well-boat operations accounting for about a third of the sector's emissions. Decarbonizing the vessel fleet is thus a critical challenge in meeting Norway's emission goals. Transitioning to zero-emission fuels, such as hydrogen, presents a promising solution. However, the adoption of hydrogen propulsion for well-boats is hindered by the lack of hydrogen infrastructure, which is currently non-existent. This highlights the urgent need for strategic planning in the development of hydrogen refueling infrastructure to support the move towards a sustainable aquaculture sector.

To address this challenge, we introduce the Zero-Emission Well-Boat Location Routing Problem (ZEWB-LRP). This problem integrates the routing of well-boats with the strategic placement of hydrogen refueling stations, aiming to minimize the combined costs of station opening, vessel deployment, and operation. Additionally, the routing of vessels must ensure that the service demands of the fish farms are met. We formulate the problem using a hybrid arc-flow and path-flow approach, employing a-priori voyage generation with a dynamic labeling algorithm to efficiently eliminate unnecessary and infeasible voyages.

We propose both an exact and a heuristic solution approach. In the exact method we employ an iterative procedure where subtour elimination constraints are relaxed and added to the problem when needed. Our heuristic method follows a two-step approach where it first determines the station locations, and secondly, solves a pure routing problem. Both methods are tested on real-world instances from the area of Lofoten and Vesterålen. Our results show that the proposed heuristic approach provides near-optimal solutions much faster than the exact method, especially for larger instances. For instances that are not solved to optimality by the exact method, the heuristic provides both better lower bounds and upper bounds.

Moreover, we conduct analyses to evaluate how seasonal variations in the demand for well-boat services, changes in station cost and varying vessel ranges affect the optimal location decisions. The results show three key findings:

- Station opening decisions based on high demand periods are robust. - A robust set of refueling stations ensures stable operational costs. - Opening additional stations in strategically advantageous locations can reduce overall costs.