Wie man unteilbare Pakete am besten verschickt
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/art
Integer and Unsplittable Multiflows in Series-Parallel Digraphs; Mohammed
Majthoub Almoghrabi, Martin Skutella, Philipp Warode; IPCO 2025: 427-441:
<https://link.springer.com/cha
Förderpreis für Exzellente Nachwuchsforschung im Großhandel,
<https://www.forveg.de/forschu
