AA3 – Next Generation Networks

Project

AA3-17

Efficient Algorithms for Quickest Transshipment Problems

Project Heads

Martin Skutella

Project Members

Lizaveta Manzhulina

Project Duration

01.01.2024 – 31.12.2025

Located at

TU Berlin

Description

The Quickest Transshipment Problem is to route flow as quickly as possible from sources with supplies to sinks with demands in a network with capacities and transit times on the arcs. It is of fundamental importance for numerous applications in areas such as logistics, traffic, evacuation, and finance. This project aims at a better structural understanding of quickest transshipments leading to practically efficient algorithms that can a find optimal or near-optimal solutions in large-scale traffic networks. The main mathematical challenge is to find more efficient ways to deal with the underlying submodular functions whose repeated minimization constitutes the main bottleneck of known algorithmic approaches.

Project Webpages

Selected Publications

  • Miriam Schlöter, Martin Skutella, Khai Van Tran. A faster algorithm for quickest transshipments via an extended discrete Newton method. In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 90-102, 2022. Doi: 10.1137/1.9781611977073.5
  • Martin Skutella. An introduction to transshipments over time. In Felix Fischer and Robert Johnson, editors, Surveys in Combinatorics 2024, pages 239-270, Cambridge University Press, 2024. Doi: 10.1017/9781009490559.009
  • Martin Skutella. A note on the quickest minimum cost transshipment problem. Operations Research Letters 51(3): 255-258, 2023. Doi: 10.1016/J.ORL.2023.03.005

Selected Pictures

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.