Planning Annual Delivery Programs in the Liquefied Natural Gas Industry

Abstract

Å planlegge langdistansetransport av flytende naturgass (LNG) er en kompleks prosess for LNG produsenter å håndtere. Dette innebærer å sette opp et såkalt årlig leveringsprogram (ADP), som er en plan for levering av LNG for en produsent over en periode på ett år. En ADP inkluderer vanligvis planlegging av leveranser til forskjellige kunder og lokasjoner, lagerkontroll for én eller flere produksjonsanlegg, og optimal allokering av sjøruter for LNG-skipene slik at produsentens kostnader minimeres. Ved å sette opp en LNG-ADP kan LNG-produsenten mer effektivt administrere verdikjeden sin og sikre at kundene får LNG-leveransene sine i tide og på en kostnadseffektiv måte. I denne masteroppgaven skal vi definere og løse "LNG-ADP med optimering av seilingshastighet og flere lastehaver"-problemet (LNG-ADP-SO-MLP).

LNG-ADP-SO-MLP er en spesialversjon av LNG-ADP-problemet, hvor vi utvider eksisterende modeller som finnes i litteraturen ved å håndtere flere lastehavner, optimere skipenes seilingshastighet, variere produksjonsrater, og gi produsenten muligheten til å leie ut sine egne skip. Vi foreslår videre en ny matematisk modell for LNG-ADP-SO-MLP-problemet, formulert som en blandet lineær heltallsmodell (MILP) med diskret tid. På grunn av problemets størrelse og kompleksitet er det nærmest umulig å finne optimale løsninger ved bruk av en kommersiell MILP-problemløser for å løse modellen for et helt år.

Som følge av dette implementerer vi et heuristisk rammeverk med rullende horisont (RHH) for å løse modellen. RHHen deler opp planleggingshorisonten i flere mindre subhorisonter, og løser dem iterativt ved hjelp av en kommersiell problemløser for å finne en komplett løsning. Vår industripartner Quorum Software ga oss et sett med realistiske testinstanser, som varierer i antall lastehavner, skip, etterspørsel fra kunder og lengde på planleggingshorisonten for å teste RHHen som løsningsmetode. Resultatene fra beregningsstudien viser at RHHen finner lovlige og gode løsninger for planleggingshorisonter på opp til 12 måneder, innenfor rimelige løsningstider. Vi viser også at RHHen kan brukes til å gi verdifull strategisk innsikt, som kan brukes til å informere både taktiske- og strategiske beslutninger for produsenten, for eksempel for å vurdere verdien av å investere i mer lagerkapasitet på lastehavnen(ene), og av å ha en delt flåte for lastehavnene, i stedet for å ha separate flåter.

Planning long-distance transportation of liquefied natural gas (LNG) is a complex process faced by the LNG producers. This includes setting up a so-called Annual Delivery Program (ADP), a plan for the delivery of LNG from a producer over a period of one year. The ADP typically includes the scheduling of deliveries to different locations/customers, inventory control at the liquefaction plant(s), and the allocation and optimization of LNG vessel routes to minimize costs. By creating an LNG-ADP, LNG producers can more efficiently manage their supply chains and ensure that customers receive their LNG deliveries in a timely and cost-effective manner. In this thesis, we define and solve the Liquefied Natural Gas Annual Delivery Program Planning Problem with Speed Optimization and Multiple Loading Ports (LNG-ADP-SO-MLP).

The LNG-ADP-SO-MLP is a special version of the LNG-ADP, where we extend existing models for the LNG-ADP problem found in the literature by handling multiple loading ports (or liquefac- tion plants), optimizing vessel speeds, selling LNG in the spot market, varying production rates, and having the option of chartering out the producer’s vessels. We propose a novel model for the LNG-ADP-SO-MLP, formulated as a mixed-integer linear program (MILP) based on a time-space network structure with a discrete-time representation. Due to the scale and complexity of the problem, it is challenging, if not impossible, to find optimal solutions using a commercial solver for real-world cases.

Consequently, we develop a rolling horizon heuristic (RHH) to solve the model. The RHH divides the planning horizon into sub-horizons and solves them iteratively using a commercial solver to obtain a complete solution. Our industry partner Quorum Software provided a number of realistic test instances, varying in the number of loading ports, number of vessels, customer demands, and the length of the planning horizons to test the RHH as a solution method. The computational results show that the RHH is able to find feasible and good solutions for planning horizons of 12 months within a reasonable amount of time. We also show that the application of the RHH to solve the LNG-ADP-SO-MLP yields valuable managerial insights that can inform both strategic and tactical decision-making for the producer, e.g., for evaluating the value of investing in larger storages at the liquefaction plant(s) and for having a shared fleet across the liquefaction plants instead of separate ones.