A Branch-Price-Cut-And-Switch Approach for Optimizing Team Formation and Routing for Airport Baggage Handling Tasks with Stochastic Travel Times

Im Herzen eines jeden großen Flughafens liegt eine komplexe, hochriskante logistische Herausforderung, die die meisten Reisenden nie sehen: der Transport von Gepäck vom Terminal zum Flugzeug und wieder zurück. Dieser Prozess beruht auf Teams von Bodenpersonal, die zusammengestellt, ausgerüstet und mit chirurgischer Präzision über das Vorfeld geleitet werden müssen. Jeder Flug hat ein strenges Zeitfenster für das Be- oder Entladen, und das Versäumen dieser Fristen kann eine Kaskade von Verzögerungen, finanzielle Strafen für die Fluggesellschaft und frustrierte Passagiere auslösen. Die Schwierigkeit wird dadurch verschärft, dass das Bodenpersonal nicht austauschbar ist; sie verfügen über unterschiedliche Qualifikationsstufen, um spezifische schwere Maschinen wie High-Loader oder Förderbänder zu bedienen. Zudem ist das Vorfeld eine dynamische Umgebung, in der die Fahrzeiten zwischen den Parkpositionen selten vorhersehbar sind und oft durch kreuzende Flugzeuge oder lokale Verkehrsengpässe verlangsamt werden. Seit Jahrzehnten versuchen Planer, das Bedürfnis nach Geschwindigkeit mit der Realität dieser Unwägbarkeiten in Einklang zu bringen, wobei sie sich oft auf vereinfachte Annahmen stützen, die die chaotische Natur realer Abläufe nicht berücksichtigen.

Forscher der Technischen Universität München haben einen neuen Ansatz entwickelt, um dieses Rätsel zu lösen, indem sie über die statischen Modelle hinausgehen, die das Feld lange Zeit dominiert haben. Anstatt davon auszugehen, dass Fahrzeiten fix sind oder immer das Worst-Case-Szenario eintritt, behandelten sie die Bewegung der Bodenfahrzeuge als eine Variable mit bekannten Wahrscheinlichkeiten. Sie entwickelten einen hochentwickelten Algorithmus, der gleichzeitig entscheidet, welche Arbeiter ein Team bilden, welches Flugzeug sie bedienen und in welcher Reihenfolge dies geschieht, während er gleichzeitig die Wahrscheinlichkeit von Verzögerungen berücksichtigt. Der Kern ihrer Innovation ist eine Methode, die sie „Branch-Price-Cut-and-Switch“ nennen. Diese Technik ermöglicht es dem Computer, seine Strategie dynamisch zu ändern, während er nach der besten Lösung sucht. Er beginnt mit einer breiten, vereinfachten Sicht auf die Belegschaft, um schnell gute Optionen zu finden, aber wenn er auf einen Plan stößt, der mathematisch zwar fundiert, aber in der Realität unmöglich auszuführen ist – wie etwa ein Szenario, in dem ein Arbeiter ohne Fahrzeit magisch zwischen Aufgaben teleportiert wird –, wechselt er sofort zu einem detaillierteren, strengeren Modell, um den Fehler zu korrigieren. Dieser Wechselmechanismus stellt sicher, dass der endgültige Plan nicht nur ein mathematisches Ideal, sondern eine praktikable Realität ist.

Das Team testete seinen Algorithmus unter Verwendung von Daten, die von einem großen europäischen Drehkreuz generiert wurden, wobei Planungshorizonte von bis zu zwei Stunden mit dreißig ankommenden oder abfliegenden Flügen pro Stunde simuliert wurden. Sie verglichen ihre neue Methode mit bestehenden Ansätzen und stellten fest, dass sie diese signifikant übertraf, indem sie mehr komplexe Instanzen optimal löste und die Lücke zwischen der bestmöglichen Lösung und der vom Computer gefundenen Lösung verringerte. Entscheidend war, dass die Studie zeigte, dass die explizite Planung von Unsicherheit bessere Ergebnisse liefert als das Ignorieren derselben. Wenn der Algorithmus mit deterministischen Daten gefütert wurde – unter der Annahme, dass Fahrzeiten auf ihre Durchschnitts- oder Best-Case-Werte fixiert waren –, führten die resultierenden Pläne bei Tests gegen die simulierte reale Variabilität oft dazu, dass die Service-Anforderungen nicht erfüllt wurden. Im Gegensatz dazu konnten die Pläne, die durch die Berücksichtigung stochastischer, oder wahrscheinlichkeitstheoretischer Fahrzeiten erstellt wurden, konsistent hohe Service-Level aufrechterhalten und so sicherstellen, dass Flüge mit einem hohen Maß an Zuverlässigkeit pünktlich beladen wurden.

Eines der bemerkenswertesten Ergebnisse war, wie der Algorithmus den Kompromiss zwischen Effizienz und Sicherheit handhabte. Durch die Verwendung eines spezifischen statistischen Schwellenwerts, um zu bestimmen, wie viel Personal für potenzielle Verzögerungen reserviert werden sollte, konnten die Forscher das System so tunen, dass es entweder konservativer oder aggressiver agiert. Sie entdeckten, dass eine Planung mit einem moderaten Maß an Vorsicht, statt von den schlimmstmöglichen Verkehrsbedingungen auszugehen, eine effizientere Nutzung der verfügbaren Crew ermöglichte, während gleichzeitig garantiert wurde, dass Verzögerungen innerhalb akzeptabler Grenzen blieben. Dieser Ansatz baute effektiv Sicherheitspuffer in den Zeitplan ein, ohne Ressourcen zu verschwenden. Die Studie hob auch hervor, dass die bloße Annahme von durchschnittlichen Fahrzeiten unzureichend war; obwohl sie bessere Ergebnisse als die Annahme des Best-Case-Szenarios lieferte, führte sie dennoch häufig zu Verletzungen der Servicestandards. Nur durch die Modellierung des gesamten Spektrums möglicher Fahrzeiten und deren Wahrscheinlichkeiten konnte das System einen stabilen Service-Level garantieren und so die Art von unvorhersehbaren Verzögerungen verhindern, die Passagiere am Gepäckband warten lassen oder dazu führen, dass sie Anschlussflüge verpassen.

Die Implikationen dieser Arbeit erstrecken sich über das Vorfeld hinaus. Der Algorithmus bewies, dass es möglich ist, hocheffiziente, robuste Zeitpläne für komplexe, unsichere Umgebungen zu erstellen, ohne auf Vermutungen oder eine übermäßig konservative Planung zurückzugreifen, die Ressourcen brachliegen lässt. Durch den dynamischen Wechsel zwischen verschiedenen mathematischen Modellen und die Verwendung exakter Methoden, um praktikable Lösungen von rein theoretischen zu trennen, lieferten die Forscher einen Bauplan für den Umgang mit Unsicherheit in ressourcenbeschränkten Systemen. Ihre Ergebnisse legen nahe, dass Flughafenbetreiber eine höhere Pünktlichkeit und niedrigere Kosten erreichen können, indem sie die Unvorhersehbarkeit ihrer Umgebung annehmen, anstatt zu versuchen, sie zu ignorieren. Die Studie kommt zu dem Schluss, dass die explizite Berücksichtigung der stochastischen Natur von Fahrzeiten nicht nur eine theoretische Verbesserung, sondern eine praktische Notwendigkeit für moderne Flughafenabläufe ist, die einen Weg bietet, die verfügbare Belegschaft effizienter zu nutzen und gleichzeitig einen stabilen Service-Level für den Gepäckabfertiger zu gewährleisten.