NTNU Open: A Tabu Search Heuristic for Chartering Offshore Wind Farm Installation Vessels under Uncertainty
A Tabu Search Heuristic for Chartering Offshore Wind Farm Installation Vessels under Uncertainty
Voster, Miriam; Kjelby, Sara Marie
no.ntnu:inspera:55508684:57885826.pdf (5.577Mb)
https://hdl.handle.net/11250/2777013
Etterspørselen etter nye energikilder vil øke de neste tiårene. Offshore vindkraft har potensiale til å dekke deler av denne etterspørselen. Kostnadene knyttet til offshore vindkraft er høye, og må reduseres for at offshore vindkraft kan konkurrere med fossile energikilder. En mulighet for kostnadsreduksjons er å estimere leieperiodene til installasjonsfartøyene med større presisjon. Denne masteroppgaven er skrevet i samarbeid med SINTEF, og formålet er å utvikle en metode for å redusere leiekostnader for installasjonsfartøy.
Beslutninger som må tas for installasjonsfartøy i planleggingsfasen av en offshore vindpark er startdato, sluttdato og antall opsjoner for hvert installasjonsfartøy. Når installasjonen starter, bestemmes værvinduer installasjonsaktiviteter kan utføres i. Målet er å minimere de forventede kostnadene for leie av installasjonsfartøy. Det som skiller dette problemet fra tidligere forskning på installasjon av havvindmøller, er hovedsakelig hensynet til værusikkerhet og dens effekt på strategien for innleie av installasjonsfartøy. I tillegg blir utvidelsesopsjoner og fastsettelse av pris for fastpriskontrakter tatt i betraktning. Det finnes forskning som tar hensyn til værusikkerhet, men disse antar at flåten består av kun ett installasjonsfartøy eller vurderer kun de mest væravhengige installasjonsaktivitetene.
En matematisk to-stegs stokastisk modell er formulert for å beskrive problemet. Førstestegsbeslutningen blir tatt før installasjonsfasen starter. Andrestegsbeslutninger dreier seg om planlegging av installasjonsaktivitetene gitt leieperiodene for installasjonsfartøyene og det realiserte været.
En tabu-søk heuristikk er foreslått for å løse modellen for store test-instanser. En simulator er integrert i heuristikken for å simulere andrestegsbeslutninger og estimere kostnadene for førstestegsbeslutningene foreslått av heuristikken. Ulike forbedringsstrategier, tabu-listestrukturer og stoppkriterier er testet for å øke effektiviteten til tabu-søket og unngå å stå fast i lokale optimum. En kombinasjon av en enkel nabolagsstruktur i heuristikken og en simulator som evaluerer naboer, resulterte i et effektivt søk som fant løsninger i optimum eller i nærheten av optimum for realistiske instanser innen rimelig tid. Videre indikerer testingen at opsjoner utgjør en betydelig del av installasjonsfartøyenes leieperioder, selv om opsjoner er dyrere enn faste leieperioder. De forventede kostnadene er lavere ved å inkludere opsjoner ettersom antall dager det tar å installere vindparken varierer med værscenarier, og opsjonene gir fleksibilitet i kontrakten.
The demand for new energy sources will increase in the next decades. Offshore wind farms have the potential to meet a portion of this demand. However, the costs related to offshore wind farms are high and must be reduced to compete with fossil energy sources. One cost reduction opportunity lies within the chartering of installation vessels for the wind farm. This thesis is written in collaboration with SINTEF, and the purpose is to provide a method for wind farm developers to reduce the chartering cost.
The installation vessels chartering problem under weather uncertainty, involves deciding the start date, end date, and the number of extension options for each vessel before the installation starts. When the installation starts, weather windows for installation activities are found. The goal is to minimize the expected cost of chartering installation vessels. What distinguishes this problem from previous research on offshore wind farm installation, is mainly the consideration of weather uncertainty and its effect on the chartering strategy. In addition, the use of extension options and pricing of lump-sum contracts are considered. There exist papers considering weather uncertainty, but these papers assume that the fleet consists of only one vessel or considers only the most weather-sensitive installation activities.
A mathematical two-stage stochastic model is formulated to describe the problem. The first stage relates to the chartering decisions taken years before the installation. The second stage is concerned with scheduling installation activities given the vessel´s charter periods and the realized weather. A tabu search heuristic is proposed to solve the problem for large instances. A simulator is integrated within the heuristic to estimate the cost for a first-stage solution the heuristic suggests, and simulate the second-stage decisions. Different improvement strategies, tabu list structures, and stopping criteria have been tested to increase the tabu search efficiency and to avoid getting stuck in local optima. A simple neighborhood structure in the heuristic, combined with a simulator to evaluate neighbors, resulted in an efficient search which found the optimal solution or a solution close to optimum for real sized instances within a reasonable time limit. Moreover, testing indicates that extension options constitute a significant part of the charter period, even though options are more expensive than fixed periods. The expected cost is lower with included options, as the number of days to install the wind farm varies with weather scenarios, and options add flexibility in the contract.