Project
AA3-4
Flow-Preserving Graph Contractions with Applications to Logistics Networks
Project Heads
Max Klimm, Torsten Mütze, Guillaume Sagnol, Martin Skutella
Project Members
Frieder Smolny (TU), Philipp Warode (TU)
Project Duration
01.01.2019 – 31.12.2021
Located at
TU Berlin
Description
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).
Selected Publications
- Travelling on Graphs with Small Highway Dimension, Y. Disser, A. E. Feldmann, M. Klimm, and J. Koenemann. In Proc. 45th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), pp. 175-189, 2019.
- Distance-Preserving Graph Contractions, A Bernstein, K. Däubel, Y. Disser, M. Klimm, T. Mütze and F. Smolny. In SIAM J. Discrete Math. 33(3): 1607-1636, 2019.
- The cone of flow matrices: Approximation hierarchies and applications, G. Sagnol, M. Blanco and T. Sauvage, Networks 72(1):128-150, 2018.
Selected Pictures
Network contractions
Network contractions are obtained when merging the end vertices of an edge.
Highway dimension
In a graph with small highway dimension, we can identify, for all local neighbourhoods, a small number of hubs that should be traversed by any shortest path of a certain length.Please insert any kind of pictures (photos, diagramms, simulations, graphics) related to the project in the above right field (Image with Text), by choosing the green plus image on top of the text editor. (You will be directed to the media library where you can add new files.)
(We need pictures for a lot of purposes in different contexts, like posters, scientific reports, flyers, website,…
Please upload pictures that might be just nice to look at, illustrate, explain or summarize your work.)
As Title in the above form please add a copyright.
And please give a short description of the picture and the context in the above textbox.
Don’t forget to press the “Save changes” button at the bottom of the box.
If you want to add more pictures, please use the “clone”-button at the right top of the above grey box.