ISBN 978-3-8439-3129-8

978-3-8439-3129-8, Reihe Mathematik

Christine Hayn
Computing maximal entry and exit capacities of transportation networks - Complexity analysis and a discrete relaxation applied to gas transmission systems

114 Seiten, Dissertation Universität Erlangen-Nürnberg (2016), Softcover, A5

Zusammenfassung / Abstract

This thesis deals with a novel multi-stage non-convex optimization problem arising from the gas network operators' duty to determine available entry and exit capacities.

Since the introduction of the so-called entry-exit system in the course of gas market liberalization, network users can contract entry and exit capacity separately. These capacities are generally freely allocable. This means that each exit point can be supplied from any entry point without any restrictions. When selling the capacity rights, the network operator has to assure that all resulting transportation requests can be fulfilled. In addition, he is obliged to regularly publish available capacity.

The focus of this work is on the related deterministic optimization problem: Given a transportation network, determine maximal upper bounds on the supplies and demands, such that all balanced transportation requests within these bounds can be fulfilled. These bounds are called capacities, and the underlying feasibility problem is called verification of booked capacities. Related to linear networks, this subproblem appears in the context of robust network design with hose-models, where the aim is to find cost-efficient arc capacities such that all demands within the given bounds can be satisfied.

The question addressed in this work differs from the network design problem in the objective that involves the former bounds as variables. Especially, this leads to a non-convex feasible region.

Complementing this feasibility problem with a suitable objective function yields the multi-stage problem of computing maximal freely allocable entry and exit capacities. This work contains the first approach to solving it.

It turns out that even on linear networks, the problem of verifying booked capacities is CoNP-hard. We propose a compact binary programming model for deciding this decision problem.

Aiming at solving the capacity allocation problem on gas networks, we develop a flexible two-step solution approach, combining a refinement algorithm with a disjunctive master model. The resulting relaxation gives upper bounds on the weighted sum of bookable capacities as well as a solution of predefined quality.

Computational experiments are carried out on small academic and large-scale realistic instances. In addition to a performance analysis, we examine the effect of some given exit load onto the amount of bookable capacity as well as different shapes of sets of feasible nominations.