L-shaped decomposition for the two-stage stochastic facility location problem with capacity adjustments
Master thesis
Permanent lenke
https://hdl.handle.net/11250/3024656Utgivelsesdato
2022Metadata
Vis full innførselSamlinger
Sammendrag
Denne oppgaven har som mål å designe en optimal verdikjede for hydrogen til bruk i norsk maritim transport. Transportsektoren i Norge gjennomgår en overgang til bruk av lav- og nullutslippdrivstoff. Den maritime passasjertransporten utpeker seg som en viktig kandidat, da det er assosiert høye utslipp per passasjerkilometer i dette segmentet. For å kunne realisere overgangen til en maritim transportsektor med nullutslipp, er vi avhengig av et omfattende verktøy for beslutningsstøtte for å kunne designe en fremtidig verdikjede som håndterer usikkerheten i hydrogenetterspørselen.
Vi har utviklet en modell for å løse et two-stage stochastic facility location problem with capacity adjustments (to-stegs lokaliseringsproblem med kapasitetsjusteringer). Modellen minimerer den samlede forventede kostnaden for investering i hydrogenproduserende anlegg, kapasitetsjusteringer, produksjon og distribusjon for ulike produksjonsteknologier i løpet av planleggingshorisonten. Videre undersøker vi ulike tilnærminger for å redusere løsningstiden for modellen vår, inkludert utformingen av en L-shaped algoritme, sammen med ulike akselerasjonsteknikker. Ved å redusere løsningstiden kan vi løse større forekomster av problemet, fange usikkerheten knyttet til den virkelige verden i større grad, som til slutt resulterer i bedre beslutningsstøtte.
Ved bruk av våre foreslåtte dekomponeringsmetoder, er vi alltid i stand til å finne en lovlig løsning til modellen vår innenfor de definerte termineringskriteriene. Dekomponeringsteknikkene blir utkonkurrert av de vanlige kommersielle problemløserne for de fleste av probleminstansene våre. For de minste tilfellene er vi i stand til å finne optimale løsninger ved bruk av vår dekomponeringsteknikk. I de største instansene klarer dekomponeringsteknikken å finne fram til bedre løsninger enn standard kommersielle løsere, målt i målfunksjonsverdi.
Modellen vår foreslår å bygge en desentralisert verdikjede bestående av flere små fabrikker spredt omkring i Norge. Alle fabrikkene beyntter seg av elektrolyse som produksjonsteknologi for å kunne tilfredsstille hydrogenetterspørselen fram mot 2035 i vår case study. This thesis studies how to design an optimal hydrogen supply chain for maritime transportation in Norway. The transportation sector in Norway as a whole faces a transition to low- and zero-emission fuels. The maritime passenger transportation segment points out to be an important contributor to reducing emissions, having high emissions per passenger-kilometre. To realise the pathway to zero-emission maritime transportation, we need a comprehensive model for decision support. The decision must support the design of a future hydrogen supply chain that handles the uncertainty in customer demand.
We model the problem of solving a two-stage stochastic facility location problem with capacity adjustments. The model minimises the overall expected cost for investment in hydrogen-producing facilities, capacity adjustments, production and distribution for different production technologies over the planning horizon. We examine an alternative approach to solve the model with the aim of reducing the solution time, including developing an L-shaped algorithm and different additional acceleration methods. By reducing the solution time, we can solve larger instances of the problem, improving the capturing of the real world's uncertainty and ultimately providing better decision support.
The L-shaped decomposition technique always finds a feasible solution to our model within the defined termination criteria, but gets outperformed by standard commercial solvers for most of our problem instances. For the smallest instances, we are able to find optimal solutions with the use of our L-shaped algorithm. In addition, we manage to find better solutions for the largest instances with respect to objective value than the commercial solver within the termination criteria.
Our model suggests building a decentralised supply chain consisting of many facilities spread throughout Norway. Each facility is installed with electrolysis as production technology to cover hydrogen demand towards 2035 for our case study.