Refine
Document Type
- Article (3)
Language
- English (3)
Has Fulltext
- no (3) (remove)
Institute
- Energy Network Optimization (3) (remove)
In 2005 the European Union liberalized the gas market with a disruptive change
and decoupled trading of natural gas from its transport. The gas is now trans-
ported by independent so-called transmissions system operators or TSOs. The
market model established by the European Union views the gas transmission
network as a black box, providing shippers (gas traders and consumers) the
opportunity to transport gas from any entry to any exit. TSOs are required
to offer the maximum possible capacities at each entry and exit such that any
resulting gas flow can be realized by the network. The revenue from selling these
capacities more than one billion Euro in Germany alone, but overestimating the
capacity might compromise the security of supply. Therefore, evaluating the
available transport capacities is extremely important to the TSOs.
This is a report on a large project in mathematical optimization, set out
to develop a new toolset for evaluating gas network capacities. The goals and
the challenges as they occurred in the project are described, as well as the
developments and design decisions taken to meet the requirements.
This article discusses the Length-Constrained Cycle Partition Problem (LCCP), which constitutes a new generalization of the Travelling Salesperson Problem (TSP). Apart from nonnegative edge weights, the undirected graph in LCCP features a nonnegative critical length parameter for each vertex. A cycle partition, i.e., a vertex-disjoint cycle cover, is a feasible solution for LCCP if the length of each cycle is not greater than the critical length of each vertex contained in it. The goal is to find a feasible partition having a minimum number of cycles. Besides analyzing theoretical properties and developing preprocessing techniques, we propose an elaborate heuristic algorithm that produces solutions of good quality even for large-size instances. Moreover, we present two exact mixed-integer programming formulations (MIPs) for LCCP, which are inspired by well-known modeling approaches for TSP. Further, we introduce the concept of conflict hypergraphs, whose cliques yield valid constraints for the MIP models. We conclude with a discussion on computational experiments that we conducted using (A)TSPLIB-based problem instances. As a motivating example application, we describe a routing problem where a fleet of uncrewed aerial vehicles (UAVs) must patrol a given set of areas.
Compressor stations are the heart of every high-pressure gas transport network.
Located at intersection areas of the network they are contained in huge complex plants, where they are in combination with valves and regulators responsible for routing and pushing the gas through the network.
Due to their complexity and lack of data compressor stations are usually dealt with in the scientific literature in a highly simplified and idealized manner.
As part of an ongoing project with one of Germany's largest Transmission System Operators to develop a decision support system for their dispatching center, we investigated how to automatize control of compressor stations. Each station has to be in a particular configuration, leading in combination with the other nearby elements to a discrete set of up to 2000 possible feasible operation modes in the intersection area.
Since the desired performance of the station changes over time, the configuration of the station has to adapt.
Our goal is to minimize the necessary changes in the overall operation modes and related elements over time, while fulfilling a preset performance envelope or demand scenario.
This article describes the chosen model and the implemented mixed integer programming based algorithms to tackle this challenge.
By presenting extensive computational results on real world data we demonstrate the performance of our approach.