Optimization Models and Algorithms for the Natural Gas Supply Chain

Abstract

Sammendrag

Denne PhD-avhandlinga består av sju artikler om operasjonsanalytiske modeller og algorit- mer for forsyningskjeden for naturgass. Fokus er på oppstrømsdelen av forsyningskjeden, fra produksjon til salg i markeder eller kontrakter.

Artikkel I introduserer modellering av den rørbaserte forsyningskjeden, inkludert både fysiske og kommersielle perspektiver. Artikkel II presenterer en taktisk modell for en produsent/skiper i den rørbaserte forsyningskjeden. Gjennom tester på både syntetiske og realistiske datasett vises tilleggsverdien ved å hensynta markedsusikkerhet og ved å ha et forsyningskjedeperspektiv i slike modeller. Artikkel III presenterer en taktisk modell for forsyningskjeden for flytende natur- gass (LNG). Modellen er en utvidelse av det klassiske ‘lagerstyrte rutingproblemet’ (‘inventory routing problemet’, IRP). Artikkelen illustrerer den potensielle gevinsten ved å inkludere mer fleksibilitet enn hva som har vært industriens praksis, ved å tillate ikke-fulle skipslaster, å tillate flere ventedager i planene samt å integrere handel i planleggingen. Artikkel IV omhandler også LNG forsyningskjeden og presenterer en strategisk modell som gir anbefalinger om investering og avhending av LNG terminaler, skip og langsiktige kontrakter. To små eksempler brukes for å illustrere den forventede gevinsten av å ta et porteføljeperspektiv og å adressere prisusikkerhet ved hjelp av stokastisk programmering. Artikkel V presenterer et rammeverk med flere optimeringsmodeller designet for å evaluere bruken av avbrytbare transporttjenester i markedet for rørtransport. Resultatene fra en case-studie viser betydelig forbedret nettverksutnyttelse når avbrytbare transporttjenester supplerer garanterte transporttjenester i situasjoner hvor utfall og andre hendelser som reduserer kapasiteten kan inntreffe.

De to siste artiklene presenterer algoritmer. Artikkel VI omhandler en ‘lås-og-løs-opp’ (‘fix- and-relax’) heuristikk for IRP’en presentert i Artikkel III. Numeriske resultater viser at heuris- tikken reduserer løsningstiden betydelig sammenlignet med å løse hele problemet med en generell blandet-heltallsløser, men den oppnår samtidig en noe dårligere målfunksjonsverdi. Artikkel VII presenterer en algoritme som løser matematiske program med likevektsbeskrankninger og heltallskrav (‘discretely-constrained mathematical program with equilibrium constraints’, DC-MPEC). Algoritmen bevises å konvergere til den optimale verdien. Artikkelen inneholder også et eksempel på en anvendelse i naturgassindustrien. Numeriske resultater viser at algoritmen gir en reduksjon i løsningstid relativt til den heuristiske motparten som har blitt publisert tidligere.

Summary

This PhD-thesis presents seven papers on operations research models and algorithms for the natural gas supply chain, focusing on the upstream part of the supply chain, from production to sale in markets or contracts.

Paper I gives an introduction to modeling of the pipeline-based supply chain, including both physical and commercial perspectives. Paper II presents a tactical planning model for a pro- ducer/shipper in the pipeline supply chain. Tests on both synthetical and realistic datasets show the added value of addressing market uncertainty and taking a supply chain perspective in such models. Paper III presents a tactical model for the liquefied natural gas (LNG) supply chain, an extension of the classical inventory routing problem (IRP). The paper illustrates the potential gain from adding more flexibility than common business practice, by allowing partially loading/unloading of vessels, allowing more waiting days in the schedules and integrating mar- ket trade in the planning. Paper IV also treats the LNG supply chain, presenting a strategic model that recommends investment and disinvestment decisions in LNG terminals, vessels and long-term contracts. Two small examples are used to illustrate the expected gain from using a portfolio perspective and addressing price uncertainty through stochastic programming. Paper V presents a framework of multiple optimization models to evaluate the use of interruptible transportation services in the market for transportation capacity by pipeline. In a case study results show substantial improved network utilization with interruptible services as a supplement to firm services when outages and other capacity-reducing events might happen.

The two last papers present algorithms. Paper VI treats a fix-and-relax heuristic for the IRP presented in Paper III. Numerical results show that the heuristic reduces solution times consid- erably compared to solving the whole problem in a general mixed integer solver, at the cost of slightly worse objective function values. Paper VII presents an algorithm to solve discretely- constrained mathematical programs with equilibrium constraints, including a proof of conver- gence to optimality and an example application in the natural gas industry. Numerical results show reduced solution times relative to the previously published heuristic counterpart of the algorithm.