direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

Flow-Preserving Graph Contractions with Applications to Logistics Networks

Dynamic Models and Algorithms for Equilibria in Traffic Networks
Project heads:
Max Klimm, Torsten M├╝tze, Guillaume Sagnol, Martin Skutella
Frieder Smolny
01.2019 - 12.2021
Project Number

This research is is supported by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany's Excellence Strategy-- The Berlin Mathematics Research Center MATH+ (EXC-2046\/1, project ID: 390685689).


Logistics networks keep growing in size and complexity, rendering them intractable for traditional optimization techniques. We investigate a contraction framework reducing the networks to manageable size, while preserving the routability of demands at a given cost, and under dynamic changes of the network.

Networks are a fundamental way of representing, organizing, and processing data. In recent years, two emerging trends challenge all traditional network optimization techniques. On the one hand, the amount of data has grown incessantly, eluding the main storage capacities of regular computing devices. Moreover, the types of network data available have become very diverse, rendering the direct application of standard solvers impossible. A prime example for these phenomenona are logistics networks, where data complexity arises from three independent developments.

First, a growing demand for individualized deliveries increases the number of point-to-point connections in the network. Second, the continuous accumulation of sensor data regarding the handling and delivery time of shipped items increases the amount and types of available data. Third, the high competitiveness of the logistics business is mirrored by complicated tariff structures that are difficult to represent in a mathematical model.

In this project, we address these challenges by network contractions. The general idea is to algorithmically generate appropriate approximations of the underlying network with a lower complexity in terms of the represented data. Then, the optimization problem at hand is solved for the contracted network. Finally, the solution for the smaller network is expanded to a solution of the full network. Unlike previous approaches on graph sparsification, which focused on preserving distances (spanners) or cuts (spectral sparsifiers), this project aims at retaining some more complex, structured features of the graph (existence of flows satisfying some demands and cost constraints).




Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

Auxiliary Functions