| dc.description.abstract | Verdenssamfunnet tar sikte på å bli et lavkarbonsamfunn basert på fornybare energikilder innen kort tid. Havvind har vist potensiale til å kunne spille en sentral rolle i denne overgangen, men det er både tekniske og økonomiske utfordringer som må løses før dette kan realiseres fullt ut. En av utfordringene er at det i dagens marked er svært få fartøy som kan bidra i installasjonsfasen av en offshore vindpark. Dette resulterer i høye leiekostnader som gir et betydelig bidrag til de totale installasjonskostnadene og vindparkens livssykluskostnad. I denne masteravhandlingen studerer vi et optimeringsproblem knyttet til leiekontraktsbestemmelser for disse fartøyene under værusikkerhet, med sikte på å minimere både kostnader og varigheten av installasjonsfasen. Mer spesifikt, er målet å bestemme hvilke typer fartøy som skal leies inn, start- og slutt dato for deres leieperiode, samt om det skal inkluderes kontraktuelle opsjoner. For å oppnå dette ser vi blant annet på operasjonelle tidsplaner med scheduling av aktiviteter for hvert fartøy.
Vi presenterer to ulike matematiske formuleringer av problemet. Først presenteres en to-stegs stokastisk modell som viser seg å være vanskelig å løse for realistiske test instanser ved bruk av en kommersiell solver. Derfor har vi gjort en Dantzig-Wolfe reformulering av modellen og utviklet en branch-and-price algoritme med en enkel primal heuristikk som løsningsmetode. I den reformulerte modellen kombineres tidsplaner for hvert enkelt fartøy til en gyldig prosjektplan for fullføring av hele vindparken. Subproblemene som benyttes i branch-and-price metoden løses som korteste-vei-problemer med ressursbegrensninger på et asyklisk nettverk, og vi presenterer to ulike labeling algoritmer for å løse disse. Et lignende problem med tilsvarende detaljnivå har så vidt vi vet ikke blitt studert i tidligere publisert litteratur. Videre skiller vårt arbeid seg fra eksisterende forskning ved at det er lite utbredt å benytte branch-and-price for å løse stokastiske modeller.
Våre resultater viser at ved å løse den dekomponerte modellen med branch-and-price lykkes vi med å oppnå bedre duale grenser enn de som ble funnet med kommersiell solver for den opprinnelige to-stegs modellen. Vår dekomponeringsmetode finner opp til 700 % bedre duale grenser. Dette skyldes hovedsakelig at den reformulerte modellen har en sterkere LP-relaksering. Ved hjelp av primalheurisitkken er vi også i stand til å oppnå et lavere optimalitetsgap på større testinstanser. | |
| dc.description.abstract | A global transition to low carbon and renewable energy is happening now, with offshore wind at the center of the revolution. However, challenges related to the installation of offshore wind turbines must be solved to realize the full potential of offshore wind in a sustainable future and to ensure profitability. Today, the number of eligible installation vessels is scarce, and vessel day rates make a significant contribution to the installation cost and wind farm life cycle cost. The problem studied in this thesis is that of designing charter contracts for installation vessels at offshore wind farms. The goal is to minimize both the charter costs and project duration of the installation phase, while considering uncertainty in the weather conditions and complying with many real-life restrictions. More specifically, the mix of vessels that should be chartered, the start and end date of these vessels’ charter periods, as well as which options to include in their contracts must be decided on. To achieve this, operational schedules that include information on which activities the chartered vessels are to perform, and when, are considered.
A two-stage stochastic mathematical formulation for the design of charter contracts is presented. As the formulation proves to be difficult to solve for realistic test instances using a commercial solver, we propose a Dantzig-Wolfe reformulation of the mathematical formulation that combines schedules into a feasible project plan in order to design the contracts. The schedules are generated by a number of subproblems formulated as shortest path problems with resource constraints on acyclic networks of nodes, and we present two labeling algorithms to solve these. A branch-and-price algorithm with the extension of a primal heuristic is implemented to solve the reformulated problem. A similar problem with all the considered aspects has to the best of our knowledge not previously been investigated in published research. Furthermore, branch-and-price is an approach scarcely used to solve stochastic problems and the research on this topic is limited.
We find that the branch-and-price algorithm succeeds at finding much better dual bounds compared with a commercial mixed integer programming solver. Computational results reveal that our method finds up to 700% better dual bounds. This is mainly due to the improved linear programming relaxation from the Dantzig-Wolfe reformulation. Further, the implemented primal heuristic is able to exploit the generated schedules to find good integer feasible solutions, resulting in lower optimality gaps for larger test instances. | |
