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

In het hart van elk groot vliegveld ligt een complexe, risicovolle logistieke uitdaging die de meeste reizigers nooit zien: het transport van bagage van de terminal naar het vliegtuig en weer terug. Dit proces rust op teams van grondpersoneel die moeten worden samengesteld, uitgerust en over het platform gerouteerd met chirurgische precisie. Elke vlucht heeft een strikt tijdsvenster voor het laden of lossen, en het missen van deze deadlines kan een cascade aan vertragingen, financiële boetes voor de luchtvaartmaatschappij en gefrustreerde passagiers veroorzaken. De moeilijkheid wordt vergroot door het feit dat het grondpersoneel niet uitwisselbaar is; zij beschikken over verschillende niveaus van vaardigheid en zijn gekwalificeerd om specifieke zware machines te bedienen, zoals high-loaders of lopende banden. Bovendien is het platform een dynamische omgeving waar reistijden tussen parkeerplaatsen zelden voorspelbaar zijn, vaak vertraagd door passerende vliegtuigen of lokale congestie. Decennialang hebben planners geprobeerd de behoefte aan snelheid te balanceren met de realiteit van deze onzekerheden, waarbij ze vaak vertrouwden op vereenvoudigde aannames die er geen rekening mee houden met de chaotische aard van de praktijkoperaties.

Onderzoekers aan de Technische Universiteit van München hebben een nieuwe aanpak ontwikkeld om dit puzzelstuk op te lossen, waarbij ze verder gaan dan de statische modellen die het veld al lang overheersen. In plaats van ervan uit te gaan dat reistijden vaststaan of dat het slechtste scenario altijd zal optreden, behandelden zij de beweging van grondvoertuigen als een variabele met bekende waarschijnlijkheden. Ze creëerden een geavanceerd algoritme dat gelijktijdig beslist welke werkers een team vormen, welk vliegtuig zij bedienen en in welke volgorde, terwijl er rekening wordt gehouden met de waarschijnlijkheid van vertragingen. De kern van hun innovatie is een methode die zij "Branch-Price-Cut-and-Switch" noemen. Deze techniek stelt de computer in staat om de strategie dynamisch te wijzigen terwijl hij naar de beste oplossing zoekt. Het begint met een breed, vereenvoudigd beeld van de beroepsbevolking om snel goede opties te vinden, maar als het een plan tegenkomt dat wiskundig gezien wel klopt maar in de praktijk onmogelijk uitvoerbaar is — zoals een scenario waarin een werker magisch tussen taken wordt geteleporteerd zonder reistijd — schakelt het direct over naar een gedetailleerder, rigoureuzer model om de fout te corrigeren. Dit schakelmechanisme zorgt ervoor dat het uiteindelijke plan niet alleen een wiskundig ideaal is, maar een haalbare realiteit.

Het team testte hun algoritme met behulp van gegevens gegenereerd van een grote Europese hub-luchthaven, waarbij planningshorizonten van maximaal twee uur werden gesimuleerd met dertig vluchten die per uur arriveren of vertrekken. Ze vergeleken hun nieuwe methode met bestaande benaderingen en stelden vast dat het de bestaande methoden aanzienlijk overtrof, door meer complexe instanties tot optimaliteit op te lossen en de kloof tussen de best mogelijke oplossing en de door de computer gevonden oplossing te verkleinen. Cruciaal was dat de studie aantoonde dat expliciet plannen voor onzekerheid betere resultaten oplevert dan het negeren ervan. Wanneer het algoritme werd gevoed met deterministische gegevens — uitgaande van het scenario dat reistijden vaststonden op hun gemiddelde of beste waarde — faalden de resulterende plannen vaak in het voldoen aan de vereisten voor serviceniveaus wanneer ze werden getest tegen de gesimuleerdeerde onzekerheid van de echte wereld. In contrast hiermee behielden de plannen die werden gegenereerd door rekening te houden met stochastische, of probabilistische, reistijden consistent hoge serviceniveaus, waardoor werd gegarandeerd dat vluchten met een hoge mate van betrouwbaarheid op tijd werden geladen.

Een van de meest opvallende bevindingen was hoe het algoritme de afweging tussen efficiëntie en veiligheid beheerde. Door een specifieke statistische drempelwaarde te gebruiken om te bepalen hoeveel personeel er gereserveerd moest worden voor potentiële vertragingen, konden de onderzoekers het systeem afstemmen om ofwel conservatiever ofwel agressiever te zijn. Ze ontdekten dat plannen met een matig niveau van voorzichtigheid, in plaats van uit te gaan van de slechtst mogelijke verkeersomstandigheden, een meer efficiënt gebruik van de beschikbare crew mogelijk maakte, terwijl er nog steeds werd gegarandeerd dat vertragingen binnen acceptabele grenzen zouden blijven. Deze aanpak bouwde effectief veiligheidsbuffers in de planning in zonder middelen te verspillen. De studie benadrukte ook dat het simpelweg aannemen van gemiddelde reistijden onvoldoende was; hoewel het betere resultaten opleverde dan het aannemen van het best-case scenario, leidde het nog steeds tot frequente schendingen van de servicestandaarden. Alleen door het volledige bereik van mogelijke reistijden en hun waarschijnlijkheden te modelleren, kon het systeem een stabiel serviceniveau garanderen, wat de onvoorspelbare vertragingen voorkomt die passagiers laten wachten bij de bagageafhandeling of doen missen van aansluitende vluchten.

De implicaties van dit werk reiken verder dan het platform. Het algoritme bewees dat het mogelijk is om zeer efficiënte, robuuste schema's te creëren voor complexe, onzekere omgevingen zonder terug te vallen op gokwerk of overdreven conservatieve planning die middelen onbenut laat. Door dynamisch te schakelen tussen verschillende wiskundige modellen en exacte methoden te gebruiken om haalbare oplossingen te scheiden van oplossingen die slechts theoretisch zijn, boden de onderzoekers een blauwdruk voor het omgaan met onzekerheid in systemen met beperkte middelen. Hun resultaten suggereren dat luchthavenexploitanten een hogere punctualiteit en lagere kosten kunnen bereiken door de onvoorspelbaarheid van hun omgeving te omarmen in plaats van te proberen deze te negeren. De studie concludeert dat het expliciet rekening houden met de stochastische aard van reistijden niet alleen een theoretische verbetering is, maar een praktische noodzaak voor moderne luchthavenoperaties, wat een manier biedt om de beschikbare beroepsbevolking efficiënter te benutten en tegelijkertijd een stabiel serviceniveau te garanderen voor de bagageafhandelaar.