A Multi-Sector Planning Support Model for en Route Air Traffic Control

Le concept de planification multisectorielle (PM) a été récemment introduit dans le contrôle du trafic aérien. Ce concept consiste à remplacer le contrôleur de planification par un planificateur multisectoriel (PrM). Le PrM est responsable des tâches de planification dans un ensemble de secteurs adjacents. L'objectif principal du PrM est de minimiser et d'équilibrer la charge de travail des contrôleurs entre les secteurs. Le PrM a besoin d'outils d'aide à la décision pour l'aider à accomplir ses tâches. L'objectif de cette thèse est de fournir au PrM un modèle d'aide à la décision qui minimise et équilibre la charge de travail des contrôleurs dans un ensemble de secteurs en route sur un horizon de temps moyen, soit 20 à 90 minutes. On propose une définition complète du problème de la résolution de la complexité, qui est une mesure de la charge de travail, dans le contexte de la PM. On représente la charge de travail des contrôleurs par le nombre de conflits. Pour obtenir des solutions optimales rapidement pour des problèmes impliquant de nombreux avions (par exemple 200), nous avons choisi d'utiliser un modèle de programmation linéaire mixte. Notre modèle minimise et équilibre le nombre des conflits de croisement et de rattrapage avec le nombre minimum de trajectoires modifiées. Nous présentons une formulation linéaire pour la détection et la résolution des conflits de croisement et de rattrapage. Notre formulation repose sur une transformation des distances de séparation en temps de séparation, et consiste à examiner ces temps en utilisant des contraintes linéaires. Nous avons aussi proposé une première méthode permettant d'équilibrer le nombre de conflits entre les secteurs. Notre modèle permet l'utilisation de changements de vitesse, de cap et d'altitude. Nous avons formulé le modèle de telle sorte que toutes les combinaisons de ces trois manœuvres puissent être utilisées ou empêchées. Nous avons défini les trois manœuvres pour obtenir des changements minimes du temps de parcours des trajectoires modifiées. Notre modèle ne modifie pas les points d'arrivée et de sortie des avions dans les secteurs. Pour un ensemble de problèmes étalons de détection-résolution de conflits, notre modèle a éliminé 100% des conflits dans des problèmes impliquant 25 avions et 300 conflits simultanés. Ces résultats ont été obtenus en moins d'une seconde de calculs. Pour un ensemble de problèmes de résolution de complexité générés aléatoirement et impliquant jusqu'à 200 avions, notre modèle a éliminé tous les conflits en modifiant moins de 30% des trajectoires. Le retard moyen par trajectoire modifiée était inférieur à 2,5% du temps de parcours. Nous concluons que notre modèle est un outil efficace pour réduire le nombre de conflits dans un ensemble de secteurs adjacents tout en minimisant le nombre de trajectoires modifiées. Notre modèle permet de calculer des solutions avec le nombre minimum de conflits dans un temps raisonnable (<10 minutes). Nous avons montré que l'ajout des changements de cap et d'altitude aux changements de vitesse permet de réduire significativement le nombre de conflits non résolus et le nombre de trajectoires modifiées. Nous avons aussi montré que notre méthode d'équilibrage des conflits entre les secteurs permet d'éviter de surcharger l'un des secteurs sans augmenter significativement le nombre total de conflits.

Abstract

The concept of multi-sector planning (MSP) was recently introduced into air traffic control to accommodate the continuous growth of air traffic. This concept consists in replacing the planner controller by a multi-sector planner (MSPr). The MSPr is responsible for the planning tasks in a set of adjacent sectors. The primary aim of the MSPr is to minimize and balance the workload among sectors. The MSPr needs advisory tools and models to help him fulfil his tasks. The main objective of this thesis is to develop a MSP support model that minimizes and balances controllers workload in a set of adjacent en route sectors over a medium time horizon, i.e. 20 to 90 minutes. We introduce a complete definition of the complexity resolution problem in a MSP context. The complexity is a measure for controllers workload. We choose to measure the controllers workload by the number of conflicts. Since the MSPr deals with many aircraft and requires relatively fast solutions, we formulate our model using a mixed integer linear program. Our model minimizes and balances the crossing and trailing conflicts with the minimum number of modified trajectories. We introduce a linear formulation for the detection and resolution of crossing and trailing conflicts. Our formulation relies on the transformation of safe separation distances into safe separation times and on the examination of the separation times between aircraft using linear constraints. We also propose a first method to take into account workload balancing in the complexity resolution problem. Our model enables the use of speed, heading and altitude changes. We formulated the model so that any combination of these three manoeuvres can be used or prevented. We defined the three manoeuvres so that the model ensures minimal changes in the travel duration of the modified trajectories. Our model also ensures spatial trajectory recovery. For a set of conflict detection and resolution benchmark problems, our model eliminates 100% of the conflicts in problems that involve up to 25 aircraft and 300 simultaneous conflicts. The solutions are obtained in less than one second. For a set of randomly generated complexity resolution problems, our model eliminates all the conflicts in problems that involve up to 200 aircraft by modifying less than 30% of the trajectories. The average delay per modified trajectory is less than 2.5% of the travel duration through the multi-sector area. We conclude that our model is an efficient tool to decrease and balance the total number of conflicts in a set of adjacent sectors using the minimum number of modified trajectories. Our model is able to obtain solutions with the minimum number of conflicts in a reasonable amount of time (<10 minutes). In comparison with the use of only speed changes, the introduction of the heading and altitude changes can reduce significantly the number of unresolved conflicts and the number of modified trajectories. We also found that our workload balancing method prevents overloading one of the sectors without a significant increase of the total number of conflicts.