💻 computer science

Assigning and optimising airport ground-handling operations: an rVNS metaheuristic

Diese Arbeit präsentiert eine kooperative reduzierte Variable Neighbourhood Search (rVNS) Metaheuristik zur Optimierung des komplexen Multi-Trip Kapazitätsbeschränkten Fahrzeugrouting- und Zeitplanungs-Problems mit Zeitfenstern und Mahlzeitenpausen (MTCVRSPTW-MB) für Catering-Abläufe am Flughafen, wobei sie deren überlegene Effizienz und Kilometerreduktion gegenüber exakten Methoden bei realen Instanzen am San Francisco International Airport demonstriert.

Ursprüngliche Autoren: Alexandre Dupaquis, Ronan Guivarch, Sandrine Mouysset, Daniel Ruiz, Vincent Charvillat, Frédéric Bouilhaguet

Veröffentlicht 2026-07-07

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Alexandre Dupaquis, Ronan Guivarch, Sandrine Mouysset, Daniel Ruiz, Vincent Charvillat, Frédéric Bouilhaguet

Originalarbeit lizenziert unter CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich einen geschäftigen Flughafen als ein riesiges, hochriskantes Puzzle vor. Auf der einen Seite kommen hunderte von Flugzeugen an und starten, von denen jedes verpflegt werden muss. Auf der anderen Seite befindet sich eine Flotte von Lastwagen und Fahrern, von denen jeder über spezifische Fähigkeiten, begrenzte Zeit und strikte Regeln bezüglich seiner Mittagspausen verfügt.

Das Ziel ist simpel: Jedes Flugzeug rechtzeitig zu verpflegen und dabei die geringste Anzahl an gefahrenen Kilometern der Lastwagen zu erreichen. Aber die Mathematik dahinter ist unglaublich komplex. Wenn man versucht, dies mit einem Standard-Computerprogramm zu lösen, ist es so, als würde man versuchen, ein einzelnes spezifisches Sandkorn an einem Strand zu finden, indem man jedes Korn einzeln überprüft – das dauert zu lange.

Dieses Paper stellt eine intelligentere, schnellere Methode zur Lösung dieses Puzzles vor, die als rVNS (reduced Variable Neighbourhood Search) bezeichnet wird. So funktioniert es, heruntergebrochen auf alltägliche Konzepte:

1. Das Problem: Das „Tetris“ der Flughafenverpflegung

Betrachten Sie das Bodenabfertigungsteam des Flughafens wie ein Spieler bei einem rasanten Spiel „Tetris“.

Die Blöcke: Dies sind die Aufgaben (ein Flugzeug beladen, ein Flugzeug entladen).
Die Slots: Dies sind die Fahrer und Lastwagen.
Die Regeln: Ein Fahrer kann nur einen bestimmten Lastwagen fahren; ein Lastwagen kann nur eine bestimmte Menge an Nahrung transportieren; ein Fahrer muss eine 30-minütige Mittagspause zwischen 4 und 5 Stunden nach Arbeitsbeginn einlegen; und ein Flugzeug muss innerhalb eines bestimmten Zeitfensters verpflegt werden.

In der Vergangenheit haben Forscher zwei Wege versucht, um dies zu lösen:

Der „perfekte“ Weg (Exakte Methode): Den Versuch, jede einzelne Möglichkeit zu berechnen, um die absolut beste Lösung zu finden. Das ist so, als würde man versuchen, jedes Buch in einer Bibliothek zu lesen, um die beste Geschichte zu finden. Es ist genau, dauert aber zu lange.
Der „schnelle“ Weg (Greedy Heuristic): Die jeweils beste Entscheidung im Moment zu treffen. Das ist so, als würde man das am nächsten gelegene Buch greifen, ohne nach anderen zu schauen. Es ist schnell, führt aber oft zu einem mittelmäßigen Ergebnis.

2. Die Lösung: Das „Schlaue Durchmischen“ (rVNS)

Die neue Methode, rVNS, ist wie ein Meister-Puzzellöser, der weiß, dass man manchmal eine gute Anordnung aufbrechen muss, um eine bessere zu schaffen.

Anstatt zu versuchen, das perfekte Puzzle von Grund auf neu aufzubauen, beginnt der Algorithmus mit einer ordentlichen Anordnung und spielt dann ein Spiel aus „Shuffle und Swap“ (Durchmischen und Tauschen).

Das Shuffle (Durchmischen): Es wählt zufällig einige Aufgaben (Blöcke) aus, entfernt sie aus dem Zeitplan und legt sie in einen „Warteraum“.
Das Swap (Tauschen): Es versucht dann, diese Aufgaben wieder einzufügen, aber diesmal versucht es, sie an andere Stellen einzupassen oder mit anderen Aufgaben zu tauschen, um zu sehen, ob das Gesamtbild besser aussieht.

Warum „Reduced“ (Reduziert)?
Normalerweise versuchen diese Algorithmen, riesige Teile des Puzzles durchzumischen, was langsam ist. Diese neue Methode mischt kleine Stücke durch, tut dies aber sehr schnell und wiederholt. Es ist wie ein Koch, der eine Suppe probiert und eine Prise Salz hinzufügt und dann erneut probiert, anstatt jedes Mal das gesamte Rezept umschreiben zu wollen.

3. Die Geheimzutat: Zwei verschiedene Strategien

Der Algorithmus ist klug genug zu wissen, wann er worauf fokussieren muss. Er hat zwei Modi:

Modus A (Der „Füller“): Sein Hauptziel ist es, sicherzustellen, dass keine Aufgabe vergessen wird. Er mischt den Zeitplan durch, um zu gewährleisten, dass jedes Flugzeug verpflegt wird.
Modus B (Der „Kilometer-Sparer“): Sobald die meisten Aufgaben zugewiesen sind, wechselt er den Fokus auf das Benzinsparen. Er sucht nach Möglichkeiten, die Lastwagen so umzuplanen, dass sie weniger Kilometer zwischen den Flugzeugen fahren.

4. Das „Team-Huddle“ (Parallelisierung)

Um dies noch schneller zu machen, haben die Forscher nicht nur ein einzelnes Computergehirn verwendet, sondern ein Team. Stellen Sie sich eine Gruppe von Detektiven vor, die versucht, ein Verbrechen aufzuklären. Anstatt dass eine Person jeden Hinweis prüft, teilen sie die Arbeit auf:

Detektiv-Team 1 arbeitet am Zeitplan für die Vormittagsschicht.
Detektiv-Team 2 arbeitet am Zeitplan für die Nachmittagsschicht.
Alle 10 Sekunden kommen sie zusammen, besprechen ihre besten Ideen und kombinieren ihre Ergebnisse.

Dies stellt sicher, dass sie nicht in einer „Sackgasse“ (einem lokalen Optimum) stecken bleiben, in der sie glauben, die beste Lösung gefunden zu haben, aber eigentlich eine bessere übersehen haben.

5. Die Ergebnisse: Schneller, Besser und Reibungsloser

Als sie diese neue Methode mit realen Daten vom San Francisco International Airport (SFO) testeten:

Erfolgsrate: Die alten Methoden konnten etwa 80–89 % der Aufgaben zuweisen. Die neue rVNS-Methode wies 99 % bis 99,8 % der Aufgaben zu. Sie lässt fast nie ein Flugzeug unversorgt.
Kraftstoffersparnis: Da sie den Zeitplan effizienter umstellt, fuhren die Lastwagen etwa 20 % bis 30 % weniger Kilometer als zuvor.
Geschwindigkeit: Sie fand diese nahezu perfekten Lösungen in weniger als einer Minute, was schnell genug ist, um in Echtzeit-Operationen eingesetzt zu werden.

Zusammenfassung

Kurz gesagt präsentiert dieses Paper einen neuen „schlauen Durchmischungs“-Algorithmus, der Flughafenmanagern hilft, die Verpflegungsaufgaben für Fahrer und Lastwagen zuzuweisen. Indem er das Problem in kleinere Teile zerlegt, sie zufällig durchmischt, um bessere Passformen zu finden, und ein Team von Computern nutzt, die zusammenarbeiten, stellt das System sicher, dass fast jedes Flugzeug verpflegt wird, während gleichzeitig deutlich weniger Kilometer gefahren werden als bei bisherigen Methoden. Es verwandelt ein chaotisches, unlösbares Puzzle in eine handhabbare, effiziente tägliche Routine.

Technisches Resümee: Zuweisung und Optimierung von Bodenabfertigungsabläufen am Flughafen mittels rVNS

Problemdefinition
Die Studie befasst sich mit der komplexen kombinatorischen Optimierung von Bodenabfertigungsabläufen am Flughafen, wobei der Schwerpunkt auf Catering-Diensten liegt. Das Kernproblem wird als Multi-Trip Capacitated Vehicle Routing and Scheduling Problem with Time Windows and Meal Breaks (MTCVRSPTW-MB) modelliert, welches erweitert wurde, um eine heterogene Flotte von LKWs und Fahrern mit unterschiedlichen Qualifikationen und Beladungsmustern zu berücksichtigen.

Das Ziel ist zweigeteilt:

Primär: Maximierung der Anzahl der zugewiesenen Catering-Aufgaben (Be- und Entladen von Flugzeugen) an verfügbare Fahrer und LKWs.
Sekundär: Minimierung der für die Ausführung dieser Aufgaben erforderlichen Gesamtfahrleistung (Kilometerleistung).

Das Problem unterliegt strengen operativen Regeln, einschließlich:

Fahrer-Beschränkungen: Schichtpläne, obligatorische 30-minütige Mahlzeitenpausen (die 4–5 Stunden nach Schichtbeginn stattfinden) und Qualifikationsanforderungen für spezifische Flugzeugtypen und Fluggesellschaften.
LKW-Beschränkungen: Kapazitätsgrenzen, spezifische LKW-Typen (14FT, 16FT, 22FT) und begrenzte tägliche Verfügbarkeit.
Aufgaben-Beschränkungen: Zeitfenster für die Ausführung, Kompatibilität zwischen LKW/Fahrer und der spezifischen Fluggesellschaft/Fluggesellschaft sowie Volumenanforderungen.
Mission-Beschränkungen: Regeln zur Steuerung von Multi-Task-Missionen, wie das Verbot von inländischen Entladungen nach internationalen Beladungen innerhalb derselben Mission, die Gewährleistung ausreichender Reisezeiten zwischen den Aufgaben und die Anforderung, dass alle Missionen in der Haupt-Catering-Einheit beginnen und enden.

Die Studie nutzt Echtzeitdaten des San Francisco International Airport (SFO) aus dem März 2023, die etwa 350 tägliche Aufgaben, 80 Fahrer und 40 LKWs umfassen. Eine kritische Anforderung ist, dass Lösungen innerhalb von einer Minute generiert werden müssen, um operativ lebensfähig zu sein.

Methodik
Die Autoren schlagen eine kooperative reduzierte Variable Neighborhood Search (rVNS) Metaheuristik vor. Dieser Ansatz wurde gegenüber der traditionellen Variable Neighborhood Search (VNS) und der Adaptive Large Neighborhood Search (ALNS) gewählt, um ein Gleichgewicht zwischen Recheneffizienz und Lösungsqualität zu finden.

Die Kernkomponenten der Methodik umfassen:

Reduzierter VNS (rVNS) Rahmen:
- Im Gegensatz zum klassischen VNS, das Schrittweiten variiert, verwendet das rVNS eine feste, kleine Schrittweite.
- Der Algorithmus arbeitet durch einen Dekonstruktions- und Rekonstruktionszyklus: Er weist eine feste Anzahl von Aufgaben ( $n$ ) aus der aktuellen Lösung ab und versucht, diese zufällig neu zuzuweisen.
- Um die feste Schrittweite zu kompensieren, nutzt der Algorithmus die hohe Symmetrie des Zeitplanungs-Problems. Durch die Exploration „äquivalenter“ Lösungen (unterschiedliche Zeitpläne mit identischen Scores) durch zufällige Vertauschungen diversifiziert der Suchprozess, ohne dass große, rechenintensive Schritte erforderlich sind.
Algorithmische Struktur:
- Zerlegung (Problem-Dichotomie): Der Tagesplan wird in zwei Teilprobleme (Vormittag und Nachmittag) basierend auf den Schichtüberlappungen der Fahrer aufgeteilt, was eine parallele Verarbeitung ermöglicht.
- Warm-Start-Heuristik: Das rVNS wird mit einer Lösung initialisiert, die durch eine Greedy-Heuristik erzeugt wurde, welche Aufgaben mit weniger qualifizierten Fahrern und obligatorischen Mahlzeitenpausen priorisiert. Dies verhindert, dass die Suche in einem schlechten lokalen Optimum startet.
- Dual-Objective-Randomisierung: Der Algorithmus wechselt zwischen zwei Randomisierungsstrategien basierend auf der Konvergenz des Objekts:
  - Primärer Fokus: Weist Aufgaben mit ähnlichen zeitlichen Positionen ab, um Raum für nicht zugewiesene Aufgaben zu schaffen.
  - Sekundärer Fokus: Weist Aufgaben ab, die am signifikantesten zur Gesamtfahrleistung beitragen.
- Sequenzierungs-Heuristik: Eine schnelle Heuristik (Algorithmus 3) prüft, ob eine Aufgabe in die Sequenz eines Fahrers eingefügt werden kann, ohne gegen Beschränkungen zu verstoßen, was entscheidend für die Aufrechterhaltung der Geschwindigkeit während der Rekonstruktionsphase ist.
- Kooperative Parallelisierung: Eine Multi-Start-Strategie läuft auf 8 Kernen (4 pro Teilproblem). Alle 10 Sekunden tauschen die parallelen Einheiten Ergebnisse aus und starten von der aktuellen besten Lösung aus, um die Varianz zu reduzieren und lokale Optima zu vermeiden.
Zielfunktion:
Die gesamte Zielfunktion $F$ ist eine gewichtete Summe, die die Aufgabenzuweisung priorisiert, gefolgt von der Reduzierung der Fahrleistung und schließlich der Missionseffizienz:
$F = 10^6 \sum a_i + 10^3 \sum (x_i + y_i) + \sum e_i$
Wobei $a_i$ die nicht zugewiesenen Aufgaben repräsentiert, $x_i$ und $y_i$ die Fahrstrecken darstellen und $e_i$ die Missionstarts zählt.

Wichtigste Ergebnisse
Die Studie vergleicht das vorgeschlagene rVNS mit einer Greedy-Heuristik und einer Matheuristic (zuvor entwickelt in [1]) unter Verwendung zweier Datensätze (S1: weniger, stärker beschränkte Aufgaben; S2: zahlreiche, weniger beschränkte Aufgaben).

Aufgabenzuweisung: Das rVNS übertrifft bisherige Methoden signifikant. Während die Greedy- und die Matheuristic-Ansätze etwa 80–89 % der Aufgaben zuwiesen, erreichte das rVNS Zuweisungsraten von 99,0 % bis 99,8 % in beiden Datensätzen.
Reduzierung der Fahrleistung: Das rVNS reduzierte die Gesamtfahrleistung der Flotte im Vergleich zur Matheuristic um etwa 30 % für den S1-Datensatz und um 20 % für den S2-Datensatz.
Stabilität und Konvergenz:
- Das parallelisierte rVNS zeigte eine größere Konsistenz als die sequentielle Version, mit einer Standardabweichung in der Fahrleistung von 2–3 % im Vergleich zu 4–6 % beim sequentiellen Ansatz.
- Konvergenzgeschwindigkeit: Für den kleineren Datensatz (S1) konvergierte das primäre Ziel (Aufgabenanzahl) schnell (innerhalb von ~1 Sekunde), während die Optimierung der Fahrleistung bis zu einer Minute lang weiter Verbesserungen aufwies. Für den größeren Datensatz (S2) benötigte das primäre Ziel etwa 10 Sekunden zur Konvergenz, wobei nach einer Minute abnehmende Grenzerträge eintraten.
Ausführungszeit: Alle Lösungen wurden innerhalb des geforderten Fensters von einer Minute generiert (speziell ~55–60 Sekunden inklusive Overhead).

Bedeutung und Ansprüche
Das Paper behauptet, dass die rVNS-Metaheuristik eine robuste, flexible Lösung für die Bodenabfertung am Flughafen bietet, die bestehende exakte und heuristische Baselines übertrifft. Die primäre Bedeutung liegt in:

Operativer Lebensfähigkeit: Es löst ein hochgradig beschränktes, multi-objektives Problem innerhalb des strengen Ein-Minuten-Zeitrahmens, der für das Echtzeit-Dispatching erforderlich ist.
Duale Optimierung: Es balanciert erfolgreich die Maximierung der Aufgabenerfüllung mit der Minimierung der operativen Kosten (Fahrleistung), ein Merkmal, das in früheren Arbeiten nicht vollständig optimiert wurde.
Flexibilität: Die Autoren merken an, dass die Struktur des Algorithmus die Integration neuer Beschränkungen oder Ziele ermöglicht, wie etwa das Management des Aufladens elektrischer Fahrzeuge oder Multi-Depot-Operationen.
Reale Anwendung: Die Studie zeigt, dass der Algorithmus die Komplexität realer Daten (einschließlich gleitender Zeitfenster und heterogener Flotten) besser handhaben kann als bisherige Modelle und somit ein Werkzeug darstellt, mit dem Bodenabfertiger hunderte tägliche Aufgaben automatisch zuweisen können.

Die Autoren bleiben bescheiden hinsichtlich der absoluten Optimalität und räumen ein, dass der Algorithmus keine globale Optimalität garantiert, jedoch konsistent Lösungen liefert, die bestehenden Methoden sowohl in der Geschwindigkeit als auch in der Qualität überlegen sind. Sie betonen das Potenzial für zukünftige Anwendungen in Szenarien der Echtzeit-Neuplanung, in denen verzögerte Aufgaben dynamisch neu geplant werden müssen.