Nouveaux types d'algorithmes d'optimisation en nombres entiers et applications aux horaires d'équipages aériens

点击翻译按钮获取中文摘要

La planification des horaires d'équipages dans les grandes compagnies aériennes s'effectue en deux étapes qui sont traitées séquentiellement : 1- construction des rotations d'équipage et 2- construction des horaires mensuels des membres d'équipage. De plus, durant les opérations, des perturbations peuvent survenir et requérir des mises à jour 3- des rotations d'équipages et 4- des horaires mensuels. Les 4 étapes présentent une structure similaire et se formulent à l'aide de modèles du type partitionnement ou recouvrement d'ensemble. Ces problèmes sont résolus dans l'industrie avec la méthode de génération de colonnes pour obtenir des solutions fractionnaires et une méthode de branchement pour obtenir une solution entière. Des méthodes de résolution plus performantes sont requises, car la taille des problèmes à traiter augmente. Non seulement les réseaux aériens sont plus grands, mais on veut traiter directement des problèmes mensuels de construction de rotations au lieu de les décomposer en problèmes hebdomadaires.Un premier objectif est de développer pour ces problèmes un tout nouveau type d'optimiseur qui, à partir d'une solution entière, produit une meilleure solution entière sans passer par des solutions fractionnaires comme les méthodes de branchement. Pour les très grands problèmes, cet optimiseur pourra utiliser tout le temps disponible pour produire la meilleure solution possible. Il pourra aussi être utilisé pour améliorer la solution produite par une autre méthode s'il reste du temps disponible.Un deuxième objectif sera de développer les modèles et les algorithmes pour optimiser simultanément les rotations d'équipages et les blocs mensuels, et ce lors de la planification et lors de la mise à jour suite à des perturbations le jour d'opération. Ces traitements intégrés devraient produire des gains de productivité intéressants, car la méthode actuelle qui fixe d'abord les rotations limite le choix pour les horaires mensuels.Le traitement de plus grands problèmes dans des temps raisonnables et la production de meilleures solutions donneront des avantages concurrentiels à notre partenaire industriel sur les marchés internationaux.