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

Au cœur de chaque grand aéroport se cache un défi logistique complexe et à enjeux élevés que la plupart des voyageurs ne voient jamais : le mouvement des bagages du terminal vers l'avion et inversement. Ce processus repose sur des équipes d'agents de piste qui doivent être rassemblées, équipées et acheminées sur le tarmac avec une précision chirurgicale. Chaque vol dispose d'une fenêtre de temps stricte pour le chargement ou le déchargement, et manquer ces échéances peut déclencher une cascade de retards, des pénalités financières pour la compagnie aérienne et l'exaspération des passagers. La difficulté est accentuée par le fait que les agents de piste ne sont pas interchangeables ; ils possèdent différents niveaux de compétence, étant qualifiés pour opérer des machines lourdes spécifiques comme des chargeurs de conteneurs ou des tapis roulants. De plus, le tarmac est un environnement dynamique où les temps de trajet entre les postes de stationnement sont rarement prévisibles, souvent ralentis par le passage d'aéronefs ou la congestion locale. Pendant des décennies, les planificateurs ont lutté pour équilibrer le besoin de rapidité avec la réalité de ces incertitudes, en s'appuyant souvent sur des hypothèses simplifiées qui ne tiennent pas compte de la nature chaotique des opérations réelles.

Des chercheurs de l'Université technique de Munich ont développé une nouvelle approche pour résoudre ce casse-tête, dépassant les modèles statiques qui dominent le domaine depuis longtemps. Au lieu de supposer que les temps de trajet sont fixes ou que le pire scénario se produira toujours, ils ont traité le mouvement des véhicules au sol comme une variable dotée de probabilités connues. Ils ont créé un algorithme sophistiqué qui décide simultanément quelle équipe de travailleurs former, quel avion desservir et dans quel ordre, tout en tenant compte de la probabilité de retards. Le cœur de leur innovation est une méthode qu'ils appellent « Branch-Price-Cut-and-Switch » (Ramification-Prix-Coupe-et-Commutation). Cette technique permet à l'ordinateur de changer dynamiquement de stratégie lorsqu'il recherche la meilleure solution. Il commence par une vue large et simplifiée de la main-d'œuvre pour trouver rapidement de bonnes options, mais s'il rencontre un plan qui semble mathématiquement cohérent mais impossible à exécuter dans la réalité — comme un scénario où un travailleur serait téléporté magiquement entre deux tâches sans temps de trajet — il bascule instantanément vers un modèle plus détaillé et rigoureux pour corriger l'erreur. Ce mécanisme de commutation garantit que le plan final n'est pas seulement un idéal mathématique, mais une réalité réalisable.

L'équipe a testé son algorithme en utilisant des données générées par un grand aéroport pivot européen, simulant des horizons de planification allant jusqu'à deux heures avec trente vols arrivant ou partant chaque heure. Ils ont comparé leur nouvelle méthode aux approches existantes et ont constaté qu'elle les surpassait de manière significative, résolvant davantage d'instances complexes de manière optimale et réduisant l'écart entre la meilleure solution possible et celle trouvée par l'ordinateur. Crucialement, l'étude a démontré que planifier explicitement l'incertitude produit de meilleurs résultats que de l'ignorer. Lorsque l'algorithme était alimenté par des données déterministes — supposant que les temps de trajet étaient fixes à leurs valeurs moyennes ou optimales — les plans résultants échouaient souvent à respecter les exigences de niveau de service lorsqu'ils étaient testés contre la variabilité réelle simulée. En revanche, les plans générés en considérant des temps de trajet stochastiques, ou probabilistes, maintenaient systématiquement des niveaux de service élevés, garantissant que les vols soient chargés à temps avec un haut degré de fiabilité.

L'une des découvertes les plus frappantes fut la façon dont l'algorithme gérait le compromis entre efficacité et sécurité. En utilisant un seuil statistique spécifique pour déterminer la quantité de main-d'œuvre à réserver pour les retards potentiels, les chercheurs pouvaient régler le système pour qu'il soit soit plus conservateur, soit plus agressif. Ils ont découvert qu'une planification avec un niveau de prudence modéré, plutôt que de supposer les pires conditions de trafic possibles, permettait une utilisation plus efficace de l'équipage disponible tout en garantissant que les retards resteraient dans des limites acceptables. Cette approche intégrait ainsi des marges de sécurité dans le planning sans gaspiller de ressources. L'étude a également souligné que supposer simplement des temps de trajet moyens était insuffisant ; bien que cela produise de meilleurs résultats que de supposer le meilleur scénario, cela entraînait tout de même de fréquentes violations des normes de service. Ce n'est qu'en modélisant toute la gamme des temps de trajet possibles et leurs probabilités que le système pouvait garantir un niveau de service stable, évitant ainsi les retards imprévisibles qui laissent les passagers attendre à la livraison des bagages ou manquer leurs correspondances.

Les implications de ce travail s'étendent au-delà du tarmac. L'algorithme a prouvé qu'il est possible de créer des calendriers hautement efficaces et robustes pour des environnements complexes et incertains sans recourir à des conjectures ou à une planification excessivement conservatrice qui laisserait les ressources oisives. En basculant dynamiquement entre différents modèles mathématiques et en utilisant des méthodes exactes pour séparer les solutions réalisables de celles qui sont purement théoriques, les chercheurs ont fourni un modèle pour gérer l'incertitude dans les systèmes à ressources limitées. Leurs résultats suggèrent que les opérateurs d'aéroports peuvent atteindre une ponctualité plus élevée et des coûts moindres en embrassant l'imprévisibilité de leur environnement plutôt qu'en essayant de l'ignorer. L'étude conclut qu'en tenir compte explicitement de la nature stochastique des temps de trajet n'est pas seulement une amélioration théorique, mais une nécessité pratique pour les opérations aéroportuaires modernes, offrant un moyen d'utiliser la main-d'œuvre disponible plus efficacement tout en garantissant simultanément un niveau de service stable pour l'opérateur de traitement des bagages.