Metropolitan Infrastructure

Our society relies on the availability of efficient infrastructure networks for transportation, communication, energy supply, health care, and education, to mention some examples. Infrastructure design has a long-term impact for the effective functioning of our daily life, it is expensive and design decisions are often almost irreversible.

In view of the complexity arising from the interplay between various factors belonging to different planning steps, mathematics has become an indispensable tool for the layout and efficient operation of infrastructure networks. And Matheon develops the mathematical techniques for that.

Networks are fundamental structures of graph theory and combinatorics which constitute the mathematical roots of many projects in this application field. Just as the application problems addressed have developed towards more general and unifying topics, the range of mathematical techniques employed has broadened. Besides classical mathematical areas such as, for example, combinatorial optimization, network flow theory, and integer linear programming, also younger areas such as approximation and online algorithms, robust optimization, algorithmic game theory and integer nonlinear programming have moved into the focus of this application field.

Topics

  • Optimization for infrastructure networks
  • Optimization under uncertainty
  • Lineplaning and timetabling in public transport
  • User equilibria and algorithmic game theory



Topics

  • Optimierung für Infrastrukturnetzwerke
  • Optimierung unter Unsicherheit
  • Linien- und Fahrplanung im ÖPNV
  • Marktgleichgewichte und algorithmische Spieltheorie


Running projects

Financed by ECMath

  • MI1

    Design and operation of infrastructure networks under uncertainty

    Prof. Dr. Martin Skutella

    Project heads: Prof. Dr. Martin Skutella
    Project members: Julie Meißner
    Duration: 01.06.2014 - 31.05.2017
    Status: running
    Located at: Technische Universität Berlin

    Description

    Uncertainty in the input data is an omnipresent issue in most real world planning processes. Metropolitan infrastructure -its design, operation and maintenance- induces complex planning processes where data uncertainty lies, e. g. in processing durations, transit times, cost, market prices, customer demands, capacity, bandwidth, energy consumption, et cetera. Since decisions on the infrastructure are typically very cost-intensive and of long-term impact, there is an urgent need of best possible mathematical support in this decision making process.

    The quality of solutions for optimization problems (e. g. in infrastructure networks) with uncertain input data crucially depends on the amount of uncertainty. More information, or even knowing the exact data, allows for significantly improved solutions. It is impossible to fully abolish/avoid uncertainty. Nevertheless, it is sometimes possible to obtain exact data, but it may involve certain exploration cost in time, money, energy, bandwidth, etc.

    In telecommunication networks planning, for example, information on the existing infrastructure (copper lines, optical fiber etc.) or the transmission range might not be easily available. The challenging major task of this project is to develop a structural understanding and algorithmic methods on how to balance the cost for data exploration with the actual benefit for the quality of solution to the optimization problem under consideration.

    Project Webpage

    http://www.coga.tu-berlin.de/index.php?id=159901
  • MI2

    Optimized noise reduction in transportation and interior spaces

    Dr. Kersten Schmidt

    Project heads: Dr. Kersten Schmidt
    Project members: Robert Gruhlke / Dr. Anastasia Thöns
    Duration: 01.06.2014 - 31.05.2017
    Status: running
    Located at: Technische Universität Berlin

    Description

    The reduction of the excited noise of transportation, especially in gas turbines of airplanes and ships or mufflers of cars, is currently of major public and industrial interest. We aim to describe the effective absorption properties of sound absorbing resonator structures and perforated walls. As the governing equations and structures possess several scales, we study the problems asymptotically. In this project we derive and study approximative boundary and transmission conditions, that take into account the physical phenomena on the small scales inside the holes of the perforated absorber and the boundary layers in their neighbourhood.

    https://www.math.tu-berlin.de/fachgebiete_ag_modnumdiff/nachwuchsgruppe_dr_kersten_schmidt/nachwuchsgruppe_dr_kersten_schmidt/forschung/matheon_b_mi2/
  • MI3

    Infrastructure design and passenger behavior in public transport

    Prof. Dr. Ralf Borndörfer / Dr. Marika Karbstein

    Project heads: Prof. Dr. Ralf Borndörfer / Dr. Marika Karbstein
    Project members: Heide Hoppmann
    Duration: 01.06.2014 - 31.05.2017
    Status: running
    Located at: Konrad-Zuse-Zentrum für Informationstechnik Berlin

    Description

    The strategic planning process in public transport is usually divided into consecutive planning steps - network design, line planning, and timetabling. In line planning, one has to find a set of lines defined by their paths and frequencies in a public transportation network such that a given travel demand can be routed. The task of timetabling is to schedule the trips of each line, i.e., by determining periodic arrival and departure times at their stations. The goal of each planning step is to provide a transportation system that is both attractive for passengers and can be operated economically. Integrating passenger behaviour is a major challenge in infrastructure design optimization.

    The aim of this project is the adequate treatment of passenger routing in optimization models for public transport. We want to extend our existing theoretic and algorithmic base in line planning and timetabling by (advanced) passenger routing methods in order to construct efficiently solvable integrated models.

    Project Webpage

    http://www.zib.de/projects/infrastructure-design-and-passenger-behaviour-public-transport

more projects »


Financed by others

  • MI-AP1

    Competitive Exploration of Large Networks

    Dr. Yann Disser / Prof. Dr. Max Klimm

    Project heads: Dr. Yann Disser / Prof. Dr. Max Klimm
    Project members: -
    Duration: 01.06.2014 - 31.05.2017
    Status: running
    Located at: Technische Universität Berlin

    Description

    The goal of this project is to deepen the understanding of algorithms that operate on very large networks and the dynamics that arise from the competition or cooperation between such algorithms. To achieve this goal, we want to combine models and techniques from the areas of graph exploration and algorithmic game theory. To date, the literature in these areas is mostly disjoint. By closing this gap, we hope to develop new insights into the important algorithmic and economic challenges faced in large networks, most prominently in those that are part of the Internet.

    https://www.coga.tu-berlin.de/v-menue/projects/competitive_exploration_of_large_networks/?no_cache=1&tx_sibibtex_pi1[sort]=year%3A0
  • MI-AP10

    Centralized Respository for Test Data

    Prof. Dr. Thorsten Koch

    Project heads: Prof. Dr. Thorsten Koch
    Project members: -
    Duration: 01.10.2014 - 30.06.2018
    Status: running
    Located at: Konrad-Zuse-Zentrum für Informationstechnik Berlin

    Description

    The subproject Z02 aims for a central database of realistic gas network data in standardized formats, and providing interfaces to allow an easy access to the data. This common data standard and common pool of test data drive the workflow and cooperation of all subprojects. A gas network is described by many parameters. Experiences show that it is a very hard task to generate realistic data for gas networks with no access to real data of existing networks.This subproject cooperates with the biggest German network operator, Open Grid Europe GmbH, to compile test data from real gas network data. The generated test data will extend the existing GasLib library for stationary networks. This database relieves other subprojects from generating their own test data, and provides common test cases for them. So, different subprojects can compare their results more easily, since they use the same underlying data. One focus of the subproject Z02 is to standardize the data formats used, and to provide interfaces to them.This interfaces ease the data access for others. The usage of the same data structure throughout the different subprojects leads to more compatible programs and an easier cooperation. The overall goal of the subproject Z02 is to compile a selection of data sets, which can be used to run different demonstration scenarios. The data sets and their descriptions will be published, such that transparency and reproducibility of the results are assured.

    http://trr154.fau.de/index.php/en/subprojects/z02e
  • MI-AP17

    Efficient network flow methods for non-steady-state gasflows

    Prof. Dr. Martin Skutella

    Project heads: Prof. Dr. Martin Skutella
    Project members: -
    Duration: 01.10.2014 - 30.06.2018
    Status: running
    Located at: Technische Universität Berlin

    Description

    The goal of this subproject is to apply network flow theory to simplified models for gas pipelines and related transportation networks. Network flow theory has proven itself to be a powerful and valueable tool for solving complex problems in many areas of application, like traffic networks, telecommunication networks, and logistic networks. All of these networks can be designed and operated using network flow algorithms, which exhibit a very efficient runtime behaviour, making them capable of handling the large instances occuring in practice. In this subproject, we strive to employ network flow algorithms for solving problems in gas and related networks. Conventional network flow theory is insufficient to describe gas networks, since it neither accounts for pressures in nodes, nor for the non-linear dependency of the flow from the pressure in nodes. However, there are several problems in gas networks which occur in a similar form in network flow theory and are known and well understood there, for example generalized or length-bounded flows. Furthermore, non-linear relationships in other aspects like for example the flow velocity in traffic networks, have been studied and solved by network flow theory. As a base for our models we use a model based on the Weymouth equations, which can be solved using convex minimum cost flows. This flow model and its solution techniques can be generalized from the stationary to the transient case, analogous to how classic network flows can be generalized to dynamic network flows. For solving dynamic networks (approximately), there are useful techniques known from network flow theory, e.g. adaptive time-expanded networks, which have a great number of applications. These techniques are to be made useable for transient gas flows in this subproject. Gas networks usually contain a number of active elements - valves, compressors, and so on - which require integral decisions which have a significant impact on the gas flow. Therefore, these elements have to be incorporated in the network flow model. This can be handled by Branch & Bound based methods, or by adaption of techniques from network design. For Branch & Bound based techniques it is crucial to identify infeasible solutions as fast as possible. In gas networks, this means identifying partial configurations of active elements which imply infeasiblity. Therefore, analysis of infeasiblity will be a focus of the research done in this subproject. By developing efficient models and solution techniques for gas networks and characterizing infeasibility in these models, this subproject will contribute for Demonstrator 1, with a special focus on large gas networks.

    http://trr154.fau.de/index.php/en/subprojects/a07e

more projects »