L'augmentation des besoins en bande passante dans les réseaux de télécommunications pousse les opérateurs à déployer de nouvelles infrastructures. Pour le réseau d'accès fixe, la fibre optique est la technologie envisagée. Du fait des enjeux financiers et de la complexité qui vont de pair avec ce déploiement, il est crucial d'optimiser son coût tout en respectant à la fois les attentes en qualité de service et les règles d'ingénierie du déploiement. Cette thèse fait suite à des travaux antérieurs, à l'issue desquels le problème avait été modélisé sous la forme d'un programme linéaire en nombres entiers. Un travail conséquent quant à l'amélioration de la résolution de ce problème avait été fourni, et de nombreuses pistes de recherches avaient été envisagées pour faire suite à ces travaux. Parmi ces pistes, il y avait le traitement de l'incertitude sur la demande qui occupe une grande partie de cette étude. En effet, les futurs clients ne s'étant pas encore déclarés, il n'est plus possible de dimensionner le réseau par rapport à des données connues et fixées. Dans ce cas, le problème devient un problème d'optimisation combinatoire dans l'incertain. Le choix a été fait de le traiter sous l'angle de l'optimisation robuste. Cette approche permet de se prémunir contre l'incertitude en garantissant la faisabilité des solutions dans tous les cas ainsi qu'une optimisation du " pire cas ". Le formalisme qui en découle rend souvent les problèmes étudiés complexes à résoudre. En effet, ils font intervenir des formulations à plusieurs niveaux où les décisions sont prises en séquence, avant ou après la réalisation du scénario incertain. Des algorithmes adaptés ont été développés pour permettre l'application de la robustesse au déploiement des réseaux de fibres optiques. Ces algorithmes, exacts ou approchés, ont permis, via leurs résultats, d'obtenir une connaissance stratégique réelle pour les déploiements à venir. A la suite de ces investigations sur le problème du déploiement optique, certains résultats ont pu être étendus et généralisés à d'autres problèmes d'optimisation robuste, comme par exemple des bornes de probabilité sur la pertinence des ensembles d'incertitudes ou une estimation probabiliste des coûts futurs dans les problèmes d'optimisation robuste en deux étapes. En marge de ces travaux sur l'incertitude qui occupent la plus grande partie de cette étude, d'autres travaux ont été réalisés sur ce problème. En effet, dans le but d'améliorer la prise en compte des coûts futurs du réseau (maintenance, gestion, etc.) qui sont, sur le long terme, les plus importants, une approche a été développée qui permet de prendre en compte les " bonnes pratiques " de déploiement directement dans l'optimisation. L'intégration de ces considérations, regroupées sous le terme d'OA&M (pour Organisation, Administration et Maintenance), a été validée par le développement de macro-modèles de coûts, à même d'estimer les gains futurs à attendre de ces nouvelles contraintes. Enfin, nos efforts ont porté sur la résolution d'une version particulière du problème, dans des graphes qui sont des arbres, avec la prise en compte des contraintes de câblage dans l'optimisation. Pour ce problème qui avait déjà été étudié, un nouvel algorithme de programmation dynamique a été proposé. Il s'appuie fortement sur les propriétés du problème et les utilise pour n'explorer qu'un nombre très limité de solutions tout en restant exact. Les performances de l'algorithme ont montré une nette amélioration du temps de calcul par rapport à des approches de type programmation linéaire en nombres entiers. L'ensemble de ces travaux a permis de découvrir d'autres pistes de recherche, notamment sur des versions alternatives du traitement de l'incertitude, ainsi que sur une prise en compte plus fine du câblage dans l'optimisation.

La programmation mathématique est une technique qui peut être utilisée pour résoudre des problèmes concrets où l'on veut maximiser, ou minimiser, une fonction objectif soumise à des contraintes sur les variables décisionnelles. Les caractéristiques les plus importantes de la programmation mathématique sont la création d'un modèle pour décrire le problème (aussi appelé formulation), et la mise en œuvre d'algorithmes efficaces pour le résoudre (aussi appelés solveurs). Dans cette thèse, on s'occupe du premier point. Plus précisemment, on étudie certains problèmes qui proviennent de domaines diffèrents, et en commençant par les modèles les plus naturels pour les décrire, on présente des formulations alternatives, qui partagent certaines propriétés avec le modèle original mais qui sont en quelque sorte meilleures (par exemple au niveau du temps d'exécution nécessaire pour obtenir la solution par le solveur). Ces nouveaux modèles sont appelés reformulations. On suit la classification des reformulations proposée par Liberti dans [Reformulations in Mathematical Programming: Definitions and Systematics, RAIRO-OR, 43(1):55-86, 2009]: exact reformulations (aussi appellées opt-reformulations), narrowings, relaxations. Cette thèse concerne trois applications de la programmation mathématique où les reformulations ont été fondamentales pour obtenir une bonne solution. Le premier problème étudié est le partitionnement de graphes sur la base de la maximisation de la modularité. Comme ce problème est NP-difficile, plusieurs heuristiques sont proposées. On s'occupe d'un algorithme séparatif hiérarchique qui fonctionne en divisant récursivement une classe en deux nouvelles classes de façon optimale. Cet étape de division est accomplie en résolvant un programme binaire quadratique et convexe. Il est reformulé de manière exacte pour obtenir une forme plus compacte sans modifier l'ensemble des solutions optimales (exact reformulation). On considère aussi l'impact donné par la réduction du nombre des solutions symétriques globalement optimales. Les temps d'exécution sont considérablement réduits par rapport à la formulation originelle. Le deuxième problème étudié dans cette thèse est le placement de cercles égaux dans un carré (Packing Equal Circles in a Square, ou PECS), où l'on veut placer des cercles égaux dans un carré de côté 1 sans avoir de superposition et en maximisant le rayon commun. L'une des raisons pour laquelle le problème est difficile à résoudre vient de la présence de plusieurs solutions symétriques optimales, et par conséquent un arbre de séparation-et-évaluation (ou Branch-and-Bound) très large. Certaines solutions symétriques optimales sont rendues irréalisables en ajoutant des contraintes pour briser les symétries (Symmetry Breaking Constraints, ou SBCs) à la formulation, en obtenant ainsi un narrowing. Le temps d'exécution et la dimension de l'arbre de Branch-and-Bound sont tous les deux meilleurs par rapport à la formulation originelle. La troisième application considérée dans cette thèse est le calcul de la relaxation convexe pour des problèmes multilinéaires, et la comparaison de la formulation ''primale'' avec celle obtenue par une représentation ''duale''. Bien que ces deux relaxations soient déjà connues, il est intéressant de voir que la relaxation duale conduit à des meilleures performances de calcul.

Ce mémoire illustre la difficile déclinaison du paradigme de l'optimalité lors de sa confrontation aux principes de réalité de systèmes toujours plus complexes. Après avoir récapitulé l'expérience de recherche acquise à travers des contributions variées, qui nous emmènent de problèmes de contrôle en dimension infinie à des applications dans les domaines du spatial, de l'énergie et de l'automobile, les développements spécifiques en matière de prospective long terme seront l'objet d'une attention particulière. Ainsi, le credo que l'optimalité est un canevas nécessaire pour envisager les enjeux d'une modélisation du long terme sera défendu, soutenant l'idée que cette approche devra rester centrale dans nos perspectives de recherche. Mais dans la tradition d'une formation "à la française", cette réflexion ne saura être menée sans revenir au préalable sur les grands principes sous jacents à l'optimalité et leur liaison naturelle avec l'étude des systèmes dynamiques.

En raison de problèmes opérationnels et d’autres événements inattendus, un grand nombre d’incidents se produisent quotidiennement dans les systèmes de transport ferroviaire. Certains d’entre eux ont un impact local, mais quelques fois, essentiellement dans les réseaux ferroviaires plus saturés, des petits incidents peuvent se propager à travers tout le réseau et perturber de manière significative les horaires des trains. Dans cette thèse doctorale, nous présentons le problème de réordonnancement de plan de circulation ferroviaire en cas d’incident comme la problématique de créer un plan de circulation provisoire de manière à minimiser les effets de la propagation des incidents. Ce travail est issu du projet MAGES (Module d’Aide à la Gestion des Sillons) qui développe des systèmes de régulation pour le trafic ferroviaire. Nous présentons deux modèles différents qui permettent de trouver des solutions à ce problème : Programmation Linéaire en Nombres Entiers (PLNE) et Programmation Par Contraintes (PPC). Du fait de la nature fortement combinatoire du problème et de la nécessité de répondre rapidement aux incidents, il ne paraît pas raisonnable d’envisager une résolution exacte. Les méthodes correctives proposées consistent donc à explorer un voisinage restreint des solutions : right-shift rescheduling; une méthode basée sur des coupes de proximité; une méthode d’analyse statistique de la propagation des incidents (SAPI) et un méthode basée sur la PPC. Additionnellement, certaines de ces méthodes ont été adaptées sous forme d’algorithmes itératifs avec l’objectif d’améliorer progressivement la solution quand le temps d’exécution le permet. SAPI est une des principales contributions de cette thèse. SAPI intègre les concepts de right-shift rescheduling avec les coupes de proximité. Du fait de la taille des réseaux en jeu et du nombre de circulations, les phénomènes complexes de propagation d’un incident font qu’il est très difficile de connaitre de manière précise les événements qui seront affectés. Toutefois, il est tout de même envisageable d’évaluer la probabilité qu’un événement soit affecté. Pour calculer cette probabilité, un modèle de régression logistique est utilisé avec des variables explicatives dérivées du réseau et des circulations. Diverses variantes de ces méthodes sont évaluées et comparées en utilisant deux réseaux ferroviaires localisés en France et au Chili. À partir des résultats obtenus, il est possible de conclure que SAPI est meilleure que les autres méthodes en terme de vitesse de convergence vers l’optimum pour les instances de petite taille et moyenne alors qu’une méthode coopérative PNLE/PPC est capable de trouver des solutions pour les instances de plus grande taille. La difficulté de comparer SAPI avec d’autres méthodes présentées dans la littérature nous a encouragés à appliquer la méthode à un autre problème. Ainsi, cette méthodologie a été également adaptée au problème de réordonnancement de passagers, vols et appareils (avions) en cas de perturbations, problème originalement proposé dans le contexte du Challenge ROADEF 2009. Les résultats montrent que SAPI est efficace pour résoudre ce problème avec des solutions au-dessus de la moyenne des équipes finalistes en obtenant la troisième place du challenge / For operational and unpredictable reasons, many small incidents occur day after day in rail transportation systems. Most of them have a local impact; but, in some cases, minimal disruptions can spread out through the whole network and affect significantly the train schedules. In this Thesis, we present the Railway Rescheduling Problem (RRP) as the problem of finding a new schedule of trains after one or several incidents by minimizing some measure of the effect, e.g., the total delay. This Thesis has been developed in the context of the MAGES project that builds mathematical models and algorithms for optimizing railway operations. Two complementary formulations are proposed to model this problem: Mixed-Integer Programming (MIP) and Constraint Programming (CP). Because of the impossibility of solving real-world instances by using standard solvers, we propose several solutions methods: right-shift rescheduling; a MIP-based local search method; Statistical Analysis of Propagation of Incidents (SAPI); and a CP-based approach. Some methods are presented in different versions by extending them to iterative approaches. Among them; SAPI is one of the major contributions of this Thesis. It integrates the concepts of right-shift rescheduling and the MIP-based local search method by fixing integer variables and adding linear inequalities (cuts). SAPI assumes that the effects of disruptions can be propagated to other upcoming events. Nevertheless, this propagation is not uniform to all events and could be forecasted by a statistical analysis. Different versions of the methods are compared in two different networks located in France and Chile. From the results, it is possible to conclude that SAPI finds good solutions faster than the other methods, while a cooperative CP/MIP approach that takes advantage of both formulations seems to be appropriate for large instances. Because of the difficulty to compare SAPI to other methods presented in the literature due to lack of public benchmarks, we applied it to another problem where public instances are available. Hence, the methodology was adapted and applied to the problem of rescheduling passengers, flights, and aircraft under disrupted operations in the context of the ROADEF challenge 2009. SAPI took the third position on this competition, showing that the method seems to be effective solving such type of problems efficiently

Cette thèse porte sur la résolution exacte et heuristique de plusieurs problèmes ayant des applications dans le domaine de l'Informatique dématérialisé (cloud computing). L'Informatique dématérialisée est un domaine en plein extension qui consiste à mutualiser les machines/serveurs en définissant des machines virtuelles représentant des fractions des machines/serveurs. Il est nécessaire d'apporter des solutions algorithmiques performantes en termes de temps de calcul et de qualité des solutions. Dans cette thèse, nous nous sommes intéressés dans un premier temps au problème d'ordonnancement sur plusieurs machines (les machines virtuelles) avec contraintes de précédence, c.-à-d., que certaines tâches ne peuvent s'exécuter que si d'autres sont déjà finies. Ces contraintes représentent une subdivision des tâches en sous tâches pouvant s'exécuter sur plusieurs machines virtuelles. Nous avons proposé plusieurs algorithmes génétiques permettant de trouver rapidement une bonne solution réalisable. Nous les avons comparés avec les meilleurs algorithmes génétiques de la littérature et avons défini les types d'instances où les solutions trouvées sont meilleures avec notre algorithme. Dans un deuxième temps, nous avons modélisé ce problème à l'aide de la programmation linéaire en nombres entiers permettant de résoudre à l'optimum les plus petites instances. Nous avons proposé de nouvelles inégalités valides permettant d'améliorer les performances de notre modèle. Nous avons aussi comparé cette modélisation avec plusieurs formulations trouvées dans la littérature. Dans un troisième temps, nous avons analysé de manière approfondie la sous-structure du sous-graphe d'intervalle ne possédant pas de clique de taille donnée. Nous avons étudié le polytope associé à cette sous-structure et nous avons montré que les facettes que nous avons trouvées sont valides pour le problème d'ordonnancement sur plusieurs machines avec contraintes de précédence mais elles le sont aussi pour tout problème d'ordonnancement sur plusieurs machines. Nous avons étendu la modélisation permettant de résoudre le précédent problème afin de résoudre le problème d'ordonnancement sur plusieurs machines avec des contraintes disjonctives entre les tâches, c.-à-d., que certaines tâches ne peuvent s'exécuter en même temps que d'autres. Ces contraintes représentent le partage de ressources critiques ne pouvant pas être utilisées par plusieurs tâches. Nous avons proposé des algorithmes de séparation afin d'insérer de manière dynamique nos facettes dans la résolution du problème puis avons développé un algorithme de type Branch-and-Cut. Nous avons analysé les résultats obtenus afin de déterminer les inégalités les plus intéressantes afin de résoudre ce problème. Enfin dans le dernier chapitre, nous nous sommes intéressés au problème d'ordonnancement d'atelier généralisé ainsi que la version plus classique d'ordonnancement d'atelier (open shop). En effet, le problème d'ordonnancement d'atelier généralisé est aussi un cas particulier du problème d'ordonnancement sur plusieurs machines avec des contraintes disjonctives entre les tâches. Nous avons proposé une formulation à l'aide de la programmation mathématique pour résoudre ces deux problèmes et nous avons proposé plusieurs familles d'inégalités valides permettant d'améliorer les performances de notre algorithme. Nous avons aussi pu utiliser les contraintes définies précédemment afin d'améliorer les performances pour le problème d'ordonnancement d'atelier généralisé. Nous avons fini par tester notre modèle amélioré sur les instances classiques de la littérature pour le problème d'ordonnancement d'atelier. Nous obtenons de bons résultats permettant d'être plus rapide sur certaines instances / The Cloud Computing appears as a strong concept to share costs and resources related to the use of end-users. As a consequence, several related models exist and are widely used (IaaS, PaaS, SaaS. . .). In this context, our research focused on the design of new methodologies and algorithms to optimize performances using the scheduling and combinatorial theories. We were interested in the performance optimization of a Cloud Computing environment where the resources are heterogeneous (operators, machines, processors...) but limited. Several scheduling problems have been addressed in this thesis. Our objective was to build advanced algorithms by taking into account all these additional specificities of such an environment and by ensuring the performance of solutions. Generally, the scheduling function consists in organizing activities in a specific system imposing some rules to respect. The scheduling problems are essential in the management of projects, but also for a wide set of real systems (telecommunication, computer science, transportation, production...). More generally, solving a scheduling problem can be reduced to the organization and the synchronization of a set of activities (jobs or tasks) by exploiting the available capacities (resources). This execution has to respect different technical rules (constraints) and to provide the maximum of effectiveness (according to a set of criteria). Most of these problems belong to the NP-Hard problems class for which the majority of computer scientists do not expect the existence of a polynomial exact algorithm unless P=NP. Thus, the study of these problems is particularly interesting at the scientific level in addition to their high practical relevance. In particular, we aimed to build new efficient combinatorial methods for solving parallel-machine scheduling problems where resources have different speeds and tasks are linked by precedence constraints. In our work we studied two methodological approaches to solve the problem under the consideration : exact and meta-heuristic methods. We studied three scheduling problems, where the problem of task scheduling in cloud environment can be generalized as unrelated parallel machines, and open shop scheduling problem with different constraints. For solving the problem of unrelated parallel machines with precedence constraints, we proposed a novel genetic-based task scheduling algorithms in order to minimize maximum completion time (makespan). These algorithms combined the genetic algorithm approach with different techniques and batching rules such as list scheduling (LS) and earliest completion time (ECT). We reviewed, evaluated and compared the proposed algorithms against one of the well-known genetic algorithms available in the literature, which has been proposed for the task scheduling problem on heterogeneous computing systems. Moreover, this comparison has been extended to an existing greedy search method, and to an exact formulation based on basic integer linear programming. The proposed genetic algorithms show a good performance dominating the evaluated methods in terms of problems' sizes and time complexity for large benchmark sets of instances. We also extended three existing mathematical formulations to derive an exact solution for this problem. These mathematical formulations were validated and compared to each other by extensive computational experiments. Moreover, we proposed an integer linear programming formulations for solving unrelated parallel machine scheduling with precedence/disjunctive constraints, this model based on the intervaland m-clique free graphs with an exponential number of constraints. We developed a Branch-and-Cut algorithm, where the separation problems are based on graph algorithms. [...]

Étude de certains problèmes d'optimisation combinatoire. Le premier concerne un problème de régulation de trafic pour lequel on donne une formulation mathématique et on propose une méthode permettant de le résoudre. Le deuxième problème traité est un des problèmes de la physique statistique qui relève de la combinatoire et de l'optimisation, celui du fondamental d'un verre de spins (modèle d'Ising). Enfin on étudie, deux autres problèmes d'optimisation combinatoire: l'absorbant et le Ki-recouvrement de poids minimum

La tomographie est un ensemble de techniques visant à reconstruirel'intérieur d'un objet sans toucher l'objet lui même comme dans le casd'un scanner. Les principes théoriques de la tomographie ont été énoncéspar Radon en 1917. On peut assimiler l'objet à reconstruire à une image,matrice, etc.Le problème de reconstruction tomographique consiste à estimer l'objet àpartir d'un ensemble de projections obtenues par mesures expérimentalesautour de l'objet à reconstruire. La tomographie discrète étudie le cas où lenombre de projections est limité et l'objet est défini de façon discrète. Leschamps d'applications de la tomographie discrète sont nombreux et variés.Citons par exemple les applications de type non destructif comme l'imageriemédicale. Il existe d'autres applications de la tomographie discrète, commeles problèmes d'emplois du temps.La tomographie discrète peut être considérée comme un problème d'optimisationcombinatoire car le domaine de reconstruction est discret et le nombrede projections est fini. La programmation mathématique en nombres entiersconstitue un outil pour traiter les problèmes d'optimisation combinatoire.L'objectif de cette thèse est d'étudier et d'utiliser les techniques d'optimisationcombinatoire pour résoudre les problèmes de tomographie.

Afin de pouvoir subvenir aux futurs besoins en matière de transport aérien il est nécessaire d'augmenter la capacité de l'espace aérien. Les contrôleurs aériens, qui occupent une place centrale dans la gestion du trafic, doivent quotidiennement faire face à des situations conflictuelles (conflits) lors desquelles deux vols risquent de violer les normes de séparation en vigueur si aucune modification de trajectoire n'est envisagée. La détection et la résolution des conflits potentiels contribuent à augmenter la charge de travail des contrôleurs et peuvent potentiellement les conduire à diriger les vols vers des zones moins denses de l'espace aérien, induisant a posteriori un retard pour les vols. Le problème de la capacité de l'espace aérien peut donc être abordé en régulant les flux de trafic de façon réduire la quantité de conflits aériens. L'objectif de cette thèse est de mettre au point une méthodologie destinée à minimiser les risques de conflits aériens en modifiant légèrement les vitesses des appareils. Cette approche est principalement motivée par les conclusions du projet ERASMUS portant sur la régulation de vitesse subliminale. Ce type de régulation a été conçu de façon à ne pas perturber les contrôleurs aériens dans leur tâche. En utilisant de faibles modulations de vitesse, imperceptibles par les contrôleurs aériens, les trajectoires des vols peuvent être modifiées pour minimiser la quantité totale de conflits et ainsi faciliter l'écoulement du trafic dans le réseau aérien. La méthode retenue pour mettre en œuvre ce type de régulation est l'optimisation sous contrainte. Dans cette thèse, nous développons un modèle d'optimisation déterministe pour traiter les conflits à deux avions. Ce modèle est par la suite adapté à la résolution de grandes instances de trafic en formulant le modèle comme un Programme Linéaire en Nombres Entiers. Pour reproduire des conditions de trafic réalistes, nous introduisons une perturbation sur la vitesse des vols, destinée à représenter l'impact de l'incertitude en prévision de trajectoire dans la gestion du trafic aérien. Pour valider notre approche, nous utilisons un outil de simulation capable de rejouer des journées entières de trafic au dessus de l'espace aérien européen. Les principaux résultats de ce travail démontrent les performances du modèle de détection et de résolution de conflits et soulignent la robustesse de la formulation face à l'incertitude en prévision de trajectoire. Enfin, l'impact de notre approche est évalué à travers divers indicateurs propres à la gestion du trafic aérien et valide la méthodologie développée.

Afin de pouvoir subvenir aux futurs besoins en matière de transport aérien il est nécessaire d'augmenter la capacité de l'espace aérien. Les contrôleurs aériens, qui occupent une place centrale dans la gestion du trafic, doivent quotidiennement faire face à des situations conflictuelles (conflits) lors desquelles deux vols risquent de violer les normes de séparation en vigueur si aucune modification de trajectoire n'est envisagée. La détection et la résolution des conflits potentiels contribuent à augmenter la charge de travail des contrôleurs et peuvent potentiellement les conduire à diriger les vols vers des zones moins denses de l'espace aérien, induisant a posteriori un retard pour les vols. Le problème de la capacité de l'espace aérien peut donc être abordé en régulant les flux de trafic de façon réduire la quantité de conflits aériens. L'objectif de cette thèse est de mettre au point une méthodologie destinée à minimiser les risques de conflits aériens en modifiant légèrement les vitesses des appareils. Cette approche est principalement motivée par les conclusions du projet ERASMUS portant sur la régulation de vitesse subliminale. Ce type de régulation a été conçu de façon à ne pas perturber les contrôleurs aériens dans leur tâche. En utilisant de faibles modulations de vitesse, imperceptibles par les contrôleurs aériens, les trajectoires des vols peuvent être modifiées pour minimiser la quantité totale de conflits et ainsi faciliter l'écoulement du trafic dans le réseau aérien. La méthode retenue pour mettre en œuvre ce type de régulation est l'optimisation sous contrainte. Dans cette thèse, nous développons un modèle d'optimisation déterministe pour traiter les conflits à deux avions. Ce modèle est par la suite adapté à la résolution de grandes instances de trafic en formulant le modèle comme un Programme Linéaire en Nombres Entiers. Pour reproduire des conditions de trafic réalistes, nous introduisons une perturbation sur la vitesse des vols, destinée à représenter l'impact de l'incertitude en prévision de trajectoire dans la gestion du trafic aérien. Pour valider notre approche, nous utilisons un outil de simulation capable de rejouer des journées entières de trafic au dessus de l'espace aérien européen. Les principaux résultats de ce travail démontrent les performances du modèle de détection et de résolution de conflits et soulignent la robustesse de la formulation face à l'incertitude en prévision de trajectoire. Enfin, l'impact de notre approche est évalué à travers divers indicateurs propres à la gestion du trafic aérien et valide la méthodologie développée. / As global air traffic volume is continuously increasing, it has become a priority to improve air traffic control in order to deal with future air traffic demand. One of the current challenges regarding air traffic management is the airspace capacity problem, which is acknowledged to be correlated to air traffic controllers' workload. Air traffic controllers stand at the core of the traffic monitoring system and one of their main objective is to ensure the separation of aircraft by anticipating potential conflicts. Conflict detection and resolution are likely to increase workload and may lead them to reroute aircrafts to less dense areas, triggering off flight delay. The airspace capacity problem can hence be tackled by regulating air traffic flow in order to reduce the global conflict quantity. The objective of this thesis is to develop a methodology aiming at minimizing potential conflicts quantity by slightly adjusting aircraft speeds in real time. This approach is mainly motivated by conclusions of the ERASMUS project on subliminal speed control, which was designed to keep air traffic controllers unaware of the ongoing regulation process. By focusing on low magnitude speed modulations, aircraft trajectories can be modified to reduce the quantity of conflicts and smoothen air traffic flow in the airspace network. The method used to carry out this type of regulation is constraint optimization. In this thesis, we develop a deterministic optimization model for two-aircraft conflicts which is then adapted to large scale instances using Mixed-Integer Linear Programming. In order to reproduce realistic navigation conditions, uncertainty on aircraft speeds is introduced with the goal of modeling the impact of trajectory prediction uncertainty in air traffic management. To validate our approach, a simulation device capable of simulating real air traffic data over the European airspace is used. Main results of this work reveal a significant conflict quantity reduction and demonstrate the robustness of the developed model to the uncertainty in trajectory prediction. Finally, the impact of our model on air traffic flow is measured through several air traffic management indicators and validates the proposed methodology.

Cette thèse s’intéresse au cas d’un port maritime dans lequel des terminaux à conteneurs coopèrent afin de fournir un meilleur service global. Pour coordonner les opérations entre les terminaux, un modèle et plusieurs méthodes de résolution sont proposés. L’objectif est de minimiser les temps de rotation des navires aux longs cours, des navires caboteurs, des barges fluviales et des trains. Une solution au modèle fournit une affectation des véhicules de transport de conteneurs aux terminaux, ce qui inclue les camions, ainsi qu’une allocation de ressources et des intervalles temporels pour leurs prises en charge et pour celles de leurs conteneurs. Pour obtenir des solutions au modèle, une formulation du problème comme un programme linéaire en variables mixtes est proposée, ainsi que plusieurs heuristiques basées sur la programmation mathématique. Une méthode de planification en horizon glissant est introduite pour la gestion dynamique avec prise en compte des incertitudes. Des expériences numériques sont conduites avec des milliers d’instances réalistes variées, dont les résultats indiquent la viabilité de notre approche. Des résultats démontrent qu’autoriser la coopération entre terminaux augmente significativement la performance du système. / This thesis deals with the case of a maritime port in which container terminals are cooperating to provide better global service. In order to coordinate operations between the terminals, a model and several solving methods are proposed. The objective is to minimize turnaround times of mother and feeder vessels, barges and trains. A solution to the model provides an assignment of container-transport vehicles to the terminals, including trucks, as well as an allocation of resources and time intervals to handle them and their containers. To obtain solutions to the model, a mixed-integer programming formulation is provided, as well as several mathematical programming based heuristics. A rolling horizon framework is introduced for dynamic management under uncertainty. Numerical experiments are conducted on thousands of various realistic instances. Results indicate the viability of our approach and demonstrate that allowing cooperation between terminals significantly increases the performance of the system.