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.

Abstract

Commercial airlines optimization aims at reducing costs and maximizing revenues. The cost reduction can be improved by solving various resource allocation problems such as crew pairing problem. The increase in revenues can be estimated by approximating passenger ticket sales, value-added services to customers compared to competition. In air transportation networks, passenger flow models are used for evaluating revenues from passenger ticket sales. Such models are useful for determining how the network will provide services to customers and what are the occupation levels on each flight. High levels of occupation could indicate that a service offer is insufficient. This, in turn, could suggest to the planner that a flight schedule modification is needed or that reviewing the type of aircraft assigned to satisfy the demand is needed. However, to function well, the passenger flow model requires a set of passenger itineraries in input. The objective of this masters thesis is to present and compare methods for enumerating a set of passenger itineraries. Two methods are introduced, both of them using a heuristic for accelerating computations by limiting the number of itineraries being generated that are not suitable from the passengers point of view. The heuristic in use is a lower bound on the travel time between each pair (O,D) of airports, O being an origin and D a destination. The first method uses a mathematical model vastly used in transportation networks optimization, a space-time network. We proceed with a modified version of a classical algorithm on graphs, the depth-first search. The second method is a combinatorial approach, leaves aside the need for the mathematical model used by the first method and only uses intermediate data structures for the fast retrieval of subsets of itineraries, which depends on the combinations to be evaluated. In each case, an alternate version is also implemented in regards to the computing of the heuristic's information In the original version of the two algorithms mentioned above, the heuristic is computed as a pre-treatment and values are obtained by a shortest-path algorithm whereas the heuristic is being updated dynamically in the alternate version by use of a relaxation technique. Actual optimization techniques in use for transportation networks are such that sub-problems, like crew assignment or flight scheduling for instance, are resolved in an iterative process. This leads to successively improving each solution of the sub-problems up to a point where a global, satisfying solution is found. The passenger route enumeration depends on the flight schedule and the resulting set needs to be updated whenever the schedule is modified. However, these modifications are often made locally, meaning that only a limited number of the passenger itineraries are being affected by the modifications. This, in turn, means that only a few geographical regions are being concerned. It is therefore interesting to proceed by performing only local recomputations, avoiding useless recomputations. And the second method described above, in its dynamic version, is being tested in such conditions.