Show simple item record

dc.contributor.advisorMagnus Stålhane
dc.contributor.authorMohammed Alhayek, Bjørn Løvland Manheim, Henrik Klauset Svensson
dc.date.accessioned2019-10-25T14:00:41Z
dc.date.available2019-10-25T14:00:41Z
dc.date.issued2019
dc.identifier.urihttp://hdl.handle.net/11250/2624531
dc.description.abstractNaturgass er forventet å spille en viktig rolle i en overgang mot energiproduksjon med lavere klimagassutslipp. 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.description.abstractNatural gas (NG) is expected to play a significant role in the transition toward a lower-carbon energy mix. For long-distance trade, NG is transformed into a liquid state and transported by sea in specially built vessels. Many of the operational challenges associated with liquified natural gas (LNG) transportation can be modeled and solved using mathematical programming. This makes LNG transportation interesting from an operations research perspective. This thesis examines a short-term ship routing and scheduling problem for an LNG producer with a heterogeneous fleet of LNG vessels. This problem aims to create routes and schedules for the vessel fleet such that the producer fulfills a set of long-term contracts and at the same time exploit the opportunities in the spot market. A review of relevant literature is conducted. The surveyed literature comprises operational LNG planning problems and routing problems that are tightly related to the problem studied in this thesis. The findings indicate that exact solution methods are insufficient to solve similar problems of realistic sizes within a reasonable time. In addition, many of the surveyed problems in the LNG literature are solved by incorporating a mixed integer linear program in a heuristic solution procedure. This is often attributed to complicating side-constraints. In addition to a mixed integer linear program formulation, two heuristic solution methods for solving the optimization problem are presented. These two methods are referred to as The LNG Adaptive Large Neighborhood Search heuristic (ALNS) and The LNG Fix and Optimize heuristic (FO). The models are applied to realistic problem data sets. Similar to the surveyed problems in the literature review, results show that a MIP is not able to solve the largest and most complex instances within a time frame of 3600 seconds, even with onboard heuristics activated in a commercial MIP solver. The first solution method, FO, assumes a feasible solution populated with vessel legs at hand. It then searches the solutions space by destroying (removing) some of the vessel legs before applying a MIP, attempting to repair (rebuild) the solution for a pre-specified amount of time. The second solution method, ALNS, searches the solution space by destroying and repairing the solution many times, while adjusting methods for destroying and repairing in an adaptive manner, attempting to reach new, improving solutions. Further, two different algorithms are developed to construct initial feasible solutions as input to the solution methods. Both solution methods show promising results compared to MIP as they find high-quality solutions within a reasonable time. However, FO outperforms ALNS in terms of consistency in finding high-quality solutions. Alongside these two solution methods, an event-based simulation program has been developed. The simulation program has been applied to evaluate solutions not only in terms of projected deterministic monetary value but also in terms of statistical robustness. One of the concrete outputs from this simulation program is an approximation of a Pareto frontier between profitability and total arrival time violation of time windows. The frontier is defined by a set of non-dominated high-quality solutions consisting of a trade-off between profitability and robustness. This frontier allows the decision maker to select a solution that fits his risk preferences. In addition, we propose three robustness strategies to guide the proposed solution methods to find more robust and reliable solutions. The strategies comprise penalizing late arrivals, planning with exaggerated sailing times and buffer quantities. The effect of these strategies is benchmarked against a case base where no strategies are implemented. Test results are promising and indicate a significant value add for a decision maker.
dc.languageeng
dc.publisherNTNU
dc.titleMatheuristic Approaches to the Short-Term LNG Routing and Scheduling Problem
dc.typeMaster thesis


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record