idw – Informationsdienst Wissenschaft
Nachrichten, Termine, Experten
Nachrichten, Termine, Experten
TU-Mathematikerin entwickelt Algorithmus für Waren- und Datentransport
Die Mathematikerin Srinwanti Debgupta hat in ihrer Masterarbeit einen Algorithmus entwickelt, mit dem Waren oder Daten in einem Netzwerk möglichst effizient versandt werden können, ohne einzelne Paletten, Container oder Datenpakete aufteilen zu müssen. Ihren Ansatz wird sie im Rahmen eines Projekts des Exzellenzclusters MATH+, bei dem die TU Berlin eine der antragstellenden Hochschulen ist, weiterverfolgen. Das Thema ist auch Grundlage für ihre Promotion am Fachgebiet „Kombinatorische Optimierung und Graphenalgorithmen“ von Prof. Dr. Martin Skutella an der TU Berlin. Er sowie Dr. Sarah Morell von der Arbeitsgruppe „Kombinatorische Optimierung und Logistik“ der Universität Bremen haben zu den Ergebnissen beigetragen. Srinwanti Debgupta wurde nun für ihre Masterarbeit von der Forschungsvereinigung Großhandel e. V. (ForveG) bei deren Forschungsförderpreis 2025 mit einer Lobenden Erwähnung ausgezeichnet.
In der Großhandelslogistik müssen Waren aus mehreren Lagern zu einem Netzwerk von Einzelhandelsgeschäften möglichst effizient transportiert werden. Oftmals wäre es dabei nicht sinnvoll, Paletten, Container oder Lkw-Ladungen aufzuteilen und getrennt zu transportieren. Manchmal verbieten das sogar Regularien. Gleichzeitig unterliegt aber auch das Transportnetzwerk bestimmten Beschränkungen: Straßen können nur eine bestimmte Verkehrsmenge bewältigen, Umschlagplätze haben eine begrenzte Durchsatzkapazität, Lkw, Güterwagons und Binnenschiffe nur eine bestimmte Ladekapazität. Und in der Telekommunikation gibt es Datenpakete, die in einem Informationsnetzwerk mit begrenzten Kapazitäten versandt werden müssen und nicht aufgeteilt werden dürfen.
Keine exakte mathematische Lösung in vertretbarer Rechenzeit
Wie also können Güter oder Datenpakete über ein Netzwerk transportiert werden, sodass jede Sendung einem einzigen Weg folgt, keine Straße oder kein Knotenpunkt überlastet wird und jeder Empfänger das erhält, was er benötigt? „Wir untersuchen die mathematische Abstraktion dieses Problems, das wir als ‚unsplittable transshipments‘ bezeichnen“, erklärt Srinwanti Debgupta. Aufbauend auf Vorarbeiten, die nur ein Lager betrachteten, hat sie in einem generalisierten Ansatz ein Netzwerk mit vielen Lagern und Anlieferstellen betrachtet und festgestellt, dass dies eigentlich ein „NP-schweres“ Problem ist – es existieren also keine exakten mathematischen Lösungen, die für große Netzwerke in vertretbarer Zeit berechnet werden könnten. Debgupta konnte in ihrer Masterarbeit aber einen Algorithmus finden, der eine Lösung in angemessener Zeit errechnet, wenn gewisse Überschreitungen der Anforderungen zugelassen werden.
Algorithmus lässt Überschreitungen um das Doppelte zu
„In Situationen, in denen eine Überlastung unvermeidbar ist, stellt der Algorithmus sicher, dass die Überschreitung nie mehr als das Doppelte beträgt. Das hört sich zunächst viel an, ist aber oft tolerierbar“, erklärt Srinwanti Debgupta. Vor allem könne dieser „Faktor zwei“ auf verschiedene Arten angewandt werden: Entweder müssen doppelt so viele Straßen befahren werden, oder eine Straße muss den doppelten Verkehr tolerieren. „Wir können auch die Zeit variieren, und die Auslieferung auf zwei Runden aufteilen.“ Dies sei für die Logistik-Branche keine ungewohnte Anforderung, denn dort würden Lieferungen stets in zeitlichen Wellen, Runden oder Zeitfenstern organisiert.
Integration in digitale Planungswerkzeuge in der Logistik
Mit dem Algorithmus bleiben für Großhandelsunternehmen also Überlastungen innerhalb vorhersehbarer, kontrollierbarer Grenzen. Er läuft in berechenbarer „polynominaler“ Zeit und skaliert mit der Netzwerkgröße. Dadurch eignet er sich für große Verteilungsnetze und für die Integration in digitale Planungswerkzeuge in der Logistik. Auch in sogenannten digitalen Zwillingen, die Logistik-Netzwerke eins zu eins simulieren, könnte er zum Einsatz kommen. „Die einzige Randbedingung ist, dass die Nachfrage insgesamt durch die Gesamtkapazität des Netzwerks überhaupt gedeckt werden kann“, sagt Debgupta. Dann stünde einem unteilbaren Transport nichts mehr im Weg.
Zusätzliche Informationen:
Die Masterarbeit von Srinwanti Debgupta ist nicht online verfügbar, dafür aber diese Veröffentlichungen zum Thema:
Single source unsplittable flows with arc-wise lower and upper bounds; Sarah Morell, Martin Skutella; Math. Program. 192(1): 477-496 (2022): https://link.springer.com/article/10.1007/s10107-021-01704-4
Integer and Unsplittable Multiflows in Series-Parallel Digraphs; Mohammed Majthoub Almoghrabi, Martin Skutella, Philipp Warode; IPCO 2025: 427-441: https://link.springer.com/chapter/10.1007/978-3-031-93112-3_31
Förderpreis für Exzellente Nachwuchsforschung im Großhandel, https://www.forveg.de/forschungspreis/
Weitere Informationen erteilt Ihnen gern:
Srinwanti Debgupta
Fachgebiet „Kombinatorische Optimierung und Graphenalgorithmen“
Fakultät II – Mathematik und Naturwissenschaften
Technische Universität Berlin
E-Mail: srinwanti.debgupta@campus.tu-berlin.de
Criteria of this press release:
Journalists
Mathematics, Traffic / transport
transregional, national
Research results, Studies and teaching
German
You can combine search terms with and, or and/or not, e.g. Philo not logy.
You can use brackets to separate combinations from each other, e.g. (Philo not logy) or (Psycho and logy).
Coherent groups of words will be located as complete phrases if you put them into quotation marks, e.g. “Federal Republic of Germany”.
You can also use the advanced search without entering search terms. It will then follow the criteria you have selected (e.g. country or subject area).
If you have not selected any criteria in a given category, the entire category will be searched (e.g. all subject areas or all countries).
