Vis enkel innførsel

dc.contributor.advisorAsbjørnslett, Bjørn Egil
dc.contributor.advisorStålhane, Magnus
dc.contributor.authorSvensson, Henrik Klauset
dc.contributor.authorAlhayek, Mohammed
dc.contributor.authorManheim, Bjørn Løvland
dc.date.accessioned2020-01-08T15:01:20Z
dc.date.available2020-01-08T15:01:20Z
dc.date.issued2019
dc.identifier.urihttp://hdl.handle.net/11250/2635418
dc.description.abstractNaturgass er forventet å spille en viktig rolle i en overgang mot energiproduksjon med lavere klimagassutslipp, som for eksempel $CO_2$. I forbindelse med langdistanse handel og transport av naturgass, er gassen kjølt kraftig ned slik at den blir til væske, kalt flytende naturgass eller LNG, før væsken blir transportert med spesielt egnede skip. Mange av de operasjonelle utfordringene som oppstår i forbindelse med frakt av LNG kan modelleres og løses ved hjelp av matematisk programmering, nærmere bestemt av et lineært blandet heltallsprogram. Dette gjør LNG transport til et relevant og viktig forskningsområde innen optimering og beslutningstøtte (eng: operations research). Denne masteroppgaven omhandler rute -planlegging og de øvrige beslutningene på kort sikt for en LNG-produsent med en flåte av ulike skip. Kort sikt betyr i denne sammenheng en periode på ~90 dager. Resultatet fra masteroppgaven har som mål å utforme ruter og tidsplaner for flåten av skip innen rimelig tid for relativt store problemstørrelser ($>$10 skip). Rutene og tidsplanene samt øvrige beslutninger må tilfredsstille en rekke krav, i tillegg til å tilfredsstille grunnprinsipper som å imøtekomme behov fra faste kunder. At fokusområdet er planlegging på kort sikt innebærer mer detaljert modellering samt at potensielle salgsmuligheter i spotmarkedet blir hensyntatt. En studie som omhandler relevant litteratur har blitt gjennomført. Studien omhandler operasjonelle planleggingsproblemer for LNG, rute-planleggingsproblemer som er tett knyttet til problemet som denne masteroppgaven omhandler. Tidlige studier indikerer at eksakte løsningsmetoder ikke evner å finne gode løsninger på problemet innen tidsbegrensningene som er satt. Videre observeres det at mye av den relevante litteraturen tar utgangspunkt i en heuristisk løsningsmetode kombinert med bruk av et blandet heltallsprogram. Dette er mye på grunn av kompliserende tilleggs-begrensninger som gjør at problemet skiller seg fra tradisjonelle rute-planleggingsproblem for kjøretøy (VRP). I tillegg til en formulering basert på blandet heltallsproblem metodikk, er det også presentert to heuristiske metoder for å løse optimeringsproblemet. Disse to metodene refereres til som LNG Adaptive Large Neighborhood Search heuristic (ALNS) og LNG Fix and Optimize heuristic (FO). Modellene er testet på realistiske datasett. Resultatene fra eksakte løsningsmetoder av det blandete heltallsproblemet viser at disse metodene ikke er i stand til å løse de største og mest komplekse problemene innen en tidsramme på 3600 sekunder, dette gjelder også for kommersielle optimeringsprogram med innebygde heuristiske metoder aktivert. Disse resultatene er i tråd med problemene som har blitt forsøkt løst i relatert litteratur. Den første heuristikken, FO, tar utgangspunkt i en gyldig løsning på optimeringsproblemet. Deretter går metoden ut på å søke etter nye, bedre, løsninger gjennom å ødelegge og reparere løsningsrommet gjentatte ganger. Ødelegging foregår ved at en delmengde av rutevariablene settes fri mens resten av rutevariablene fikseres. Reparasjonsprosedyren foregår ved at et kommersielt optimeringsprogram løser et blandet heltallsproblem der den resterende delmengden av løsningen er fiksert. Den andre heuristikken, ALNS, søker også etter nye løsninger slik som FO ved hjelp av å ødelegge og reparere løsninger gjentatte ganger. Denne heuristikken justerer parametere og hvilke metoder som blir brukt for å ødelegge og reparere adaptivt. Hovedforskjellen fra FO er at denne heuristikken bruker langt flere metoder for å ødelegge og reparere løsninger. Videre så blir to ulike algoritmer for å konstruere en initial-løsning presentert. Begge heuristikkene viser lovende resultater ved sammenlikning opp mot å løse et blandet heltallsproblem, ettersom de ofte finner gode løsninger innen relativt kort tid. FO har dog vist seg å være overlegen sammenliknet med ALNS. Den er mer konsistent, og er i tillegg en langt kraftigere løsningsmetode når den er på sitt beste. Videre så er FO vist å være bedre både når det gjelder å finne løsninger på under 250 sekunder og under 3600 sekunder. I tillegg til disse to løsningsmetodene, så har et simuleringsprogram blitt utviklet. Simuleringsprogrammet er brukt til å evaluere løsninger, ikke kun ved hjelp av å vurdere lønnsomhet, men også ved å vurdere robusthet. En av de konkrete leveransene fra dette arbeidet er en approksimasjon av en Pareto-front mellom lønnsomhet og total forsinkelse. Denne fronten gjør det mulig for bruker å ta avgjørelser som passer med brukerens risikopreferanser. I tillegg presenteres tre robusthets-strategier. Disse strategiene har som formål å styre de nevnte løsningsmetodene mot å finne robuste løsninger. De tre strategiene inkluderer: straff ved sen ankomst, planlegging med overdrevne seilingstider samt økte buffer-kvantiteter. Tester viser at disse strategiene fungerer godt og at de gir betydelig verdi for beslutningstaker.
dc.languageeng
dc.publisherNTNU
dc.titleMatheuristic Approaches to the Short-term LNG Routing and Scheduling Problem
dc.typeMaster thesis


Tilhørende fil(er)

Thumbnail

Denne innførselen finnes i følgende samling(er)

Vis enkel innførsel