💻 computer science

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

Dit artikel presenteert een coöperatieve gereduceerde Variable Neighbourhood Search (rVNS) metaheuristiek om het complexe Multi-Trip Capacitated Vehicle Routing and Scheduling Problem met Time Windows en pauzes voor maaltijden (MTCVRSPTW-MB) voor cateringoperaties op luchthavens te optimaliseren, waarbij de superieure efficiëntie en reductie in kilometers over exacte methoden wordt aangetoond op real-life instanties op de San Francisco International Airport.

Oorspronkelijke auteurs: Alexandre Dupaquis, Ronan Guivarch, Sandrine Mouysset, Daniel Ruiz, Vincent Charvillat, Frédéric Bouilhaguet

Gepubliceerd 2026-07-07

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Alexandre Dupaquis, Ronan Guivarch, Sandrine Mouysset, Daniel Ruiz, Vincent Charvillat, Frédéric Bouilhaguet

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je een druk vliegveld voor als een gigantische, hoogwaardige puzzel. Aan de ene kant heb je honderden vliegtuigen die arriveren en vertrekken, die elk voedsel moeten krijgen geladen of gelost. Aan de andere kant heb je een vloot vrachtwagens en chauffeurs, elk met specifieke vaardigheden, beperkte tijd en strikte regels over wanneer ze een pauze mogen nemen.

Het doel is simpel: elk vliegtuig op tijd voeden met zo min mogelijk gereden kilometers door de vrachtwagens. Maar de wiskunde erachter is ongelooflijk complex. Als je probeert dit met een standaard computerprogramma op te lossen, is het alsof je probeert een specifiek zandkorreltje op een strand te vinden door elk korreltje één voor één te controleren — dat duurt te lang.

Dit artikel introduceert een slimmere, snellere manier om deze puzzel op te lossen met een methode genaamd rVNS (reduced Variable Neighbourhood Search). Hier is hoe het werkt, uitgelegd aan de hand van alledaagse concepten:

1. Het Probleem: De "Tetris" van de luchthavenvoedselvoorziening

Denk aan het grondafhandelingsteam van de luchthaven die een razendsnel spelletje Tetris spelen.

De Blokken: Dit zijn de taken (een vliegtuig laden, een vliegtuig lossen).
De Slots: Dit zijn de chauffeurs en vrachtwagens.
De Regels: Een chauffeur kan alleen een specifieke vrachtwagen besturen; een vrachtwagen kan maar een bepaalde hoeveelheid voedsel vervoeren; een chauffeur moet een pauze van 30 minuten nemen tussen de 4 en 5 uur nadat hij is begonnen; en een vliegtuig moet binnen een specifieke tijdvenster gevoed worden.

In het verleden probeerden onderzoekers twee manieren om dit op te lossen:

De "Perfecte" Manier (Exacte Methode): Elke mogelijke berekening uitvoeren om de absoluut beste oplossing te vinden. Dit is als het proberen te lezen van elk boek in een bibliotheek om het beste verhaal te vinden. Het is accuraat, maar het duurt te lang.
De "Snelle" Manier (Greedy Heuristic): Op het moment zelf de beste keuze maken die beschikbaar is. Dit is als het pakken van het dichtstbijzijnde boek zonder naar de andere te kijken. Het is snel, maar leidt vaak tot een matig resultaat.

2. De Oplossing: De "Slimme Shuffle" (rVNS)

De nieuwe methode, rVNS, is als een meester-puzzeloplosser die weet dat je soms een goede ordening moet verbreken om een betere te maken.

In plaats van te proberen een perfecte puzzel vanaf nul op te bouwen, begint het algoritme met een redelijke ordening en speelt vervolgens een spel van "Shuffle en Swap".

De Shuffle: Het kiest willekeurig een paar taken (blokken) en haalt ze uit het schema, waardoor ze in een "wachtkamer" terechtkomen.
De Swap: Vervolgens probeert het algoritme die taken weer terug te plaatsen, waarbij het probeert ze op andere plekken te laten passen of te wisselen met andere taken om te zien of het algemene plaatje er beter uitziet.

Waarom "Reduced"?
Normaal gesproken proberen deze algoritmen enorme stukken van de puzzel te herschikken, wat traag is. Deze nieuwe methode herschikt kleine stukjes, maar doet dit zeer snel en herhaaldelijk. Het is als een chef die een soep proeft en er een snufje zout aan toevoegt, en dan weer proeft, in plaats van telkens het hele recept te willen herschrijven.

3. Het Geheime Ingrediënt: Twee Verschillende Strategieën

Het algoritme is slim genoeg om te weten waar het zich op moet focussen. Het heeft twee modi:

Modus A (De "Vuller"): Het hoofddoel is om ervoor te zorgen dat geen enkele taak wordt achtergelaten. Het herschikt het schema om te garanderen dat elk vliegtuig gevoed wordt.
Modus B (De "Kilometerbespaarder"): Zodra de meeste taken zijn toegewezen, schakelt het over naar de focus op brandstofbesparing. Het zoekt naar manieren om de vrachtwagens zo te rangschikken dat ze minder kilometers rijden tussen de vliegtuigen door.

4. De "Teamvergadering" (Parallelisatie)

Om dit nog sneller te maken, gebruikten de onderzoekers niet slechts één computerbrein, maar een heel team. Stel je een groep detectives voor die een misdaad probeert op te lossen. In plaats van dat één persoon elk bewijsstuk controleert, verdelen zij het werk:

Detective Team 1 werkt aan het schema voor de ochtenddienst.
Detective Team 2 werkt aan het schema voor de middagdienst.
Elke 10 seconden komen ze samen voor een korte overleg, delen hun beste ideeën en combineren hun bevindingen.

Dit zorgt ervoor dat ze niet vastlopen in een "doodlopende weg" (een lokaal optimum), waarbij ze denken dat ze de beste oplossing hebben gevonden, terwijl ze eigenlijk een betere hebben gemist.

5. De Resultaten: Sneller, Beter en Soepeler

Toen ze deze nieuwe methode testten met echte gegevens van San Francisco International Airport (SFO):

Succespercentage: De oude methoden slaagden erin om ongeveer 80–89% van de taken toe te wijzen. De nieuwe rVNS-methode wijsde 99% tot 99,8% van de taken toe. Het laat bijna nooit een vliegtuig onbediend.
Brandstofbesparing: Omdat het het schema efficiënter herrangschikt, reden de vrachtwagens ongeveer 20% tot 30% minder kilometers dan voorheen.
Snelheid: Het vond deze bijna perfecte oplossingen in minder dan een minuut, wat snel genoeg is voor real-time operaties.

Samenvatting

Kortom, dit artikel presenteert een nieuw "slimme shuffle"-algoritme dat luchthavenmanagers helpt bij het toewijzen van voedselleveringstaken aan chauffeurs en vrachtwagens. Door het probleem op te splitsen in kleinere stukken, ze willekeurig te herschikken om een betere pasvorm te vinden, en een team van computers te gebruiken om samen te werken, zorgt dit systeem ervoor dat bijna elk vliegtuig gevoed wordt terwijl er aanzienlijk minder kilometers worden gereden dan met eerdere methoden. Het verandert een chaotische, onmogelijk op te lossen puzzel in een beheersbare, efficiënte dagelijkse routine.

Technische Samenvatting: Toewijzing en Optimalisatie van Grondafhandeling op Luchthavens via rVNS

Probleemdefinitie
De studie behandelt de complexe combinatorische optimalisatie van grondafhandeling op luchthavens, specif으로 gericht op cateringdiensten. Het kernprobleem wordt gemodelleerd als het Multi-Trip Capacitated Vehicle Routing and Scheduling Problem with Time Windows and Meal Breaks (MTCVRSPTW-MB), uitgebreid om een heterogene vloot van vrachtwagens en chauffeurs met variërende kwalificaties en laadpatronen te accommoderen.

Het doel is tweeledig:

Primair: Maximaliseer het aantal cateringtaken (laden/lossen van vliegtuigen) toegewezen aan beschikbare chauffeurs en vrachtwagens.
Secundair: Minimaliseer de totale kilometerafstand die nodig is voor het uitvoeren van deze taken.

Het probleem wordt beperkt door strikte operationele regels, waaronder:

Chauffeursbeperkingen: Dienstroosters, verplichte pauzes van 30 minuten (4–5 uur na aanvang van de dienst) en kwalificatievereisten voor specifieke vliegtuigtypen en luchtvaartmaatschappijen.
Vrachtwagenbeperkingen: Capaciteitslimieten, specifieke vrachtwagentypes (14FT, 16FT, 22FT) en beperkte dagelijkse beschikbaarheid.
Taakbeperkingen: Tijdvensters voor uitvoering, compatibiliteit tussen vrachtwagen/chauffeur en de specifieke vlucht/l luchtvaartmaatschappij, en volumvereisten.
Missiebeperkingen: Regels die multi-taakmissies beheersen, zoals het verbieden van binnenlandse lossingen na internationale ladingen binnen dezelfde missie, het waarborgen van voldoende reistijd tussen taken, en de vereiste dat alle missies starten en eindigen bij de centrale cateringunit.

De studie maakt gebruik van real-world data van San Francisco International Airport (SFO) voor maart 2023, waarbij ongeveer 350 dagelijkse taken, 80 chauffeurs en 40 vrachtwagens betrokken zijn. Een cruciale vereiste is dat oplossingen binnen één minuut gegenereerd moeten worden om operationeel levensvatbaar te zijn.

Methodologie
De auteurs stellen een coöperatieve reduced Variable Neighborhood Search (rVNS) metaheuristiek voor. Deze benadering werd gekozen boven traditionele Variable Neighborhood Search (VNS) en Adaptive Large Neighborhood Search (ALNS) om een balans te vinden tussen computationele efficiëntie en de kwaliteit van de oplossing.

Kerncomponenten van de methodologie zijn:

Reduced VNS (rVNS) Framework:
- In tegenstelling tot klassieke VNS die stapgroottes varieert, gebruikt de rVNS een vaste, kleine stapgrootte.
- Het algoritme werkt via een deconstructie- en reconstructiecyclus: het haalt een vast aantal taken ( $n$ ) uit de huidige oplossing en probeert deze willekeurig opnieuw toe te wijzen.
- Om dit te compenseren voor de vaste stapgrootte, maakt het algoritme gebruik van de hoge symmetrie van het planningsprobleem. Door "equivalente" oplossingen te verkennen (verschillende schema's met identieke scores) via willekeurige wissels, diversifieert de zoektocht zonder dat er grote, computationeel dure stappen nodig zijn.
Algoritmische Structuur:
- Decompositie (Probleemdichotomie): Het dagelijkse schema wordt gesplitst in twee subproblemen (Ochtend en Middag) op basis van de overlap in de diensten van chauffeurs, wat parallelle verwerking mogelijk maakt.
- Warm-Start Heuristiek: De rVNS wordt geïnitialiseerd met een oplossing gegenereerd door een greedische heuristiek die prioriteit geeft aan taken met minder gekwalificeerde chauffeurs en verplichte maaltijdpauzes. Dit voorkomt dat de zoektocht in een slecht lokaal optimum begint.
- Dual-Objective Randomization: Het algoritme wisselt tussen twee randomisatiestrategieën op basis van convergentie van de doelstellingen:
  - Primaire focus: Haalt taken met vergelijkbare temporele posities weg om ruimte te creëren voor niet-toegewezen taken.
  - Secundaire focus: Haalt taken weg die het meest significant bijdragen aan de totale kilometerstand.
- Sequencing Heuristiek: Een snelle heuristiek (Algoritme 3) controleert of een taak in de sequentie van een chauffeur kan worden ingevoegd zonder de beperkingen te schenden, wat cruciaal is voor het behoud van snelheid tijdens de reconstructiefase.
- Coöperatieve Parallelisatie: Een multi-start strategie draait op 8 kernen (4 per subprobleem). Elke 10 seconden delen parallelle eenheden resultaten en starten ze opnieuw vanaf de huidige beste oplossing om variantie te verminderen en lokale optima te vermijden.
Doelfunctie:
De totale doelfunctie $F$ is een gewogen som die prioriteit geeft aan taaktoewijzing, gevolgd door kilometerreductie en ten slotte missie-efficiëntie:
$F = 10^6 \sum a_i + 10^3 \sum (x_i + y_i) + \sum e_i$
Waarbij $a_i$ de niet-toegewezen taken vertegenwoordigt, $x_i$ en $y_i$ de reisafstanden vertegenwoordigen, en $e_i$ het aantal missiestarts telt.

Belangrijkste Resultaten
De studie vergelijkt de voorgestelde rVNS met een Greedy Heuristic en een Matheuristic (voorheen ontwikkeld in [1]) met behulp van twee datasets (S1: minder, beperkte taken; S2: talrijke, minder beperkte taken).

Taaktoewijzing: De rVNS presteert aanzienlijk beter dan eerdere methoden. Terwijl de Greedy en Matheuristic benaderingen ongeveer 80–89% van de taken toewezen, bereikte de rVNS een toewijzingspercentage van 99,0% tot 99,8% over beide datasets.
Kilometerreductie: De rVNS verminderde de totale kilometerstand van het wagenpark met ongeveer 30% voor de S1-dataset en 20% voor de S2-dataset vergeleken met de Matheuristic.
Stabiliteit en Convergentie:
- De geparalleliseerde rVNS vertoonde meer consistentie dan de sequentiële versie, met een standaarddeviatie in kilometerstand van 2–3% vergeleken met 4–6% voor de sequentiële aanpak.
- Convergentiesnelheid: Voor de kleinere dataset (S1) convergeerde de primaire doelstelling (aantal taken) snel (binnen ~1 seconde), terwijl de optimalisatie van de kilometerstand verbeterde tot wel één minuut. Voor de grotere dataset (S2) vereiste de primaire doelstelling ~10 seconden voor convergentie, met afnemende meeropbrengsten na één minuut.
Executietijd: Alle oplossingen werden gegenereerd binnen de vereiste tijdvenster van één minuut (specifiek ~55–60 seconden inclusief overhead).

Betekenis en Claims
Het artikel beweert dat de rVNS metaheuristiek een robuuste, flexibele oplossing biedt voor grondafhandeling op luchthavens die superieur is aan eerdere exacte en heuristische baselines. De primaire betekenis ligt in:

Operationele Levensvatbaarheid: Het lost een zeer beperkt, multi-objective probleem op binnen de strikte tijd van één minuut die vereist is voor real-time dispatching.
Dubbele Optimalisatie: Het slaagt erin een balans te vinden tussen het maximaliseren van de voltooiing van taken en het minimaliseren van de operationele kosten (kilometers), een functie die in eerder werk niet volledig werd geoptimaliseerd.
Flexibiliteit: De auteurs merken op dat de structuur van het algoritme de integratie van nieuwe beperkingen of doelstellingen toestaat, zoals het beheren van het opladen van elektrische voertuigen of multi-depot operaties.
Real-World Applicatie: De studie toont aan dat het algoritme de complexiteit van real-world data (inclusief verschuivende tijdvensters en heterogene vloten) beter kan afhandelen dan eerdere modellen, waardoor het een instrument wordt dat grondafhandelaars kunnen gebruiken om automatisch honderden dagelijkse taken toe te wijzen.

De auteurs blijven bescheiden over absolute optimaliteit en erkennen dat, hoewel het algoritme geen globale optimum garandeert, het consequent oplossingen bereikt die superieur zijn aan bestaande methoden in zowel snelheid als kwaliteit. Ze benadrukken het potentieel voor toekomstige toepassing in scenario's van real-time herverdeling waarbij vertraagde taken dynamisch opnieuw gepland moeten worden.