Génération d'itinéraires de passagers dans un réseau de transport aérien

L'optimisation des opérations liées au domaine du transport aérien vise à réduire les coûts d'exploitation et à maximiser les revenus. La réduction des coûts peut être améliorée par la résolution de divers problèmes reliés à l'affectation des ressources comme la rotation des équipages par exemple. Les revenus peuvent être évalués par une approximation des ventes de billets et du positionnement par rapport à la concurrence et aussi grâce à la valeur ajoutée au service. Dans le transport aérien, l'évaluation des revenus issus de la vente de billets est faite grâce à des modèles de flots de passagers. Ces modèles servent à déterminer de quelle manière un réseau de transport pourra fournir le service de transport à d'éventuels passagers et quels seront les niveaux d'achalandage des différents vols; des niveaux élevés pourraient indiquer qu'une offre de service est insuffisante et suggérer aux planificateurs qu'une modification à l'horaire des vols soit requise ou qu'un type d'avion capable de transporter beaucoup de passagers est nécessaire pour suffire à la demande. Mais pour fonctionner, un modèle de flots de passagers requiert de connaître des itinéraires que les passagers sont susceptibles d'emprunter. L'objet des présents travaux de recherche porte sur des méthodes d'énumération d'un ensemble d'itinéraires de passagers. Deux méthodes d'énumération sont présentées, toutes deux faisant appel une approximation utilisée pour accélérer les calculs en limitant le nombre d'itinéraires générés. La première méthode se base sur un modèle mathématique fort répandu dans le domaine de l'optimisation des réseaux de transport: un réseau espace-temps. On y applique une variante de l'algorithme classique de recherche en profondeur (\emph{depth-first search}). La seconde méthode est de nature combinatoire et ne requiert aucun modèle mathématique particulier mais fait appel à des structures de données accessoires afin de produire des combinaisons rapidement. Dans chaque cas, des variantes sont utilisées visant à améliorer le temps de calcul par une heuristique. L'heuristique utilisée est l'information relative aux bornes inférieures de temps entre chaque paire $(O,D)$ où $O$ est une origine et $D$ une destination pour lesquelles on souhaite trouver des itinéraires. Dans un premier temps, les bornes sont calculées \emph{a priori} et dans un second temps, elles sont mises à jour dynamiquement par une technique de relaxation. Les techniques d'optimisation des réseaux de transport sont telles que les sous-problèmes, comme la rotation de personnel ou la confection d'un horaire des vols par exemple, soient résolus de manière itérative. Ainsi, des améliorations successives peuvent être apportées aux solutions de chacun de ces sous-problèmes jusqu'à l'obtention d'une solution globale jugée satisfaisante dans son ensemble. L'énumération d'itinéraires de passagers dépend d'un horaire de vols et doit être mise à jour dès lors qu'une modification y est apportée. Or ces modifications sont souvent faites localement, c'est-à-dire que seuls quelques vols sont modifiés, souvent n'affectant que quelques régions géographiques particulières. Il est donc intéressant de procéder uniquement aux re-calculs nécessaires et d'éviter les calculs redondants. La seconde méthode décrite ci-haut, dans sa version dynamique, sera mise à contribution dans de telles conditions.